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

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

ема решаемых задач, которые обеспечивает система остаточных классов.

3.2. СХЕМЫ СЛОЖЕНИЯ, ВЫЧИТАНИЯ И УМНОЖЕНИЯ ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ

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

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

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

При дальнейшем изложении будем считать, что каждый из остатков cti........ а„, любого числа {А}м представлен в двоичной системе счисления независимо от способов выполнения модульных операций, поскольку память вычислительной машины, как правило, строится на элементах с двумя устойчивыми состояниями.

Если 2‘~] < р ^ 2 1, то сумму [ct+ßlji можно вычислять при по­

величиной основания и корректировать данный результат путем

вычитания модуля, если окажется, что a + ß ^ p .

Количество оборудования, реализующего указанные дополни­ тельные операции, существенно зависит от типа используемъіх эле­ ментов, способа построения двоичного сумматора (накапливающе­

82

Обратный код числа ß соответствует величине ß ==2'—I—ß. Поэтому

I “ — ßlp = I“ + P - (2' - 1 - - P)\„ - H’a + J + p + 1|2,| p.

Итак, при выполнении операции вычитания требуется либо при помощи специальной схемы вычислять разность д -ß, либо после сложения уменьшаемого с обратным кодом вычитаемого осуще­ ствлять коррекцию результата. В первом случае возрастают аппа­ ратурные затраты, а во втором— время выполнения операции.

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

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

I a - ß — (2' — р) |2, = I a — р + р 12, .

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

Для вычисления произведения |a ß |P также можно воспользо­ ваться схемой сложения по модулю р, если остатки а и ß пере­ множать как обычные двоичные числа при помощи итеративной процедуры:

влево числу у(/—1). Если символ, соответствующий старшему раз­ ряду этого числа, равен единице, то 2у(/— 1 )^ 2 ' и, следовательно, после сдвига необходимо выполнить такую же коррекцию резуль­ тата, как и при сложении. В противном случае сдвиг суммы у (/—1) выполняется без коррекции.

Рассмотренный способ вычисления произведения является до­ вольно медленным. Значительно быстрее можно выполнить умно­ жение по модулю р, если вместо остатков использовать их индексы. Для пояснения метода приведем некоторые сведения из теории чисел.

Пусть числа а и а взаимно просты с модулем р. Тогда вели­ чина / называется индексом числа а по модулю р и основанию а, если а и а1 сравнимы по модулю р, т. е. / = inda а, если a l= а mod р. В этом случае величину а можно назвать антииндексом числа /,

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

84

Предположим, что р является простым числом. Тогда справед­ ливы следующие соотношения:

если а н р mod р, то ind а = ind ß mod (р — 1), и наоборот:

пп

ind (a/ß) = (ind a — ind ß) mod (p — 1); ind 1 = 0 ;

ind 0 не существует.

Кроме простых модулей, индексы существуют для любых целых

V (aß) = [Ü (a) -f V (ß)] mod 2г_2-

Если обозначить (и, ѵ) = ind а, то

пп

85

по модулю р. Если сумма индексов меньше, чем 2', то результат операции умножения определяется непосредственно из таблицы ан-

ной сумме прибавить величину 2'—р+1.

Применение индексов для выполнения операции умножения на­ кладывает определенные ограничения на выбор оснований, входя­ щих в СОК, поскольку в качестве модулей могут использоваться только простые числа. Что касается модулей вида /У, 2р1 или 2', то из-за отсутствия индексов для чисел, имеющих общие дели­

зующей операцию * по модулю р, условимся понимать комбина­ ционную схему, которая каждой паве операндов а и ß ставит в со­ ответствие величину |а* Р |р .

Возможны различные способы построения подобных таблиц, но чаще всего для этих целей используется схема, приведенная на рис. 3.2. Схема состоит из двухступенчатых дешифратора и шифра­ тора. Дешифраторы первой ступени ДШ 1-1 н ДШ 1-2 преобразуют операнды а и ß из двоичной формы в унитарную. Дешифратор ДШ2 и шифратор Ш1 обеспечивают вычисление результата |oH}tß|p в унитарном коде, а шифратор Ш2 переводит полученный резуль­ тат в двоичную форму.

Будем считать, что дешифраторы состоят из логических эле­ ментов И, а шифраторы —• из элементов ИЛИ, причем слож­ ность этих элементов оценивается числом их входов. Тогда слож­ ность комбинационной схемы, которая предназначена для реализа­ ции таблицы, приведенной на рис. 3.2, можно оценить следующим образом:

Lp (Т) = 2L (ДШ1) + L (ДШ2) + L (Ш1) + L (Ш2) =

= 2рі + 2р* + р* + Ip ß ,

где L — сложность комбинационных схем; I— число двоичных раз­ рядов, необходимых для представления модуля.

86