Расчет и оптимизация характеристик дискретного канала

Министерство  образования и науки Украины

Одесский Национальный Морской Университет

Кафедра «Информационные  технологии»

Курсовая работа

Расчет  и оптимизация характеристик  дискретного канала

Выполнила:

студентка КСФ II к. 4 гр.

Топалова Александра

Александровна

Поверили:

Ширшков А.К.

Сафонова Н.В.

Одесса 2012 

Содержание

1. Система  передачи дискретных сообщений 3

1.1 Блок-схема  передачи СПДС. 3

1.2 Функции  блоков источника сообщений: 4

1.3 Виды информации: 4

1.4 Виды и  функции линий связи 4

1.5 Функции  блока приемника сообщений: 5

2. Информационные  характеристики дискретного канала 5

2.1 Информационные  характеристики источника сообщений. 5

2.2 Информационные  характеристики приемника сообщений. 6

2.3 Расчет  канальных матриц 6

2.4 Характеристики  источника сообщений 8

2.5 Характеристики  приемника сообщения 9

2.6 Скоростные  характеристики 10

2.7 Рекомендации  и вывод по надежности и  эффективности канала 10

3. Оптимальное  кодирование 11

3.1 Назначение  ОНК 11

3.2 Равномерный  двоичный код 11

3.2.1 Корневое  бинарное дерево РДК 12

3.3 Метод Шеннона–Фано 13

3.3.1 Алгоритм  метода бисекции вычисления ОНК: 13

3.3.2 КБР ОНК  Шеннона–Фано 14

3.3.3 Информационные  характеристики ОНК Шеннона–Фано 14

3.4 Метод Хаффмена 15

3.4.1 Алгоритм  Хафффмена: 15

3.4.2 КБД ОНК  Хаффмена 16

3.4.3 Информационные  характеристики ОНК Шеннона–Фано 17

4. Помехоустойчивое кодирование 18

4.1 Обнаруживающие  коды 18

4.1.1 Обнаруживающий  код чётности (ОКЧ) 18

4.1.2 Обнаруживающий код удвоения (ОКУ) 19

4.1.3 Обнаруживающий код инверсией (ОКИ) 20

4.1.4 Обнаруживающий  код стандартный телеграфный  код №3 (ОК СТК №3) 21

4.2 Корректирующие  коды 21

4.2.1 Корректирующий  систематический код Хэмминга (КСК  Хэмминга) 21

4.3 Корректирующий  циклический код (КЦК) 23

4.4 Коды, корректирующие  кратную ошибку 26

4.4.1 Корректирующий мажоритарный код (КМК)(код по голосованию)  (К – удвоения) 26

Литература 27

Информация – с лат. языка «разъяснение, просвещение»:

1. осведомление, сообщение, сведение о чем-либо;
2. обмен сведениями между людьми, между человеком и автоматом (ЭВМ), между автоматами, обмен между животными и растительным миром, передача признаков от клетки к клеткам (наследственность, коды ДНК).

В кибернетике и математике, информация – это количественная мера устранения неопределенности (энтропия).

Теория информации (теория сообщений) – область кибернетики, в которой математическими методами исследуется:

1. способы измерения количества информации;
2. сбора информации;
3. кодирование;
4. преобразование;
5. передача.

Теория информации: определение количества информации, потери информации на канале связи под воздействием помех, пропускная способность канала связи, скорость модуляции и скорость передачи данных, надежная и эффективная эксплуатация телекоммуникационных каналов.

Теория информации изучает  математические методы, с помощью  которых оценивается количество информации, действие помех на каналах связи, определяет эффективность скорости модуляции передачи данных.

В Шеноновской теории количество информации определяется только по ее вероятностным свойствам.

Теория кодирования: включает в себя три направления:

1. оптимальное кодирование: сжатие данных без потерь содержания информации;
2. помехоустойчивое кодирование: защита данных от действия помех;
3. криптографическое кодирование: защита данных от несанкционированного доступа (ПСД).

1. Система передачи дискретных сообщений

