Систематические коды. Код Хэмминга

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

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

Обычно производящая матрица строится при помощи двух матриц:

Единичной, ранг которой определяется числом информационных разрядов, и добавочной, число столбцов которой определяется числом контрольных разрядов кода. Каждая строка добавочной матрицы должна содержать не менее d₀ -1 единиц, а сумма по модулю для любых строк не менее d₀-2 единиц (где d₀ - минимальное кодовое расстояние).

Производящая матрица позволяет находить все остальные кодовые комбинации.

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

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

Соотношения между n, r, k для кода Хэмминга представлены в таблице. Зная основные параметры корректирующего кода, определяют, какие позиции сигналов будут рабочими, а какие - контрольными. Практика показала, что номера контрольных символов удобно выбирать по закону

2ⁱ, где i = 0, 1, 2, 3,... - натуральный ряд чисел.

Номера контрольных символов в этом случае равны 1, 2, 4, 16, 32... Затем определяют значения контрольных коэффициентов (0 или 1), руководствуясь следующим правилом:

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

Соотношения между количеством информационных и контрольных символов в коде Хэмминга

Проверочные позиции выбирают следующим образом. Составляют табличку для ряда натуральных чисел в двоичном коде. Число ее строк n=r+k. Первой строке соответствует проверочный коэффициент a ₁, второй а₂ и т. д.:

Затем выявляют проверочные позиции, выписывая коэффициенты по следующему принципу:

в первую проверку входят коэффициенты, которые содержат единицу в младшем разряде (a₁, а₃, a₅, a₇, a₉, a₁₁ и т. д.);

во вторую - во втором разряде (а₂, а₃, а₅, а₇, а₉, a₁₁ и т. д.);

в третью - в третьем разряде и т. д.

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

Номера проверочных позиций кода Хэмминга

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