Устройство для деления

 

Изобретение относится к вычислительной технике. Цель изобретения - повышение достоверности вычисления результата. Сущность изобретения заключается в использовании рекурсивного принципа вычисления значений арифметической функции деления. Устройство для деления содержит две схемы сравнения 1-2, итерационные блоки , в состав которых входят схемы сравнения 4;, элементы И 5,--6; и реверсивные счетчики 7; , коммутаторы 11-13, 16, накапливающие сумматоры 14-15, 17 сумматор 18, входы .пуска 9, делимого 19, делителя 20, логического нуля 21, кбнстант 23-24. Устройство обеспечивает высокое быстродействие при отработке -малых приращений входных данных. 1 з.п., 3 ил., 1 табл. в (/) С у I

СОЮЗ СОВЕТСНИХ

СОЦИАЛ ИСТИЧЕСНИХ

РЕСПУБЛИН (5D 4 G 06 F 7/52

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ABTOPCHOMV СВИДЕТЕЛЬСТВУ

1 3 (°

ГОСУДАРСТВЕННЫЙ НОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИЙ (21) 3995702/24-24 (22) 24.12.85 (46) 23.09.87. Бюл. N - 35 (71) Ленинградский электротехнический институт им. В.И.Ульянова(Ленина) (72) А.А.Валов, Л.M.Âèòêèí и И.В.Герасимов (53) 681.325(088.8) (56) Авторское свидетельство СССР

У 1013948, кл. С 06 F 7/52, 1981.

Авторское свидетельство СССР

Ф 781813, кл. С 06 F 7/52, 1978. (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ (57) Изобретение относится к вычислительной технике. Цель изобретения— повышение достоверности вычисления зи идам. а1 результата. Сущность изобретения заключается в использовании рекурсивного принципа вычисления значений арифметической функции деления. Устройство для деления содержит две схемы сравнения 1-2, итерационные блоки 3, -3, в состав которых входят схемы сравнения 4;, элементы И 5;-6; и реверсивные счетчики 7<, коммутаторы 11-13, 16, накапливающие сумматоры 14-15, 17 сумматор 18, входы .пуска 9, делимого 19, делителя 20, логического нуля 21, констант 23-24.

Устройство обеспечивает высокое быстродействие при отработке малых приращений входных данных. 1 з.п., 3 ил»

1 табл.

Ю Ф

1 133955

Изобретение относится к вычислительной технике и может быть испольz< + 1

x;+h у;

+ 2

К; >

i+1

1Ф i

У}+

}1;

1+<

45 то — z;

1Ф! х „ у;,, h;Ä, К, „

= х; (2) у;

= }1; если Х увеличивается или Х вЂ” постоянное., а У уменьшается, то — z

1 — X

I+1 у„,, +

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

Цель изобретения — повышение дос товерности вычисления результата.

На фиг. 1 представлена функциональная схема устройства для деления; на фиг. 2 — пример выполнения блока микропрограммного управления; на фиг. 3 временная диаграмма работы устройства.„

Устройство для деления (фиг. 1) содержит две схемы t и 2 сравнения, первый и второй итерационные блоки

3< и 3, содержащие схему 4 (i=1 2) сравнения, два элемента И 5; -6,, реверсивный счетчик 7,, блок 8 микропрограммного управления, вход 9 пуска, выход 10 готовности результата, третий, первый и второй коммутаторы ,11-13, первый и второй накапливающие сумматоры 14 и 15, четвертый коммутатор 16, третий накапливающий сумматор 17, сумматор 18, входы 19 и 20 делимого и делителя, вход 21 логического нуля, выход 22 частотного. входы

23 и 24 первой и второй констант, выход 25 "Больше" схемы 1 сравнения, выход 26 "Меньше" схемы 2 сравнения, выходы 27-44 блока 8.

Блок микропрограммного управления (фиг. 2) содержит генератор 45 импульсов, регистр 46, первый блок 47 памяти, первый элемент задержки 48, второй блок 49 памяти, элемент ИЛИ

