Принципы помехоустойчивого кодирования

Идея помехоустойчивого кодирования состоит в том, что в передаваемую кодовую комбинацию по определенным правилам вносится избыточность (признаки разрешенной комбинации). Правила внесения избыточности, т.е. признаки, должны быть известны как на передающей, так и на приемной стороне. Если на приемной стороне эти признаки в кодовой комбинации не обнаруживаются, то считается, что кодовая комбинация принята правильно (является разрешенной). Внесение избыточности при использовании помехоустойчивых (корректирующих кодов обязательно связано с увеличением числа разрядов (длины) кодовой комбинации — n. При этом все множество N₀=2n комбинаций можно разбить на два подмножества: подмножество разрешенных комбинаций, т. е. обладающих определенными признаками, и подмножество запрещенных комбинаций, этими признаками не обладающих. Корректирующий код отличается от обычного тем, что в канал передаются не все кодовые комбинации (N₀), которые можно сформировать из имеющегося числа разрядов n, а только их часть N, которая составляет подмножество разрешенных комбинаций: N< N₀.

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

Поскольку любая из N разрешенных комбинаций может превратиться в любую из N₀ возможных, то общее число таких случаев равно NN₀. Очевидно, что число случаев, в которых ошибки обнаруживаются, равно N(N₀ — N), где N₀-N — число запрещенных комбинаций. Тогда доля обнаруживаемых ошибочных комбинаций составит:

(30.1)

Большинство разработанных до настоящего времени кодов предназначено для корректирования взаимно независимых ошибок определенной кратности и пачек (пакетов) ошибок.

Кратностью ошибки называется количество искаженных символов в кодовой комбинации.

Степень отличия любых двух кодовых комбинаций характеризуется кодовым расстоянием (расстоянием Хэмминга). Оно выражается числом символов, в которых комбинации отличаются одна от другой, и обозначается через d.

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

Минимальное расстояние, взятое по всем параметрам кодовых разрешенных комбинаций кода, называют минимальным кодовым расстоянием.

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

Очевидно, что при минимальном кодовом расстоянии d = 1 все кодовые комбинации являются разрешенными.

При построении корректирующих кодов возникает задача нахождения наибольшего числа N кодовых комбинаций n -значного двоичного кода, расстояние между которыми не менее d. Общее решение этой задачи неизвестно. Некоторые частные результаты приведены в табл. 30.1:

Таблица 30.1

d	N
	2^n
	2^n-1
…	…
2j+1

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

Дата добавления: 2014-01-04