Постановка задачи кодирования

Код – правила, описывающие соответствие знаков или их сочетаний одного алфавита знакам или их сочетаниям другого алфавита.

Кодирование – перевод информации в последовательность кодов.

Декодирование – операция, обратная кодированию, т.е. восстановление информации по полученной последовательности кодов.

Предполагается, что кодирование предшествует передаче информации, а сама передача осуществляется посредством некоторого набора сигналов - элементарных сигналов.

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

Но выгодность кода не идентична временной выгодности всей цепочки: кодирование – передача – декодирование. Возможна ситуация, когда за использование эффективного кода придется расплачиваться тем, что операции кодирования и декодирования будут занимать больше времени и иных ресурсов (например, места в памяти технического устройства).

Пусть имеется сообщение, для записи которого используется некоторый алфавит из n символов.

Требуется закодировать это сообщение, т.е. представить его в виде последовательности из m различных элементарных сигналов наиболее выгодным образом.

Рассмотрим ситуацию, когда используются лишь два типа сигналов (m=2).

С практической точки зрения это наиболее просто реализуемый вариант (например, наличие или отсутствие напряжения в проводе). Такое кодирование называется двоичным.

Удобство двоичных кодов и в том, что при равных длительностях каждый элементарный сигнал (0 или 1) несет в себе 1 бит информации, что сводит определение количества переданной информации к простому подсчету числа импульсов и пауз.

Итак, ПЗ кодирования:

Вход: сообщение, построенное с использованием алфавита из n символов.

Выход:

1. Закодировать сообщение во вторичном алфавите, состоящем из двух символов (0 и 1) наиболее выгодным образом.

2. При этом необходимо учесть проблему выделения из потока сигналов (последовательностей импульсов и пауз) отдельных кодов символов.

Возможные варианты решения ПЗ

Приемное устройство фиксирует интенсивность и длительность сигналов.

Элементарные сигналы (0 и 1) могут иметь одинаковые или разные длительности.

Их количество в коде (длина кода) также может быть одинаковым (равномерный код) или разным (неравномерный код). В результате возможны следующие сочетания:

В случае использования неравномерного кодирования или кодирования сигналами разной длительности (ситуации (2), (3) и (4)) для отделения кода одного знака от другого между ними необходимо передавать специальный сигнал – временной разделитель (признак конца знака).

При равномерном кодировании одинаковыми по длительности сигналами (ситуация 1) передачи специального разделителя не требуется, поскольку отделение одного кода от другого производится по общей длительности, которая для всех кодов оказывается одинаковой.

Количественной характеристикой относительной эффективности кода Q является избыточность кода: где Н_{0 -} средняя длина полученного кода и должна выражаться целым числом бит, т.е. H₀ ³ log₂ N; Н - длина кода для того же алфавита при равновероятном появлении всех знаков (т.к. она максимальна).

Из определения ясно, что Q³1, причем, чем больше значение Q, тем код выгоднее. Применение этой величины позволяет сравнивать различные способы кодирования одной и той же системы знаков.