1.1 Блок-схема передачи  СПДС.

Система передачи дискретных сообщений (СПДС). Непрерывная информация, которая много раз меняет свою форму, по мере того как проходит по схеме. Но при этом первоначальное содержание не изменяется. СПДС включает в себя следующие информационные блоки.

источник сообщений

приемник сообщений

1.2 Функции блоков источника сообщений:

1. Аналогово-цифровой преобразователь – преобразует непрерывное сообщение в дискретное.
2. Шифратор – защита от не санкционированного доступа (НСД).
3. Кодер ОНК (оптимальное неравномерное кодирование) – сжимает данные (конверсия).
4. Кодер ПЗК (помехо-защищенного кода) – защита данных от помех.
5. Модулятор – преобразует цифровые данные в электрический сигнал.

1.3 Виды информации:

В процессе обработки и  прохождения по блокам источника  и приёмника, информация многократно  меняет свою форму, сохраняя при этом содержание:

1. непрерывная, аналоговая информация;
2. цифровая, дискретная информация;
3. криптографические коды;
4. оптимальный, неравномерный код, сжатые данные;
5. помехоустойчивый код;
6. электрические сигналы.

Обозначения:

1. Алфавит сообщения – кортеж уникальных символов  А={a₁, a₂, …, a_n};
2. Сообщение – кортеж символов S={s₁, s₂, …, s_n};
3. Вероятность появления символа P(a_i) – для алфавита

                                                         P(x_i) – для символов

Единицы измерения количества информации определяется видом log.

Log – Бит

Ln – Нат

Lg – Дит

1.4 Виды и функции  линий связи

Линии связи – физическая середа, в которой распространяются сигналы: проводниковые, кабельные, радио и спутниковые линии.

Виды линий связи:

1. проводная;
2. кабельная;
3. спутниковая;
4. радио.

Функции: линии связи предназначены для передачи данных на различные расстояния. Информация может менять свою форму при передаче, но содержание при этом сохраняется.

1.5 Функции блока приемника сообщений:

1. Демодулятор – преобразует электрические сигналы в двоичный код.
2. Декодер ПЗК – обнаруживает ошибку, вычисляет ее адрес, корректирует ошибку, снимает контрольные биты.
3. ЦАП (цифрово–аналоговый преобразователь) – преобразует дискретную информацию в аналоговую (непрерывную) – звук, видео и т.д.
4. Дешифратор – снятие защиты от НСД.
5. Декодер ОНК – переход к равномерному двоичному коду.

2. Информационные  характеристики дискретного канала

2.1 Информационные  характеристики источника сообщений.

Количество информации символа  сообщения определяется вероятностью появления этого символа в данном сообщении.

I(a_i) =–log₂ p(a_i)

Свойства  количества информации:

1. Количества информации – величина не отрицательная I(a_i) ≥ 0.
2. Чем выше вероятность, тем меньше количества информации. Чем выше вероятность – тем больше информации.

P(a₁) < P(a₂) → I(a₁) > I(a₂)

3. I(a_i) = 0 ↔ P(a_i) = 1(достоверное сообщение).
4. Свойство аддитивности I(a₁) + I(a₂) = I(a₁, a₂).

Каждый символ сообщения  имеет свое количество информации. Энтропия – это среднее количество информации на символ данного сообщения, то есть математическое ожидание количества информации.

Н (а) = –Σ Р(а_i) log Р(а_i) (бит/символ)

Свойства энтропии:

1. H (a) ≥ 0
2. H (а) = 0 ≡ а_i Î Х   P (а_i) = 1. Тогда и только тогда в ДАС есть достоверный символ.
3. Энтропия всегда конечна для любого ДАС. H (а) ≤ log n, где n –количество символов сообщения.
4. Для бинарного ДАС, энтропия обладает свойством симметрии.
5. Для сложного ДАС энтропия будет выглядеть так:

H(X, Y) = H(X) + H(Y).

Частотно  условная энтропия источника:

ЧУЭП – определяет информационные потери приемника сообщений B={b₁, b₂,…,b_n} относительно переданного сигнала a_i.

H (B/a_i) = – Σ P(b_j/a_i) log P(b_j/a_i), i=1, 2,…, n

Общая условная энтропия источника:

ОУЭИ – определяет потери информации при приеме ансамбля

B={b₁, b₂,…,b_n} относительно переданного ансамбля А={а₁, а₂...a_n}

H (B/A) = – Σ Σ P(a_i) P(b_j/a_i) log P(b_j/a_i)

Для равно вероятностного а_i Р(а_i) = 1/n (i = 1,2,3...n).

Суммарные потери информации определяет общие условия энтропии источника и имеет вид:

H (B/A) = – 1/n Σ Σ P(b_j/a_i) log P(b_j/a_i)

2.2 Информационные  характеристики приемника сообщений.

Частотно  условная энтропия приемника:

ЧУЭП – определяет информационные потери источника сообщений А={а₁, а₂...a_n} относительно принятого сигнала b_j.

H (A/b_j) = – Σ P(a_i/b_j) log P(a_i/b_j), j=1, 2,…, n

Общая условная энтропия приемника:

ОУЭП – определяет потери информации при передаче ансамбля А={а₁, а₂...a_n} относительно принятого ансамбля B={b₁, b₂,…,b_n}.

H (A/B) = – Σ Σ P(b_j) P(a_i/b_j) log P(a_i/b_j)

Для равно вероятностного b_j Р(b_j) = 1/n (i = 1,2,3...n)

Суммарные потери информации определяет общие условия энтропии приемника и имеет вид:

H (A/B) = – 1/n Σ Σ P(a_i/b_j) log P(a_i/b_j)

2.3 Расчет канальных  матриц

Теорема 1. «О скорости передачи» Определяет критическую скорость передачи данных R_кр, зависимую только от распределения вероятностей, при которой существует средство передачи со скоростью R близкой к критической (R < R_кр), при которой возможно восстановление начального сообщения (если скорость R < R_кр, восстановление сообщения невозможно). Критическая скорость равняется:

где H(A) – энтропия источника, С – пропускная способность канала.

Теорема 2. «О кодировании» Если производительность источника H’(А) меньше пропускной способности канала:

H’(А) < С,

то существует средство кодирования  и декодирования информации при которой вероятность ошибки может быть сколько угодно мала и наоборот.

Дано: канальная матрица условных вероятностей, которые отображают действие помех дискретного канала связи.

Безусловные вероятности  появления символов на выходе источника  сообщений равны: p(a₁) = 0,4; p(a₂) = 0,2; p(a₃) = 0,1; p(a₄) = 0,3. Длительность передачи одного символа τ = 0,0002, передано сообщение из 400 символов.

Вычислить информационные характеристики дискретного канала связи, включая I(a_i), H(A), H(B/a_i), H(B/A), p(b_j), H(B), I(A,B), n, H’(A), R, C, K_э, R_кр.

Проверить выполнение теорем Шеннона про скорость передачи и  про кодирование. Сделать вывод  про надежность и эффективность  канала связи.

А. Вычислим канальную матрицу объединения:

Зная КМИ можно вычислить КМО по формуле:

p(a_i;b_j) = p(a_i) * p(b_j/a_i)

Канальная матрица объединения

Проверка:

ΣΣ p(a_i;b_j) = 0,39 + 0 + 0 + 0 + 0,03 + 0,15 + 0,02 + 0 + 0,03 + 0,02 + 0,05 +

+ 0,01 + 0 + 0,01 + 0,01 + 0,29 = 1

Вывод: КМО составлена правильно.

Б. Зная КМО, найдем КМП:

p(a_i/b_j) = p(a_i;b_j) / p(b_j)

p(b₁) = 0,39 + 0,03 + 0,03 + 0 = 0,45

p(b₂) = 0 + 0,15 + 0,02 + 0,01 = 0,18

p(b₃) = 0 +0,02 +0,05 +0,01= 0,08

