Код Хемминга

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

Порядок построения кода Хемминга:

1. Определяется количество информационных k и проверочных r разрядов. Число проверок в дальнейшем будет равняться числу проверочных разрядов r. Результат каждой проверки обозначается символом 0 или 1.

Записанные справа налево символы образуют число в двоичной системе счисления, соответствующее номеру искаженного разряда. Так как это число не может быть меньше k, а число разрядов в нем равно r, то должно выполняться условие .

2. Все проверки заключаются в вычислении суммы по модулю 2 кодовых элементов в соответствующих разрядах кодовой комбинации. При первой проверке выбираются те разряды, двоичный номер которых содержит 1 во втором разряде, то есть 2, 3, 6, 7, 10-й. При третьей проверке выбираются 4, 5, 6, 7, 12, 13-й разряды и так далее.

3. Место расположения проверочных разрядов в принципе может быть выбрано произвольным, но при выбранном правиле проверок проверочные символы (0 или 1) удобнее размещать в разряда, номера которых равны целой степени числа 2, то есть в 1, 2, 4, 8-м и т.д. разрядах.

4. Способ заполнения проверочных разрядов определяется правилом проверки корректирующего кода.

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

В нем образование разрешенных кодовых комбинаций производится циклической перестановкой одной кодовой комбинации. Она называется образующей. Сдвиг осуществляется справа налево. Левый крайний символ каждый раз переносится в конец кодовой комбинации. Циклический код задается в виде матрицы с n столбцами и k строками:

.

При описании циклических кодов n размерная кодовая комбинация представляется в виде многочленов с фиктивной переменной X. Показатели степени у Х соответствуют номерам разрядов, а коэффициентами при Х являются элементы поля GF(m) (где m- основание матрицы), то есть элементы матрицы.

Многочлен для циклического кода, рассмотренного выше:

.

В последнем выражении - образующий многочлен.

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

При этом циклический сдвиг, образующий кодовые комбинации соответствуют умножению образующего многочлена на Х.

.