ГЛАВА 13. КОДЫ ДЛЯ ПРОВЕРКИ АРИФМЕТИЧЕСКИХ ОПЕРАЦИЙ

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

13.1. Определение понятий "ошибка" и "расстояние"

Будем предполагать, что числа представлены в виде многочлена по степеням основания

где каждое целое число меньше, чем Число записывается в виде Важнейшие частные случаи такого представления чисел — это двоичная система счисления, где десятичная система счисления, где

Пример. Двоичное число

в сумме дает 26. Десятичное число 382 означает

Вес числа определяется как минимальное число слагаемых в представлении этого числа в виде

где целые числа могут быть положительными или отрицательными, но по абсолютной величине должны быть обязательно меньше, чем Расстояние между двумя числами определяется как вес разности Если передано число и получено число и если расстояние между равно то говорят, что появилась -кратная ошибка. Таким образом, появление -кратной ошибки в числе эквивалентно добавлению к числа веса Отметим, что при таком определении расстояние зависит от выбора основания

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

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

Пример. В случае расстояние между числами 171 и 203 равно 1, так как Расстояние между числами 17 и 32 равно В случае десятичной системы счисления расстояние между числами 1296 и 1193 равно 2, так как Расстояние между числами 1296 и 1305 равно 1, несмотря на то что они отличаются в трех знаках, так как

Данное определение расстояния, отличающегося от расстояния Хэмминга, в контексте этой главы математически более удобно. Оно более правильно отражает типы ошибок, которые могут появляться в процессе работы арифметических устройств вычислительных машин. Ясно, что если произошла ошибка в одном знаке, то это одиночная ошибка. Если произошли ошибки в d знаках, то это самое большее d-кратная ошибка. Таким образом, устройство, которое может исправлять все ошибки кратности d или меньше в описанном выше смысле, правильно исправляет все числа, в которых изменилось не более чем d знаков. Однако в сумматоре одна ошкбка в одном разряде из-за переносов может привести при сложении к тому, что ошибки появятся в нескольких разрядах. Ошибка при переносе также может повлиять на несколько разрядов. При введенном нами определении расстояния такие ошибки трактуются тем не менее как одиночные!

Нетрудно построить параллельные двоичные сумматоры для вычислительной машины так, чтобы ошибка в одном разряде сумматора влияла не более чем на один разряд суммы или на один перенос. Код, исправляющий в определенном выше смысле одиночные ошибки, будет исправлять ошибку в любом разряде такого сумматора, несмотря на то, что из-за переноса могут оказаться неверными несколько разрядов результата.