2.2.1.   Оптимальные коды

Если источник вырабатывает сообщения, состоящие из фикси­рованного набора символов х с вероятностями появления р(хi), то при оптимальном кодировании они заменяются символами кода z или комбинациями символов кода так, чтобы количество информации на один символ кода было максимальным. Для случая, когда отсутствует статистическая связь между символами сообщения, Шенноном и Фано разработана методика построения кода, близкого к оптимальному и дающего оптимальный результат в том случае, когда вероятности р(хi) выражаются отрицательными степенями двойки. В оптимальном коде, называемом кодом Шеннона-Фано, используются символы 0 или 1, т.е. оптимальный код является двоичным.

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

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

2) в качестве первого символа кода всем буквам, вошедшим в первую группу, приписывается единица, а буквам второй группы – нуль;

3) каждая из полученных групп вновь разбивается на две под­группы  примерно с одинаковыми  вероятностями;

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

Разбиение на подгруппы производится до тех пор, пока в каждой подгруппе не останется по одной букве.

Процедура кодирования представлена в таблицах 2.1 и 2.2, составленных для двух случаев.

Оценим эффективность метода Шеннона-Фано, определив энт­ропию полученного кода. Для этого определим вероятности появления символов кода:

где  – число символов zj в кодовой комбинации, соответствую­щей букве хi;  – общее число символов в этой комбинации.

В коде Шеннона-Фано используются символы 1 или 0. Найдем вероятности их появления. Для случая, представленного в таблице 2.1, они будут равны:

что и следовало ожидать, так как р(1) + р(0) = 1.

Энтропия кода равняется Н = -0,5 log20,5 – 0,5 log20,5 = 1 бит. Полученный результат свидетельствует о том, что вероятности появ­ления символов кода одинаковы и энтропия кода максимальна.

Для случая, представленного в таблице 2.2, они будут равны:

Энтропия кода Н = 0,9988 бит, а избыточность DOTH = 1 – Н/Нmax = 0,0012. И в этом случае полученный код близок к оптимальному. Однако не всегда удается осуществить разбиение на груп­пы примерно с одинаковыми вероятностями, поэтому  избыточ­ность кода будет значительной. Для уменьшения избыточности в та­ких случаях производится группирование букв в блоки с последующим кодированием блоков. Например,  имеется две буквы  сообщения р(x1) = 0,7, а р(х2) = 0,3. При присвоении одной из букв символа 1,  а второй – 0 энтропия  полученного кода будет равна 0,88 бит. Из букв х1 и х2 могут быть образованы следующие блоки (таблица 2.3).

Энтропия полученного кода Н = 0,975 бит, а избыточность DOTH = 0,025. При  группировании букв в более длинные блоки удается получить еще меньшую избыточность. При кодировании блоков большей  длины  можно реализовать скорость передачи информации, сколь  угодно  близкую  к  пропускной  способности канала  связи.

Код Шеннона-Фано рассчитан  на  использование двоичного алфавита. Хаффменом  предложена  методика, позволяющая  построить оптимальный код с минимальной избыточностью при любом основании кода m.

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

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

1) n0 наименее вероятных букв объединяются в одну вспомогательную, вероятность которой определяется суммой вероятностей входящих в нее букв. Число n0 определяется из условия 2 £. n0 £ m  так, чтобы выполнялось  соотношение:

tent/image_post/elekpromust/pic24_1.gif>

где М – число символов сообщения; j -целое число;

2) в качестве последних символов кода, приписываемых буквам, вошедшим во вспомогательную букву, выбирается n0 различных символов кода;

3) оставшиеся буквы и  вспомогательная  буква располагаются в порядке  убывания  вероятностей;

4) составляется вторая вспомогательная буква, в которую входят m наименее вероятных букв. Вошедшим буквам присваиваются раз­личные  символы  кода  и  т.  д.

Образование вспомогательных букв производится до тех пор, пока не будет получена одна буква с вероятностью, равной единице. Образование кодовых комбинаций производится с учетом всех символов, приписанных буквам на всех этапах их объединения. Процедура кодирования представлена на таблице 2.4, составленной для основания кода m = 4.

Согласно выражению (2-28), для данного случая n0 = 3. Нетрудно заметить, что цифры младших разрядов кода определяются на первой стадии кодирования,  а цифры старших разрядов – на последней. Энтропия полученного кода Н = 1,97 бит, т.е. мало отличается от Нmax =  log2m = 2 бит, избыточность примерно равна: DОТН  » 0,015.

Таблица 2.5 иллюстрирует процедуру кодирования того же ансамбля двоичным кодом, m = 2.

Энтропия полученного кода Н @ 0,99 бит, что при Нmax = 1 бит дает избыточность  DOTH » 0,01. Таким образом, полученный резуль­тат близок к оптимальному.

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

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