Устройство для деления чисел Советский патент 1981 года по МПК G06F7/52 

1

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

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

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

Наиболее близким к предлагаемому являетсяО устройство для деления чисел, формирующее в каждом цикле деления -k цифр частного (k 2, 3, 4,..., п/2, где п - разрядность обрабатьгеаемой информации), содержащее регистр делителя, регистры делимого и частного с цепями однотакт- 15 ного сдвига на -k разрядов, шифратор, блок умножения, регистр адреса, блока памяти, регистры верхнего и нижнего значений -k цифр частного, коммутатор и блок управления, причем входы шифратора соединены с зна- jg чений -k старших разрядов регистров дегамого и делителя, а выход соединен с первым входом регистра нижнего значения k 1щфр частного, втоfou вход которого соединен с первым выходом

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

Недостатком известного устройства является относительно низкое быстродействие вследствие большой .Щительности цикла формирования -k цифр частного, который формируется в цикле по многотактному принципу.. Минимальное число тактов в цикле равно двум. 38 максимальное - (i + l). Время выполнения дь ле1«1я двух п-разрядных чисел примерно равно т -И- т 4 -jT Li , где Тц - среднее время цикла формирования дафр частного. В первом приближении максимальное и минимальное премя Тцравно .(к.,)с, ,.T, где - временная задержка блока умноженкя (здесь предполагалось, что вычитание в известном устройстве перекрывается во времени с умножением) . Цель изобретения - увеличение быстродействия известного устройства за счет уменьшения времени цикла формирования -k цифр частного. Поставленная цель достигается тем, что в устройство для деления чисел, содержащее регистр делителя, регистры делимого и частного, шифратор,блок умножения, регистр адреса, блок памяти, регистры верхнего и нижнего значений 1 цифр частного, первый коммутатор и блок управления, причем входы шифратора соединены с шинами значений t. старших разрядов регистров делимого и делителя, а выход соединен с первым входом регистра нижнего значения 4с цифр частного, второй вход которого соединен с первым выходом блока памяти, второй выход которого соединен с входом регистра верхнего значе шя -К Ш1фр частного выходы регистров верхнего и нижнего значений ic цифр частного соединенъ с входами коммутатора, выход которого соединен с первым входом блока умножения, с входом k младших разрядов регистра частного и с входом регистра адреса, вы ход которого соединен с входом блока памяти регистра делителя соединен с вторым входом блока умножения, первый и второй входы блока управления соединены с выходами младших разрядов регист ра соответственно верхнего и нижнего значений 1 цифр частного, а его выходы соединены с управляющими входами регистров делимого, делителя и частного, регистров верхнего и нижнего значений 4 цифр частного, первого коммутатора и регистра адреса, введены сумматор-вычитатель, второй комм татор и деишфратор, входы которого соединены с выходами регистров верхнего и нижнего значений -k цифр частного, а выход соединен с третьим входом блока управления и с управляющим входом второго коммутатора, информационные входы которого соединены с выходами регистра делителя и блока умножения, а выход - с первым входом сумматора-вы-, читателя, второй вход которого соединен с выходом регистра делимого, а выход - с входом регистра делимого, выход знакового разря да сумматора - вычитатеяя соединен с .четвертым входом блока управления, дополнительный выход которого соединен с управляющим входом сумматора- вычитателя. БЛОК управления содержит регистр, дешифратор, два узла памяти и узел задержки, причем вход узла задержки соединен с выходом первого узла памяти, а выход - с входом регистра, выход которого соединен со входом дешифратора, выход которого соединен с входом второго узла памяти и с первым входом первого узла памяти, другие входы которого i подключены к входам блока управления, выходы второго узла памяти подключены к выходам блока управления. На фиг. 1 приведена структурная схема предлагаемого устройства для деления чисел; на фиг. 2 - диаграмма выборки из блока памяти верхнего и нижнего значений k цифр частного; на фиг. 3 - схема дешифратора; на фиг. 4 граф-схема алгоритма работы блока управления; на фиг. 5 - структурная схема блока управления. ; Устройство для деления чисел содержит регистр 1 делителя, регистры 2 и 3 соответственно делимого и частного, шифратор 4, блок 5 умножения, регистр 6 дреса, блок 7 памяти, регистры 8 и 9 соответственно верхнего и нижнего значений 1 цифр частного, первый коммутатор 10, второй коммутатор 11, сумматорвычитатель 12, дешифратор , 13 и блок 14 управления, причем входы шифратора 4 соединены с шинами 15- и 16 значений 1 старших разрядов регистров 2 и 1 делимого и делителя соответственно, а выход соединен с первым входом регистра 9 нижнего значения 1 цифр частного, второй вход которого соединен с первым выходом блока 7 памяти, второй выход которого соединен со входом регистра 8 верхнего знач ™ частного, выходы регистров 8 и 9 верхнего и нижнего значечий 1с цифр частного соединены со входами дешифратора 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, 123, 24, 25, 26 и 27 соединены соответственно

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

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

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

