Файл: Торгашев В.А. Система остаточных классов и надежность ЦВМ.pdf

Теорема І.І. Если для любого целого числа Д = {а„...

Поэтому число |С — В\м должно делиться на рі, т. е |С — В\м>Рі- Если С < В, то С < ІК. Но поскольку мы приняли, что

С >\1К, то

СВ + Р і ^- IK + Pi-

Рассмотрим теперь числа А — Рі и С — рі. Для этих чисел позиционные характеристики равны, но

Следовательно, теорема доказана.

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

13

Из теоремы 1.1 следует, что для чисел, представленных в СОК со взаимно простыми основаниями ph ..., рт, величина области опре­ деления любой позиционной характеристики Як (-4) = я к (аі, d2, .... а™)

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

Следствие 1.1.1.

Величина области определения любой позиционной характери­

d xd\

что и требовалось доказать.

В качестве модуля Pt можно выбрать любое основание СОК-

общих делителей у оснований имеет тот же порядок). Поскольку обычно величина М имеет порядок ІО6— ІО10, то табличный метод реализации произвольной функции в данном случае, естественно, отпадает.

Поэтому попытаемся представить позиционную характеристику числа Як (А) при помощи набора функций, зависящих не более чем от двух переменных (остатков).

бы одним аргументом. Связь между этими функциями и позицион­ ными характеристиками чисел можно установить при помощи тео­ ремы 1.2.

Теорема 1.2.

Для системы остаточных классов со взаимно простыми основа­ ниями pt, ..., pm между множествами значений позиционной харак­

14

стене в том и только том случае, если К является делителем произ­ вольного основания рі заданной СОК, а а,- служит аргументом всех функций фі..... ф®.

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

Легко убедиться в том, что число различных комбинаций аргу­ ментов, соответствующих каждому значению некоторой функции фі(а,', ctj), должно быть кратно К■ Но поскольку величина области определения этой фунции равна pfPj, то число К будет делителем данного произведения. Аналогичное утверждение справедливо и для остальных функций заданной системы. Следовательно, величи­ ны областей определения всех функций ср,,..., ф„ должны иметь общий делитель, равный К.

При взаимно простых модулях СОК К может быть делителем только одного из двух оснований, соответствующих аргументам функции ф;(аг, аД, например модуля р,-. Но поскольку ни одно из других оснований СОК не содержит делителей модуля р,-, то в каждое из произведений, соответствующих областям определения функций фі, .... фз, должен входить данный модуль, т. е. а,- явля­ ется аргументом в с е х функций данной системы. Что и требова­ лось’доказать.

Из теоремы 1.1 следует, что в состав аргументов системы функ­ ций фі...... фз должны входить все остатки см, ..., ат■ Но каждая из функций должна отличаться хотя бы одним аргументом. Поэтому число этих функций либо равно числу аргументов, либо на единицу меньше.

Пусть р і= р і. Тогда рассматриваемые функции можно пред­ ставить в следующем виде:

?і («1. “0. Ts (“г- “і). • • •- <?т(%> “і)-

Если рі= К , то первая функция может принимать только одно значение, т. е. является константой, а области изменения каждой из остальных функций фг.....фт соответственно равны р2, ..., р,„; таким образом, этим функциям можно сопоставить определенные модуль­ ные операции, а каждому значению позиционной характеристики — некоторое число, представленное в системе остаточных классов с ос­ нованиями Рг,..., рт :

ментов той же системы функций. Применив данное преобразование

где у, 1 = 1, 2, . . . , т и а° = щ. Тогда позиционную характери-

15

стику ъ'к (Л) можно представить в следующей форме:

Итак, из теоремы 1.2 следует, что число последовательно выпол­ няемых бинарных модульных операций при вычислении позицион­ ной характеристики Па'(Л) соответствует числу модулей СОК, яв­ ляющихся делителями К, и в большинстве практических случаев

равно т — 1.

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

ными в СОК и ОПС, существует взаимно однозначное соответст­ вие, и определение некоторой позиционной характеристики Як (А) можно свести к вычислению значений старших разрядов числа, представленного в ОПС.

Чаще всего в качестве позиционной характеристики числа А ис­ пользуется одна из величин: [A/К] или [А/К] К. Для вычисления по­ зиционной характеристики первого типа используется метод, сводя­ щийся к переводу числа из СОК в ОПС [9], а для определения ха­ рактеристики второго типа применяется метод, называемый «нулеви-

16