САМОКОРРЕКТИРУЮЩИЙСЯ КОД ДЛЯ КАНАЛЬНОГО КОДИРОВАНИЯ ИНФОРМАЦИИ

SELF-CORRECTING CODE FOR CHANNEL INFORMATION CODING

Maxim Kravchina

student, department of hardware and software systems, Don State Technical University,

Russia, Rostov-on-Don

Alexandra Kravchina

student, department of hardware and software systems, Don State Technical University,

Russia, Rostov-on-Don

АННОТАЦИЯ

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

ABSTRACT

The paper uses the detecting capabilities of the Hamming code to prevent the appearance of errors in the information bits, which is relevant with the use of radio reception of the message. At the same time, they must be equipped with the control and monitoring of logical devices.

Ключевые слова: самокорректирующийся код, код Хэмминга, информационные разряды.

Keywords: self-correcting code, Hamming code, information discharges.

Коды, в которых возможно автоматическое исправление ошибок, называются кодами самокоррекции. Для создания самокорректирующегося кода, предназначенного для исправления единичных ошибок, одного контрольного бита недостаточно [1]. Как видно из нижеприведенного, количество контрольных битов k должно быть выбрано таким, чтобы выполнялось неравенство или, где m - количество основных двоичных битов кодового слова. Минимальные значения k для заданных значений m, найденные в соответствии с этим неравенством, приведены в таблице 1.

Таблица 1

Минимальное значение k для заданных m

Имея m+k разрядов, самокорректирующийся код можно построить следующим образом. Присвоим каждому из разрядов свой номер – от 1 до m+k; запишем эти номера в двоичной системе счисления. Поскольку 2k > m + k , каждый номер можно представить, очевидно, k-разрядным двоичным числом.

Предположим далее, что все биты кода m + k разделены на группы управления, которые частично перекрываются, и что биты в двоичном представлении номера битов указывают на его принадлежность к определенным группам управления. Например: бит номер 5 относится к 1-й и 3-ей группам управления, потому что в двоичном представлении его числа 510 = ... 0001012 - 1-я и 3-я цифры содержат единицы.

Среди m+k разрядов кода при этом имеется k разрядов, каждый из которых принадлежит только к одной контрольной группе:

- разряд № 1: 110 = …0000012 принадлежит только к 1-й контрольной группе;

- разряд № 2: 210 = …0000102 принадлежит только к 2-й контрольной группе;

- разряд № 4: 410 = …0001002 принадлежит только к 3-й контрольной группе;

- разряд № 2k − 1 принадлежит только к k-й контрольной группе [11].

Каждая из k контрольных групп имеет бит управления. Мы помещаем такое число (0 или 1) в каждую контрольную цифру, чтобы общее количество единиц в вашей контрольной группе было четным. Например, довольно распространен код Хемминга с m = 7 и k = 4. Исходное слово (кодовое слово без контрольных битов) - 01101012. Обозначим Pi - контрольный бит №i; Di - информационный бит номер i, где i = 1,2,3,4. Показано в таблице 2.

Таблица 2

Перекрещивание контрольных групп (Первая группа контролирует разряды № 3,7,5 исходного кода, вторая 3,7,6…)

Интересно посмотреть, как перекрываются контрольные группы в данном случае. Первая группа контролирует разряды № 3,5,7,9,11 исходного кода, вторая — 3,6,7,10,11 (№ группы = № контрольного разряда). Очевидно, что они частично перекрываются.

Теперь предположим, например, что при передаче этого кодового слова 10001100101 произошла ошибка в 11-м бите, для которого было получено новое кодовое слово 10001100100. 1-я, 2-я и 4-я контрольная группа, а также 3-я контрольная группа. Это указывает, во-первых, на наличие ошибки и, во-вторых, это означает, что номер ошибочно принятого бита в двоичном представлении содержит единицу на первом, втором и четвертом месте и ноль на третьем месте, потому что есть только один ошибка и 3 - моя контрольная сумма оказалась верной. Пример есть в таблице 3.

Таблица 3

Ошибки прошли в 3-м и 7-м разрядах исходного кода (1 и 2 контрольные биты даже не замечают ошибки)

Из таблицы следует, что ошибка произошла в 11-м разряде и её можно исправить. Построенный код, разумеется, не рассчитан на возможность одновременной ошибки в двух разрядах [2].

Список литературы:

1. Долгов, А.И. О применимости математического масштабирования и нормирования при решении прикладных задач / А.И. Долгов, Д.В. Маршаков // Вестник Донского государственного технического университета. –2018. – Т. 18. – № 4. – С. 92-101.
2. Ефанов, Д. В. Предельные свойства кода Хэмминга в схемах функционального диагностирования / Д. В. Ефанов // Информатика и системы управления – 2011. – №3(29). – С. 70-79.