Методы кодирования сигналов

Кодирование по методу Шеннона—Фано

При кодировании по этому методу код строится следующим образом. Буквы алфавита сообщений выписываются в таблицу в порядке убывания вероятностей. Затем они разделяются на две группы так, чтобы суммы вероятностей в каждой из групп были по возможности одинаковыми. Всем буквам верхней половины в качестве первого символа приписывается «1», а всем нижним — «О». Каждая из групп разбивается на две подгруппы с одинаковыми суммарными вероятностями и т.д. Процесс повторяется до тех пор, пока в каждой подгруппе не останется по одной букве [2].

В таблице 2.1 представлен алфавит из 8 букв (z z%) с вероятностями появления каждой. В последнем столбце показаны кодовые комбинации, которые характеризуются тем, что чем выше вероятность появления буквы, тем меньше двоичных символов используется.

При обычном кодировании (не учитывающем статистические характеристики букв) для представления каждой буквы потребуется три символа, поскольку 23 = 8.

Среднее число разрядов на одну букву

где n(Zj) — число разрядов в кодовой комбинации, соответствующей букве Zi-

Таблица 2.1

Вероятность появления букв и их кодовые комбинации

Буквы

Вероятности

Кодовые

комбинации

Z

0,22

11

Z2

0,20

101

Z3

0,16

100

Z4

0,16

01

Z5

0,10

001

Z6

0,10

0001

Z?

0,04

00001

Z8

0,02

00000

Нетрудно подсчитать, что

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

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