Согласно методике Хаффмена, для построения оптимального кода N символы первичного алфавита выписываются в порядке убывания вероятностей. Последние символов, где [6] и - целое число, объединяют в некоторый новый символ с вероятностью, равной сумме вероятностей объединенных символов Последние символы с учетом образованного символа вновь объединяют, получают новый, вспомогательный символ, опять выписывают символы в порядке убывания вероятностей с учетом вспомогательного символа и т. д. до тех пор, пока сумма вероятностей т оставшихся символов после -го выписывания в порядке убывания вероятностей не даст в сумме вероятность, равную 1. На практике обычно, не производят многократного выписывания вероятностей символов с учетом вероятности вспомогательного символа, а обходятся элементарными геометрическими построениями, суть которых сводится к тому, что символы кодируемого алфавита попарно объединяются в новые символы, начиная с символов, имеющих наименьшую вероятность. Затем с учетом вновь образованных символов, которым присваивается значение суммарной вероятности двух предыдущих, строят кодовое дерево, в вершине которого стоит символ с вероятностью 1. При этом отпадает необходимость в упорядочивании символов кодируемого алфавита в порядке убывания вероятностей.

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

Максимально эффективными будут те ОНК, у которых

Для двоичных кодов

(52)

так как log22 = 1. Очевидно, что равенство (52) удовлетворяется при условии, что длина кода во вторичном алфавите

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

Эффективность ОНК. оценивают при помощи коэффициента статистического сжатия:

(53)

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

(54)

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

Для наиболее общего случая неравновероятных и взаимонезависимых символов

Для случая неравновероятных и взаимозависимых символов

ТЕМА 6. ОБНАРУЖЕНИЕ И ИСПРАВЛЕНИЕ ОШИБОК В СООБЩЕНИЯХ

Понятие об идее коррекции ошибок

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

10110 - переданная кодовая комбинация;

10010 - 1-я принятая комбинация;

10100 - -я принятая комбинация;

00110 - 3-я принятая комбинация;

10110 - накопленная комбинация.

Как видим, несмотря на то, что во всех трех принятыхкомбинациях были ошибки, накопленная не содержит ошибок[8].

Принятое сообщение может также состоять из кода и его инверсии. Код и инверсия посылаются в канал связи как одно целое. Ошибка на приемном конце выделяется при сопоставлении кода и его инверсии.

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

(55)

где - число единиц в кодовом слове. Если бы не существовало условия постоянного веса, то число комбинаций кода могло бы быть гораздо большим, а именно . Примером кода с постоянным весом может служить стандартный телеграфный код № 3 (см. приложение 4). Комбинации этого кода построены таким образом, что на 7 тактов, в течение которых должна быть принята одна кодовая комбинация, всегда приходятся три токовые и четыре безтоковые посылки. Увеличение или уменьшение количества токовых посылок говорит о наличии ошибки.

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

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