p(b₄) = 0 + 0 + 0,01 + 0,29 = 0,29

Канальная матрица приемника

Проверка:

Σ p(a₁/b_j) = 0,88 + 0,07 + 0,05 +0 =1

Σ p(a₂/b_j) = 0,02 + 0,84 + 0,11 +0,03 = 1

Σ p(a₃/b_j) = 0,05 + 0,24 + 0,60 +0,11 = 1

Σ p(a₄/b_j) = 0 + 0 + 0,02 + 0,98 = 1

Вывод: КМИ составлена правильно.

2.4 Характеристики  источника сообщений

1. Количество  информации I(a_i) каждого символа b₁, b₂, b₃, b₄ дискретного сообщения В:

I(a_i) = – log p(a_i)

I(a₁) = – log p(a₁) = –log 0,4 = 1,321928

I(a₂) = – log p(a₂) = – log 0,2 = 2,321928

I(a₃) = – log p(a₃) = – log 0,1 = 3,321928

I(a₄) = – log p(a₄) = – log 0,3 = 1,736966

2. Среднее  количество информации на символ  сообщения определяет энтропию  источника сообщений H(A):

H(A) = 1,8464 бит/символ

Максимальная  энтропия источника сообщений H_max(A):

H_max(A) = log 4 = 2 [бит/символ]

3. Информационные  потери при передаче каждого  символа определяют частную условную  энтропию источника H(B/a_i)

, (i=1,2,3,4), [бит/символ]

H(B/a₁) = – (0,98 log 0,98 + 0,01 log 0,01 + 0,01 log 0,01 + 0) = 0,1614бит/симв

H(B/a₂) = – (0,15 log 0,15 + 0,75 log 0,75 + 0,10 log 0,10 + 0) = 1,054бит/симв

H(B/a₃) = – (0,25 log 0,25 + 0,20 log 0,20 + 0,50 log 0,50 + 0,05 log 0,05 ) =

=1,6805бит/симв

H(B/a₄) = – (0 + 0,02 log 0,02 + 0,03 log 0,03 + 0,95 log 0,95 ) = 0,3349бит/симв

4. Средние  потери информации при передаче  одного символа определяет общую  условную энтропию источника  H(B/A):

= 0,4 * 0,1614+ 0,2 * 1,054 + 0,1 * 1,6805 + 0,3 * 0,3349 =

= 0,5439 бит/символ

5. Общие  потери информации в канале  связи при передачи сообщения  из 400 символов ΔI:

ΔI = k H(B/A) = 400 * 0,5439 = 217,5644 бит,

где k – количество символов в переданном сообщении.

2.5 Характеристики приемника сообщения

1. Безусловные вероятности появления сигналов на входе приемника p(b_j) определяются по форме:

, (j = 1,2,3,4)

p(b₁) = 0,4 * 0,98 + 0,2 * 0,15 + 0,1 * 0,25 + 0 = 0,447

p(b₂) = 0,4 * 0,01 + 0,2 * 0,75 + 0,1 * 0,20 + 0,3 * 0,02 = 0,18

p(b₃) = 0,4 * 0,01 + 0,2 * 0,10 + 0,1 * 0,50 + 0,3 * 0,03 = 0,083

p(b₄) = 0 + 0 + 0,1 * 0,05 + 0,3 * 0,95 = 0,29

Проверка:

2. Среднее количество информации, принятое приемником на один символ, определяется энтропией приемника H(B):

= – ( 0,447 log 0,447 + 0,18 log 0,18 + 0,083 log 0,083 + 0,29 log 0,29) =

= 1,7805 бит/символ

Максимальная  энтропия источника сообщений H_max(B):

H_max(B) = log 4 = 2 [бит/символ]

3. Среднее количество полученной приемником информации, полученная приемником на один символ с учетом потерь информации, пораженной помехами, I(A,B):

I(A,B) = H(B) – H(B/A) = 1,7805 – 0,5439 = 1,2366 бит/символ

2.6 Скоростные характеристики

1. Скорость модуляции дискретного источника сообщений, n:

