Построение групповых кодов, исправляющих одиночные ошибки

Вырабатываемое источником информации единичное сообщение формируется в безызбыточную комбинацию, причем все комбинации должны иметь одинаковую длительность (разрядность n).

Рассмотрим пример кодирования и исправления однократных ошибок групповым кодом Хемминга для n = 4 разрядных информационных блоков. Из условия (3.3.) следует, что m = 7, код (7,4) имеет семь разрядов, из них 4 информационных.

Построим "матрицу ошибок", т.е. переберем все возможные однократные ошибки (место ошибки определим вектором с одной единицей):

.             (3.4)

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

В качестве примера закодируем информационный блок 1010.

В выбранном 7 элементном блоке 1, 2, 4 разряды заняты под проверочные, а в 3, 5, 6, 7 разрядах запишем передаваемую информацию.

Найдем проверочные символы из уравнения (3.5,б)

а₁ = а₃ Å а₅ Å а₇ = 0 Å 1 Å1 = 0           а₁ = 0

а₂ = а₃ Å а₆ Å а₇ = 0 Å 0 Å 1 = 1          а₂ = 1

а₄ = а₅ Å а₆ Å а₇ = 1 Å 0 Å 1 = 0          а₄ = 0

Теперь запишем закодированный блок

число 1010010.

Допустим, что при приеме этого блока произошла ошибка в третьем разряде (т.е. мы приняли блок вида 1010110), тогда проверочные равенства (3.5,а) в приемнике дадут синдром ошибки:

а₁ Å а₃ Å а₅ Å а₇ = 0 Å 1 Å 1 Å 1 = 1

а₂ Å а₃ Å а₆ Å а₇ = 1 Å 1 Å 0 Å 1 = 1

а₄ Å а₅ Å а₆ Å а₇ = 0 Å 1 Å 0 Å 1 = 0.

Полученный синдром 011 указывает, что ошибка произошла в третьем разряде, и, значит, третий разряд надо исправить (просто инвертировать на обратный знак). Так можно обнаружить и исправить любую однократную ошибку (в любом разряде).

Мажоритарное декодирование групповых кодов

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

Пример. Рассмотрим код (7,4), построенный в подразделе 3.3.3. На базе системы проверочных равенств для каждого информационного символа составляем свою систему проверочных равенств (для а₇ первые три уравнения получаем из уравнения (3.5,а), четвертое получаем суммирование первых трех уравнений, пятое записываем, исходя из требования нечетного количества уравнений; для а₆ первое и второе уравнения получаем из уравнения (3.5,а), третье уравнение получаем из нового первого уравнения путем замены члена а₇ первым уравнением из столбца для а₇ и сокращением двойных элементов, четвертое уравнение получаем аналогично третьему заменой во втором новом уравнении столбца а₆ элемента а₇ из первого уравнения столбца а₇ и т.д.):

и т.д.

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

В некоторых случаях мажоритарное декодирование дает возможность упростить схему декодера и уменьшить время декодирования, но мажоритарное декодирование применимо не для всех вариантов групповых кодов.