Коды Хэмминга

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

Код Хэмминга, обеспечивающий исправление всех однократных ошибок, должен иметь минимальное кодовое расстояние dmin=3. Код строится таким образом, чтобы в результате p = n-k проверок получилось двоичное число, указывающее номер позиции с искажением в кодовой комбинации. Для этого проверочные символы должны находиться на номерах позиций, которые выражаются степенью двойки, так как каждый из них входит только в одно из проверочных уравнений. Таким образом, если нумеровать позиции слева на право, то контрольные символы должны находиться на первой, второй, четвертой и т. Д. позициях.

Результат первой проверки дает цифру младшего разряда синдрома в двоичной записи. Если результат этой проверки даст 1, то один из символов проверочной группы искажен. Таким образом, первой проверкой должны быть охвачены символы с номерами, содержащими в двоичной записи единицы в первом разряде: 1,3,5,7,9 и т. д. Результат второй проверки дает цифру второго разряда синдрома. Следовательно второй проверкой должны быть охвачены символы с номерами, содержащими в двоичной записи единицы во втором разряде: 2,3,6,7,10 и т. д.

Аналогично при третьей проверке должны проверяться символы, номера которых в двоичной записи содержат единицу в третьем разряде: 4,5,6,12 и т. д.

Таким образом, проверочные группы должны иметь вид:

S1 = a1 + a3 + a5 + a7 + a9 +….

S2 = a2 + a3 + a6 + a7 + a10 +….

S3 = a4 + a5 + a6 + a7 + a12 +….

S4 = a8 + a9 + a10 + a11 + a12 +….

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

Например, для кода длиной n=9, обеспечивающего исправление однократных ошибок, количество избыточных символов p=4. При этом в качестве проверочной может быть выбрана следующая матрица:

H = 0 0 0 0 0 0 0 1 1

0 0 0 1 1 1 1 0 0

0 1 1 0 0 1 1 0 0

1 0 1 0 1 0 1 0 1

Представим в качестве примера простую двоичную комбинацию 10011 кодом Хэмминга. Так как содержать информацию должны третий, пятый, шестой и девятый символ, то для рассматриваемого кода a3 = 1, a5 = 0, a6 = 0, a7 = 1, a9 = 1. Из условия обеспечения четности сумм получим следующие значения проверочных символов: a1 = 1, a2 = 0, a4 = 1, a8 = 1. Следовательно, простому пятизначному коду 11011 соответствует девятизначный код Хэмминга 101100111.

Пусть теперь при передаче произошло искажение пятого символа, т. е. код принял вид 101110111. Тогда в результате первой проверки получим 1, второй - 0, третий - 1 и четвертый - 0. Таким образом, в результате проверок получим синдром 0101, указывающий на искажение пятого символа. Исправление ошибки производится с помощью инвертирования пятого символа.

Код Хэмминга с кодовым расстоянием dmin = 4 получается путем добавления к коду Хэмминга с dmin = 3 проверочного символа, представляющего собой результат суммирования по модулю два всех символов кодовой комбинации. Операция декодирования состоит из двух этапов. На первом определяется синдром, соответствующий коду с dmin = 3, на втором - проверяется последнее проверочное соотношение.

Для рассмотренного ранее кода с dmin = 4 проверочная матрица может иметь вид

= 0 0 0 0 0 0 0 1 1 0

0 0 0 1 1 1 1 0 0 0

0 1 1 0 0 1 1 0 0 0

1 0 1 0 1 0 1 0 1 0

1 1 1 1 1 1 1 1 1 1

Дополнительное проверочное соотношение, вводимое для увеличения минимального расстояния кода Хэмминга до dmin = 4, имеет вид:

= a1 + a2 + a3 + a4 + a5 + a6 + a7 a8 + a9 + a10

Избыточность кода Хэмминга зависит от количества информационных символов при измерении k от 4 до 1013 изменяется от 0,429 до 0,098 при dmin = 3 и от 0,5 до 0,0107 при dmin = 4.

Другие стьтьи в тему

Расчёт трассы прокладки волоконно-оптического кабеля между населёнными пунктами
В современном мире быстрыми темпами наращиваются объёмы информации, соответственно повышаются требования к передающей аппаратуре, поскольку каждые пять-шесть лет объём передаваемой информации увеличивается вдвое. Задача передачи такого количества информации с высокой степенью дост ...

Разработка алгоритмов работы и оценка информационных характеристик системы передачи информации
Как известно, все процессы, которые происходят в окружающем мире, в том числе и на производстве, связаны с информацией - её получением, обработкой, хранением, передачей и отображением. В дисциплине «информационные основы электронной техники» понятие «информация» является одной из осно ...