2. Продуктивность дискретного источника сообщений, H’(A):

3. Скорость передачи информации, R:

в данном случае скорость равна

4. Пропускная способность (емкость) С дискретного канала связи определяется максимальной скоростью передачи С = max R:

в данном случае

5. Коэффициент эффективности дискретного канала связи К_э

6. Критическая скорость передачи R_кр:

2.7 Рекомендации и вывод по надежности и эффективности канала

1. Теорема  Шеннона о скорости передачи

R < R_кр

6182,9567 < 3942,99   не выполняется

2. Теорема  Шеннона о кодировании

H’(A) < C

9232 < 7280,5   не выполняется

3. Рекомендации  по повышению надёжности и  эффективности

Так как теоремы о скорости передачи не выполняется, восстановление исходного сообщения становится невозможным.

Существует способ кодирования  и декодирования информации, при  котором вероятность ошибки может  быть очень большой. Для увеличения значения С, требуется увеличить  количество символов сообщения.

В данной работе теоремы  Шеннона не выполняются, следовательно, канал связи не является надежным и эффективным.

3. Оптимальное кодирование

3.1 Назначение ОНК

Оптимальный неравномерный код (ОНК) – это такой код, для которого средняя длина кода является минимальной.

Основная характеристика дискретного канала связи – скорость передачи данных. При избыточности переданного сообщения уменьшается  скорость передачи. Математические и  программные средства компрессии данных (без потерь содержания информации), в том числе оптимальное кодирование, используют для исключения избыточности сообщения.

Для сжатия (компрессии данных) применяется оптимальное кодирование, что позволяет эффективно использовать память ЭВМ, уменьшить длительность и увеличить скорость передачи сообщений, выполнять архивацию данных, уменьшить  действие помех на информацию.

Основная идея оптимального кодирования: символам сообщения, которые  имеют большую вероятность, присваиваются  короткие бинарные коды, то есть образуются бинарные кодовые слова разной длины  – неравномерные коды.

Оптимальное кодирование  позволяет:

• сжимать время передачи данных при той же скорости;
• уменьшать возможные потери и искажения информации;
• сжимать данные (компрессия);
• архивировать данные;
• эффективно использовать память.

3.2 Равномерный двоичный код

Сообщение:

Х={ТОПАЛОВА АЛЕКСАНДРА АЛЕКСАНДРОВНА}.

Длина сообщения:

L_x= 32 [символ].

Алфавит сообщения:

А={А, В, Д, Е, К, Л, Н, О, П, Р, С, Т, пробел}.

Длина алфавита:

L_А= 13 [символ].

Вероятности символов алфавита и равномерный двоичный код РДК

L_РДК = 4 [бит].

L_Sрдк = L_х * 4 = 33 * 4 =132 [бит].

Проверка:

Σ p(a_i) = 0,2424 + 0,0606*7 + 0,0909*3 + 0,0303*2=1;

Σ V_i =33 [символ];

все правильно.

S_РДК = 110100101100000100110010010100011011000100110111100010100001010001101

  001000110110001001101111000101000010100011010010010010101000001

3.2.1 Корневое бинарное дерево РДК

(4–ого порядка)

3.3 Метод Шеннона–Фано

3.3.1 Алгоритм метода бисекции вычисления ОНК:

• предварительный шаг: вероятности ранжируются по убыванию или возрастанию;
• шаг 1: все вероятности делятся на две равновероятные группы; символам верхней строки секции назначается 0, нижним – 1 (или наоборот); т.о. вычислен первый бит ОНК;
• шаг 2: каждую группу делим на две равновероятные подгруппы; верхним – 0, нижним –1 (или наоборот). Вычислен второй бит и т. д.

Деление заканчивается, когда  в подгруппе остается 1 символ.

Для однозначности кодирования  и декодирования оптимальных  неравномерных кодов необходимо, чтобы они были префиксными, т.е. для них должен выполняться критерий Фано: ни одно кодовое слово ОНК  не является началом другого кодового слова ОНК.