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

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

Код Хэмминга, обеспечивающий исправление всех однократных ошибок, должен иметь минимальное кодовое расстояние 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.

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

Расчет канала связи
В данной курсовой работе требуется разработать структурную схему системы связи для передачи сигнала, представляющего собой человеческую речь в диапазоне частот 0,3кГц-3,4кГц. Вообще, человеческая речь - это аналоговый сигнал, но для его передачи разрабатываться будет дискретный (цифр ...

Расчет дискретной системы связи, предназначенной для передачи непрерывных сообщений
преобразователь демодулятор кодер информация Рассчитать основные характеристики системы передачи информации, структурная схема которой дана на рисунке 1. Рисунок 1 - Структурная схема системы передачи, где: ИС - источник непрерывного сообщения ; АЦП - аналого - цифровой пр ...

Разделы

Радиоэлектроника и телекоммуникации © 2019 : www.techelements.ru