Избыточность сообщений.

Чем больше энтропия, тем большее количество информации содержит в среднем каждый элемент сообщения.

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

Русский алфавит, включая пропуск между словами, содержит 32 элемента, следовательно, Н = Iog32 = 5 бит. Анализ показывает, что с учетом неравномерности появления различных букв алфавита Н = 4,35 бит, а с учетом зависимости двухбуквенных сочетаний Н = 3,52 бит.

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

Эффективное кодирование. При кодировании каждая буква исходного алфавита представляется различимыми последовательностями, состоящими из кодовых букв (цифр). Если исходный алфавит содержит т букв, то для построения равномерного кода с использованием k кодовых букв необходимо удовлетворить соотношение т < k^q, где q — количество элементов в кодовой последовательности. Отсюда

Для построения равномерного кода достаточно пронумеровать буквы исходного алфавита и записать их коды как q –разрядные числа в k-ичной системе счисления. Например, при двоичном кодировании 32 букв русского алфавита используется q — Iog32 = 5 разрядов, на чем и основан телетайпный код. Кроме двоичных, наибольшее распространение получили восьмеричные коды. Пусть, например, необходимо закодировать алфавит, состоящий из 64 букв. Для этого потребуется 6 двоичных или 2 восьмеричных разряда. Буква с номером 13 получит соответственно коды 001 101 или 15. Часто используются также двоично-десятичные коды, в которых цифры десятичного номера буквы представляются двоичными кодами. Так, для нашего примера буква с номером 13 кодируется как 0001 0011.

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

При построении неравномерных кодов необходимо обеспечить возможность их однозначной расшифровки. В равномерных кодах такая проблема не возникает, так как при расшифровке достаточно кодовую последовательность разделить на группы, каждая из которых состоит из q элементов. В неравномерных кодах можно использовать разделительный символ между буквами алфавита (так поступают, например, при передаче сообщений с помощью азбуки Морзе). Если же отказаться от разделительных символов, то следует запретить такие кодовые комбинации, начальные части которых уже использованы в качестве самостоятельной комбинации. Например, если 101 означает код какой-то буквы, то нельзя использовать комбинации 1, 10 или 10101.

Практические методы оптимального кодирования просты и основаны на очевидных соображениях. Прежде всего, буквы (или любые сообщения, подлежащие кодированию) исходного алфавита записываются в порядке убывающей вероятности. Упорядоченное таким образом множество букв разбивается на два подмножества так, чтобы суммарные вероятности этих подмножеств были примерно равны. Затем каждое подмножество снова разбивается на два подмножества с соблюдением того же условия равенства вероятностей. Такое разбиение продолжается до тех пор, пока в подмножествах не окажется только по одной букве кодируемого алфавита. При каждом разбиении буквам верхнего подмножества присваивается кодовый элемент 1, а буквам нижнего подмножества — 0.

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

Ошибка в кодовой комбинации появляется вследствие замены одних элементов другими, причем r-кратная ошибка возникает при искажении г элементов. Например, если кодовая комбинация 0110111 принята как 0100110, то имеет место двукратная ошибка. Вообще различие между парой кодовых комбинаций выражается расстоянием, которое равно числу несовпадающих двоичных разрядов. Его можно также определить как число единиц в сумме этих комбинаций по модулю два: 0110111 +0100110 = 0010001. Если двоичным комбинациям длины q (равномерный код) сопоставить вершины q-мерного куба, то расстояние означает число ребер, отделяющих одну вершину от другой.

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

Наименьшее расстояние между комбинациями данного кода называют кодовым расстоянием. Более полное представление о свойствах кода дает матрица расстояний D, элементы которой равны расстояниям между каждой парой из всех т разрешенных комбинаций. Например, код 000; 001; 010; 111, кодовое расстояние которого d = 1, представляется симметричной матрицей четвертого порядка:

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