Экономичное кодирование

В общем случае избыточность является полезным свойством сообщений, так как повышает помехоустойчивость. Благодаря ей, например, речь естественного языка достаточно устойчива к различного рода помехам и искажениям. Если в предложении текста исказить одну - две буквы то, как правило, смысл фразы сохраняется.

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

Для передачи дискретных сообщений в системах связи используют, как правило, два алфавита. Один алфавит - внешний - имеющий достаточно большой объем, применяется для формирования сообщения на языке источника информации и адресата. Другой алфавит- внутренний - используется непосредственно для передачи информации по каналу связи. Он содержит небольшое количество символов, например, 0 и 1. (Словам, составленным из 0 и 1, при передаче могут соответствовать последовательности импульсов тока.)

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

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

Равномерные коды

Каждая сформированная кодовая комбинация состоит из некоторого количества знаков, которые определяют ее размер.

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

Примерами равномерного кода являются двоичное кодирование символов (буквы, цифр и других знаков), телеграфный код Бодо (Предложен для передачи 56 символов 5-значным двоичным кодом. Использует дополнительную кодовую комбинацию (регистр), предшествующую знаковой комбинации) и код Трисиме, в котором знакам латинского алфавита ставятся в соответствие кодовые комбинации из одинакового количества 3-х знаков из алфавита объемом 3 знака: "1", "2", "3" (рис. 2).

Рис. 2. Код Трисиме

Простые коды

Если дискретное сообщение, образованно знаками входного алфавита объемом N, то для его передачи m знаками выходного алфавита объемом n необходимо N_k = n^m > N кодовых комбинаций. Если N_k = N, то используются все комбинации и код является безизбыточным. Однако обычно точное исполнение такого равенств не выполняется ввиду не кратности N степеням выбранной системы счисления. Но обязательно должно быть выполнено условие N_k > N, в результате чего N_k - N кодовых комбинаций не используется.

Код, для которого выполняется условие n^m-1 < N< n^m называют простым или первичным кодом. Основное назначение первичных кодов – экономно представлять кодовыми комбинациями заданное множество дискретных величин, обычно счетное множество цифровых величин.

Простые коды подразделяют на взвешенные (позиционные), старшим разрядам которых присваивается больший вес, чем младшим (2^m-1, 2^m-2, …, 2¹, 2⁰) и невзвешенные (непозиционные), все разряды которых имеют одинаковый вес.

Примером взвешенного когда является обычный двоичный код с весами знаков
2^m-1, 2^m-2, …, 2¹, 2⁰. Примером невзвешенного кода является код Грея.

Взвешенный двоичный код прост в реализации и удобен при выполнении вычислительных операций в ЭВМ. Но ошибка в старшем разряде искажает сообщение более значимо, чем ошибка в младшем разряде.

В невзвешенных кодах ошибка в любом разряде имеет одинаковое значение - будет искажена вся кодовая комбинация. Перед обработкой невзвешенный код преобразуют в обычный двоичный. Недостатком невзвешенных кодов является сложность декодирования и вычислений.

Не нашли, что искали? Воспользуйтесь поиском: