Самокорректирующиеся коды

Предисловие

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

Самокорректирующиеся коды

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

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

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

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

1°. Передаваемая информация – длинная последовательность нулей и единиц – разбивается на блоки по символов.

2°. Каждый блок кодируется двоичным словом из символов, где .

3°. Коды передаются по каналу связи и принимаются на другом его конце с возможными искажениями.

4°. Искаженные коды подвергаются процедуре декодирования, в результате которой восстанавливается первоначальный блок из символов.

Первым примером такой схемы передачи информации был 7-разрядный код Хемминга, исправляющий единичные ошибки.

Передаваемая информация разбивается на блоки по 4 символа (полубайты), блоки кодируются словами из 7 символов:

.

Разряды кодового слова определяются так. Полубайт записывается в разряды 3, 5, 6, 7 (информационные):

.

Остальные разряды кодового слова (контрольные) определяют так, чтобы выполнялись соотношения:

,

,

.

Другими словами, количество единиц в группах разрядов

.

должно быть четным. После приема слова с возможными искажениями подсчитываются суммы

,

,

.

Если ошибок не было, все три суммы равны нулю. Если был искажен один разряд, то – его номер.