2. Эффективное кодирование

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

Пусть имеется источник дискретных сообщений, алфавит которого K. При кодировании сообщений данного источника двоичным, равномерным кодом, потребуетсяL_рк=log₂K двоичных элементов на кодирование каждого сообщения. Если вероятностиP(a_i)появления всех сообщений источника равны, то энтропия источника (или среднее количество информации в одном сообщении) максимальна и равнаH_max(x)= log₂K.В данном случае каждое сообщение источника имеет информационную емкостьlog₂K=L_рк бит, и очевидно, что для его кодирования (перевозки) требуется двоичная комбинация не менееL_ркэлементов. Каждый двоичный элемент, в этом случае, будет переносить 1 бит информации. Если при том же объеме алфавита сообщения не равновероятны, то энтропия источника будет меньше

.

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

бит/элемент.

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

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

К наиболее известным эффективным кодам можно отнести код Хафмена и арифметический код.

3. Корректирующее кодирование

Корректирующие коды делятся на блочные и непрерывные к блочным относятся коды, в которых каждому символу алфавита соответствует блок (кодовая комбинация) из n (i) элементов, где i – номер сообщения. Если n (i) = n, т.е. длина блока постоянна и не зависит от номера сообщения, то код называется равномерным. Такие коды чаще применяются на практике. Если длина блока зависит от номера сообщения, то такой код называется неравномерным. В непрерывных кодах передаваемая информационная последовательность не разделяется на блоки, а проверочные элементы размещаются в определенном порядке между информационными.

Корректирующие коды позволяют получить и обнаружить ошибку.

Рисунок 2. Множество кодовых комбинаций.

Всё множество комбинаций делится на подмножества разрешённых и запрещённых кодовых комбинаций. Заменяя принятую запрещённую комбинацию ближайшей разрешённой, можно исправить ошибку. Расстояние Хемминга – определяет степень различия кодовых комбинаций. Минимальное расстояние Хемминга (d) называется кодовым расстоянием (d₀).

Расстояние - это минимальное расстояние Хемминга между всеми парами разрешенных комбинаций.