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

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

Отправным пунктом была фундаментальная работа К. Шеннона [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. Ал. А. Марков..