50, второй элемент 51 задержки.

Работа устрйоства основана на рекурсивном принципе вычисления значений арифметической функции деления (Z = ††). При этом для рекурсивного

Х

50 представления функции деления используются лишь элементарные функции непосредственного следования, непосредственного предшествования, константы и оператор примитивной рекурсии. Вычисление значения рекурсивно опреде55 ленной функции деления для заданных аргументов является многошаговым процессом, похожим на метод последова3 2 тельных приближений, так как при аа<числении отслеживается разность между исходными и заданными значениями аргументов путем положительного или отрицательного наращивания значений исходных аргументов. 3а счет отслеживания разности удается повысить достоверность рекурсивных вычислений, так как ошибочное значение аргумента можно рассматривать как его новое исходное значение. Рекурсивный метод вычислений становится самоисправляющимся, помехоустойчивым эа счет некритичности к единичным сбоям делимого Х и. делителя У.

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

При органиэации вычисления функции деления по рекуррентным соотношениям будем считать (для .определенности), что при делителе, равном нулю, частное будет также равно нулю, Х т.е. — — = О.

Если делимое Х и делитель У увеличиваются одновременно, то используются для вычисления значения частного Z рекуррентные соотношения если Х и У уменьшаются одноверменно, 1339553

h;, если Х уменьшается или Х вЂ” постоян5 ное, а У увеличивается, то

< +1 х

1+1

У<1!

h»

Б 1+1

= х;

И<+<

+ 1 (4) 10

= У»

= h;

+ 2; если Х увеличивается, а У вЂ” постоянно, то 15

z". + 1 ! х; +у;

У, h;+1 к

<+! с

Х1+!

У

h;„

>, Я»« (5) 20 если Х уменьшается, а У вЂ” постоянно, то

1 ! х — у;

У, h1 - 1

g +1.

\11 х;„

У +<

h;, 1+1 (6) 30

Начальные значения функции и .аргументов: < = О, х, = О, у, = О, Ь

- 1, g, =.-1.

Условие завершения рекурсивного процесса операции деления следующие:

RA — (х, — X g у, — YJ, Пусть делимое и делитель, частХ Y Z ное представимы дробями ——

К R R

Z Х Y y

При этом — — = ——

R R R R

При двоичном представлении чисел 45

R = 2", где n — - количество разрядов двоичного представления числа.

Пусть Х, У вЂ” суть целые числа.

Нетрудно заметить, что если Х делится на У нацело и результат равен Z, 50 причем разрядность представления z равно р, то и при делении любого целого числа g e (X, Х + У - 1j на У, результат, представленный р разрядами, также равен Z Действительно, пусть Z — - частное от деления Х на У, Z + 1 — частное от деления < на У. .Тогда 4 = Х + У и для любых 8E (Хд) результат деления 8 на У будет равен

Z. При вычислении по рекуррентным формулам текущего значения делимого х;, признаком достижения х задан1 ного значения Х будет попадание Х в интервал (к;, х, + У вЂ” 1) . Операцию деления над дробными представлениями делимого, делителя и частного можно путем предварительных преобразований свести к операции деления над целочисленными представлениями ее аргументов и функций.

Представим рекуррентные соотношения (1) — (6) несколько иначе. Введем новые переменные а; и b;, при этом а; > Ь; . Эти переменные имеют следующий смысл: если соответствует значению делителя у;, то Ь; соответствует значению частного к, если Ь, соответствует значению делителя у., то а соответствует значению частно<

ro г;.

B процессе отслеживания разности между исходными и заданными значениями операндов текущее значение делителя у; будем сравнивать со значениями а; и b; . Учитывая, что а; з Ь,, возможны следующие соотношения между заданными и текущими значениями Х и х,, У и а;, b;:

> х I

> х„, + х;, х,, о х

> Х;, с х;, с Х;, с Х;, х;, х;, Х 1 х;, Х»т х;, Х;

Х, q

Х:1

С учетом введенных переменных а; и

Ь; рекурентные соотношения (1) — (6) преобразуются в следующие:

Если Х».;, У>а., У> Ь,, то в качетстве у; примем а;, в качестве

z-, — Ь;, рекуррентные соотношения будут:

= x; + Ь;

=а +1

=Ь; +1

1+1 а;„

bii

{7) 1. Х

2. Х

3. Х

4. Х

5. Х

6. Х

7. Х

8. Х

9. Х

10. Х

11. Х

12. Х

13. X

14. Х

15. Х

16. Х

17. Х

18. Х

Y ) a;, Y с а;, У с а;, У с а, Y = а;, Y = a;, Y)а;, У са;

