13.6. Раздельные сумматор и проверяющее устройство

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

Рис. 13.2. Система с раздельными сумматором и проверяющим устройством.

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

Рассмотрим систему, изображенную на рис. 13.2. Здесь обозначает проверочный символ, соответствующий числу , а обозначает операцию, совершаемую проверяющим устройством. Требуется, чтобы выход проверяющего устройства совпадал с выходом сумматора, т. е. чтобы

Это накладывает на код ограничения очень специального типа.

Теорема 13.4. Если кисло проверочных символов меньше общего числа элементов в допустимой области целых чисел и проверочный символ удовлетворяет соотношению (13.9), то должен быть вычетом числа Ы, взятого в некоторой закодированной форме, по модулю некоторого основания где число различных проверочных символов, а в уравнении (13.9) обозначает сложение по модулю

Доказательство. Пусть — совокупность всех целых чисел проверочные символы для которых совпадают с проверочным символом для 0, т. е. -совокупность всех целых чисел удовлетворяющих соотношению Доказательство теоремы начнем с доказательства того, что - идеал в кольце целых чисел. По определению, 0 принадлежит совокупности . Заметим, что , и, следовательно, независимо от того, сколько сомножителей стоит слева. Таким образом, если а принадлежит , то а также принадлежит ибо

Кроме того, если а принадлежит совокупности то

и поэтому —а также принадлежит . Итак, — идеал.

Далее заметим, что тогда и только тогла, когда целые числа и лежат в одном и том же классе вычетов по 5. Доказывается это следующим образом:

Если и лежат в одном и том же классе вычетов, то разность принадлежит идеалу Поэтому

С другой стороны, если то

и поэтому разность принадлежит идеалу лежат в одном и том же классе вычетов по 5. Между прочим, это означает, что если два различных целых числа имеют один и тот же проверочный символ, то идеал нетривиален, потому что в этом случае так что идеал, помимо 0, содержит по крайней мере еще один элемент,

В соответствии с утверждением теоремы главный идеал. Это означает, что идеал состоит из всех чисел, делящихся на некоторое целое число Классы вычетов являются классами вычетов по модулю Таким образом, имеется взаимно однозначное соответствие между классами вычетов и проверочными символами. Для каждого рассмотрим в качестве кода для класса вычетов, содержащего т. е. положим Тогда по модулю Таким образом, проверочная операция состоит в сложении по модулю b. Ч. т. д.

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

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

В этом случае число, получаемое прибавлением к

т. е. делится на А и, следовательно, является кодовым числом из AN-кода. Но как число, представленное в записи по основанию число содержит разряды числа в качестве старших разрядов и разряды числа в качестве младших разрядов. Таким образом, расстояние между двумя словами, каждое из которых состоит из числа и его проверочного символа, равно по меньшей мере минимальному расстоянию в AN-коде. В частности, обнаружение одиночной ошибки всегда можно проводить, выбирая в качестве вычет числа по модулю а значения даваемые табл. 13.1, можно использовать для нахождения проверочных символов кодов, исправляющих одиночные ошибки, и кодов, исправляющих одиночные ошибки и обнаруживающих двойные ошибки.

Эти коды принадлежат к классу кодов, выделяемых теоремой 13.4. В качестве кода для числа в этом случае выбирается представление в системе по основанию вычета числа Интересно отметить сходство этого метода кодирования и метода кодирования для циклических кодов, описанного в разд. 8.5.

Замечания

Эта глава основывается на работе Брауна [10], которая в свою очередь основывается на короткой заметке Даймонда [28]. Теорема 13.4 взята из работы [56]. Аналогичные результаты, но для логических, а не для арифметических операций, были получены Элайесом [127], а также Питерсоном и Рабином [60]. Коды, проверочные символы которых образуют класс вычетов, были предложены Гарнером [19]. Представленные в табл. 13.1 коды с расстоянием, равным 3, были найдены Брауном [10], а коды с рассто нием, равным 4, были найдены Джоном Селфриджем (J. Selftidge),

Задача

(см. скан)