Делимое

Делитель

1246 1246 1246 1246 Г 2 3 4 1234 1234 1234

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

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

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

цифр частного заносится в таблицу.

Например, пусть старише четыре разряда делимого и делителя соответственно равны 6 и 10, т.е. 0,0110 и OJ010. Тогда Q d - lllOllll:

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

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

Шифратор 4 предназначен для предсказания Щ1ФР частного по значению ic старших разрядов делимого и делителя и может быть реализован

в виде быстродействующей комбинационной схемы в соответствии с таблицей ().

15

14

13

12

11

10 121415--10 12121415-8 10121214158-101012141415

781010121414

15-68910121214

1415

141415

67810101212

15

151414

678910II12

:0,,101, Q,nft, 0,ОПО:0,10П ОДООО. Из диаграммы (фиг. 2) видно, что к диапазону 8-11 частного можно обратиться, первоначально предсказав с помощью цгафратора 4 частное 10.

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

Сумматор-вычитатель 12 предназначен для формирования текущих остатков и может быть реализован любьпи из хорощо известных способов. Функция Сложение или Вычитание

сумматора-вьрттателя определяется значением управляющего сигнала с выхода 27 блока 14 управления. В первом гакте каждого цикла он работает в режиме Вычитание. В последующих тактах режим определяется следующим образом: если в предыдущем такте знак результата сумматора-вычитателя был положительнь1Й, то выполняется вычитание, в противном случае сложение.

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

На фиг. 3 представлена функциональная схема дешифратора 13 для случая k4.Дешифратор 13 содержит узел 18 управления выборкой делителя У, узел 29 управления выборкой двукратного делителя 2У, узел 30 управления выборкой учетверенного делителя 4У, узел 31 управления выборкой восьмикратного делителя 8У и узел 32 управления выборкой произведения, сформированного на выходе блока 5 умножения. Каждый из этих узлов может быть реализован на элементах И-ИЛИ в соответствии со следующими логическими выражениями:

1. ) ИЛИ 1 4 l- v4-Yv8- VX a.( 4./ (4нЛО) Й./ 8цЛО® .

10

.AO,

а

где , например, 14 означает, что содержимое

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

Блок 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).

Так, например запись Per. 9: - А. в операторной вершине 34 следует понимать как регистру 9 присвоить значение, сформированное на выходе шифратора 4. Через М обозначена кратность делителя, хранимого в регистре Значение М в каждом такте работы блока управления определяется дешифратором }3(М в рассматриваемом случае может принимать значение 1, 2, 4 или 8). Микрооперация Сдвиг информации в регистре осуществляется по однотактному принципу на 1 разрядов. В вершине 35 проверяется условие, равно ли значние на выходе узла 32 дешифратора 13 единице Если оно равно единице, то в первом такте цикла определения k цифр частного вьшолняетс умножение и вычитание, в противном случае с помощью коммутатора 11 выбирается значение простого кратного делителя и осуществляется только вьиитание. В условной вершине 39 анализируется знак результата на выходе сумматоравычитателя 12 (Ai9 1, если результат отрицательный,в противном случае ). С помощью условных вершин 40 и 41 определяется окончание цикла определения k цифр частного (если А - l, то цикл определения очередных k цифр частного заканчивается).

