Кодирование

 

Пример 16. Закодировать сообщения источника, при­веденные в табл 7, двоичным кодом Хафмана. Оценить эффектив­ность полученного кода.

Решение. В соответствии с алгоритмом построения ко­да Хафмана делаем последовательно следующие шаги:

1) располагаем сообщения источника в порядке убывания ве­роятностей;

2) образуем вспомогательный алфавит, объединяя наиболее маловероятные буквы u ₁ и u ₄ (m ₀=2), тогда вероят­ность новой буквы равна p ₁= р (u ₁)+ р (u ₄)=0, 1+0, 05=0, 15. Оставляем эту букву на месте, так как p ₁= р (u ₆);

3) объединяем первую вспомогательную букву и букву u ₆, тогда вероятность второй вспомогательной буквы равна р ₂= р ₁+ р (u ₆)=0, 15+0, 15=0, 3; перемещаем ее вверх в соответствии с этой вероятностью;

4) объединение продолжаем до тех пор, пока в ансамбле не останется единственное сообщение с вероятностью единица.

Построение кода Хафмана приведено на рис. 4.

Сообщения источника являются теперь концевыми узлами ко­дового дерева. Приписав концевым узлам значения символов 1 и 0, записываем кодовые обозначения, пользуясь следующим пра­вилом: чтобы получить кодовое слово, соответствующее сооб­щению u ₄, проследим переход u ₄ в группировку с наиболь­шей вероятностью, кодовые символы записываем справа на­лево (от младшего разряда к старшему), получим 1100.

Для сообщения u ₁ – 1101 и т.д. (см. рис. 4).

Оценим эффективность полученного кода.

Энтропия источника сообщений:

на одну букву на выходе источника.

Средняя длина кодового слова (формула (4.14) [1])

.

Для оценки эффективности кода используем коэффициент эффективности

Для оптимального двоичного кода и .

Полученный нами код имеет избыточность R =0, 0109, т.е. код близок к оптимальному.

Пример 17. Сообщение источника X составляется из статистически независимых букв, извлекаемых из алфавита А, В, С с вероятностями 0, 7; 0, 2; 0, 1. Произвести двоичное кодирование по методу Шенно­на-Фано отдельных букв и двухбуквенных блоков. Сравнить коды по их эффективности.

Решение. Производим побуквенное кодирование ме­тодом Шеннона-Фано.

1) Располагаем буквы алфавита источника в порядке убыва­ния вероятностей.

2) Делим алфавит источника на две (m =2) примерно рав­новероятные группы. Всем сообщениям верхней группы (буква А) приписываем в качестве первого кодового симво­ла 1, всем сообщениям нижней группы приписываем сим­вол 0.

3) Производим второе разбиение на две группы (буквы В и С) и снова букве в верхней группе (В) приписываем сим­вол 1, а в нижней (С) в качестве второго символа кодового слова приписываем 0. Так как в каждой группе оказалось по одной букве, кодирование заканчиваем. Результат приведен в табл. 8.

Оценим эффективность полученного кода. Энтропия источника

Средняя длина кодового слова

.

Видим, что L > H (X), и коэффициент эффективности

а избыточность R ₁=0, 1102.

Покажем, что кодирование блоками по 2 буквы (k =2) увеличивает эффективность кода. Строим вспомогательный алфавит из N =3² блоков. Вероятности блоков находим по формуле (1.8) [1], считая буквы исходного алфавита независимыми. Располагаем блоки в порядке убывания вероятностей и осуществляем кодирование методом Шеннона-Фано. Все полученные двухбуквенные блоки, вероятности их и соответствующие кодовые обозначения сведены в табл. 9.

При блоковом кодировании средняя длина кодового слова на одну букву

.

При этом коэффициент эффективности

Избыточность при двухбуквенном кодировании R ₂=0, 0045.

Получили γ ₂ > γ ₁, R ₂< < R ₁, что и требовалось показать.

