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

кодирование неравномерное,- представление информации в стандартной форме, при к-рой элементарным синтаксическим единицам языка сообщений (буквам алфавита языка) последовательно сопоставляются кодовые комбинации символов из нек-рого заданного алфавита (здесь под информацией понимается линейная запись букв). Примером К. а. может служить известный код Морзе, в к-ром слова кодируются побуквенно, а буквам сопоставлены слова в алфавите трех символов [img: http://localhost:8080/file/021224-74.jpg] где [img: http://localhost:8080/file/021224-75.jpg] - пробел. Примером естественно сложившегося кодирования, к-рое не укладывается в модель К. а., является десятичная система счисления. Источником идей для развития теории К. а. являются кибернетич. точка зрения на информационные процессы и системы, с одной стороны, и потребность техники связи (где часто возникает необходимость преобразования информации к более удобной в каком-то отношении форме) - с другой; отправным пунктом была фундаментальная работа К. Шеннона [1], опубликованная в 1948. Теория К. а.- раздел прикладной математики, включающий в себя изучение различных математич. моделей каналов связи с использованием разнообразных математич. методов. Лучше всего изучено равномерное или блочное кодирование, при к-ром кодовые комбинации имеют фиксированную длину. Для этого класса имеется развитый математич. аппарат (см. Код с исправлением ошибок). Более общей абстрактной схемой является автоматное кодирование, при к-ром соответствие реализуется конечным автоматом. В практич. отношении равномерное кодирование обеспечивает, как правило, удовлетворительные результаты, поэтому использование других методов кодирования должно иметь очень веские достоинства (напр., существенное сжатие информации) при не слишком серьезных недостатках (усложнение кодирования и декодирования). Основные результаты общего характера можно сформулировать для случая побуквенного К. а. (когда кодирующий автомат имеет одно внутреннее состояние), так как известные обобщения не имеют принципиального значения, а исследования, связанные с другими моделями, не получили еще значительного теоретич. развития. Рассматривается следующая модель канала связи: [img: http://localhost:8080/file/021224-76.jpg] А= {а 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 есть [img: http://localhost:8080/file/021224-77.jpg] где wij- число вхождений буквы aj в слово vi, а искомое математическое ожидание есть [img: http://localhost:8080/file/021224-78.jpg] (Е f наз. также стоимостью кодирования f). В общем случае Е f зависит от структуры кода, к-рая описывается структурным многочленом [img: http://localhost:8080/file/021224-79.jpg] - производящей функцией, перечисляющей слова кода по их составу. В частном случае, когда t(а 1)=...=t(а n)=t, имеем [img: http://localhost:8080/file/021224-80.jpg] т. е. Е f определяется только спектром длин слов кода {l1, l2,..., 1 т), где li- длина слова vi. Для этого случая проблема выбора оптимального кода (т. е. минимизирующего стоимость) решается полностью; доказано [2] необходимое и достаточное спектральное условие для существования однозначно декодируемого кода [img: http://localhost:8080/file/021224-81.jpg] (1) Показано [4], что вместе с неравенством (1) условие [img: http://localhost:8080/file/021224-82.jpg] необходимо и достаточно для существования кода с данным спектром, имеющего так наз. свойство самосинхронизации, к-рое состоит в том, что ошибка при декодировании автоматически локализуется с вероятностью 1. Для сложности декодирования, с абстрактной точки зрения, наиболее интересна качественная мера: наличие свойства конечности задержки декодирования, означающее возможность реализации декодирования конечным автоматом (количественные оценки сложности схемной реализации автоматов выходят за рамки теории кодирования). Так наз. префиксные коды (свойство префиксности состоит в том, что никакое слово Vне является начальным отрезком другого слова из V)все имеют это свойство. Было показано [2], что любой код, для к-рого f взаимно однозначно, спектрально эквивалентен нек-рому префиксному коду. Класс префиксных кодов относительно хорошо обозрим, чем и объясняется результативность исследования случая t(а 1)=... = t(а n). В общем случае известны алгоритмич. решения вопросов распознавания свойств взаимной однозначности кодирования и конечности задержки декодирования. Свойство взаимной однозначности f можно рассматривать как минимальный уровень помехоустойчивости кода V. Имеется алгоритмич. решение задачи вычисления фактической корректирующей способности произвольного кода в общем случае и с дополнительным требованием конечной задержки декодирования. Класс всех свободных кодов (т. е. однозначно декодируемых) устроен весьма сложно, но экстремальные требования к кодам часто приводят к существенным ограничениям. Напр., показано, что для максимальных по включению кодов (для к-рых неравенство (1) обращается в равенство и к-рые наз. полными, так как для них и только для них алфавит канала используется полностью в том смысле, что любое слово из А* является частью нек-рого закодированного сообщения) свойство конечной задержки имеет место в том и только в том, случае, если код префиксный.