Арифметические коды
Среди цифровой информации большое место занимает числовая. Результаты измерений физических величин, большая часть экономической и документальной информации представляется в числовой форме. В некоторых случаях для обнаружения и исправления ошибок при передаче и обработке числовой информации могут быть применены общие метода теории кодирования. Однако более эффективным оказывается использование специальных методов кодирования числовой информации. Так, для контроля работа различных устройств ЭВМ и в первую очередь правильности выполнения арифметических операций в процессорах, в особенности процессов суммирования, применяются специальные арифметические коды.
Рассмотрим арифметические АN-коды. АN-коды пригодны для обнаружения и исправления ошибок при суммировании и записи чисел в случае, если речь идет о конечном множестве целых чисел. Для возможности обнаруживать ошибки нужно, чтобы при проведении операций не все числа были разрешенными. Тогда появление неразрешенного числа и будет признаком наличия ошибки.
Ограничимся рассмотрением случая, когда числа записываются в бинарной форме, что чаще всего бывает в ЭВМ. Если при операциях использовать числа не в естественном виде, а предварительно умноженные на некоторое число А, называемое генератором, причем в качестве генератора взять простое число (делящееся на единицу и на самое себя), в результате суммирования, вычитания или умножения получится число, делящееся на А без остатка. Если же по каким-либо причинам в одном из разрядов числа произойдет ошибка (вместо нуля будет записана единица или наоборот), то такое число не будет делиться на А без остатка. Следовательно, наличие остатка при делении числа на А может быть признаком ошибки в записи числа. Более того, при соблюдении определенных условий ошибки в разных разрядах будут приводить к остаткам разной величины. Тогда по значению остатка можно будет судить однозначно о номере разряда, в котором произошла ошибка, а следовательно, исправлять ее.
Приведем простейшие примеры, по которым можно проследить методику построения AN-кодов.
Пример. Примем значение генератора А=19. Определим значения остатков при наличии одиночной ошибки в разных разрядах. Ошибка в одном и том же разряде в виде перехода 1 в 0 (1→0) и 0 в 1 (0→1) приводят к разным значениям остатков, поэтому учтем оба варианта. Результаты расчетов запишем в таком виде:
номер разряда | ||||||||||||
0→1 | ü ý остатки þ | |||||||||||
1→0 |
Полученные результаты позволяют сделать следующие выводы. Вели исследуемое число AN имеет количество разрядов не более девяти, то такой код может обнаруживать и исправлять все одиночные ошибки, так как при ошибках в пределах этих разрядов значения остатков не повторяются.
Начиная с 10-го разряда значения остатков повторяются (например, ошибка вида 0→1 в 10-м разряде дает такой же остаток, как и 1→0 в 1-м разряде).
Анализируя приведенные данные, нетрудно убедиться, что кратные ошибки могут и не быть обнаруженными рассматриваемым кодом. Например, ошибки вида 0→1 в 11-м и 2-м разрядах дадут сумму остатков, равную 19, т.е. А; следовательно, число с ошибками в указанных разрядах делится на А без остатка. Если же исследуемое число имеет количество разрядов не более девяти, то данный код обнаруживает все одиночные и двойные ошибки, поскольку в пределах этих разрядов никакие два остатка не дают сумму, равную А=19.
Таким образом, АN-код с A=19 может применяться для исправления одиночных или для обнаружения двойных ошибок, если проверяемое число АN имеет не более девяти двойных разрядов, а также для обнаружения одиночных ошибок, если число разрядов больше девяти.
Наибольшее число из множества, в котором при А=19 исправляются все одиночные ошибки, равно 111111111, т.е. 511. Следовательно. наибольшее число из множества чисел, подлежащего кодированию
Nmax = ANmax : 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. Задано значение порождающего числа А. Произвести декодирование числа и записать получившееся число в десятичной форме (N10).
Пример: А=19, AN=1100111. Произвести декодирование.
Ответ: AN=1100011, N10=95.
Дата добавления: 2016-06-24; просмотров: 1336;