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

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

В то же время практически любое изменение числа оснований

Если при вычислении позиционных характеристик используется не функциональное преобразование, а обычные модульные опера­ ции умножения (что позволяет уменьшить аппаратурные затраты), то, очевидно, характеристика */<(Л) требует меньшего объема вы­

числений по сравнению с кк (А).

Помимо рассмотренных выше точных способов вычисления пози­ ционных характеристик, известно большое число приближенных ме­ тодов .[3], некоторые из которых позволяют уменьшить число после­ довательно выполняемых модульных операций, необходимых для вычисления зхкт_і (Л), до величины ]log2/ti[*. Однако в этом слу­ чае резко возрастает требуемое количество аппаратуры, причем чаще всего эту аппаратуру приходится выделять в специальный блок. Пример организации такого блока приводится в работе [3]. Наличие подобной аппаратуры существенно ограничивает возможности ЦВМ, поскольку для защиты машины от ошибок данного блока приходится применять резервирование. Поэтому в настоящей работе, посвящен­ ной вопросам повышения надежности, а не быстродействия ЦВМ, приближенные методы вычисления позиционных характеристик не рассматриваются.

Приведем теперь несколько примеров, иллюстрирующих изло­ женный выше материал.

Пример 1.3. Определим позиционные характеристики числа ■Д={1, 0, 0, 2}jf, представленного в СОК с основаниями рі= 3, Р г= 4, Рз=5, Р4= 7, путем перевода этого числа в ОПС.

Из приложения для оснований заданной СОК найдем константы, соответствующие обратным мультипликативным величинам:

* Под величиной ]х[ понимается ближайшее целое число, боль­ шее или равное х, т. е. дробное число х, округленное в большую сторону.

20

из диапазона [240, 420] — отрицательными. Тогда знак числа А мож­ но определить по старшему разряду двоичного представления вели­

ются взаимно простыми, то дальше определение позиционных харак­ теристик числа А осуществляется так же, как и в предыдущем примере.

1.4. РАСШИРЕНИЕ СИСТЕМЫ ОСНОВАНИИ

При вычислениях в системе остаточных' классов довольно часто складывается такая ситуация, когда остатки, соответствующие неко­ торым основаниям СОК, становятся неопределенными. Однако ос­ тальные остатки однозначно определяют число. С таким положениеммы уже сталкивались в § 1.2 при модульном делении чисел, пред­

21

ставленных в СОК и в § 1.3 при вычислении позиционных' характе­ ристик n Kj(A). Поэтому одной из основных немодульных операций

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

Пусть число А однозначно представлено в СОК с основаниями

но, то для определения величин ап+г.......ат удобнее воспользо­ ваться рекуррентным соотношением

чины которых зависят от порядка следования модулей, существенно ограничивает возможности изменения числа оснований и их взаим­

22

Используя рекуррентную формулу (1.13) для вычисления *лг(2 ), получим выражения, определяющие любой из остатков ап+і при і = 1, 2, ..., г:

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

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

жения найдем обратные мультипликативные величины;

I ѵ*|. = 1; 1'M s = 4; I V. la =-2.

Далее по формулам (1.14) и (1.27) вычислим

сс° = а, = 3; а“ = 0; а° = | 3 |, = 0;

= К — 3) -1 |з --= 0;

Рі

23

системе остаточных классов. Для этого сначала изменим индексы

Следовательно, {яд-з (Д)}^ = {2,0}12. Переходя снова к исходной

СОК, получим {**, (Д)}л, = {2, 0,3, 1}42„.

1.5. УМНОЖЕНИЕ ДРОБНЫХ ЧИСЕЛ

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

24

Для того чтобы эти дроби были правильными при любом А должно выполняться условие: | Д | < N. Если числители А могут изменяться в интервале ( — Lu І 2), то условие правильности дроби примет вид: N шах (£„ А2).

Чаще всего диапазоны изменения положительных и отрицатель­ ных чисел, представленных в ЦВМ, принимаются одинаковыми. По­ этому примем N = L ^ = L 2.

Но для однозначного представления числителя А в СОК интер­

Рассмотрим произведение двух дробей AjN и B/N, пусть А и В положительны:

C_j _ A _ J 3 ____ 1 ( Л В \ N = N N - N \ N .)■

Очевидно, что С должно быть целым положительным числом. Поэто­ му в тех случаях, когда произведение AB не кратно N, примем:

дулей СОК не является четным. В этом случае каждому числу, пред­ ставленному в СОК, соответствует некоторая правильная дробь. Если же использовать больший по величине модуль рп+1 (или в об­ щем случае группу модулей р„ +1, .. . , рт), то среди чисел, пред­ ставленных в СОК, окажутся и неправильные дроби с ненулевыми целыми частями. За счет увеличения М при постоянном N появляет­ ся возможность легко обнаруживать переполнения при сложениях и вычитаниях, корректировать ошибки округления для некоторых способов умножения дробей и, как будет показано в гл. 2, обнару­ живать и исправлять ошибки, возникающие в ходе вычислений.

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

