8.2. Циклические коды, исправляющие одиночную ошибку

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

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

Процедура кодирования, декодирования, обнаружения и исправления ошибок зависит от количества ошибок. Рассмотрим процедуру кодирования для кодов, исправляющих одиночную ошибку (d₀ = 3).

1. Для заданного k и S определяется число контрольных разрядов m и длину кодовой комбинации n по формулам:

m = [log₂ {(k+1)+ [log₂(k+1)]}];

n=m+k.