Математическая энциклопедия - кодирование алфавитное

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

Примером естественно сложившегося кодирования, к-рое не укладывается в модель К. а., является десятичная система счисления. Источником идей для развития теории К. а. являются кибернетич. точка зрения на информационные процессы и системы, с одной стороны, и потребность техники связи (где часто возникает необходимость преобразования информации к более удобной в каком-то отношении форме) с другой; отправным пунктом была фундаментальная работа К. Шеннона [1], опубликованная в 1948. Теория К. а.раздел прикладной математики, включающий в себя изучение различных математич. моделей каналов связи с использованием разнообразных математич. методов. Лучше всего изучено равномерное или блочное кодирование, при к-ром кодовые комбинации имеют фиксированную длину. Для этого класса имеется развитый математич. аппарат (см. Код с исправлением ошибок). Более общей абстрактной схемой является автоматное кодирование, при к-ром соответствие реализуется конечным автоматом. В практич. отношении равномерное кодирование обеспечивает, как правило, удовлетворительные результаты, поэтому использование других методов кодирования должно иметь очень веские достоинства (напр., существенное сжатие информации) при не слишком серьезных недостатках (усложнение кодирования и декодирования).

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

А= {а 1, ..., а п}алфавит канала связи, т. е. перечень сигналов, к-рые могут передаваться по каналу, t( а i) -длительность сигнала а i, В = {b1,..., b т}алфавит языка сообщений. В простейшем случае источник сообщений есть вероятностная схема, на выходе к-рой в каждый момент дискретного времени появляется одна из букв В, причем вероятности Pi=p(bi )появления букв не зависят от времени. Схема кодирования f отображает буквы Вв слова А*( А*моноид, порожденный A), f(bi) = vi и слова В* кодируются побуквенно:f(bi1, ... bik)=f(bi1)...f(bik). Таким образом, отображение f полностью задается кодом V={v1, ..., vm}. Если f взаимно однозначно, то задача схемы декодирования восстановить переданное сообщение, реализуя отображение f^-1.

Оценочными факторами для модели являются информации скорость передачи и сложность декодирования, определяемые выбором кода V. Скорость передачи характеризуется количественно величиной математич. ожидания времени, к-рое требуется для передачи одной буквы сообщения: длительность передачи буквы bi есть

где wijчисло вхождений буквы aj в слово vi, а искомое математическое ожидание есть

(Е f наз. также стоимостью кодирования f). В общем случае Е f зависит от структуры кода, к-рая описывается структурным многочленом

производящей функцией, перечисляющей слова кода по их составу. В частном случае, когда t( а 1)=...=t( а n)=t, имеем т. е. Е f определяется только спектром длин слов кода {l1, l2,..., 1 т), где liдлина слова vi. Для этого случая проблема выбора оптимального кода (т. е. минимизирующего стоимость) решается полностью; доказано [2] необходимое и достаточное спектральное условие для существования однозначно декодируемого кода

(1)

Показано [4], что вместе с неравенством (1) условие

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

Для сложности декодирования, с абстрактной точки зрения, наиболее интересна качественная мера: наличие свойства конечности задержки декодирования, означающее возможность реализации декодирования конечным автоматом (количественные оценки сложности схемной реализации автоматов выходят за рамки теории кодирования). Так наз. префиксные коды (свойство префиксности состоит в том, что никакое слово Vне является начальным отрезком другого слова из V)все имеют это свойство. Было показано [2], что любой код, для к-рого f взаимно однозначно, спектрально эквивалентен нек-рому префиксному коду. Класс префиксных кодов относительно хорошо обозрим, чем и объясняется результативность исследования случая t(а 1)=. . . = t( а n).

В общем случае известны алгоритмич. решения вопросов распознавания свойств взаимной однозначности кодирования и конечности задержки декодирования. Свойство взаимной однозначности f можно рассматривать как минимальный уровень помехоустойчивости кода V. Имеется алгоритмич. решение задачи вычисления фактической корректирующей способности произвольного кода в общем случае и с дополнительным требованием конечной задержки декодирования. Класс всех свободных кодов (т. е. однозначно декодируемых) устроен весьма сложно, но экстремальные требования к кодам часто приводят к существенным ограничениям. Напр., показано, что для максимальных по включению кодов (для к-рых неравенство (1) обращается в равенство и к-рые наз. полными, так как для них и только для них алфавит канала используется полностью в том смысле, что любое слово из А* является частью нек-рого закодированного сообщения) свойство конечной задержки имеет место в том и только в том, случае, если код префиксный.

Лит.:[1] Шеннон К., Работы по теории информации и кибернетике, пер. с англ., М., 1963; [2] Мак-Миллан Б., "Кибернетич. сб.", 1961, в. 3, с. 88-92; [3] Xаффмен Д., там же, с. 79-87; [4] Schutzenberger M. P., "Information and Control", 1967, v. 11, p. 396-401; [5] Марков А л. А., "Пробл. кибернетики", 1962, в. 8, с. 169-86; 1964, в. 12, с. 137 53; 1967, в. 19, с. 307-09; 1976, в. 31, с. 77 108.

Ал. А. Марков.

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985