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

1.2. МОДУЛЬНЫЕ ОПЕРАЦИИ

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

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

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

Пусть один из сомножителей (А) отрицателен, а другой (В) — положителен. Тогда

Положим теперь, что оба сомножителя являются отрицательными;

~ { М * - М . \ А \ - М . \ В \ + \А 1 .\В \}м = {\А 1 - \В ]}м .

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

Равенство (1.2) справедливо лишь в том случае, если результат операции не выходит за пределы интервала определения.

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

К модульным операциям можно отнести и деление целых чисел

9

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

Пусть для какого-либо модуля Рі остаток ß,- равен нулю. Это означает, что р; является делителем числа В. Но поскольку число А по условию делится на В без остатка, то основание 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