The Hamming code is self-checking and self-correcting code. Built in relation to the binary number system. Allows you to fix a single error and find a double one. Written in python 3 using the Numpy library.
In this work, a systematic coding is considered, where a systematic code is a code for which the first k characters of a word correspond to message i.
The pictures below show the following: x1, x2, x3, x4 - message, a1, a2, a3 - control bits.
The input receives 4 bits of the original text, then we multiply this vector of the original message by the generating matrix G. As a result of multiplication, we get the encoded text with three control bits at the end.
We have received a message from the sender on a communication channel in which there may be interference. There is a possibility that the transmitted text was distorted as a result of interference. In order to determine if there is an error, multiply F 'by the matrix H and get the syndrome. Syndrome zero (000) indicates that there are no or no reception errors. Otherwise, a certain configuration of errors corresponds to any syndrome; they are corrected using a matrix of single errors E. As a result, we get the original text.
Коды Хэмминга позволяют исправлять одиночную ошибку в блоке.
Построение кодов Хэмминга основано на принципе проверки на четность числа единичных символов: к последовательности добавляется такой элемент, чтобы число единичных символов в получившейся последовательности было четным.
Составим матрицу преобразования, состоящую из 7 столбцов и 3-х строк. Где количество столбцов - это кол-во битов в закодированном слове, а кол-во строк показывает количество проверочных битов. Хэмминг предложил построить матрицу следующим образом, где каждый столбец проверочной матрицы будет соответствовать битовому представлению номера разряда числа, которому он соответствует. Так выглядит данная матрица:
Эта матрица должна иметь систематический вид, поэтому приведем ее к каноническому виду. Мы переставим в конец столбцы с одной единицей. Тогда матрица H примет вид:
Теперь нам нужно построить порождающую матрицу G из матрицы Н. Проверочная матрица H в каноническом виде имеет вид: H=(An−k,k | En−k), а порождающая матрица G: G = (Ek | A⊤n−k, k). Матрице E принадлежат столбцы с одной единицей => возьмем матрицу А из матрицы H:
Тогда транспонированная матрица А будет иметь вид:
Ek - матрица со столбцами с одной единицей, где k = числу информационных битов:
Теперь составим порождающую матрицу G:
Правило формирования проверочных символов составим по вышеупомянутой матрице:
Теперь можно произвести алгоритм кодирования:
(i1 i2 i3 i4) - информационные биты, то есть, кодируемый текст, а ( r1 r2 r3 ) - контрольные биты. ( i1 i2 i3 i4 r1 r2 r3 ) - кодовое слово.
Транспонированная матрица H будет иметь вид:
Предположим, что на вход декодера для (7,4)-кода Хэмминга поступает кодовое слово
Штрих означает, что любой символ слова может быть искажен помехой в канале связи и возникает ошибка E В декодере в режиме исправления ошибок строится последовательность синдромов:
S = (S1, S2, S3) называется синдромом последовательности. Получение синдрома происходит по такому выражению:
И выглядит следующим образом:
В данном случае синдром S представляет собой сочетание результатов проверки на четность соответствующих символов кодовой группы и характеризует определенную конфигурацию ошибок(вектор ошибок).
Число возможных синдромов определяется выражением 2^3=8
При числе проверочных символов имеется восемь возможных синдромов (2^3 = 8).
Для определения и исправления искаженного разряда можно использовать матрицу E одиночных ошибок (а можно пользоваться и просто матрицей H
Данная матрица одиночных ошибок выглядит так:
При определении синдрома в проверочной матрице находится комбинация синдрома. Искаженный разряд – это разряд в данной строке, в которой стоит «1». Искаженный разряд исправляем посредством сложения строки в матрице ошибок полученной комбинации