Обнаружение и исправление ошибок в двоичных комбинациях с помощью кода Хэмминга

Код Хэмминга - блочный, систематический код содержит n = k + r разрядов, из которых k - информационные, а r-контрольные (проверочные), которые находятся на строго определенных позициях. Проверочная матрица кода имеет r строк и 2^r-1 столбцов. Столбцами матрицы кода являются все ненулевые r-разрядные двоичные комбинации. Контрольные разряды вводятся в таблицу кодовых комбинаций таким образом, чтобы, проведя серию проверок, можно было определить искаженную позицию в принятом коде.

Каждый проверочный разряд b_j формируется проверкой на четность определенных информационных разрядов а_i

Результаты каждой проверки записываются в виде комбинации двоичных цифр: при отсутствии ошибки - 0, а при наличии

ее - 1. Таким образом, в результате проверок получается синдром (опознаватель):

S = {S_r, S_r-l, …, S_l}

в виде двоичного r-разрядного числа, десятичный эквивалент которого укажет номер искаженной позиции в кодовой комбинации. Разряды синдрома записываются в порядке очередности проверок справа налево, а номер разряда искаженной позиции в кодовой комбинации читается слева направо. Для обнаружения ошибки в n-разрядной комбинации необходимо сделать г проверок на четность. Общее число комбинаций (позиций), изображаемых r-разрядным контрольным числом, должно охватывать все разряды, т.е. быть не менее n + I. Значит:

2^r >= n + I.

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

r >= log₂(n-1), где r - целое число.

Отсюда число информационных разрядов

k < n – log₂(n+1)

Эти неравенства являются исходными для определения разрядности кодовой комбинации при заданной разрядности k информационных элементов. На основании (6.8.2) н (6,8.4) построена табл. 6.8.1 соответствия между длинами кодовой комбинации n, информационной k и проверочной r частями.

Таблица. 6.8.1.

Представим n-разрядную кодовую комбинацию в общем виде: {a_n, a_n-1, …, a₁}

Количество проверок на четность соответствует числу контрольных разрядов г. При каждой проверке контролируется четность числа единиц в определенных позициях кода. Чтобы обнаружить ошибку, необходимо определить, какие из кодовых комбинаций должны использоваться при каждой проверке. Пусть в результате первой проверки на четность число единиц в проверяемых разрядах оказалось нечетным, то есть один из элементов кодовой комбинации искажен. Таким образом, в младшем разряде синдрома будет единица S₁=1. А наличие единицы в младших разрядах комбинации двоичных чисел свидетельствует о том, что искаженный разряд является нечетным, т.к. единицу в младшем разряде имеют все нечетные числа. Значит, первой проверкой должны охватываться все нечетные разряды принятой комбинации:

Номера проверки

Номера проверяемых разрядов в двоичной комбинации

Из приведенной таблицы следует, что элемент а₁, встречается только в первой проверке, элемент а₂ - во второй, элемент a₃ только в третьей, a₄- только в четвертой и т.д. Следовательно, каждый первый элемент в любой проверке может быть контрольным.