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

 

(ii 85797?

Оп ИКАНИЕ

ИЗОБРЕТЕН ИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

Союз Советских

Соцкалкстичесимх

Республик (6I ) Дополнительное к авт. свид-ву (22) Заявлено 04.01.80 (21) 2869013/18 — 24 с присоединением заявки М (23) Приоритет (5t)A%. Кл. (3 06 F 7/52

Гееударетвеииый комитет

СССР аа делам изебретеиий я еткрытий

Опубликовано 23.08.81. Бюллетень J6 31

Дата опубликования описания 23.08.81 (53) УДК 681.3 (088.8) =— ( ( (72) Авторы изобретения

Б. В. Цесин и А. А. Шостак

Минский радиотехнический ин (7I) Заявитель (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ЧИСЕЛ!

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

Известно устройство для деления чисел, содержащее регистры делимого, делителя и частного, сумматор, блок управления (1).

Недостатком известного устройства является низкое быстродействие вследствие формирования в каждом цикле деления одной цифры частного.

Наиболее близким к предлагаемому является 1п устроиство для деления чисел, формирующее в каждом цикле деления % цифр частного (% 2, 3, 4,..., n/2, где п — разрядность обрабатываемой информации), содержащее регистр делителя, регистры делимого и частного с цепями однотакт- 1з ного сдвига на * разрядов, шифратор, блок умножения, регистр адреса, блока памяти, регистры верхнего и нижнего значений * цифр частного, коммутатор и блок управления, причем входы шифратора соединены с шинами зна- II чений 4с старших разрядов регистров делимого и делителя, а выход соединен с первым входом регистра нижнего значения 1с цифр частного, второй вход которого соединен с первым выходом блока памяти, второй выход которого соединен с входом регистра верхнего значения * цифр частного, выходы регистров верхнего и нижнего значений к цифр частного соединены с входами коммутаторов, выход которого соединен с первым входом блока умножения, с входом 1( младших разрядов регистра частного и с входом регистра адреса, выход которого соединен с входом блока памяп, выход регистра делителя соединен с вторым входом блока умножения, первый и второй входы блока управления соединены с выходами младших разрядов регистра соответственно верхнего и нижнего значений к цифр частного, а его выходы соединены с управляющими входами регистров делимого, делителя и частного, регистров верхнего и нижнего значений к цифр частного, первого коммутатора и регистра адреса (2(, Недостатком известного устройства является относительно низкое быстродействие вследствие большой длительности цикла формирования Ф цифр честного. который формируется в цикле по многотактному принципу.. Минимальное число тактов в цикле равно двум, 857977

15 максимальное — (1+1). Время выполнения де ления двух и-разрядных чисел примерно равно где Т,„— среднее время цикла формирования цифр частного.

В первом приближении максимальное и минимальное время Т,„равно

1о1Х

= (4++1) ьу, т„ где ьУ вЂ” временная задержка блока умножения (здесь предполагалось, что вычитание в известном устройстве перекрывается во времени с умножением), Цель изобретения — увеличение быстродействия известного устройства за счет уменьшения врсмени цикла формирования М цифр частного, Поставленная цель достигается тем, что в устройство для деления чисел, содержащее регистр делителя, регистры делимого и частного, шифратор, блок умножения, регистр адреса, блок памяти, регистры верхнего и нижнего значений с цифр частного, первый коммутатор и блок управления, причем входы шифратора соединены с шинами значений Ф.. старших разрядов регистров делимого и делителя, а выход соединен с первым входом регистра нижнего значения к цифр частного, второй вход которого соединен с первым выходом блока памяти, второй выход которого соединен с входом регистра верхнего значения Ф цифр частного выходы регистров верхнего и нижнего значений Ф цифр частного соединены с входами коммутатора, выход которого соединен с первым входом блока умножения, с входом к младших разрядов регистра частного и с входом регистра адреса, выход которого соединен с входом блока памяти, в ход регистра делителя соединен с вторым входом блока умножения, первый и второй входы блока управления соединены с выходами младших разрядов регистра соответственно верхнего и нижнего значений к цифр частного, а его выходы соединены с управляющими входами регистров делимого, делителя и частного, регистров верхнего и нижнего значений Й цифр частного, первого коммутатора и регистра адреса, введены сумматор-вычитатель, второй коммутатор и дешифратор, входы которого соединены с выходами регистров верхнего и нижнего значений М цифр частного, а выход соединен с третьим входом блока управления и с управляющим входом второго коммутатора, информационные входы которого соединены с выходами регистра делителя и блока умножения, а выход — с первым входом сумматора — вы-. читателя, второй вход которого соединен с выходом регистра делимого, а выход — с входом регистра делимого, выход знакового разря. да сумматора — вычитателя соединен с яетвертым входом блока управления, дополнительный выход которого соединен с управляющим входом сумматора- вычитателя.

Блок управления содержит регистр, дешифратор, два узла памяти и узел задержки, при. ,чем вход узла задержки соединен с выходом первого узла памяти, а выход — с входом регистра, выход которого соединен со входом дешифратора, выход которого соединен с входом второго узла памяти и с первым входом первого узла памяти, другие входы которого подключены к входам блока управления, выхо. ды второго узла памяти подключены к выходам блока управления.

На фиг. 1 приведена структурная схема предлагаемого устройства для деления чисел", на фиг. 2 — диаграмма выборки из блока памяти верхнего и нижнего значений 1с цифр частного; на фиг. 3 — схема дешифратора; на фиг. 4— граф-схема алгоритма работы блока управления; на фиг. 5 — структурная схема блока управления.;

Устройство для деления чисел содержит регистр 1 делителя, регистры 2 и 3 соответственно делимого и частного, шифратор 4, блок 5 умножения, регистр 6 адреса, блок 7 памяти, регистры 8 и 9 соответственно верхнего и нижнего значений М цифр частного, первый коммутатор 10, второй коммутатор 11, сумматорвычитатель 12, дешифратор, 13 и блок 14 управления, причем входы шифратора 4 соединены с шинами 15 и 16 значений % старших разрядов регистров 2 и 1 делимого и делителя соответственно, а выход соединен с первым входом регистра 9 нижнего значения 1с цифр частного, второй вход которого соединен с первым выходом блока 7 памяти, второй выход которого соединен со входом регистра 8 верхнего значения к цифр частного, выходы регистров 8 и

9 верхнего и нижнего значений % цифр частного соединены со входами дешифратора 13 и первого коммутатора 10, выход которого соединен с первым входом блока 5 умножения, с входом

1с младших разрядов регистра 3 частного и с входом регистра 6 адреса, выход которого соединен со входом блока 7 памяти, выход регистра 1 делителя соединен со вторым входом блока 5 умножения и с первым информационным входом второго коммутатора 11, второй информационный вход которого соединен с выходом блока 5 умножения, а управляющий вход соединен с выходом дешифратора 13, выход коммутатора 11 соединен с первым входом сумматора-вычитателя 12, второй вход которого соединен с выходом регистра 2 делимого, а выход соединен с входом регистра 2 делимого, входы блока 14 управления соединены с выходами 17 и 18 младших разрядов регистров

8 и 9 верхнего и нижнего значений 1с цифр частного соответственно, с выходом дешифратора

13 и с выходом 19 знакового разряда сумматора-вычитателя 12, а его выходы 20, 21, 22, ! 23, 24, 25, 26 и 27 соединены соответственно

857977

9 10 11 12 13 14 15

1 2 3 4 5 6 7

1 2 4 6 8 10 12 14

14 15

8 10 12 12

°

6 8 10 12

1 2 4 6

1 2 4 6

12 14 15

1 2 4 6 6 8,10 10 12 14 14 15

1 2 3 4 6 7 8 10 10 12 14 14 15

1 2 3 4 6 6 8 9 10 12 12 14 14 15

1 2 3 4 5 6 7 8 10 10 12 12 14 14 15

1 2 3 4 5 6 7 8 9 10 11 12 15 14 14 15

45

55

5 с управляющими входами регистров 2, 1 и 3 делимого, делителя и частного, регистра 6 адреса, регистров 8 и 9 верхнего и нижнего значений * цифр частного, первого коммутатора

10 и сумматора-вычитателя 12 соответственно.

В данном устройстве регистры 1, 2 и 3 делителя, делимого и частного, регистр 6 адреса, регистры 8 и 9 верхнего и нижнего значений и цифр частного могут быть построены на основе двухтактных синхронных O-триггеров.

В качестве блока памяти может быть использована постоянная (например в виде шифратора), либо быстродействующая оперативная (регистрок вая) память емкостью 2 — 1 2k-разрядных слов. С помощью регистра 6 адреса, блока 7 памяти, регистров 8 и 9 верхнего и нижнего значений к цифр частного и первого коммутатора 10 осуществляется последовательная подборка в цикле к цифр частного, На фиг. 2 изображена диаграмма выборки из блока 7 памяти верхнего и нижнего значений к цифр частного для случая, когда используемая

Таблица строится следующим образом.

Определяются максимальное и минимальное значения 4с цифр частного Я при соответствующих значениях Ф старших разрядов делимого и, делителя, т. е. диапазон возможных значении к цифр частного.

По полученному диапазону из диаграммы на фиг. 2 определяется то значение частного, по которому путем последовательных выборок мож но выделить любое значение )с цифр частного из вычисленного диапазона. Это значение М цифр частного заносится в таблицу.

Например, пусть старшие четыре разряда делимого и делителя соответственно равны 6 н

10, т.е. 0,0110 и 0.>010. Тогда Я„, ), =-01101111:

6 система счисления двоичная, а число К одновременно формируемых в цикле цифр частного равно четырем (на диаграмме к двоичных цифр заменены целым шестнадцатиричным эквивалентом). Выборка в каждом такте цикла (за исключением первого такта) верхнего илн нижнего значения )с цифр частного осуществляется с помощью первого коммутатора 10 под действием управляющего сигнала с выхода 26 блока 14 управления, причем если в предыдущем такте цикла результат сумматора-вычитателя 12 был положительный, то выбирается верхнее значение

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

) :0,1010=0,1011, Я,= 0 0110:0,1011=0,1000.

Из диаграммы (фиг. 2) видно, что к диапазону 8 — 11 частного можно обратиться, первоначально предсказав с помощью шифратора 4 частное 10.

Блок 5 умножения предназначен для формирования произведения и-разрядного делителя на

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

Сумматор-вычитатель 12 предназначен для формирования текущих остатков и может быть реализован любым из хорошо известных способов. Функция "Сложение" или "Вычитание" сумматора-вычитателя определяется значением управляющего сигнала с выхода 27 блока 14 управления. В первом такте каждого цикла он работает s режиме "Вычитание". В последующих тактах режим определяется следующим образом: если в предыдущем такте знак результата сумматора — вычитателя был положительный, то выполняется вычитание, в противном случае сложение.

Второй коммутатор 11 вместе с дешифратором 13 определяют, что необходимо подать на один из входов сумматора-вычитателя: либо значение произведения, сформированного на выходе блока 5 умножения, либо значение делителя или его простого кратного, полученного путем соответствующего сдвига. Коммутатор может быть реализован на элементах И вЂ” ИЛИ.

На фиг. 3 представлена функциональная схема дешифратора 13 для случая k 4..

Дешифратор 13 содержитузел 18 управле20 ния выборкой делителя У, узел 29 управления выборкой двукратного делителя 2У, узел 30 управления выборкой учетверенного делителя

4У, узел 31 управления выборкой восьмикратного делителя 8У и узел 32 управления выбор25 кой произведения, сформированного на выходе блока 5 умножения. Каждый из этих узлов может быть реализован на элементах И вЂ” ИЛИ в соответствии со следующими логическими выражениями: (. =1 g >> ч 5 ч7 ч9 ч11 ч1ь v 15 ч(1„АО )

30 или1 Ч= 1 ЧчЦ ЧчЭ ЧчХ

0. = Y14 ч(2нAО )

4.3=19 V(4„AO )

8>-- 8 п08

М

Io

> = Я„ч 4н vg „ч1„л 0, где, например, 14 означает, что содержимое

Ь регистра 8 верхнего значения 1с цифр частного 40 равно 1110, а 8и означает, что содержимое регистра 9 нижнего значения * цифр частного равно 1000. Выход узла 32 дешифратора 13 поступает как на управляющий вход второго коммутатора 11, так и на первый дополнитель- 45 ный вход блока 14 управления. Именно он

"сообщает" блоку 14 управления, что будет выполняться в первом такте цикла: умножение с вычитанием или только вычитание. Во всех последующих тактах цикла выполняется либо только сложение, либо только вычитание. Окончание цикла формирования 1с цифр частного определяется блоком 14 управления по значению младших разрядов регистров 8 и 9 верхнего и нижнего значений 1< цифр частного следующим образом: если в младшем разряде регистра 8 записана "1", а в младшем разряде регистра 9 записан "0", то формируется сигнал окончания цикла определения % цифр частного.

857977 8

Блок 14 управления координирует работу блоков, входящих в устройство (фиг. 1).

Опишем работу блока 14 с помощью графсхемы алгоритма (ГСА) (фиг. 4).

ГСА содержит шестнадцать вершин 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47 и 48, в том числе одиннадцать операторных вершин 33, 34, 36, 37, 38, 42, 43, 44, 45, 46 и

47 и пять условных вершин 35, 39, 40, 41 и 48.

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

Запись А íà приведенной ГСА следует понимать как "значение на выходе г;го блока устройства деления" (фиг, 1 и 3).

Так, например запись Рег. 9: — А в операторной вершине 34 следует понимать как

"регистру 9 присвоить значение, сформированное на выходе шифратора 4". Через М обозначена кратность делителя, хранимого в регистре 1

Значение М в каждом такте работы блока управления определяется дешифратором 13 (М в рассматриваемом слччае может принимать значение 1, 2, 4 или 8) . Микрооперация

"Сдвиг информации в регистре" осуществляется по однотактному принципу íà к разрядов. В вершине 35 проверяется условие, равно ли значе. ние на выходе узла 32 дешифратора 13 единице.

Если оно равно единице, то в первом такте цикла определения tc цифр частного выполняется умножение и вычитание, в противном случае с помощью коммутатора 11 выбирается значение простого кратного делителя и осуществляется только вычитание. В условной вершине 39 анализируется знак результата на выходе сумматоравычитателя 12 (А =1, если результат отрицательный,в противном случае А О=О) . С помощью условных вершин 40 и 41 определяется окончание цикла определения Й цифр частного (если .

А1т А1В=1, то цикл определения очередных

% цифр частного заканчивается).

Алгоритм работы блока 14 управления предопределяет его структурную и функциональную схемы. На фиг. 5 приведена реализация блока 14 управления в виде микропрограммного устройства управления. Блок управления содержит регистр 49, дешифратор 50, первый 51 и второй

52 узлы памяти и узел 53 задержек, вход 54 блока управления. В узле 51 памяти содержатся адреса микрокоманд, в узле 52 памяти—

857977

30 коды микрокоманд, которые при считывании управляют работой блоков устройства деления в соответствии с ГСА (фиг. 4).

Объем первого и второго узлов памяти однозначно определяется числом операторных вершин в ГСА (фиг. 4). Узел 53 задержек фактически определяет время, необходимое на выполнение соответствующей микрокоманды. Выборка значения адреса следующей микрокоманды из первого узла 51 памяти осуществляется путем 10 возбуждения соответствующей шины с помощью дешифратора 50 и с учетом значения сигналов условий, поступающих на его вход 54 (вход

54 является входами блока 14 управления).

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

В исходном состоянии (начало деления) в регистре 2 делимого хранится прямой и-разрядный код делимого, в регистре 1 делителя— прямой п-разрядный код делителя, регистры 3 20 и 6 обнулены (здесь предполагается, что делимое и делитель правильные положительные дроби), Каждый цикл определения очередных

М цифр частного начинается с обнуления регистра 8 сдвига информации в регистре 3 частного 25 на Й разрядов в сторону его старших разрядов и предсказания шифратором 4 % цифр частного (в дальнейшем цифра частного), которые записываются в регистр 9 и затем уточняются.

Предположим, что возможно выполнение в одном такте работы блока управления микроопераций, принадлежащих следующим операторным вершинам ГСА на фиг. 4: 36 и 38, 37 и 38, 42 и 46, 43 и 46, 44 и 47, 45 и 47.

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

1-й такт. Из содержимого регистра 2 делимого вычитается в сумматоре-вычитателе 12 произведение содержимого регистра 1 делителя на цифру 12 частного, а получившийся при этом положительный результат заключается в регистр 4>

2 делимого. Одновременно с этим по адресу 12 из блока памяти 7 в регистры 8 и 9 записываются цифры 14 и 10 соответственно. Длительность такта в основном определяется временем умножения. 50

2-й такт. Из содержимого регистра 2 делимого вычитается в сумматоре-вычитателе 12 удвоенное значение содержимого регистра 1 делителя, а получившийся при этом отрицательный результат записывается в регистр 2 делимого. Одновременно с этим»o адресу 14 из блока памяти

7 в регистры 8 и 9 записываются цифры 15 и 13 соотвстствспно. )Ьительпость такта, в основном, опрслспяс1ся врсмепем вычитания.

3-й такт. К содержимому регистра 2 делимого прибавляется в сумматор-вычитатель 12 содержимое регистра 1 делителя, а получившийся при этом положительный результат записывается в регистр 2 делимого. Одновременно с этим ло адресу 13 из блока памяти 7 в регистры 8 и 9 записываются цифры 13 и 12 соответственно.

Длительность такта, в основном, определяется временем сложения.

4-й такт является последним в рассматриваемом цикле определения точного значения цифры частного, так как значения младших разрядов регистров 8 и 9 равны соответственно

"1" и "О". В нем производится запись цифры

13 в младшие четыре разряда регистра 3 частного, а также однотактный сдвиг информации на четыре разряда в сторону старших разрядов в регистре 2 делимого. В этом такте не выполняется ни операция "умножение", ни операция сложение- вычитание". В дальнейшем такты, подобные описанному, будут исключены из рассмотрения ввиду их быстрого выполнения (отсутствуют наиболее длительные операции, такие как умножение или сложение).

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

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

В известном устройстве минимальное число тактов в цикле равно 2, а максимальное— (%+1), в то время как в предлагаемом устройстве среднее минимальное число тактов цикла равно 1,5, а среднее максимальное число тактов цикла равно (4<+0,5).

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

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

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

11 85797 соединены с шинами значения 1а старших разрядов регистров делимого и делителя, а выход соединен с первым входом регистра нижнего значения * цифр частного, второй вход которого соединен с первым выходом блока памяти, второй выход которого соединен с входом регистра верхнего значения % цифр частного, выходы регистров верхнего и нижнего значений

Й цифр частного соединены с входами коммутатора, выход которого соединен с первым входом блока умножения, с входом k младших разрядов регистра частного и с входом регистра адреса, выход которого соединен с входом блока памяти, . выход регистра делителя соединен с вторым входом блока умножения, жрвый и второй входы блока управления соединены с выходами младших разрядов регистра соответственно верхнего и нижнего значений* цифр частного, а его выходы соединены с управляющими входами регистров делимого, делителя и частного, Регистров верх20 него и нижнего значений * цифр частного, первого коммутатора и регистра адреса, о т л ич а ю щ е е с я тем, что, с целью увеличения быстродействия, устройство содержит сумматор-вычитатель, второй коммутатор и дешифра25 тор, входы которого соединены с выходами регистров верхнего и нижнего значений М цифр частного, а выход соединен с третьим входом блока управления и с управляющим входом

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

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

Источники информации, принятые во внимание при экспертизе

1. Карцев М. А, Арифметика цифровых машин. M., "Наука", 1969, с. 494.

2. Патент США И 3.234.367 кл. 235 — 156, 1966 (прототип) .

857977

ЮЦЛ 305лОницеиу ЬОдй м

pc траиг жег

Составитель В. Кайданов

Техред Л, Пекарь

Корректор M. Коста

Редактор П. Ортутай

Подписное

Филиал ППП * Патент", г. Ужгород, ул. Проектная, 4

Заказ 7245(79 Тираж 745

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

113035, Москва, Ж-35, Раушская наб., д. 4/5