Арифметические коды

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

Рассмотрим арифметические АN-коды. АN-коды пригодны для обнаружения и исправления ошибок при суммировании и записи чисел в случае, если речь идет о конечном множестве целых чисел. Для возможности обнаруживать ошибки нужно, чтобы при проведении операций не все числа были разрешенными. Тогда появление неразрешенного числа и будет признаком наличия ошибки.

Ограничимся рассмотрением случая, когда числа записываются в бинарной форме, что чаще всего бывает в ЭВМ. Если при операциях использовать числа не в естественном виде, а предварительно умноженные на некоторое число А, называемое генератором, причем в качестве генератора взять простое число (делящееся на единицу и на самое себя), в результате суммирования, вычитания или умножения получится число, делящееся на А без остатка. Если же по каким-либо причинам в одном из разрядов числа произойдет ошибка (вместо нуля будет записана единица или наоборот), то такое число не будет делиться на А без остатка. Следовательно, наличие остатка при делении числа на А может быть признаком ошибки в записи числа. Более того, при соблюдении определенных условий ошибки в разных разрядах будут приводить к остаткам разной величины. Тогда по значению остатка можно будет судить однозначно о номере разряда, в котором произошла ошибка, а следовательно, исправлять ее.

Приведем простейшие примеры, по которым можно проследить методику построения AN-кодов.

Пример. Примем значение генератора А=19. Определим значения остатков при наличии одиночной ошибки в разных разрядах. Ошибка в одном и том же разряде в виде перехода 1 в 0 (1→0) и 0 в 1 (0→1) приводят к разным значениям остатков, поэтому учтем оба варианта. Результаты расчетов запишем в таком виде:

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

Начиная с 10-го разряда значения остатков повторяются (например, ошибка вида 0→1 в 10-м разряде дает такой же остаток, как и 1→0 в 1-м разряде).

Анализируя приведенные данные, нетрудно убедиться, что кратные ошибки могут и не быть обнаруженными рассматриваемым кодом. Например, ошибки вида 0→1 в 11-м и 2-м разрядах дадут сумму остатков, равную 19, т.е. А; следовательно, число с ошибками в указанных разрядах делится на А без остатка. Если же исследуемое число имеет количество разрядов не более девяти, то данный код обнаруживает все одиночные и двойные ошибки, поскольку в пределах этих разрядов никакие два остатка не дают сумму, равную А=19.

Таким образом, АN-код с A=19 может применяться для исправления одиночных или для обнаружения двойных ошибок, если проверяемое число АN имеет не более девяти двойных разрядов, а также для обнаружения одиночных ошибок, если число разрядов больше девяти.

Наибольшее число из множества, в котором при А=19 исправляются все одиночные ошибки, равно 111111111, т.е. 511. Следовательно. наибольшее число из множества чисел, подлежащего кодированию

N_max = AN_max : A = 511 : 19 = 26 (целая часть частного).

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

Как уже указывалось, кодирование при использовании AN-кода сводится к умножению исходного числа N на заранее выбранное значение генератора А.

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

При работе с многоразрядными числами приведенный метод декодирования становится технически сложным, так как требуется большой объем памяти для запоминания синдромов и усложняется схема сравнения полученного остатка с таблицей остатков. В настоящее время в этом случав используются более сложные варианты АN-кодов (например, циклические), в которых процедура декодирования и исправления ошибок более проста.

Существуют варианты АN-кодов, исправляющих не только одиночные, но и кратные ошибки.

Литература:

[1] стр. 256-260. [2] стр. 297-306. [3] стр. 152-154.

Контрольные вопросы:

1. Чем определяется количество (массив) чисел, к которым применим конкретный вариант AN-кода, исправляющего одиночные ошибки?

2. Почему в качестве порождающего числа в AN-кодах применяются только просто числа?

3. Может ли AN-код использоваться для проверки правильности деления чисел или записи чисел после деления?

Задачи:

1. Построить таблицу остатков AN-кода по заданному значению порождающего числа А.

2. Задано кодируемое число N и порождающее число А. Необходимо закодировать число N данным кодом AN.

3. Задано значение порождающего числа А. Произвести декодирование числа и записать получившееся число в десятичной форме (N₁₀).

Пример: А=19, AN=1100111. Произвести декодирование.

Ответ: AN=1100011, N₁₀=95.