Телевизор 

Контрольная работа теория информации. Неравномерное кодирование. Средняя длина кодирования

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

Показателем экономичности или эффективности неравномерного кода является не длина отдельных кодовых слов, а "средняя" их длина, определяемая равенством:

где - кодовое слово, которым закодировано сообщение, а- его длина,- вероятность сообщения,- общее число сообщений источника. Для краткости записи формул далее могут использоваться обозначенияи. Заметим, что обозначение средней длины кодирования черезподчеркивает тот факт, что эта величина зависит как отисточника сообщений , так и от способа кодирования.

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

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

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

В этой таблице, в отличие от предыдущей, наиболее частые сообщения икодируются одним двоичным знаком. Для последнего варианта кодирования имеем

в то время как для равномерного кода средняя длина (она совпадает с общей длиной кодовых слов). Из рассмотренного примера видно, что кодирование сообщений словами различной длины может дать суще-ственное (почти в два раза) увеличение экономичности кодирования.

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

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

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

Решение данной проблемы заключается в том, чтобы иметь возможность в любом кодовом тексте выделять отдельные кодовые слова без использования специальных разделительных знаков. Иначе говоря, необходимо, чтобы код удовлетворял следующему требованию: всякая последовательность кодовых знаков может быть единственным образом разбита на кодовые слова. Коды, для которых последнее требование выполнено, называются однозначно декодируемыми (иногда их называют кодами без запятой).

Рассмотрим код (схему алфавитного кодирования) , заданный кодовой таблицей

и различные слова, составленные из элементарных кодов.

Определение . Код называется однозначно декодируемым, если

то есть любое слово, составленное из элементарных кодов, единственным образом разлагается на элементарные коды.

Если таблица кодов содержит одинаковые кодовые слова, то есть если

то код заведомо не является однозначно декодируемым (схема не является разделимой). Такие коды далее не рассматриваются.

Сообщения алфавита источника выписывают в порядке убывания вероятностей их появления. Далее разделяют их на две части так, чтобы суммарные вероятности сообщений в каждой из этих частей были по возможности почти одинаковыми. Сообщениям первой части приписывается в качестве первого символа 0, а сообщениям второй части – 1 (можно и наоборот). Затем каждая из этих частей (если она содержит более одного сообщения) делится на две по возможности равновероятные части и в качестве второго символа для первой из них берется 0 , а для второй – 1. Этот процесс повторяется, пока в каждой из полученных частей не останется по одному сообщению. Для примера, приведенного в табл. 1 на первом этапе разделения первой части окажется одно сообщение а 1 с вероятностью P (а 1)=0,4, во второй части - остальные сообщения с суммарной вероятностью P Σ (а 2 -а 6)=0.6. Припишем сообщению а 1 символ 0, а остальным сообщениям в качестве первого символа – 1.

Таблица 1. Произвольное кодирование сообщений

На втором этапе разделим сообщения (а 2 ,а 3 ,а 4 ,а 5 ,а 6) на две равновероятные части, включив в первую часть сообщения а 2, а во вторую часть – сообщения (а 3 ,а 4 ,а 5 ,а 6). Припишем сообщению а 2 в качестве второго символа 0, а остальным сообщениям – 1 и т.д. В результате приходим к коду К 2, приведенному в табл. 2.

Таблица 2. Кодирование сообщений кодом Шеннона-Фано

Код по своему построению удовлетворяет свойству префикса. Поэтому вышеприведенная после последовательность двоичных символов “L ” декодируется однозначно: (а 1 ,а 1 ,а 4 ,а 1 ,а 1 ,а 1 ,а 6 ,а 1). Среднее число символов на одно сообщение с учетом их вероятностей =0,4*1+0,3*2+0,3*4=2,2 , т.е. незначительно превышает энтропию источника сообщений.

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

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

(2)

Ограничения на длины кодовых слов префиксного кода задаются неравенством Крафта и теоремой кодирования для источника.

Теорема 1. (Неравенство Крафта). Если целые числа (
) удовлетворяют неравенству

(3)

