4. Основы теории кодирования и передачи информации

4.1. Основные понятия, формирование экономичного кода алфавита

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

Операция перевода сообщения в последовательность различных сигналов называется кодированием. Правило, ставящее в соответствие каждому передаваемому сообщению некоторую комбинацию сигналов, называется кодом. Если все комбинации кода имеют одну и ту же длину(число символов или разрядов в кодовой комбинации), т.е., то такие коды называютравномерными. В остальных случаях, коды называют неравномерными. По основанию системы счисления коды делятся на двоичные , троичные и т.д. Величина определяет число значений сигнала, характеризующих каждый символ сообщений в данной системе счисления. Например, прии т.е. при делении любого натурального числа на 2 рассматривают только остатки. Из них можно составить четыре комбинации: {00}, {01}, {10}, {11}. Количество возможных комбинаций сигналов, при заданныхи _{определяется равенством}:

(20) .

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

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

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

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

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

Для наиболее распространенного двоичного кода сред­нее число двоичных элементарных сигналов , приходящихся в закодированном сообщении на одну букву исходного сообщения, не может быть меньше ,т.е., где

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

Для построения такого экономичного кода Р. Фано и К. Шенноном предложена следующая методика (код Шен-нона-Фано):

Все букв (или иных знаков, знаковых систем) располагают в столбик в порядке убывания вероятностей их появления в сообщении.

1. Разбивают все буквы на две группы: верхнюю и нижнюю так, чтобы вероятности для букв принадлежали к каж­дой из этих групп, были по возможности близки одна к другой.

2. Для букв первой группы в качестве первой цифры кодового обозначения используется цифра 1, а для букв вто­рой группы — цифра 0.

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

4. Присваивают буквам вторую цифру кодового обозна­чения: 1 или 0 в зависимости от того, принадлежит буква к первой или ко второй из этих более мелких групп.

5. Каждую из содержащих более одной буквы групп сно­ва делят на две части возможно более близкой суммарной вероятности и т.д.

6. Процесс повторяется до тех пор, пока каждая из групп не будет содержать одну единственную букву.

7. Процесс повторяется до тех пор, пока каждая из групп не будет содержать одну единственную букву.

Пример 5.

Возьмем алфавит, состоящий из 6 букв, вероятности ко­торых равны 0.4: 0.2; 0,2: 0.1;0.05 и 0.05. Необходимо составить код Шеннона Фано.

Решение. Представим решение в виде таблицы.

Номер буквы	вероятность	Разбиение на группы	Кодовые обозначения
1 2 3 4 5 6	0,4 0,2 0,2 0,1 0,05 0,05		1 01 001 0001 00001 00000

В графе «разбиение должно быть результат разбиения на группы в соответствии пунктов 5 -7:

Для данного примера наилучший равномерный код состоит из трехзначных кодовых обозначений, так как в соответствии с равенством

Поэтому в нем на каждую букву приходится три элементарных сигнала.

При использовании кода Шеннона Фано среднее число элементарных сигналов, приходящихся на одну букву равна,

Это значительно меньше 3 и очень близко к предельно минимальному значению:

Таким образом, получен экономичный код.

Еще более экономичным получается код, если по мето­ду Шеннона-Фано кодировать не отдельные буквы, а блоки букв, - буквенные блоки.

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

Двухбуквенный алфавит можно привести к простейше­му равномерному коду: 1 - для буквы и 0 - для буквы, требующему для передачи каждой буквы один двоичный знак. Это на 12% больше минимально достижимого значения_.Требу­ется определить среднее значение длины кода в двух и трехбуквенных сообщениях.

Решение. Представим коды двух и трехбуквенных комбинаций, построенные по методу

Шеннона-Фано в следующей таблице

Результаты решения к примеру 6

Комбинация букв	Вероятность	Кодовое обозначе­ние	Комбина­ция букв	Вероят­ность	Кодовое обозначе­ние
n=2			n=3
АА	0,49	1	AAA	0,343	11
АВ	0,21	01	AAB	0,147	10
ВА	0,21	001	ABA	0,147	011
ВВ	0,09	000	BAA	0,147	010
			ABB	0,063	0010
			BAB	0,063	0011
			BBA	0,063	0001
			ВBB	0,027	0000

Среднее значение длины кода для :

или на одну букву , что на 3% отличается от минимально достижимого значения. Среднее значение длины кода для:

или на одну букву , что на 3% отличается от минимально достижимого значения.

Представленные примеры отражают суть основной теоремы Шеннона о кодировании при отсутствии помех:

При кодировании сообщения, разбитого на - буквенные блоки, можно, выбрав число сколь угодно большим, добиться того, чтобы среднее число двоичных элементарных сигналов,

приходящихся на одну букву исходного сообщения, было сколь угодно близко к .

Другими словами:

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

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

1. Буквы алфавита располагают в порядке убывания вероятностей их появления:

2. Две последние буквы принимают за одну буквуполу­чая новый алфавит , состоящий из букв с вероятностямиЭта операция называетсяоднократным сжатием. Буквы алфавита , располагают в порядке убывания вероятностей.

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

4.Операция сжатия продолжается до тех пор, пока не образуется алфавит , содержащий всего две буквы. Этим буквам присваиваются кодовые обо­значения 1 и 0.

5.Если кодовое обозначение уже приписано всем бук­вам алфавита , то буквам предыдущего алфавита, сохранившимся и в алфавите, приписываются те же кодовые обозначения, которые они имели в алфавите двум буквам иалфавита,слившимся в букву алфавита, приписываются обозначения, получающиеся из кодового обозначения буквы добавлением цифр 1 и 0 в конце.

Пример 7. Исходный алфавит состоит из 6 букв с вероятностями использования 0.4, 0.2, 0.2, 0.1, 0.05, 0.05 соответственно.

Требуется осуществить кодирование алфавита по методу Хафмана.

Решение. Представим решение этой задачи в виде следующей таблицы:

Результаты решения к примеру 7

Номер буквы	Вероятности и кодовые обозначения
	Исходный Алфавит	Сжатые алфавиты
1 2 3 4 5 6	0.4 0 0.2 10 0.2 111 0.1 1101 0.05 11001 0,05 11000	0.4 0 0.2 10 0.2 111 0.1 1101 0.1 1100	0.4 0 0.2 10 0.2 111 0.2 110	0.4 0 0.4 11 0.2 10	0.6 1 0.4 0

По заданной таблице легко заметить, что столбецполучен путём объединения строки 5 и 6 из столбца, путём сложения вероятностей и для двух последних букв, столбецполучен путём объединения строки 4 и 5 из столбца, путём сложения вероятностей и для двух последних букв, и т.д.

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

Для кодов с основанием К основная теорема о кодировании при отсутствии помех может быть представлена следующим образом.

При любом методе кодирования, использующем код с основанием ,

где — энтропия одной буквы сообщения. При этомесли кодировать сразу блоки, состоящие из букв.