Изучение различных методов кодирования и декодирования информации

2

МИНИСТЕРСТВО ОБРАЗОВАНИЯ

И НАУКИ УКРАИНЫ

СЕВАСТОПОЛЬСКИЙ НАЦИОНАЛЬНЫЙ

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра технической кибернетики

Курсовая работа по дисциплине

“Теория информации и кодирования”.

Выполнил: ст. гр. А_33д Асатов С.Р.

Проверил: Мирянов В.И.

Севастополь 2002

Оглавление

Введение 3

Задание №1 3

Задание №2 4

Задание №3 7

Задание №4 9

Задание №5 10

Задание №6 11

Задание №7 13

Задание №8 15

Задание №9 18

Задание №10 21

Заключение 27

Введение

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

1. Задание №1

1) Определить количество информации в сообщении на русском языке содержащем ФИО, год, месяц, дату рождения.

Асатов Станислав Русланович 1983 11 03

Число букв и пробелов - 30.

Число цифр - 8.

Количество информации будет равно сумме количества информации буквенных и количества информации числовых символов I=I_б+I_ц[бит].

a) Расчёт для равновероятных символов алфавита:

Для равновероятных событий справедлива следующая формула: - формула Хартли, где n - общее количество символов; количество информационных символов.

Тогда количество информации в сообщении будет следующим:

I=I_б+I_ц=30*log30+8*log10=172,6[бит]

b) Для случая с разной вероятностью:

Для этого случая справедлива формула Шеннона: , где Р(а_i) - вероятность встречи каждого символа;

I=I_б+I_ц=-(5*0.062*log0.062+4*0.045*log0.045+2*0.05.*log0.053+2*0.09*log0.09+

+3*0.038*log0.038+2*0.053*log0.053+2*0.062*log0.062+0.035*log0.035+0.04*log0.04+

+0.021*log0.021+0.012*log0.012)+8*log10=30.801[бит]

c) Для случая учёта двухбуквенных сочетаний:

I=n*H[бит], где Н - энтропия. Для русского алфавита, с учётом пробела, для двухбуквенных сочетаний Н=3,52[бит/символ].

I=I_б+I_ц=30*3.52+8*log10=131.2[бит]

d) Для случая трёхбуквенных сочетаний:

Н=3,01[бит/символ]. Тогда

I=I_б+I_ц=30*3,01+8*log10=115,9[бит]

2) Определить энтропию сообщения.

Энтропия рассчитывается по формуле: , тогда

для случая а): ; для случая b): ;

для случая с): ; для случая d): ;

2. Задание №2

a) Построить канальную матрицу, где элементами будут условные вероятности Р(b_j/a_i), используя свою фамилию и имя:

Канальная матрица в общем виде имеет следующую структуру:

В элементы стоящие в главной диагонали будут вычисляться следующим образом:

, тогда

Возьмём 12 символов:

А - 0,062

С - 0,045

А - 0,062

Т - 0,053

О - 0,09

В - 0,038

С - 0,045

Т - 0,053

А - 0,062

Н - 0,053

И - 0,062

С - 0,045

b) Построить матрицу Р(а_i,b_j).

Возьмём следующие значения вероятностей: Р(а_i): P(a₁)=0.1, P)(a₂)=0.2, P(a₃)=0.3, P(a₄)=0.4;

. Тогда матрицу Р(а_i,b_j) мы можем расcчитать в пакете Mathcad следующим образом:

c) Найти Р(b_j).

Вероятности P(b_j) находим по следующей формуле: . Используем пакет Матhсаd:

d) Построить матрицу P(a_i,b_j).

Элементы матрицы P(a_i,b_j) будем находить в пакете Mathcad используя следующую формулу:

.

e) Найти частные условные энтропии H(B/a_i), Р(A,b_j).

Энтропии будем рассчитывать по формулам: ,

. Запрограммируем эти выражения в пакете Mathcad:

f) Определить полные условные энтропии H(A/B), H(B/A).

Полные условные энтропии будем рассчитывать по формулам: , . Запрограммируем эти формулы в пакете Mathcad:

g) Определить взаимную энтропию H(A,B):

Формула для определения взаимной энтропии имеет следующий вид: . Запрограммируем её в пакете Mathcad:

h) Найти количество информации на выходе канала связи I(A,B).

Найти количество информации на выходе канала будет рассчитываться по формулам:

, где H(A) и H(B) энтропия источника и энтропия приёмника соответственно. , . Запрограммируем эти формулы в пакете Mathcad:

i) Найти пропускную способность канала Cn (? любое).

Пропускная способность канала ищется по формуле: . Запрограммируем эту формулу в пакете Mathcad:

3. Задание №3

Построить оптимальный код для передачи букв фамилии:

a) Построить методом Шеннона_Фано, оценить эффективность данного метода кодирования:

А - 0,062

С - 0,045

А - 0,062

Т - 0,053

О - 0,09

В - 0,038

С - 0,045

Т - 0,053

С - 0,045

0,493 - сумма вероятностей.

Рассчитаем энтропию: = -(0,5*log0.5+4*0.09*log0.09+4*0.062*log0.062+

+4*0.062*log0.062+4*0.053*log0.053+4*0.053*log0.053+4*0.045*log0.045+4*0.045*log0.045+

+5*0.045*log0.045+5*0.038*log0.038)=2.4747

Рассчитаем среднее число разрядов на символ:

Построить оптимальный код методом Хаффмана, оценить эффективность данного метода кодирования.

Рассчитаем среднее число разрядов на символ:

b) Сравнить два метода между собой.

Среднее число разрядов на символ n_ср в методе Шеннона_Фано такое же как и вметоде Хаффмана, т.е. метод Хаффмана дал такую же эффективность как и метод Шеннона_Фано.

c) Взять любую последовательность сообщения внести ошибку и посмотреть, что получится.

Ошибка в одном разряде привела к трансформации двух символов в сообщении.

d) Оценить избыточность.

Избыточность будем искать по формуле .

e) Оценить недогруженность.

Найдём абсолютную недогруженность по формуле :

4. Задание №4.

Закодировать в телеграфном коде МТК_2 фамилию и построить график вероятности ошибки, используя Биноминальный закон распределения:

Вероятность искажения любого разряда битовой последовательности в двоичном симметричном канале одинакова.

Р₀ - вероятность искажения одного разряда.

- правило приёмника.

Вероятность ошибки P(t), где t - кратность ошибки, определяется Биноминальным законом распределения: , где n - количество разрядов в сообщении. В каждой кодовой комбинации кода МТК_2 по пять разрядов, в фамилии Асатов шесть символов, следовательно n в данном случае равно 30.

Запрограммируем эту формулу в пакете Mathcad и построим график вероятности ошибки (для

t=1, 2, 3; P₀=10^-2, 10^-3, 10^-4, 10^-5, 10^-6):

Задание №5

Из предыдущего задания воспользуемся кодом и разделим многочлен получившийся из первых четырёх символов на пятый и проверим деление умножением:

АСАТОВ: 10000001011000010101 11100.

Q(x)=?(x)*P(x) +R(x), где Q(x) - делимое, ?(x) - частное, Р(х) - делитель, R(x) - остаток от деления.

10000001011000010101 11100

11100 *

11000 1101101010000001 0000000000000000

11100 1101101010000001

10001 1101101010000001

11100 1101101010000001

11010 100000010110000111

11100 1001

11011 10000001011000010101

11100

11100

11100

00010101

11100

1001

адание №6

Закодировать свои инициалы в телеграфном коде МТК_3 и определить сколько контрольных символов необходимо для:

a) Обнаружения ошибки кратности r=4.

М 1100010 Число информационных символов m=21.

П 1000110

А 0011010

Воспользуемся формулами Хемминга для определения минимального кодового расстояния d_min чтобы вычислить кратность s исправляемой кодом ошибки для r=4:

d_min=r+1=5;

d_min=2s+1 .

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

Возьмём к=5, тогда имеем: общее число символов n=m+k=21+5=26.

следовательно к=5 является недостаточным.

Возьмём к=9: n=21+9=30,

Число контрольных символов требуемых для обнаружения ошибки кратности четыре к=9.

b) Для исправления ошибки кратности s=4:

Аналогично как и в предыдущем пункте воспользуемся формулой нижней границы Хемминга для подбора требуемого числа контрольных символов:

Пусть к=10, тогда имеем: n=21+10=31, следовательно к=10 недостаточно.

Возьмем к=17: n=21+17=38, .

Число контрольных символов требуемых для исправления ошибки кратности четыре к=17.

c) Закодировать свои инициалы в телеграфном коде МТК_2 и проиллюстрировать метод Бодо_Вердана с тремя и пятикратными повторениями:

А 10000 Число информационных символов m=21.

C 00101

Р 00111

При трёхкратном повторении:

Число контрольных разрядов в этом случае к=30, тогда n=m+k=15+30=45. Избыточность будет равняться.

При пятикратном повторении:

Число контрольных разрядов в этом случае к=60, тогда n=m+k=15+60=75. Избыточность будет равняться.

d) Закодировать свой год, месяц и дату рождения двоично_десятичным кодом и составить итеративный код, показать варианты обнаружения и не обнаружения ошибок.

26 11 1983 0000 0011 0001 0001 0001 1001 1000 0011

Всего символов 4*8=32. Добавляем четыре нуля до 36 символов для получения квадратной матрицы:

0010011000001000100011001100000110000

Строим матрицу:

Рассчитаем избыточность:

Рассмотрим варианты с различными ошибками:

Данный код способен исправить нечётную ошибку в строке если нет ошибок в соответствующем столбце. И наоборот. Также код способен обнаружить нечётную ошибку в строке, если ошибки в соответствующих столбцах нечётные. Справедливо аналогичное утверждение и для столбцов.

Задание №7

Записать буквы имени и отчества в телеграфном коде МТК_2, и эту комбинацию закодировать в систематическом коде с d_min=3.

a) Для этого построить образующую матрицу для m=10.

С 00101 Число информационных символов m=10.

Р 00111

0 0 1 0 1 0 0 1 1 1

a₁ a₂ a₃ a₄ a₅ a₆ a₇ a₈ a₉ a₁₀

Для подсчёта количества контрольных символов воспользуемся частным случаем формулы для подсчёта нижней границы Хеменга: .

Общее число символов n=m+k=10+4=14.

Построим образующую матрицу:

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

0 0 1 0 1 0 0 1 1 1 0 0 0 0

a₁ a₂ a₃ a₄ a₅ a₆ a₇ a₈ a₉ a₁₀ b₁ b₂ b₃ b₄

b) Построить проверочную матрицу:

Вычёркиваем все строки вес которых W<2 (W<(d_min-1), d_min=2s+1=3). Эти строки

будут контрольными символами, остальные - информационными.

c) Записать уравнения кодирования и декодирования:

Запишем уравнения кодирования:

Запишем уравнения декодирования:

Нулевой синдром s=0 - признак отсутствия ошибки.

Каждому вектору ошибки соответствует определённый синдром.

d) Произвести декодирование при однократной и двукратной ошибках:

При одиночной ошибке:

такой ошибке будет соответствовать синдром

Он соответствует ошибке в шестом разряде. Эту одиночную ошибку код исправит верно.

При двойной ошибке:

такой ошибке будет соответствовать синдром

Код неправильно определит местоположение ошибки и возникнет трансформация (код исправит верный девятый разряд).

Синдром двойной ошибки получается при сложении по модулю два синдромов ошибок составляющих эту двойную.

Задание №8

a) Закодировать начальные буквы фамилии и имени в МТК_2 без учёта кода регистра и пробела.

А 10000 1000000101 - кодовая комбинация информационных символов; m=10.

С 00101

b) Пояснить принцип выбора контрольных и информационных разрядов в коде Хеменга.

Записываем n сочетаний к - разрядных комбинаций. Контрольным символам в последовательном порядке присваиваем те из них, вес которых равен единице. Остальные комбинации (также в последовательном порядке) присваиваем информационным символам.

c) Записать уравнения кодирования и декодирования.

Для подсчёта количества контрольных символов воспользуемся частным случаем формулы для подсчёта нижней границы Хеменга:

Запишем уравнения кодирования для d_min=3:

Уравнения кодирования примут следующий вид:

Запишем уравнения декодирования для d_min=3:

Проверочная матрица будет иметь следующий вид:

000000101 0101

Уравнения кодирования для d_min=4:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

b₁ b₂ a₁ b₃ a₂ a₃ a₄ b₄ a₅ a₆ a₇ a₈ a₉ a₁₀ b₅

0 1 1 0 0 0 0 1 0 0 0 1 0 1 0

Разряд b₅ будет выполнять контроль паритета, т.е. дополнять число единиц в кодовой комбинации до чётного.

Уравнения кодирования примут следующий вид:

Уравнения декодирования для d_min=4:

Проверочная матрица будет иметь следующий вид:

d) Произвести декодирование при однократной и двукратной ошибке:

Однократная ошибка при d_min=3:

- искажена третья позиция.

Двукратная ошибка при d_min=3:

- искажена шестая позиция. Код неправильно определит местоположение ошибки и возникнет трансформация, т.е. код исправит верный разряд.