то существует код, обладающий свойством префикса с алфавитом объемом Д, длины кодовых слов в котором равны этим числам. Обратно, длины кодовых слов любого кода, облагающего свойством префикса, удовлетворяет неравенству (3). Теорема не утверждает, что любой код с длинами кодовых слов, удовлетворяющими (3), является префиксным. Так, например, множество двоичных кодовых слов (0; 00; 11) удовлетворяет (3), но не обладает свойством префикса. Теорема утверждает, что существует некоторый префиксный код с такими длинами, например код (0; 10; 11) . Не любой однозначно декодирующий код обладает свойством префикса, например, код К3 табл. 3. В нем каждое кодовое слово является префиксом каждого более длинного кодового слова. Вместе с тем однозначность декодирования является тривиальной, так как символ 0 всегда определяет начало нового кодового слова. Коды, обладающие свойством префикса, отличаются, однако, от других однозначно декодируемых кодов тем, что конец кодового слова всегда может быть опознан, так что декодирование может быть выполнено без задержки наблюдаёмой последовательности кодовых слов (код. К4 табл.3). По этой причине префиксные коды иногда называют мгновенными кодами.

Таблица 3. Однозначно декодируемые коды

Так как длины кодовых слов любого однозначно декодируемого кода удовлетворяют (3) и можно построить префиксный код для любого множества длин, удовлетворяющих (3), то любой однозначно декодируемый код можно заменить на префиксный код без изменения длин кодовых слов. Таким образом, нижеследующая теорема 2 для кодирования источника относительно средней длины кодового слова предложена как к однозначно декодируемым кодам, так и к подклассу префиксных кодов.

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

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


## ## ## ## ## ## ## ## ## ##
## ## ## ## ## ## ##
####### ## ## ## ## ######## ########
## ## ## ######### ## ## ## ##
## ## ## ## ## ## ## ## ##
####### ##### ## ####### #######

Введите число, изображенное выше:

Подобные документы

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

    курсовая работа , добавлен 17.04.2009

    Описание и особенности некоторых алгоритмов архивации. Построение кода Хаффмана. Динамический алгоритм построения кода Хаффмана. Обратное восстановление текста. Способы двухступенчатого кодирования информации. Практическая реализация алгоритма LZ77.

    курсовая работа , добавлен 24.12.2012

    Оценка вычислительной сложности программы. Реализация алгоритма кодирования информации Хаффмана. Кодировка теста двоичным кодом и в дереве Хаффмана. Бинарный код символов. Символ и частота его появления в тексте. Вычисление трудоемкости алгоритма.

    контрольная работа , добавлен 16.12.2012

    Определение среднего количества информации. Зависимость между символами матрицы условных вероятностей. Кодирование методом Шеннона–Фано. Пропускная способность канала связи. Эффективность кодирования сообщений методом Д. Хаффмана, характеристика кода.

    контрольная работа , добавлен 04.05.2015

    Определение понятий кода, кодирования и декодирования, виды, правила и задачи кодирования. Применение теорем Шеннона в теории связи. Классификация, параметры и построение помехоустойчивых кодов. Методы передачи кодов. Пример построения кода Шеннона.

    курсовая работа , добавлен 25.02.2009

    Анализ эффективности способов кодирования. Средний размер одного разряда и средняя длина кодового слова. Кодирование по методу Хаффмена. Кодирование информации по методу Шенона-Фано. Построение кодового дерево для различных методов кодирования.

    контрольная работа , добавлен 15.10.2013

    Кодирование и декодирование, преобразование дискретного сообщения в дискретный сигнал. Построение математической модели корректирующего кода. Образующая матрица информационного кода. Модульная структура программы. Спецификация на программные модули.

    курсовая работа , добавлен 28.11.2014


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Полученный нами код имеет избыточность 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 1 =0,1102.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

г) Избыточность кода находим из следующих соображе­ний. Для передачи равновероятных сигналов a 1 , а 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) . Действительно,

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

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

a 1 =00000, а 2 =10110, а 3 =01011, а 4 = 11101=a 2 +a 3 .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рассмотрим ансамбль из сообщений им с соответствующими вероятностями Каждое сообщение должно быть представлено посредством кодового слова, состоящего из последовательных символов, принадлежащих заданному алфавиту. Обозначим через число различных символов в алфавите, через число символов в кодовом слове, соответствующем сообщению Среднее число символов на одно сообщение равно по определению

Нашей первой задачей является нахождение нижней границы для

В разд. 2.8 мы видели, что энтропия ансамбля сообщений представляет собой среднее количество информации, необходимое для однозначного определения сообщения из этого ансамбля. В том же разделе мы видели, что символы несут в среднем максимальное количество информации, когда они равновероятны. Эта максимальная величина, а именно есть пропускная способность кодового алфавита. Кроме того, равенства (2.100) и (2.105) показывают, что статистическая зависимость некоторого символа от предыдущих не может увеличить среднее количество информации на этот символ. На этом основании мы можем заключить, что

Откуда получаем

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

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

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