Пример 18. Способ кодирования задан кодовой таблицей

a) составить матрицу расстояний

;

б) найти кодовое расстояние;

в) определить кратности обнаруживаемых и исправляемых ошибок;

г) определить избыточность кода, полагая буквы источника равновероятными.

Решение. а) Матрицу расстояний записываем в виде таблицы (табл. 10).

б) По табл. 10 находим кодовое расстояние

в) Кратность обнаруживаемых ошибок определяется по формуле (3.5) [1], откуда q _о≤ 3.

Кратность исправляемых ошибок находим по формуле (3.6) [1] q _и≤ 1, 5.

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

г) Избыточность кода находим из следующих соображе­ний. Для передачи равновероятных сигналов a₁, а₂, а₃, а₄ достаточно переда­вать кодовые слова 00, 10, 01 и 11 соответственно. Такой код не имеет избыточности, но не позволяет обнаруживать и, тем более, исправлять ошибки. Для обнаружения и исправления ошибок введены пять избыточных символов, т.е. количествен­но избыточность равна .

Пример 19. Линейный блочный (5, 2)-код задан произ­водящей матрицей G в систематической (канонической) форме

Пусть принят вектор b =00110 и известно, что возможны только одиночные ошибки.

Произвести декодирование следующими методами:

а) по минимуму расстояния;

б) вычислением синдрома.

Решение. Если производящая матрица записана в ка­ноническом виде, это значит, что она состоит из двух блоков: диагональной матрицы размера k k, состоящей из единиц, и прямоугольной матрицы размера r k. В этом случае пер­вые k символов в любом кодовом слове являются информаци­онными.

Проверочная матрица Н также может быть записана в каноническом виде и состоит из двух блоков. Первый блок есть прямоугольная матрица размера k r, полученная транс­понированием второго блока матрицы G. В качестве второго блока матрицы Н записывают диагональную матрицу разме­ра r r, состоящую из единиц.

Для заданного кода получаем

.

Убедимся, что полученная таким образом матрица Н удов­летворяет соотношению (3.18) [1]. Действительно,

т.е. все 6 элементов матрицы GH^T равны нулю.

Построим кодовую таблицу, воспользовавшись правилом образования кодовых слов по формуле (3.21) [1]:

a₁ =00000, а₂ =10110, а₃ =01011, а₄ = 11101= a₂ + a₃.

Всего кодовая таблица содержит 2 ^k = 4 вектора.

Из кодовой таблицы определяем величину кодового рас­стояния .

Следовательно, рассматриваемый код обнаруживает одно­кратные и двукратные ошибки и исправляет однократные.

Декодируем принятый вектор b = 00110.

а) Метод декодирования по минимуму расстояния заклю­чается в том, что, вычислив расстояния вектора b относитель­но всех векторов а_i кодовой таблицы, отождествляем приня­тый вектор с тем, расстояние до которого минимально. Расстояния d_ib приведены в табл. 11.

По величине d_{ib min} =1 решаем, что передавался вектор а₂ =10110, следовательно, ошибка в первом символе кодового слова, а информационная последовательность имеет вид х = 10.

б) Метод декодирования с помощью вычисления синдрома включает следующие операции:

1) По формуле (3.17) [1] заранее устанавливаем однознач­ную связь между векторами однократных ошибок е и соот­ветствующими им синдромами. Все возможные векторы приведены в табл. 12.

2) Вычисляем синдром для принятого слова b по формуле (3.16) [1] с = bH^T:

c₁=(00110)(10100)=1, с₂=(00110)(11010)=1,

с₃=(00110)(01001)=0,

т.е. вектор с = 110. Синдром не равен нулю, следовательно, есть ошибка.

Вектору с = 110 в табл. 12 соответствует век­тор ошибки в первом символе е =10000. Декодируем, сум­мируя принятый вектор с вектором ошибки