Однократная ошибка при d_min=4:

- искажена третья позиция. Синдром ненулевой и чётность не сохранена, следовательно декодер верно исправит ошибку.

Двукратная ошибка при d_min=4:

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

Код Хеменга с d_min=3 способен обнаруживать ошибку с r=2 или исправлять ошибку с s=1. При d_min=4 код может обнаружить ошибку с r=3 или обнаружить с r=2 и исправить с s=1.

5. Задание №9

a) Для m=10 и d_min=3 построить образующую матрицу циклического кода исправляющего одиночную ошибку:

Для подсчёта количества контрольных символов воспользуемся частным случаем формулы для подсчёта нижней границы Хеменга:

n=m+k=10+4=14

Для построения образующий матрицы разделим кодовую комбинацию10000000000000 на образующий полином . Полином всегда выбирается таким образом чтобы он имел наименьшее число слагаемых.

Построим образующую матрицу:

b) Закодировать буквы имени и отчества в МТК_2:

С 00101

Р 00111 0010100111

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

10101001110010

m k

Второй способ: дополняем кодовую комбинацию информационных символов к - числом нулей, т.е. получаем разрешенную комбинацию и делим на образующий полином. Получившийся остаток будет комбинацией контрольных символов.

c) Произвести декодирование при однократной и двукратной ошибках:

Разрешённая кодовая комбинация делится без остатка на образующий полином. Если есть ошибка, то при делении получается остаток.

Дополняем нашу кодовую комбинацию нулём до оптимальной (n=15):

Разделим искаженную кодовую комбинацию на образующий полином.

Как видно остаток ненулевой. Его вес W=2. Далее будем продолжать деление дополняя кодовую комбинацию нулями. Деление будем продолжать до тех пор пока вес остатка не станет равен единице.

Вес остатка W=1. Далее осуществляем сдвиг влево искаженной кодовой комбинации на число разрядов равное количеству добавленных нулей (в нашем случае четыре), затем сложение по модулю два искаженной кодовой комбинации с остатком и выполняем обратный сдвиг:

Код успешно исправил одиночную ошибку.

Двукратная ошибка:

Выполняем те же операции что и при декодировании однократной ошибки.

10011

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

Задание №10

В двоично_десятичном коде закодировать свою дату рождения для свёрточного кода с относительной скоростью R=0.5, закодировать данную восьмиразрядную комбинацию тремя способами.

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

По решётчатой диаграмме:

Двигаясь по решётчатой диаграмме в соответствии с заданной кодовой комбинацией получим следующую закодированную комбинацию: 1110110011101100. Путь кодирования (трасса) изображена на диаграмме пунктирной линией. Точки называются состояниями решётки, а линии - её ветвями.

a) Декодировать с однократной и двукратной ошибками полученную кодовую комбинацию в соответствии с алгоритмом Витерби:

Задача алгоритма Витерби заключаются в восстановлении пути, который был был на решётке при кодировании, причём он восстанавливается с некоторой вероятностью. Поэтому этот алгоритм называется вероятностным.

При m=8 путей будет 2⁸=256. Для нахождения пути надо просчитать сумму метрик состояний. Сумма должна быть минимальна.

Процесс декодирования состоит из двух этапов:

1) Этап развития;

2) Этап построения;

Декодирование без ошибки:

Определяем метрики ветвей и метрики состояний:

МС₁(00)=0; МС₂(10)=0; МС₃(01)=0; МС₄(11)=2; МВ₁(00)=2; МВ₁(10)=0;

МС₂(00)=МС₁(00)+МВ₁(00)=0+2=2.

Аналогичным образом просчитываем остальные метрики состояний и ветвей.

После просчёта производим декодирование по пути с наименьшей суммой метрик состояний.

Как видно декодирование без ошибки прошло успешно.

Декодирование с одиночной ошибкой:

Код успешно исправляет одиночную ошибку, декодируя по пути на котором сумма метрик состояний наименьшая.

Декодирование с двойной ошибкой:

На восьмом шаге декодирования возникает ситуация когда на различных путях одинаковая сумма метрик состояний. В этом случае декодер только обнаруживает ошибку, но не исправляет её.

Данную двойную ошибку код успешно исправляет.

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

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

Заключение

В ходе написания курсовой работы были изучены различные методы кодирования и декодирования информации, а так же приобретены навыки кодирования и декодирования информации. Были проведены исследования и сделаны выводы о возможностях обнаружения и исправления ошибок для различных кодов.