Y c.а;, с a °

iЭ

Y = --а ° ! Э

Y=a, Y o а;, Y с а;, Y с а;

Y с а;, Y=a;

Y = а,, У ) b;

Y)Ъ;

Усь;

Y = Ь;

Y>b;

Y-b, У>b, Yob, Y b;

Y = Ь;

У ) b;

Y=b; у

Y -Ь;

УсЬ;

Y -- b, Y)b;

Y=b;

1339553

h h; +2 й, 41 Б I

Ь„

1! б! а (4!

Ь„, "1! 41 (13) =: b !

=: h

=x«+g

1 !

=а -1

Ь, + 1

= h

-Е -г.

141 а„, Ь;„

h„„

В;„

Если Х сх

У = Ь, то у, рентные соотн а;, У»Ь,9 или

z; — Ь;, рекурбудут (8) 9 а;, ния оше х„ „ !

4!

Ь

h;„

К, б, х — а

1 9 а, b; — 1

h — 1 !

g, + 1

g 1(1

= х, х а„„

Ь„„

Ь „., 81+1

= а

1 (9) Ь;

= h

I (ы g

Если Х > х; у -Ь .г .(9 1 ношения будут: х + Ь ! I

G + 1

Ь;

h + 1

К;+1.!

41 (+1

Ь, Ь

I + I

И1. (.10) х; + а, а, b, + 1

h +

g — 1 !

X1б а;

Ь1„

g1-1 случаев дут: х; h;„ а, 1

b" -1

h, — 2

g, ° (б 1 !41 ь;„

h, а (12) Если Х > х; или Х = х,, У с а;, У < b, то в качестве у примем а в качестве z — Ь, рекуррентные соотношения будут:

Если Х > х, или Х = х;, У а;, У b,, то примем у, — Ь, z; — а;, еслиХсх, илиХ х;, У»а„, У:. h,, то у, — а, z; — b; . Для этих случа9 ев рекуррентные соотношения будут:

У" а;, У=Ь,, то а„рекуррентные соотЕслиХ»х;, У=а;, У> Ь,„то у, — а„, z, - b,. рекуррентные соотношения будут:

Если Х х;, Ус а;, У» Ь„, то у; -а;, z, -Ь,, еслиХ х;, У а,, У - Ь,, то у„— b; z;; — а„, для этих рекуррентные соотношения буЕсли X c x, у !4;9 У = Ъ;, то у — b,, z; — а, рекуррентные соотношения будут:

Начальные значения функций и аргументов: x, = О, а = О, b = 0, h„

= 1, g, = -1.

Условие завершения рекурсивного процесса операции деления следующее:

RA =(х; Х (а; v Ь,) = YJ, При этом если У = а;, то Z b; если У = Ь, то Z — а (5) если Y -- a; =- b; то у=r, ;, Z=a,.

Признаком достижения х заданно-! го значения Х будет попадание Х в интервал (х;, х, + У вЂ” 1) .

На основании сравнения вычислений частного по рекуррентным соотношениям (1)-(6) с вычислением частного по рекуррентным соотношениям (7), (9)

4О

< 10), (15) видно, что во втором случае результат достигается эа меньшее число шагов.

Для упрощения описания работы уст45 ройства целесообразно устновить соответствие между соотношениями (7) (15) и отдельными структурными элементами устройства для деления, которые кх реализуют. Для реалкзапк(и функций h g в устройстве используются сумматоры 14 и 15. Отслеживание разнос к между исходными и заданными значениями делимого путем наращивания ксходных значений осуществляется с

y-:

"* помощью сумматоров 18 и 17 и схем сравнения 1 и 2. Число подключенных к шине 21 логического нуля младших разрядов схем 1 к 2 сравнения равна

133955

35 числу п разрядов двоичного прецставления входных операндов и частного.

Зто связано с необходимостью предварительного сдвига делимого на п

5 разрядов влево.

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

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

Устройство работает следующим.об- . разом.

Исходное состояние задается сигналом системного сброса, по которому выходы блоков 3< и 3 устанавливаются в нулевое состояние, синхронизирующие сигналы с выходов блока 8 отсутствуют, а сигнал готовности на его выходе 10 устанавливается в единичное состояние. Выход сумматора 17 устанавливается в нулевое состояние, а в сумматоры 14 и 15 записывается код числа "1" и "-1" соответственно.

После поступления операндов Х и У соответственно на входы делимого и делителя на выходах схем 1 и 2 сравнения и на сигнальных выходах блоков

3, и 3 будет находиться информация о соотношениях между значениями поступивших операндов и исходными значениями делимого и делителя, хранящихся соответственно в сумматоре 17 и блоках 3, и 3 . После поступления единичного сигнала пуска ST = 1 на

40 вход 9 блока 8 с его выхода управляющие сигналы подготавливают накапливающие сумматоры 14, 15 и 17 и блоки

3< и 3 на вычисление частного в соответствии с рекуррентными соотноше- 45 ниями (7) †(15). Управляющим сигналом с выхода блока 8 на выход коммутатора 11 подключается информационный выход того итерационного блока, в котором находится текущее значение делителя.

Выбор блоком 8 блоков 3< и 3 отводимого для хранения текущего значения делителя и для хранения текущего значения частного производится ис- 55 ходя из следующего. Так как в блоке

3, содержится информация о переменной а, а в блоке 3 о переменной Ь и

3 8

a > Ь, Yo: если з на чение nerrr< Terr rr на входе устройства для деления боль— ше, чем значения, хранящиеся в блоках

3 и 3 то в качестве итерационного

< 9 блока делителя выбирается элемент 3,, а частного — элемент 3, если значение делителя на входе устройства меньше, чем значения хранящиеся в блоках

3„ и 3, то в качестве итерационного блока делителя выбирается элемент 3 а частного — элемент 3,, если значение делителя на входе устройства больше, чем значение, хранящееся в одном из блоков 3, или 3, и меньше, чем значение, хранящееся в другом, последний выбирается в качестве итерационного блока делителя.

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

С задержкой, определяемой временем установки накапливающих сумматоров 14, 15 и 17, на выходах 43 и 44 блока 8 формируется двухтактная последовательность синхронизирующих сигналов.

При равенстве текущих значений делимого и делителя заданным, установленным на входе устройства для деления, с выходов 25-30 в блок 4 управления поступают нулевые сигналы. При этом сигналом с выхода блока 8 на выход коммутатора 11 подключается информационный выход того итерационного блока, в котором находится вычисленное значение частного. Соответст- венно в другом итерационном блоке будет содержаться достигнутое значение делителя. Одновременно на выходе 10 блока 8 сформируется единичный сигнал, свидетельствующий о готовности результата.

Работа устройства иллюстрируется таблицей, в которой знак "-" означает отсутствие сигнала, "*" — любое состояние.

Работа блока 8 происходит следующим образом.

В начале работы, после установления на входах 25-30 информации, опре- деляющей состояние его выходов, на первый вход 9 поступает единичный импульсный сигнал, передним фронтом которого запускается генератор 45.

По переднему фронту импульса информация с входов 25-30 записывается в регистр 46 и устанавливается на входах блока 47 памяти. При этом на выходах

133

31-42 образуется комбинация сигналов, которая настраивает в соответствии с таблицей накапливающие сумматоры

14, 15 и 17 и коммутатор 11. Эти сигналы подготовляют также блоки 3, и

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

14, 15 и 17, с выхода элемента 48

Задержки поступает импульсный сигнал, по единичному значению которого на четвертом (пятом) выходах блока 8 формируется единичный сигнал, который проходит через элемент ИЛИ 50 и элемент 51 задержки. При этом соответствующие выходы блока 8 переходят в единичное состояние, которое соХраняется до момента прекращения действия единичного сигнала на первом входе блока. Задержка на элементе 51 необходима для обеспечения надежной последовательности срабатывания накапливающего сумматора 17 относительно накапливающих сумматоров 14 и 15.

При образовании единичного сигнала на выходе 10 он поступает на вход останова генератора 45 импульсов, свидетельствуя о готовности результата.

В блоках 3, и 3 на счетчиках 7 хранятся предыдущие значения делителя и частного. Если на информационный вход блоков 3< и 3 поступает значение делителя, не совпадающее со значением, хранящимся в счетчике

7, схема 4 сравнения вырабатывает соответствующие сигналы, поступающие на сигнальные выходы блоков 3. С уче— том этих сигналов в следующем такте вычислений сигналом с управляющего входа блока 3 будет подготовлен один из элементов И 5 или 6 (или не подготовлен ни один, если изменять содержание итерационного блока не требуется). В следующем такте работы устройства для деления сигнал с синхрониэирующего входа блока 3 через подготовленный ранее элемент И 5 или

6 поступает соответственно на суммирующий или вычитающий входы счетчика 7, производя изменения на единицу хранящегося в нем значения. Новое текущее значение со счетчика 7 поступает на вход схемы 4 сравнения для сравнения с входным значением делителя.

9553

Ф о р м у л а и з о б р е т е н и я

1. Устройство для деления, содержащее первый итерационный блок, два коммутатора, первую схему сравнения и блок микропрограммного управления, первый и второй выходы которого соединены с управляющими входами первого и второго коьачутаторов соответственно, выход "Больше" первой схемы сравнения соединен с первым входом признака перехоца блока микропрограммного управления, о т л и ч а ю щ е ес я тем, что, с целью повышения достоверности вычисления результата, в него введены вторые схема сравнения и итерационный блок, три накапливающих сумматора, третий и четвертый коммутаторы и сумматор, причем вход делимого устройства соединен с входами старших разрядов первого операнда первой и второй схем сравнения, входы младших разрядов первых операндов которых соединены с входом логического нуля устройства, вход делителя которого соединен с информационными входами первого и второго итерационных блоков, первые и вторые выходы которых соединены с второго по пятый входами признаков перехода блока микропрограммного управления, шестой . вход признака перехода которого соединен с выходом "Меньше" второй схемы сравнения, вход пуска устройства соединен с входом запуска блока микропрограммного управления, третий выход которого соединен с управляющим входом третьего коммутатора, первый и второй информационные входы которого соединены с,третьими выходами первого и второго итерационных блоков соответственно, синхровходы которых соединены с синхровходами первого и второго накапливающих сумматоров и с четвертым выходом блока микропрограммного управления, гятый и шестой выходы которого соединены с входами разрешения суммирования и вычитания первого итерационного блока, седьмой и восьмой выходы блока микропрограммного управления соединены с входами разрешения суммирования и вычитания второго итерационного блока, вход первой константы устройства соединен с первыми информационными входами первого и второго коммутаторов, вторые информационные входы которых соединены с входом второй

ll 133 константы устройства, выходы первого и второго коммутаторов соединены с информационными входами первого и второго сумматоров соответственно, выходы которых соединены с первым и вторым информационными входами четвертого коммутатора, третий информационный вход которого соединен с выходом третьего коммутатора, с выходом частного устройства и с первым информационным входом сумматора, второй информационный вход которого соединен с входом второго операнда второй схемы сравнения и выходом третьего накапливающего сумматора, информационный вход которого соединен с выходом четвертого коммутатора, первый и второй управляющие входы которого соединены с девятым и десятым выходами блока микропрограммного управления, одиннадцатый и двенадцатый выходы которого соединены с входами разрешения работы первого и второго накапливающих сумматоров соответственно, тринадцатый и четырнадцатый выходы блока микропрограммного управления соединены с входом разрешения работы и синхровходом соответственно

9553

12 третьего накапливающего сумматора, вход второго операнда первой схемы сравнения соединен с выходом сумматора, пятнадцатый выход блока микро5 программного управления соединен с выходом готовности результата устройства, 2. Устройства по и. 1, о т л и

l.ч а ю щ е е с я тем, что каждый итерационный блок содержит схему сравнения, два элемента И и реверсивный счетчик, причем информационный вход блока является входом первого операнда схемы сравнения, выходы "Больше" и "Меньше" которой соединены с первым и вторым выходами блока соответственно, синхровход блока соединен с первыми входами первого и второго элементов И, выходы которых соединены со счетным и вычитающим входами соответственно реверсивного счетчика, выход которого соединен с входом второго операнда схемы

2 сравнения и является третьим выходом блока,.входы разрешения суммирования и вычитания блока соединены с вторыми входами первого и второго элементов И соответственно.!

339553 (л

Х

И

M (/

Х

И ! м (( л . л ! ((-4

v v ! I (1 (1 (М

+ е

Х и о

Ц (Ч !

Х (М

I Ф и

М

CV

t +

/ »Й

И И!

K и

Ф» ! л-" (( о

Ф» ! л

Ф

+ (! С! + л л л(/ (-(&.

v v v! ( (((/ л н

v v

+ ((! ч

v! л( ч

+ (» . (-(v! м н

О!

М л (-( (.Р

+ т ч

М м ( (ю

/Ф ((I Д Ф м(-ю((! о 1 м

Ф ф Ц (" L (/ !» И х е 1 (6 (/ m

L мт м б .Ф Ф м ф

4 I(Ф о CD О т « ((о о

« «Ю

О о «

» \ ь о!

I ! о о о

Ф Ф Ю о о о о Ю о ю о о о о Ф» о Ф о о

IO о х о о

Ф» о о о Ф Ф Ю Ю о о о о о о о а о о о о о о CD

Ф Ф 9 Ф»

Ф» ° Ф Ф» о о о о о о о

% (1 У У О л (О о\

Ю ф

Ва

К( (!

"l

El

М

Х

И

+ м

Х

И (/

Н

+ м

Х

И (» (-ю

+ м

Ж

И л (/ ((v

+ м

Е

И Ф

Х (/)

I м

Ф (Х

I м

15

1б

1339553

О

Х

CD

М

CD й4

О

М

Е (Л м М М1

4Ж М Х и сл сп

1 о а

C»I!

nfl и (Л (»!

I/1

Г 4

44 4 4

+

1/1

CD! ! !

44 л н

1 н

О м м\

I

44 н

t4 44 t4

I Л Л н н н

u u o!

1 ! ! ! м !

1 л н еu u u л н н е"

u u u,41 о! I g m M а а " О

mgvamxг

1 1 !

m о

R о

III !

2 ж

К о

1» и о!

4\

О

О1х о о! !

Ю

М о

О 4

5

v о о о

CIO

»»,»

1!

2 х о

I (ц ж

Ц

Й! :

v о

Е»

О !

Ю Ю С о ю о

I о о ! о о

1339553

Фиг,2

И два@

Jest ьаоУ

Фиг. З

Составитель Н.Маркелова

Редактор Е.Папп Техред М.Дидык Корректор А.Тяско

Заказ 4223/39 Тираж 672 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035у Москва, Ж-35, Раушская наб., д. 4/5 Производственно-полиграфическое предприятие, r. Ужгород, yg. Проектная, 4