Итак, получили тот же результат: передавался вектор a₂ =10110, соответствующий информационной последователь­ности х =10.

Пример 20. Для кода, заданного в примере 19, со­ставить схему кодирующего устройства.

Решение. Обозначим буквами а ₁,..., а ₅ символы на выходе кодера, причем а ₁ и а ₂ есть информационные символы, поступающие на его вход, а символы а ₃, а ₄ и а ₅ образуются в кодере.

Из соотношения (3.22) [1] получаем

Один из вариантов схемы кодера, определяемой этими соот­ношениями, показан на рис. 5.

Кодирующее устройство работает следующим образом. В течение первых двух шагов двухразрядный регистр сдвига за­полняется информационными символами а ₁ и а ₂, а в течение следующих трех тактов его состояние сохраняется неизменным. Одновременно с заполнением регистра начинается переклю­чение мультиплексора (переключателя) MUX. Таким образом формируются 5 симво­лов кодового слова, удовлетворяющих требуемым соотноше­ниям.

Пример 21. Построить код Хэмминга, имеющий па­раметры: d_код =3, r =3.

Решение. Построение кода начинаем с проверочной матрицы. В качестве семи столбцов проверочной матрицы Н выбираем всевозможные 3-разрядные двоичные числа, исклю­чая число нуль. Проверочная матрица имеет вид

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

где I – единичная матрица.

Для этого достаточно в матрице Н выбрать столбцы, со­держащие по одной единице, и перенести их в правую часть. Тогда получим

Из формулы (4.3.5) получаем следующие соотношения для символов a ₁,..., а ₇ кодового слова:

Пользуясь этими соотношениями, составляем кодовую таблицу

Пример 22. Для кода Хэмминга, определяемого проверочной матрицей H, построенного в при­мере 21, декодировать принятый вектор 1011001.

Решение. Для принятого вектора b =1011001 по фор­муле (3.16) [1] вычисляем синдром

Синдром с ≠ 0, т.е. имеет место ошибка. В случае одиноч­ной ошибки (и только лишь) вычисленное значение синдрома всегда совпадает с одним из столбцов матрицы Н, причем номер столбца указыва­ет номер искаженного символа. Видим, что ошибка произошла в первом символе и передавался вектор

Пример 23. Производится кодирование линейным блочным кодом (15, 15- r). Найти минимальное количество проверочных символов r, при котором код был бы способен исправлять любые однократные, двукратные и трехкратные ошибки.

Решение. Поскольку в кодовой комбинации n =15 символов, то количество всевозможных однократных ошибок (q =1) равно Количество различных двукратных и трехкратных ошибок равно числу сочетаний и соответственно. Тогда суммарное количество всевозможных ошибок при q ≤ 3 равно

Чтобы любая из этих ошибок могла быть исправлена, нужно, чтобы разным ошибкам соответствовали различные значения синдрома c. Вектор c состоит из r двоичных символов, тогда максимальное количество различных ненулевых комбинаций равно (нулевая комбинация c=0 соответствует отсутствию ошибок). Отсюда получаем (это ограничение называется пределом Хэмминга), то есть

Таким образом, для исправления всех упомянутых ошибок необходимо, чтобы передаваемые комбинации содержали не менее 10 проверочных символов, т.е. k =5.

Пример 24. Для кодирования применяется (15, 5)-код БЧХ с кодовым расстоянием d_код =7, способный исправить все ошибки до трехкратных включительно.

Битовая вероятность ошибки в канале передачи p =10^-4, ошибки независимы. Определить вероятность ошибки при декодировании кодовой комбинации и битовую вероятность ошибки на выходе декодера.

Решение. Вероятность ошибки при декодировании кодовой комбинации определим по формуле (3.59) [1]

Битовую вероятность ошибки на выходе декодера определим по формуле (3.60) [1] то есть, одна ошибка приходится в среднем на бит.