Коды, обнаруживающие и исправляющие ошибки

Другой класс кодов предназначен для обеспечения безошибочной передачи информации, а не для сокрытия ее содержания. Такие коды называются обнаруживающими и исправляющими ошибки, они являются предметом широкомасштабных математических исследований. Эти коды с самых первых дней существования компьютеров используются для защиты от ошибок в памяти и в данных, записанных на магнитную ленту. Самые первые версии этих кодов, такие, например, как коды Хэмминга, способны обнаружить и исправить единичную ошибку в шестиразрядном символе. В качестве более позднего примера можно привести код, который использовался на космическом корабле "Маринер" для передачи данных с Марса. Созданный с учетом возможного значительного искажения сигнала на его долгом пути к Земле, этот код был способен корректировать до семи ошибок в каждом 32-разрядном "слове". Простым примером кода другого уровня, обнаруживающего, но не исправляющего ошибки, является код ISBN (International Standard Book Number - Международный Стандартный Книжный Номер).Он состоит из десяти знаков (десяти цифр либо девяти цифр с буквой X на конце, которая обозначает число 10), и позволяет осуществить проверку на отсутствие ошибок в номере ISBN. Проверка выполняется следующим образом: вычислим сумму

(первая цифра)1+(вторая цифра)2+(третья цифра)3+...+(десятая цифра)10.

Эти цифры обычно образуют четыре группы, для удобства отделенные друг от друга пробелами или дефисами. Первая группа цифр обозначает языковую группу, вторая указывает на издателя, третья является серийным номером издателя, а последняя группа - это одиночный проверочный символ.

Полученная нами сумма (которая называется контрольной суммой) должна быть кратна 11; если это не так, то номер ISBN содержит ошибку. Например:

номер 1-234-56789-X даёт нам контрольную сумму

(1)1+(2)2+(3) 3+(4) 4+(5) 5+(6) 6+(7) 7+(8) 8+(9) 9+(10) 10,

то есть

1+4+9+16+25+36+49+64+81+100=385=3511,

и следовательно, номер правильный. С другой стороны,

номер 0-987-65432-1 дает контрольную сумму

0+18+24+28+30+30+28+24+18+10=210=1911+1,

и следовательно, должен содержать по крайней мере одну ошибку.

Код ISBN способен обнаружить единичную ошибку, но не способен ее исправить. Если ошибок две или более, проверка может показать, что номер ISBN верен, тогда как на самом деле это может не соответствовать действительности.

Изучение кодов, обнаруживающих и исправляющих ошибки, требует от читателя знания некоторых областей высшей математики, и в этой книге далее не рассматривается. Интересующиеся могут обратиться к работам [1.1],[1.2],[1.3].