Систематические коды. Код Хэмминга.
Систематические коды представляют собой такие коды, в которых информационные и корректирующие разряды расположены по строго определенной системе и всегда занимают строго определенные места в кодовых комбинациях .
Систематические коды являются равномерными, т. е. все комбинации кода с заданными корректирующими способностями имеют одинаковую длину. Систематические коды могут строиться, как линейные на основе производящей матрицы, как это уже было рассмотрено.
Обычно производящая матрица строится при помощи двух матриц:
Единичной, ранг которой определяется числом информационных разрядов, и добавочной, число столбцов которой определяется числом контрольных разрядов кода. Каждая строка добавочной матрицы должна содержать не менее d0 -1 единиц, а сумма по модулю для любых строк не менее d0-2 единиц (где d0-минимальное кодовое расстояние).
Производящая матрица позволяет находить все остальные кодовые комбинации.
Код Хэмминга является типичным примером систематического кода. Однако при его построении к матрицам обычно не прибегают. Он настолько хорошо изучен, что уже выработался четкий алгоритм его построения :
Код Хэмминга представляет собой один из важнейших классов линейных кодов, нашедших широкое применение на практике и имеющих простой и удобный для технической реализации алгоритм обнаружения и исправления ошибок.
Соотношения между n, r, k для кода Хэмминга представлены в таблице. Зная основные параметры корректирующего кода, определяют, какие позиции сигналов будут рабочими, а какие - контрольными. Практика показала, что номера контрольных символов удобно выбирать по закону
2i, где i = 0, 1, 2, 3, ... - натуральный ряд чисел.
Номера контрольных символов в этом случае равны 1, 2, 4, 16, 32... Затем определяют значения контрольных коэффициентов (0 или 1), руководствуясь следующим правилом:
сумма единиц на проверочных позициях должна быть четной. Если эта сумма четна -значение контрольного коэффициента нуль, в противном случае - единица.
Соотношения между количеством информационных и контрольных символов в коде Хэмминга
Проверочные позиции выбирают следующим образом. Составляют табличку для ряда натуральных чисел в двоичном коде. Число ее строк n=r+k. Первой строке соответствует проверочный коэффициент a1, второй а2 и т. д.:
Затем выявляют проверочные позиции, выписывая коэффициенты по следующему принципу:
в первую проверку входят коэффициенты, которые содержат единицу в младшем разряде (a1, а3, a5, a7, a9, a11 и т. д.);
во вторую - во втором разряде (а2, а3, а5, а7, а9, a11 и т. д.);
в третью - в третьем разряде и т. д.
Номера проверочных коэффициентов соответствуют номерам проверочных позиций, что позволяет составить общую таблицу проверок.
Номера проверочных позиций кода Хэмминга