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

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

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

Предположим, что код состоит из отдельных блоков, и в каждом блоке содержится k двоичных символов: a₁, a₂,..., a_k.

Для работы в канале с переспросом этот код дополняется одним символом - четностью b, выражаемым через символ блока так:

При этом новый блок записывается так: a₁, a₂,..., a_k,b.

Контроль по четности позволяет обнаружить нечетное число ошибок в блоке. Для ответа на вопрос, в каком разряде расположена ошибка, необходимо остановить передачу сообщения и сделать переспрос. Однако, обнаружить и исправить ошибку можно без операции переспроса. Дня создания кода с возможностью исправления без переспроса по каналу обрат

связи рассмотрим, например, блок с к = 12: a₁, a₂,..., a₁₂

Расположим этот основной блок в виде матрицы:

Теперь определим четность всех строк и всех столбцов этой матрицы, приписав по ее краям символы четности b:

Считывая последовательно все строки образованной матрицы, можно получить блок с избыточностью: a1a2a3a4b1a5a6a7a8b2a9a10a11a12b3b4b5b6b7. Например, блок 101101000111 можно записать в матричной форме так:

Эту матрицу можно дополнить символами по четности. Полученный блок с избыточностью будет следующим: 10 1110 1 00101 1 1 1 100 0.

Допустим теперь, что ошибка появилась в информационном (основном) блоке a₁, a₂,..., a₁₂. Тогда изменение одного двоичного символа на обратный приводит к нарушению четности в строке и столбце, соответствующих этому символу. По этому нарушению легко восстановить правильное значение символа. Для этого достаточно символ, находящийся на пересечении строки и столбца с нарушением четности, изменить на обратный.

Если ошибка окажется в символах контроля четности, то нарушится лишь одно условие четности. Для построения кода с исправлением двух, трех и более ошибок необходимо сделать дополнительную проверку на четность, например, по диагоналям. Вводя такую проверку на четность, можно построить самокорректирующийся код с любой надежностью.