Метод кодирования по Шеннону—Фано

1. Буквы алфавита сообщения выписываются в столбец в порядке убывания их вероятностей (табл. 3.4).

  • 2. Далее они разделяются на две группы так, чтобы суммы вероятностей в каждой из них были по возможности одинаковы. Разбиение производится, пока в каждой из групп не останется по одному сообщению.
  • 3. При соответствующем разбиении принадлежность к верхней половине обозначается символом 0, а к нижней — 1, что и предопределяет символы кода Шеннона—Фано.

Пример. Сообщения X,, Х2, Х3, Х4 с вероятностями появления символов Р(Х^) = 0,5, Р(Х2) = 0,25, Р(Х3) = 0,125, Р(Х4) = 0,125 закодировать по Шеннону—Фано.

В соответствии с описанным методом кодирования построим табл. 3.4.

Таблица 3.4

Кодирование сообщений по Шеннону—Фано

С учетом статистических свойств источника сообщений длина КК для сообщений Хь Х2, Х3, Х4 будет различной. Число символов в них п(Х,) будет равно соответственно одному, двум и трем: X] = 02, Х2 = 102, Х3 = = 1102, Х4 = 1112 (см. табл. 3.4). Среднее число символов, т.е. средняя длина КК

Если при равномерном кодировании требуется два двоичных разряда (п = 2), чтобы различить 4 сообщения, то в данном примере п,_= 1,75, т.е. меньше.

Энтропия сообщения, составленного из символов Xt, Х2, Х3, Х4, равна

Минимальная длина КК выходного алфавита (ш = 2), необходимая для передачи сообщения без потери информации, составленная из символов входного алфавита (X, е X), равна

Коэффициент избыточности кода Ки, построенного по алгоритму

Шеннона—Фано, в соответствии с выражением (3.26) равен нулю, т.е.

построенный код не имеет избыточности.

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

Очевидно, что среднее время передачи сообщения при эффективном кодировании сокращается (тсср < тс).

Характеристики кода Шеннона—Фано:

  • ? код является неравномерным и неизбыточным;
  • ? каждый символ кода кодируется целым числом битов;
  • ? код является префиксным, т.е. допускает однозначное декодирование (любая короткая кодовая комбинация не является началом более длинной).

Пример. Декодировать заданную последовательность символов в кодах рассмотренного выше примера (см. табл. 3.4).

Сокращение времени передачи сообщения (при отсутствии помех) за счет использования оптимальных последовательностей кодов является несомненным достоинством кодирования по Шеннону—Фано. Эффект достигается благодаря присвоению высоковероятным сообщениям более коротких КК, и наоборот.

Недостатки кода:

  • 1) поскольку код не обладает избыточностью, каждая ошибка ведет к искажению информации;
  • 2) так как код неравномерный, некоторые символы кодируются длинными последовательностями, что приводит к длительным временным задержкам;
  • 3) метод Шеннона—Фано не всегда приводит к однозначному построению кода, так как при разбиении на подгруппы (см. табл. 3.4) большей по вероятности можно сделать как верхнюю, так и нижнюю подгруппы.

От последнего недостатка свободен код Хаффмена.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >