Корректирующие возможности кодов

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

Так, граница Плоткина определяет верхнюю границу кодового расстояния при заданном числе разрядов в кодовой комбинации и числе информацион­ных разрядов т для двоичных кодов:

(8.32)

или

, при . (8.33)

Верхняя граница Хэмминга устанавливает максимально возможное число разрешенных кодовых комбинаций любого помехоустойчивого кода при за­данных значениях и :

, (8.34)

где — число сочетаний из по элементов, которое рассчитывается согласно выражения

.

Отсюда можно получить выражение для оценки числа проверочных символов:

. (8.35)

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

. (8.36)

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

для ,

для ,

Блочные коды с и в литературе обычно называют кодами Хэмминга.

Все приведенные выше оценки дают представление о верхней границе чис­ла при фиксированных значениях и или определяют минимальное число проверочных символов : при заданных и .

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