книги из ГПНТБ / Торгашев В.А. Система остаточных классов и надежность ЦВМ

Таким образом, деление без остатка двух чисел в СОК осуще­ ствляется путем модульного умножения делимого на мультиплика­ тивную обратную величину делителя.

Пусть для какого-либо модуля Рі остаток ß,- равен нулю. Это означает, что р; является делителем числа В. Но поскольку число А по условию делится на В без остатка, то основание pt должно быть также делителем А. Следовательно, а,- = 0 и соответствующая циф­ ра частного является неопределенной:

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

А = 3 и В = 5, представленных в системе остаточных классов с осно­ ваниями рI = 4 , Рі = 5, рз = 6, и, кроме того, вычислим частные от деления произведения этих чисел на каждый из сомножителей:

10

C4< ( C 3/5)< (L ,/5) = 6, т о остатки по основаниям р , и рг одно­ значно определяют частное и, следовательно, неопределенную циф-

ют однозначно определить величину | 3 (в данном примере они одно­ значно определяют всю цифру ] 3/316) | 3= 2.

Итак, {С6}дг = {0}м = {I, 0, 5}ео.

Ниже будут приведены способы вычисления неопределенной цифры частного по значениям других остатков.

1.3. ОПРЕДЕЛЕНИЕ ПОЗИЦИОННЫХ ХАРАКТЕРИСТИК ЧИСЕЛ, ПРЕДСТАВЛЕННЫХ В СОК

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

* Такие системы счисления обычно называются обобщенными позиционными системами (ОПС), полиадическими или же системами счисления со смешанными основаниями (ССО). Обычную пози­ ционную систему с основанием р можно рассматривать как частный случай ОПС, у которой все основания равны р.

11

в ЦВМ достаточно знать позиционную характеристику числа, соот­ ветствующую лишь его старшему разряду, т. е. тЦЛ) = f (аШі).

Обозначим произведение оснований р ѵ . . р 1 ѵ соответствую­

щих разрядам, не участвующим в определении позиционной ха­ рактеристики числа -.(/1), через К. Тогда

Для чисел, представленных в СОК с основаниями рі, .... pm и общим основанием М, позиционная характеристика Як(Л) являет­

кает вопрос, нельзя ли при вычислении позиционной характеристики использовать не все, а лишь н е к о т о р ы е из остатков аі, ..., am; либо за счет преобразования этих остатков уменьшить область опре­ деления Як? Однако приводимая ниже теорема 1.1 (являющаяся модификацией теоремы кодирования Сабо [21]) показывает, что практически любые независимые преобразования отдельных перемен­ ных сц, ..., <х,п, в результате которых можно было бы уменьшить область определения позиционной характеристики, приводят к нару­ шениям однозначного соответствия между функциями [A/К] и ха­ рактеристиками Яа 04). Как будет показано ниже, если определе­ ние указанных характеристик осуществляется при помощи произ­

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

где dij — наибольший общий делитель для оснований рі и pj.

Доказательство. Любое число А можно выразить при помощи следующих равенств:

А = kipi-\- ai = kj pj + a-j.

Определим остаток от деления числа А на модуль rf/y, учитывая, что \Pi\dl j =‘ \P )\dl) = ° -

Тогда \ А \ а = \a.i\dij = \ aj \d u или l “i — aj\d lj ==0’ что

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

12

I

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

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

С >\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

систему при взаимно непростых основаниях р„ . . . , р т. Здесь уже

нельзя просто заменить деление на какое-либо основание рі умно­

жением на обратную мультипликативную величину | 1 I рі 1jпри наличии общего делителя у оснований рі и pj, так как сравнение

хрі = 1 mod p j в этом случае не имеет решения.

Алгоритм перевода при этом резко усложняется и вряд ли це­ лесообразно приводить его здесь. Поэтому в дальнейшем рассмат­ риваются лишь такие СОКН, которым можно поставить в соответст­ вие МОПС с попарно простыми основаниями.

Рассмотрим теперь метод вычисления характеристики [А/К]К:

Из этой формулы можно выразить величину a.jKj—, через пози­ ционную характеристику ~'к

(Л)aj—l

В отличие от первого метода здесь можно определить значе­ ние о/ и при 1-^.j, а именно aj = 0. Таким образом, позицион­

18