Файл: Бездудный, В. Г. Техника безопасности в шахтном строительстве.pdf

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

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

83

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

Построение ОНК по методу Шеннона — Фано справедливо как для построения вторичных алфавитов с числом качественных призна­

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

г=1

для II варианта

Lcpll = 1,62 -f 0,36 -f 0,3 + 2 • 0,27 = 2,82.

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

Пример 7 иллюстрирует тот факт, что при построении оптимальных кодов буквы кодируемого алфавита не всегда удается однозначно разбить на части с равной суммарной вероятностью. Однако если построение оптимального кода ведется правильно, то средняя длина кодового слова при любых вариантах разбиения будет оставаться одинаковой. Кроме того, из приведенного примера видно, что для од­ ного и того же алфавита по одной и той же методике полечены два, хотя и равноценных, но все же различных кода. Этой неоднозначности при построении оптимального неравномерного кода можно избежать, если использовать методику, предложенную Хаффменом [40].

Хаффмен показал, что для получения минимально возможной длины кода основания т с числом взаимонезависимых букв первичного алфавита N

84

3) любая возможная последовательность lN — 1 кодовых сло должна либо сама быть кодовой комбинацией, либо иметь своим пре­ фиксом разрешенную комбинациюх.1

1 Доказательства необходимости и достаточности этих условий приведены в работе [40].

85

Исходя из данных условий, Хаффмен предложил следующий метод построения ОН К. Символы первичного алфавита выписывают в поряд­ ке убывания вероятностей. Последние п0 символов, где 2 < п , < т и N — п0/ш — 1 — целое число, объединяют в некоторый новый сим­ вол с вероятностью, равной сумме вероятностей объединяемых сим­ волов. Последние символы с учетом образованного символа вновь объединяют и получают новый, вспомогательный, символ. Опять выпи­ сывают символы в порядке убывания вероятностей с учетом вспомога­ тельного символа' и т. д. до тех пор, пока вероятности т оставшихся сим­ волов после N — n j m — 1-го выписывания не дадут в сумме 1. На прак­ тике обычно не производят многократного выписывания вероятностей символов, а обходятся элементарными геометрическими построениями, которые будут рассмотрены ниже.

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

Пример 8. Построим ОНК для передачи сообщения, составленного из следую­ щих слов

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

Слова-блоки можно рас­ сматривать как некоторые сим­ волы, тогда энтропия на каждое слово-блок

Н = — (р1 logaPj + PglogjPa-f-

+ ‘ • + Ps l°g2 Рв) =

= —(0,5 log3 0,5+0,15 log2 0,15-f-

-f- • • • -f- 0,02 log2 0,02).

Рис. 21. К построению оптималь­ ного кода по методике Хаффмена.

Построение оптимального кода по методике Хаффмена представлено на рис. 21. Сначала находят слова с наименьшими вероятностями: sells (0,02) и horse (0,03). Затем проводят от них линию к точке, в которой вероятность появления либо слова

86

sells, либо слова horse равна 0,05. Далее, берут два слова с вероятностями 0,04 (likes) и 0,04 (house) и получают новую точку с . вероятностью 0,08. Теперь наименьшими вероятностями обладают точки, соответствующие вспомогательным символам с ве­ роятностями 0,05 и 0,08. Соединяем их линиями с новой точкой, соответствующей вспомогательному символу с вероятностью появления 0,13. Продолжают так до тех пор, пока линии от основных и вспомогательных символов не сольются в точке, даю­ щей суммарную вероятность, равную 1.

Обозначив каждую верхнюю линию рис. 21 цифрой 1, а нижнюю — цифрой O', получим ОНК, который для каждого слова представляет собой последовательность нулей и единиц, встречающихся по пути к данному слову от конечной точки (1,00).

;= 1

Нетрудно убедиться в том, что, кодируя по методу Шеннона — Фано, мы на­ шли бы ту же среднюю длину кодового слова. При этом, найденные коды имели бы вид: 0; 100; 101; 110; 11100; 11101; 11110; Ill'll.

Полученные коды (табл. 17) могут быть однозначно декодированы на приемном конце благодаря тому, что ни один из них не является началом другого, т. е. эти коды обладают свойством префикса. Более того, такой код может автоматически восста­ новить-правильное содержание даже в том случае, когда декодирование началось не сначала сообщения или код был принят с ошибкой. Например, прием сообщения the man sells the house to the man the horse runs to the man начался после первой вер­ тикальной линии1

Как видим, сообщение восстановилось уже после третьего слова.

1 Процесс декодирования начинается с того, что находится кратчайшая после­ довательность цифр, которая в этом коде обозначает слово. Так, в нашем примере после первой пунктирной линии кратчайшая последовательность нулей и единиц соответствует слову likes, затем слову man и т. д.

87