Если заданы два положительных числа {А}.^ и то их

произведение в соответствии с формулой (1.29) запишется в сле­ дующей форме:

= {"* ІАЩ%-

25

Но прежде чем вычислять позиционную характеристику, необходимо

операцию умножения при условии, что M~>N2.

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

Первый метод, предложенный А. Свободой [20], заключается в том, что исходная СОК с основанием М расширяется путем добав­

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

последней операции расширения потребуется также не более п

последовательно. 3/t+l при параллельном выполнении этих операций и 2л + 1, если исходная СОК позволяет сразу получить произведение

{ДД}м.

Произведение С, вычисленное по формуле (1.29), является за­ ниженным, так как округление всегда производится в меньшую сто­ рону. Для того чтобы погрешности обоих знаков были равновероят­

ществляется одинаково при любых знаках сомножителей. К сожале­

26

ставленным число {Л4 — | А |]ЛІ,, отнюдь не равное { — | Л |}Л[„ так как I М \м , ф 0. Поэтому результат расширения следует скоррек­

тировать, вычитая из него основание М.

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

лена правильная дробь {/1}^, то в расширении участвуют лишь

модули, соответствующие знаменателю N. Поэтому вновь получен­ ные при расширении остатки соответствуют величине {ЛГ —

Следует отметить, что знак числа А однозначно определяется его позиционной характеристикой. В частности, если А является

числителем правильной дроби {Л}^, то

что М' > 2N 2. Причем знак произведения можно определять по формуле (1.32) лишь в том случае, если Я' > N.

Нетрудно убедиться в том, что количество модульных операций, необходимых для расширения системы оснований при использовании чисел с произвольным знаком, увеличивается на единицу по сравне­ нию с вариантом, рассмотренным в § 1.4.

IПоэтому для получения округленного произведения двух дробей

спроизвольными знаками требуется выполнить:

в результате чего по меньшей мере вдвое увеличиваются аппаратур­ ные затраты иа создание арифметического устройства.

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

27

чае, сначала предположим, что оба сомножителя положительны. Представим каждый из сомножителей в виде пары чисел:

представление этих произведений в заданной СОК.

Для вычисления произведения положительных дробей в соответ­

ются позиционные характеристики в сокращенных СОК с основания­ ми M/Ni н MlNs соответственно, а далее эти системы расширяются до исходной. Число модульных операций, используемых в каждом

и{Л2Д,}лі в соответствии с формулой (1.34) определяются позицион­

го произведения почти на три единицы младшего разряда из-за оши­ бок, возникающих при округлении. Однако, если М > 3 ЛГ, то вели­ чину ошибки Д можно определить из выражения {Д}лі =*

= {лдг (АВ — CW)}AT•

Произведения {АВ}М и {СЫ}щ вычисляются формально, так как нас интересуют не сами эти величины, а их разность, которая может быть однозначно представлена в заданной СОК.

Для получения симметричной погрешности округления к произ­ ведению АВ следует прибавить величину [N/2].

Если положить Рп+і^4, то для вычисления ошибки требуется п-\-2 модульных операции, а в целом умножение двух положитель­

28

ройства, либо Зл+7 операциям, если использовать два преобразова­ теля из СОК в ОПС.

Если перемножаемые дроби имеют произвольные знаки, то при расширении системы оснований можно воспользоваться формулами, аналогичными (1.31) и (1.32). Правда, вторая формула может ис­ пользоваться для определения знака лишь у чисел, меньших чем N. В то же время произведение ЛіВ2 может превышать знаменатель дроби. Однако нетрудно убедиться в том, что Д2 и Во всегда поло­ жительны, и поэтому знак А (или А і) совпадает со знаком произве­ дения А\Вг. Что касается ошибки Д, то она так же всегда положи­ тельная независимо от знаков сомножителей А и В, ибо округление при вычислении позиционных характеристик осуществляется в мень­ шую сторону.

Число модульных операций, использующихся при вычислении произведения двух дробей с произвольными знаками, не превышает 5(п+3) либо 3(л+3) при наличии двух преобразователей из СОК

вОПС.

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

Добавив модуль Ръ— Ъ и р = П , получим новую СОК с основанием Л4'=4620, причем R '= 5 5 > N .

Представим числители дробей в этой СОК, используя формулы

{ * N (AB)}N = { 1,6}21;

{лдг (AB)}jtf, — {1, 6, 0, 2, 3).4бао.

Переходя снова к исходной СОК путем исключения цифр, соот-

29