Алгоритм работы блока 14 управления предопределяет его структурную и функциональную схемы. На фиг. 5 приведена реализация блока 1 управления в виде микропрограммного устройства управления. Блок управления содержит регистр 49, дешифратор 50, первый 51 и второй 52 узлы памяти и узел 53 задержек, вход 54 блока управления. В узле 51 памяти содержатся адреса микрокоманд, в узле 52 памяти коды микрокоманд, которь е при считывании управляют работой блоков устройства деления в соответствии с ГСА (фиг. 4).

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

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

следующим образом.

В исходном состоянии (начало деления) в регистре 2 делимого хранится прямой гъразрядный код делимого, в регистре 1 делителя Прямой п-разрядный код делителя, регистры 3 и 6 обнулены (здесь предполагается, что делимое и делитель правильные положительные дроби). Каждый цикл определения очередных k цифр частного начинается с обнуления регистра 8 сдвига информации в регистре 3 частного на 4 разрядов в сторону его старших разрядов и предсказания шифратором 4 k Щ1фр частного (в дальнейшем цифра частного), которые записываются в регистр 9 и затем уточняются.

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

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

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

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

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, а максимальное - (k+1), в то время как в предлагаемом устройстве срюднее минимальное число тактов цикла равно 1,5, а среднее максимальное число тактов цикла равно (k-K),5).

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

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

1.Устройство для деления чисел,содержаи1ее регистр делителя, регистры делимого и частного, шифратор, блок умножения, регистр адреса, блок памяти, регистры верхнего и нижнего значений к цифр частного, первый коммутатор и блок управления, причем входы ши(1)раторз соединены с шинами значения 1 старших разрядов регистров делимого и делителя, а выход соединен с первым входом регистра нижнего значения 1 цифр частного, второй вход которого соединен с первым выходом блока памяти, второй выход которого соединен с входом регистра верхнего значения цифр частного, выходы регистров верхнего и нижнего значений k цифр частного, соединены с входами коммутатора, выход которого соединен с первым входом блока умножения, с входом k младших разря дов регистра частного и с входом регистра адреса, выход которого соединен с входом блока памяти, выход регистра делителя соединен с вторым входом блока умножения, вервый и второй входы блока уп равления соединены с выходами младших разря дов регистра соответственно верхнего и нижнего значений ic цифр частного, а его выходы соединены с управляющими входами регистров делимого, делителя и частного, регистров верхнего и нижнего значений -k цифр частного, первого коммутатора и регистра адреса, отличающееся тем, что, с целью увеличения быстродействия, устройство содержит сумма тор-вычитатель, второй коммутатор и дешифратор, входы которого соединены с выходами {зегистров верхнего и нижнего значений k цифр частного, а выход соединен с третьим входом блока управления и с управляющим входом второго коммутатора, информационные входы которого соединены с выходами регистра делителя и блока умножения, а выход соединен с первым входом сумматора-вычитателя, второй вход которого соединен с выходом регистра делимого, а выход - с входом регистра делимого, выход знакового разряда сумматора-вьпитателя соединен с четвертым входом блока управления, дополнительный выход которого соединен с управляющим входом сумматора-вычнтателя. 2. Устройство по п. 1, о т л и ч а ю щ ее с я тем, что блок управления содержит регистр, дешифратор, два узла памяти и узел задержки, причем вход узла задержки соединен с выходом первого узла памяти, а выход - с входом регистра, выход которого соединен с входом дешифратора, выход которого соединен со входом второго узла памяти и с первым входом первого узла памяти, другие входы которого подключены к входам блока управления, выходы второго узла памяти подключены к выходам блока управления. Источники информации, принятые во внимание при зкспертизе 1.Карцев М. А, Арифметика цифровых машин. М., Наука, 1969, с. 494. 2.Патент США №3.234.367 кл. 235-156, 1966 (прототип).

Фиг.З

fi ynpaf/fff/ffo e f/ Sjfoffajv ycfTjpffi/cfr Sa

Л Ф Ф

iMJ

52

50

5i

i t

5

b

fpl.ff