Кодирование Алфавитное

Кодирование неравномерное,- представление информации в стандартной форме, при к-рой элементарным синтаксическим единицам языка сообщений (буквам алфавита языка) последовательно сопоставляются кодовые комбинации символов из нек-рого заданного алфавита (здесь под информацией понимается линейная запись букв). Примером К. а. может служить известный код Морзе, в к-ром слова кодируются побуквенно, а буквам сопоставлены слова в алфавите трех символов где — пробел. Примером естественно сложившегося кодирования, к-рое не укладывается в модель К. а., является десятичная система счисления. Источником идей для развития теории К. а. являются кибернетич. точка зрения на информационные процессы и системы, с одной стороны, и потребность техники связи (где часто возникает необходимость преобразования информации к более удобной в каком-то отношении форме) — с другой; отправным пунктом была фундаментальная работа К. Шеннона [1], опубликованная в 1948. Теория К. а.- раздел прикладной математики, включающий в себя изучение различных математич. моделей каналов связи с использованием разнообразных математич. методов. Лучше всего изучено равномерное или блочное кодирование, при к-ром кодовые комбинации имеют фиксированную длину. Для этого класса имеется развитый математич. аппарат (см. Код с исправлением ошибок). Более общей абстрактной схемой является автоматное кодирование, при к-ром соответствие реализуется конечным автоматом. В практич. отношении равномерное кодирование обеспечивает, как правило, удовлетворительные результаты, поэтому использование других методов кодирования должно иметь очень веские достоинства (напр., существенное сжатие информации) при не слишком серьезных недостатках (усложнение кодирования и декодирования). Основные результаты общего характера можно сформулировать для случая побуквенного К. а. (когда кодирующий автомат имеет одно внутреннее состояние), так как известные обобщения не имеют принципиального значения, а исследования, связанные с другими моделями, не получили еще значительного теоретич. развития. Рассматривается следующая модель канала связи: А= — алфавит канала связи, т. е. перечень сигналов, к-рые могут передаваться по каналу, t( а i) -длительность сигнала а i, В = — алфавит языка сообщений. В простейшем случае источник сообщений есть вероятностная схема, на выходе к-рой в каждый момент дискретного времени появляется одна из букв В, причем вероятности Pi=p(bi )появления букв не зависят от времени. Схема кодирования f отображает буквы Вв слова А*( А*- моноид, порожденный A), f(bi) = vi и слова В* кодируются побуквенно:f(bi1, ... bik)=f(bi1)...f(bik). Таким образом, отображение f полностью задается кодом . Если 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. Ал. А. Марков.