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

и 857977 Оп ИКАНИЕ ИЗОБРЕТЕНИЯ К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскихСоцкалкстичесимхРеспубликаа делам изееретеиий и еткрытий(72) Авторы изобретения Б. В, Цесин и А. А, Шостак Минский радиотехническийаявител ИЯ ЧИСЕЛ(54) УСТРОЙСТВО ДЛЯ блока памяти, второи выход которого соединенс входом регистра верхнего значенияцифрчастного, выходы регистров верхнего и нижнегозначений Ф цифр частного соединены с входамикоммутаторов, выход которого соединен с первым входом блока умножения, с входом 1(младших разрядов регистра частного и с входом регистра адреса, выход которого соединенс входом блока памяп, выход регистра делителясоединен с вторым входом блока умножения,первый и второй входы блока управлениясоединены с выходами младших разрядов регистра соответственно верхнего и нижнего значений к цифр частного, а его выходы соединены с управляющими входами регистровделимого, делителя и частного, регистровверхнего и нижнего значений к цифр частного, первого коммутатора и регистра адреса 2. Недос ется отно стане бол ния 1( ци цикле альноеИзобретение относится к вычислительной тех.нике и может быть использовано в быстродейст- .вующих, арифметических устройствах для делениичисел,Известно устройство для деления чисел, содержащее регистры делимого, делителя и частного,сумматор, блок управления 1,Недостатком известного устройства являетсянизкое быстродействие вследствие формированияв каждом цикле деления одной цифры частного.Наиболее близким к предлагаемому является 1 фустроиство для деления чисел, формирующее вкаждом цикле деления % цифр частного (т( 2,3, 4,., и/2, где п - разрядность обрабатываемойинформации), содержащее регистр делителя, регистры делимого и частного с цепями однотакт. 1 зного сдвига наразрядов, шифратор, блокумножения, регистр адреса, блока памяти, ре.гистры верхнего и нижнего значенийцифрчастного, коммутатор и блок управления, при.чем входы шифратора соединены с шинами зла Ечений 4 с старших разрядов регистров делимогои делителя, а выход соединен с первым входомрегистра нижнего значения ( цифр частного, второй вход которого соединен с первым выходом татком известного устройства являительно низкое быстродействие вследшой длительности цикла формировар частного, который формируетсяо многотактному принципу Мннисло тактов в цикле равно двум,857977 о 15 максимальное - (Э+1). Время выполнения дсления двух и разрядных чисел примерно равногде Т, - среднее время цикла формированияцифр частного.В первом приближении максимальное и минимальное время Т,равнощахТ =(К 1) ьу, Тгде ьу - временная задержка блока умножения (здесь предполагалось, что вычитание в известном устройстве перекрывается во времени с умноже.нием),Цель изобретения - увеличение быстродействия известного устройства за счет уменьшения врсмени цикла формирования М цифр частного,Поставленная цель достигается тем, что вустройство для деления чисел, содержащее ре. гистр делителя, регистры делимого и частного, шифратор, блок умножения, регистр адреса, блок памяти, регистры верхнего и нижнего значений к цифр частного, первый коммутатор и блок управления, причем входы шифратора соединены с шинами значений Ф старших разрядов регистров делимого и делителя, а выход соединен с первым входом регистра нижнего значения к цифр частного, второй вход которого соединен с первым выходом блока памяти, второй выход которого соединен с входом регистра верхнего значения Ф цифр частного выходы регист. ров верхнего и нижнего значений Ф цифр частного соединены с входами коммутатора, выход которого соединен с первым входом блока умножения, с входом 1 с младших разрядов регистра частного и с входом регистра адреса, выход которого соединен с входом блока памяти, вход регистра делителя соединен с вторым входом блока умножения, первый и второй входы блока управления соединены с выходами младших разрядов регистра соответственно верхнего и нижнего значений к цифр частного, а его выходы соединены с управляющими вхо. дами регистров делимого, делителя и частного, регистров верхнего и нижнего значений к цифр частного, первого коммутатора и регистра адреса, введены сумматор-вычитатель, второй комму. татор и дешифратор, входы которого соединены с выходами регистров верхнего и нижнегозначений к цифр частного, а выход соединен с третьим входом блока управления и с управляющим входом второго коммутатора, информационные входы которого соединены с вы. ходами регистра делителя и блока умножения, а выход - с первым входом сумматора - вы-. читателя, второй вход которого соединен с выходом регистра делимого, а выход - с вхо.дом регистра делимого, выход знакового разря да сумматора - вычитателя соединен с четвер. тым входом блока управления, дополнительный выход которого соединен с управляющим входом сумматора вычитателя. 20 25 30 35 40 45 50 55 4Блок управления содержит регистр, дешифратор, два узла памяти и узел задержки, при ,чем вход узла задержки соединен с выходом первого узла памяти, а выход - с входомрегистра, выход которого соединен со входомдешифратора, выход которого соединен с входом второго узла памяти и с первым входом первого узла памяти, другие входы которого 1 подключены к входам блока управления, выхо ды второго узла памяти подключены к выходам блока управления.На фиг, 1 приведена структурная схема пред. лагаемого устройства для деления чисел", на фиг. 2 - диаграмма выборки из блока памяти верхнего и нижнего значений к цифр частного; на фиг, 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 верхнего значения 1 с цифр частного, выходы регистров 8 и 9 верхнего и нижнего значений 1 с цифр частного соединены со входами дешифратора 13 и первого коммутатора 10, выход которого соединен с первым входом блока 5 умножения, с входом к младших разрядов регистра 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 Осистема счисления двоичная, а число К одновре. менно формируемых в цикле цифр частного равно четырем (на диаграмме к двоичных цифр заменены целым шестнадцатиричным эквивалентом). Выборка в каждом такте цикла (за ис. ключением первого такта) верхнего илн нижнего значения с цифр частного осуществляется с помощью первого коммутатора 10 под действием управляющего сигнала с выхода 26 блока 14 управления, причем если в предыдущем такте цикла результат сумматора-вычитателя 12 был положительный, то выбирается верхнее значение с цифр частного из регистра 8, в противном случае выбирается его нижнее значение из регистра 9. В первом такте каждого цикла выбирается всегда нижнее значение к цифр частного из регистра 9,Шифратор 4 предназначен для предсказания цифр частного по значению Й старших разрядов делимого и делителя и может быть реализован в виде быстродействующей комбинационной схемы в соответствии с таблицей (4).= 0,01 О:0,10 1=0,1000 2) видно, что к диана жно обратиться, перво помощью шифратора 4:0,101 Р,101 ЧеьИз диаграммы (фиг.ну 8 - 11 частного мочально предсказав счастное 10,Блок 5 умножения предназначерования произведения и-разр-разрядное частное, Предлореализован в вир,е быстродейнационной матричной схемы.ычитатель 12 предназначентекущих остатков и можеым из хорошо известных"Сложение" или "Вычита н для форм ядного делителя налагается, что он ствуюшей комби. Сумматор-вформированияреализован любсобов. Функция ыть ие" 5с управляющими входами регистров 2, 1 и 3делимого, делителя и частного, регистра 6 адреса, регистров 8 и 9 верхнего и нижнего значенийцифр частного, первого коммутатора10 и сумматора-вычитателя 12 соответственно.В данном устройстве регистры 1, 2 и 3 делителя, делимого и частного, регистр 6 адреса,регистры 8 и 9 верхнего и нижнего значенийй цифр частного могут быть построены на основе двухтактных синхронных О-триггеров.В качестве блока памяти может быть использо.вана постоянная (например в виде шифратора),либо быстродействующая оперативная (регистро.квая) память емкостью 2 - 1 2 Ы-разрядныхслов, С помощью регистра 6 адреса, блока 7памяти, регистров 8 и 9 верхнего и нижнегозначений % цифр частного и первого коммута.тора 10 осуществляется последовательная подборка в цикле к цифр частного,На фиг. 2 изображена диаграмма выборкииз блока 7 памяти верхнего и нижнего значенийк цифр частного для случая, когда используемая6 Таблица строится следующим образом. 45Определяются максимальное и минимальноезначения с цифр частного й при соответствую.щих значениях старших разрядов делимого и,делителя, т, е, диапазон возможных значении с цифр частного.150По полученному диапазону из диаграммына фиг. 2 определяется то значение частного, покоторому путем последовательных выборок можно выделить любое значение 1 с цифр частногоиз вычисленного диапазона, Это значение М55цифр частного заносится в таблицу.Например, пусть стариае четыре разрядаделимого и делителя соответственно равны 6 н10, т.е. 0,0110 и 0,3010, Тогда Яд,д-".01101111: 9 10 11 12 13 14 15сумматора.вычитателя определяется значением управляющего сигнала с выхода 27 блока 14 управления. В первом такте каждого цикла он работает в режиме "Вычитание". В последующих тактах режим определяется следующим образом: если в предыдущем такте знак ре. зультата сумматора - вычитателя был положительный, то выполняется вычитание, в противном случае сложение.Второй коммутатор 11 вместе с дешифрато. ром 13 определяют, что необходимо подать на один из входов сумматора-вычитателя; либо значение произведения, сформированного на выходе блока 5 умножения, либо значение делителя или его простого кратного, полученного путем соответствуюгцего сдвига. Коммутатор может быть реализован на элементах И - ИЛИ.На фиг, 3 представлена функциональная схема дешифратора 13 для случая Йф 4.Дешифратор 13 содержитузел 18 управле 20 ния выборкой делителя У, узел 29 управления выборкой двукратного делителя 2 У, узел 30 управления выборкой учетверенного делителя 4 У, узел 31 управления выборкой восьмикратного делителя 8 У и узел 32 управления выбор 25 кой произведения, сформированного на выходе блока 5 умножения. Каждый из этих узлов может быть реализован на элементах И - ИЛИ в соответствии со следующими логическими выражениями:1 Ч:1 ЧЪ ч 5 Ч 7 Ч 9 Ч 11 чЬ Ч 15 Ч(1 ИАО )ЭО или 1 Ч: 1 ЧчЦ 1 чЭ 1 ЧХ3:й ч 14 ч(Ъ,ЛО )4.:Р ( О)13.=8 ц 08Мю=8 ч 4-ч ч лО,где, например, 14 означает, что содержимоеЬрегистра 8 верхнего значения с цифр частного 40 равно 1110, а 8 и означает, что содержимое регистра 9 нижнего значенияцифр частного равно 1000. Выход узла 32 дешифратора 13 поступает как на управляющий вход второго коммутатора 11, так и на первый дополнитель. 45 ный вход блока 14 управления. Именно он "сообщает" блоку 14 управления, что будет вы. полняться в первом такте цикла: умножение с вычитанием или только вычитание. Во всех последующих тактах цикла выполняется либо только сложение, либо только вычитание. Окон. чание цикла формирования с цифр частного определяется блоком 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 единице.Если оно равно единице, то в первом тактецикла определения М цифр частного выполняетсяумножение и вычитание, в противном случае спомощью коммутатора 11 выбирается значениепростого кратного делителя и осуществляетсятолько вычитание. В условной вершине 39 анализируется знак результата на выходе сумматоравычитателя 12 (А =1, если результат отрицательный,в противном случае АО=О). С помощьюусловных вершин 40 и 41 определяется окончание цикла определения Й цифр частного (если .А.гт Ав=1, то цикл определения очередных% цифр частного заканчивается).Алгоритм работы блока 14 управления предопределяет его структурную и функциональнуюсхемы, На фиг. 5 приведена реализация блока 14управления в виде микропрограммного устройства управления, Блок управления содержит регистр 49, дешифратор 50, первый 51 и второй52 узлы памяти и узел 53 задержек, вход 54блока управления. В узле 51 памяти содержат.ся адреса микрокоманд, в узле 52 памяти -857977 15 ЭО коды микрокоманд, которые при считыванииуправляют работой блоков устройства деленияв соответствии с ГСА (фиг. 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. Рассмотрим последовательно работу устройства по определению точного значения частного (цикл определения пифры частного),401-й такт, Из содержимого регистра 2 делимого вычитается в сумматоре.вычитателе 12произведение содержимого регистра 1 делителяна цифру 12 частного, а получившийся при этомположительный результат заключается в регистр2 делимого. Одновременно с этим по адресу 12из блока памяти 7 в регистры 8 и 9 записываются цифры 14 и 10 соответственно. Длительность такта в основном определяется временемумножения, 502-й такт. Из содержимого регистра 2 делимо.го вычитается в сумматоре-вычитателе 12 удвоенное значение содержимого регистра 1 делителя,а получившийся при этом отрицательный результат записывается в регистр 2 делимого. Одновременно с этим по адресу 14 из блока памяти7 в регистры 8 и 9 записываются цифры 15и 13 соотвстствспцо. 3 Ьительпость такта, в основном, опрслспяс 1 ся врсмепем вычитания. 103-й такт. К содержимому регистра 2 делимого прибавляется в сумматор.вычитатель 12 содержимое регистра 1 делителя, а получившийсяпри этом положительный результат записываетсяв регистр 2 делимого. Одновременно с этим поадресу 13 из блока памяти 7 в регистры 8 и 9записываются цифры 13 и 12 соответственно.Длительность такта, в основном, определяетсявременем сложения.4-й такт является последним в рассматриваемом цикле определения точного значенияцифры частного, так как значения младших раз.рядов регистров 8 и 9 равны соответственно"1" и "0". В нем производится запись цифры13 в младшие четыре разряда регистра 3 частного, а также однотактньй сдвиг информациина четыре разряда в сторону старших разрядовв регистре 2 делимого. В этом такте не вы.полняется ни операция "умножение", ни операция сложение- вычитание". В дальнейшемтакты, подобные описанному, будут исключеныиз рассмотрения ввиду их быстрого выполнения(отсутствуют наиболее длительные операции,такие как умножение или сложение).Более высокое быстродействие предлагаемогоустройства в сравнении с известным определя.ется следующим,В известном устройстве длительность каждого такта цикла формирования М цифр частногоопределяется временем умножения, в то времякак в предлагаемом устройстве только длительность первого такта цикла определяется временемумножения, Длительность последующих тактовцикла определяется временем сложения (вычитания),В предлагаемом устройстве, если предсказанная шифратором цифра частного есть 1, 24,8,., 2, длительность первого такта цикла, такжекак и длительность последующих тактов, определяется временем сложения (вычитания).В известном устройстве минимальное числотактов в цикле равно 2, а максимальное -(1 с+1), в то время как в предлагаемом устройстве среднее минимальное число тактов цикларавно 1,5, а среднее максимальное число тактов цикла равно (4 сЮ,5).Объем дополнительно введенного оборудования в данном устройстве незначителен и равенпримерно оборудованию простого дешифратораи коммутатора. Формула изобретения 1,Устройство для деления чисел, содержащее регистр делителя, регистры делимого и частного. шифратор, блок умножения, регистр адреса, блок памяти, регистры верхнего и нижпего значений к цифр частного, первый коммутатор и блок управления, причем входы шифратора11 85797 соединены с шинами значения % старших раэря.дов регистров делимого и делителя, а выход соединен с первым входом регистра нижнего значенияцифр частного, второй вход которого соединен с первым выходом блока памяти, второй выход которого соединен с входомрегистра верхнего значения % цифр частного, выходы регистров верхнего и нижнего значений Й цифр частного соединены с входами коммутатора, выход которого соединен с первым входом блока умножения, с входом 1 с младших раэря. дов регистра частного и с входом регистра адреса, выход которого соединен с входом блока памяти, выход регистра делителя соединен с вторым входом блока умножения, жрвый и второй входы блока уп. равления соединены с выходами младших разрядов регистра соответственно верхнего и нижнего значений цифр частного, а его выходы соединены с управляющими входами регистров делимого, делителя и частного, Регистров верх 20 него и нижнего значенийцифр частного, пер.вого коммутатора и регистра адреса, о т л и .ч а ю щ е е с я тем, что, с целью увеличе.ния быстродействия, устройство содержит сумматор-вычитатель, второй коммутатор и дешифра 25 тор, входы которого соединены с выходами регистров верхнего и нижнего значений М цифр частного, а выход соединен с третьим входом блока управления и с управляющим входом 7 12второго коммутатора, информационные входыкоторого соединены с выходами регистра делителя и блока умножения, а выход соединен спервым входом сумматора-вычитателя, второйвход которого соединен с выходом регистраделимого, а выход - с входом регистра делимого, выход знакового разряда сумматора.вычита.теля соединен с четвертым входом блока управления, дополнительный выход которого соединен с управляющим входом сумматора-вычитателя.2, Устройство по п, 1, о т л и ч а ю щ ее с я тем, что блок управления содержитрегистр, дешифратор, два узла памяти и узелзадержки, причем вход узла задержки соединенс выходом первого узла памяти, а выход - свходом регистра, выход которого соединен свходом дешифратора, выход которого соединенсо входом второго узла памяти и с первымвходом первого узла памяти, другие входыкоторого подключены к входам блока управления, выходы второго узла памяти подключенык выходам блока управления.Источники информации,принятые во внимание при экспертизе1. Карцев М. А, Арифметика цифровых ма.шин. М., "Наука", 1969, с. 494,2, Патент США Иф 3.234.367 кл. 235 - 156,1966 (прототип).857977 ЮуираЬаюцеиу ЬодамуслраиьъЯг Заказ 7245(79 Тираж 745ВНИИПИ Государственного комитета СССРпо делам изобретений и открытий113035, Москва, Ж, Раушская наб., д, 4(5 одписное лиал ППП Патент", г. Ужгород, ул, Проектная,Составитель В. КайдановРедактор П. Ортутай Техред Л, Пекарь Корректор М Коста