Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Кодирование




 

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

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

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

2) образуем вспомогательный алфавит, объединяя наиболее маловероятные буквы u1 и u4 (m0=2), тогда вероят­ность новой буквы равна p1=р(u1)+р(u4)=0,1+0,05=0,15. Оставляем эту букву на месте, так как p1=р(u6);

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

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

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

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

Для сообщения u1 – 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), и коэффициент эффективности

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

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

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

.

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

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

Получили γ2 > γ1, R2 <<R1, что и требовалось показать.

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

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

;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

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

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

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

a1=00000, а2=10110, а3=01011, а4=11101=a2+a3.

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

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

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

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

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

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

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

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

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

c1=(00110)(10100)=1, с2=(00110)(11010)=1,

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

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

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

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

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

Решение. Обозначим буквами а1,...,а5 символы на выходе кодера, причем а1 и а2 есть информационные символы, поступающие на его вход, а символы а3, а4 и а5 образуются в кодере.

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

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

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

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

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

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

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

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

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

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

Пример 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] то есть, одна ошибка приходится в среднем на бит.







Дата добавления: 2014-11-10; просмотров: 5607. Нарушение авторских прав


Рекомендуемые страницы:


Studopedia.info - Студопедия - 2014-2019 год . (0.009 сек.) русская версия | украинская версия