1.6. КОДИРОВАНИЕ

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

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

При кодировании каждый символ дискретного сообщения пронумеровывается и передача сообщений сводится к передаче последовательностей чисел, записанных в той или иной системе счисления. Например, для передачи букв русского алфавита необходимо передавать числа от 1 до 32 (твердый знак не передают). Обозначим основание системы счисления через 7 (например, вдесятичной системе в двоичной Любое -разрядное числа X можно записать в виде полинома

где целые числа, удовлетворяющие условию Например, число 13 в десятичной и двоичной системе записывается так:

Когда последовательность элементов дискретного сообщения преобразована в последовательность двоичных чисел, для их передачи по каналу связи необходимы всего лишь два элементарных кодовых сигнала: 0, 1. Роль таких сигналов могут выполнять посылки постоянного тока разной полярности, колебания с различными частотами и др. При передаче двоичных сигналов требуется всего лишь пара проводов. Другим важным преимуществом двоичного кодирования является простота арифметических операций в двоичной системе счисления, которые легко реализуются с помощью простейших логических схем вычислительной техники. Сложение выполняется схемой а умножение — схемой И. Более сложные операции реализуются различными сочетаниям» схем

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

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

случаях — неравномерным. Для равномерного кода общее число различных кодовых комбинаций Например, для равномерного кода Бодо Этого числа комбинаций достаточно для кодирования всех букв латинского алфавита. Код Морзе служит примером неравномерного кода. В нем наиболее часто встречающимся буквам присваиваются наиболее короткие кодовые комбинации. Это сделано для увеличения скорости передачи информации.

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

Если т. е. код не способен обнаруживать ошибки и его называют примитивным (безызбыточным).

Избыточность корректирующего кода

Из формул (1.16), (1.17) следует, что корректирующий код обнаруживает ошибки за счет введения избыточности. Доля обнаруживаемых ошибок растет по мере увеличения избыточности.

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

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

Аналитическая запись сложения по модулю имеет вид

На рис. 1.2 показано условное обозначение логического оператора сложения по модулю. Таким образом, расстояние получают в результате поразрядного суммирования по модулю и обычного суммирования по формуле (1.18). Для равномерного двоичного кода кодовое расстояние — это число символов, на которое отличается одна комбинация от другой. Например, если то

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

Задачи анализа и синтеза кодовг устройств кодирования и декодирования решают на основе сочетания методов теории информации, высшей алгебры и теории конечных автоматов [18]. Методы теории информации позволяют строить общие алгоритмы анализа и синтеза кодов, методы высшей алгебры (теория групп, теория колец, теория полей) позволяют синтезировать и анализировать математические модели кодов, методы теории конечных автоматов — создавать конкретные структурные схемы кодеров и декодеров.

Рис. 1.2. Логический оператор сложения по модулю

Контрольные вопросы

(см. скан)