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

Если целые числа (или числители дробей), представленные в СОК с основанием М = р \ ... рт, лежат в интервале (—Л’, /V), где N=MlR=p\ ... Рп, то знак произвольного числа А однозначно определяется позиционной характеристикой jtjv(A) по формуле (1.32)-.

для определения переполнения разрядной сетки требуется выпол­ нить и модульных операций.

Тогда для перевода числа А в СОК требуется выполнить k—1 модульную операцию, вычисляя (А}м по следующей формуле:

позиционной системы. Тогда все коэффициенты а0, ..., а^_і можно найти путем последовательного деления числа {А}м на основа­ ние р.

делить позиционную характеристику в заданной СОК с основанием М. Поэтому для перевода числа {А}лг из СОК в позиционную си­ стему требуется выполнить (k—1 )п модульных операций. Если ос­ нование р не входит в состав данной СОК, то ее придется расши­ рить, добавляя этот модуль.

Рассмотрим теперь правильную дробь, представленную в пози­ ционной системе счисления с основанием р. Обозначим числитель

36

Выразив Ал через символы позиционной системы, получим выражение для определения {Д2} )(:

Поскольку величины вида Njp' являются константами, то для представления дроби в СОК требуется выполнить k—1 модульных

пршем ошибка может достигнуть величины 0,5(р—1)й. В тех слу­ чаях, когда диапазон представления входных величин намного меньше N (а именно такая ситуация характерна для большинства ЦВМ, использующих представление чисел с фиксированной запя­ той), величиной ошибки можно пренебречь.

Если число этих модулей равно п\, то для коррекции перво­ начально полученной дроби потребуется к+п\ модульных операций.

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

няется, то придется расширить исходную систему оснований). Тогда

37

Пример 1.11. Перевести дробь {1, 2, 5, 4}}^5> представленную

втой же СОК, в десятичную систему счисления.

Вданном случае можно не расширять заданную СОК, поскольку

1.8. ОСНОВНЫЕ РЕЗУЛЬТАТЫ

Эта глава, безусловно, не претендует на полный обзор различ­ ных методов выполнения арифметических операций в системе оста­ точных классов. О некоторых направлениях работы, ведущейся в данной области, читатель может получить представление из моно­ графия [3].

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

Основными операциями, выполняемыми в системе остаточных классов (кроме модульных), являются вычисление позиционных ха­ рактеристик и расширение системы оснований. К ним сводятся лю­

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

Время, необходимое для выполнения любых немодульных опе­ раций, пропорционально числу тех модулей, которые определяют знаменатель дроби. Поэтому, переходя к вычислениям с меньшей точностью (к меньшим знаменателям), можно повысить скорость вычислений. Выше эта скорость определялась через число модуль­ ных операций. Однако в тех случаях, когда производительность ЦВМ является менее важной характеристикой, чем количество аппа­ ратуры или надежность, желательно модульные операции разло­ жить на элементарные, к которым отнесем формальное умножение, сложение и вычитание. Очевидно, что некоторые из модульных опе­ раций, рассмотренных выше, эквивалентны нескольким элементар­ ным. Например, для вычисления величины (l/pj)(A —<Zj) требуется одна модульная операция, но две элементарных.

В приводимой ниже табл. 1.1 указывается число модульных операций (МО) и элементарных операций (ЭО), необходимых для выполнения арифметических операций, рассмотренных в предыду­ щих параграфах.

Примечание, k — число разрядов позиционной системы; N — знаменатель дробей; п — число оснований СОК, определяющих зна­ менатель.

Г Л А В А В Т О Р А Я

КОРРЕКТИРУЮЩИЕ КОДЫ В СИСТЕМЕ ОСТАТОЧНЫХ КЛАССОВ

2.1. ОСНОВНЫЕ ПОНЯТИЯ И ОПРЕДЕЛЕНИЯ

Рассмотрим некоторый вектор А = (а,, а2.........ат), компонен­ тами которого являются натуральные числа, удовлетворяющие

•Р = Р\Рг''-Рт-

* Буквой Р обозначим также множество всех векторов подоб­ ного вида, т. е. А еР. Таким образом, в зависимости от контекста под символом Р понимается либо множество векторов А, либо число элементов этого множества.

39