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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 09) (11) 6 Р 7/52 ОСУДАРСТВЕНПО ДЕЛАМ КОМИТЕТ СССР РЕТЕНИЙ И ОТКРЫТИЙ(21) 3514625 (22) 25,10.8 (46) 07.04.8 (72) С.И.Гав (71) Кировск институт (53) 681,325 563 1. Авто Р 331386, кл 8 Бюл. В 13илиий политехнически 088. 8)ское свидетельств0 Об Р 7/52, 197 СССР сд ля сдвига и ных соедине вход которо счетчика, вх тактовым вхо ход формиро управляющим го, третьего сдвига. ОПИСАНИЕ К А 8 ТОРСКОМУ С 2. Авторское свидетельство СССР570054, кл. 0 06 Р 7/52, 1977 (прототип).(54) (57 УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ДВОИЧНЫХ ЧИСЕЛ, содержащее регистры делимого и делителя, первый и вто- . рой сумматоры, причем выходы регистров делимого и делителя соединены соответственно с первыми и вторыми. входами первого и второго сумматоров, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия путем сокращения времени выполнения каждой итерации, в него введены сумматор результата, блок анализа переменных, первый, второй,третий и четвертый блоки сдвига,дешифратор, счетчик и формирователь сдвига, содержащий к групп из двух элементов И и элементов ИЛИ где первые входы первого и второго элементов И каждой группы объединены и являются разрядными входами формирователя сдвига, вторые входы первых элементов И групп объединеныи являются первым управляющим входом Формирователя сдвига, вторые входы вторых элементов И групп объединены и являются вторым управляющим входом Формирователя сдвига, выходы второго элемента И 1 к) -ой группы и первого элемента И к-ой группы соединены соответственно с первыми и вторыми входами элементов ИЛИ к) -ой группы, выходы которых являются разрядными выходами формирователя сдвига, причем первый и второй сумматоры устройства выполнены как сумматоры-вычитатели регистры делимого и делителя выполнены в виде отдельных регистров для положительной и отрицательной частей делимого и.делителя соответственно, поступающих на них в избыточной двоичной системе счисления, выходы регистров делимого соединены соответственно спервым и вторым входами сумматора результата и информационными входами первого и второго блоков сдвига, выходы которых соединены.соответственно с третьими и четвертыми входами первого сумматоравычитателя, выходы которого соединены соответственно с входами ре- гистров делимого, выходы регистров делителя соединены соответственно с информационными входами третьего и четвертого блоков сдвига, выходы которых соединены соответственно с третьим и четвертым входами второго сумматора-вычитателя, выходы которого соединены соответственно свходами регистров делителя, выходы старших разрядов регистров делителя соединены с первым входом блокаанализа переменных, первый выход которого соединен с управляющими входами сумматоров-вычитателей, второй выходс управляющим входом формирователя вига; разрядные входы Формироватеблока анализа переменны с выходом дешифратора, го соединен с выходом од счетчика соединен с дом устройства, а вывателя сдвига соединен с и входами первого, второи,четвертого блоковИзобретение относится к вычислительной технике и может быть использовано при построении специальных.вычислительных систем,Известно устройство для делениядвоичных чисел, содержащее регистры делимого и делителя, пирамидусумматоров, элементы И, ИЛИ 1 .Недостатком данного устройстваявляется его конструктивная сложность, т,к. количество используемых 10сумматоров с разделением цепей суммы и переносов пропорционалвноквадрату разрядности устройства.Наиболее близким по техническойсущности к изобретению является устройство для деления, содержащее регистры делимого и делителя, дваблока элементов И, два сумматора,блок управления, причем поразрядныевыходы регистра делимого подключенык соответствующим входам первогоблока элементов И, выход которогоподключен к первому входу первогосумматора, второй. вход .которого подключен к выходу младшего разрядарегистра делимого, старший разрядкоторого подключен к выходу первогосумматора, третий вход которогоподключен к выходу блока управленияи к первому входу второго сумматора,второй вход которого подключен квыходу младшего разряда регистра де-щютеля, поразрядные выходы которогоподключены к соответствующим входамвторого блока элементов И, выходкоторого подключен к третьему входу второго сумматора, выход которого подключен к входу старшего разряда регистра делителя, второй выход блока управления подключен квторым входам блоков элементов И, 40выход второго сумматора подключен квходу блока определения переполнения, выход которого подключен квходу блока управления 2 .45Недостатком, известного устройства является его низкое быстродействие.Целью изобретения является позышение быстродействия устройства за счет сокращения времени выполне- ния каждой итерации.Поставленная цель достигается тем, что в устройство для деления двоичных чисел, содержащее регистры делимого и делителя, первый и вто рой сумматоры, причем выходы регистров делимого и делителя соединены соответственно с первыми и вторыми входами первого и второго сумма-. торов, введены сумматор результата, 60 блок анализа переменных, первый, второй, третий и четвертый блоки сдвига, дешифратор, счетчик и формирователь сдвига, содержащий к гРУпп .из двух элементов И и эле- " 65 мента ИЛИ, где первые входы первого и второго элементов И каждой группы объединены и являются разрядными входами формирователя сдвига, вторые входы первых элементов И групп объединены и являются первым управляющим входом формирователясдвига, вторые входы вторых элементов И групп объединены и являются вторым управляющим входом формирователя сдвига, выходы второго элемента И к) -ой группы и первого элемента И к-ой группы соединены соответственно с первыми и вторымц входами элементов ИЛИ (к)-ой груЪ- пы, выходы которых являются разрядными выходами формирователя сдвига, причем первый и второй сумматоры устройства выполнены как сумматорывычитатели, регистры делимого и делителя выполнены в виде отдельных .Регистров для положительной и отрица-тельной частей делимого и делителя соответственно, поступающих на них в избыточной двоичной системе счисления, выходы регистров делимого соединены соответственно с первым и вторым входами сумматора результата и с информационными входами первого и второго блоков сдвига, выходы которыа соединены соответственно с третьими и четвертыми входами первого сумматора-вычитателя, выходы которого соединены соответственно с входами регистров делимого, выходы регистров делителя .соединены соответственно с информационными входами третьего и четвертого блоков сдвига, выходы которых соединены соответственно с третьим и четвертым входами. второго сумматора-вычитателя, выходы которого соединены соответственно с входами регистров делителя, выходы старших разрядов регистров делителя соединены с первым входом блока анализа переменных, первый выход которого соединен с управляющими входами сумматороввычитателей, второй выход -, с управляющим входом формирователя сдвига, разрядные входы формирователя сдвига и блока анализа переменных соединены с выходом дешифратора, вход которого соединен с выходом счетчика, вход счетчика соединен с тактовым входом устрайства, а выход формирователя сдвига соединен с. управляющими входами первого, второго, третьего и четвертого блоков сдвига.На фиг.1 представлена функциональная схема устройства для деления двоичных:чисел; на фиг,2 - функциональная схема Формироваееля сдвига для трех разрядов.Устройство содержит регистры 1 и 2 делимого, регистры 3 и 4 делитеО ля, сумматор 5 результата, первыйи второй сумматоры-вычитатели б и 7,первый, второй, третий и четвертыйблоки 8 - 11 сдвига, блок 12 анализа переменных, формирователь 13сдвига, дешифратор 14, счетчик 15,5тактовый вход 16 и выход 17 устройства, причем выходы регистров 1 и 2 делимого соединены соответственно свходами сумматора 5 результата,с входами блоков 8 и 9 сдвига ис первым и вторым входами первогосумматора-вычитателя 6, выходы кото-.рого соединены соответственно с входами регистров 1 и 2 делимого, выходы старших разрядов регистров 3 5и 4 делителя соединены с первым входом блока 12 анализа переменных, выходы остальных разрядов регистров3 и 4 делителя соединены соответст-.венно с входами блоков 10 и 11 сдви Ога и с первым и вторым входами второго сумматора-вычитателя 7 ф, выходыкоторого соединены соответственно свходами регистров 3 и 4 делителя,выходы блоков 8 и 9 сдвига соединены 25с третьим и четвертым входами сумматора-вычитателя 6, выходы блоков 10;11 сдвига соединены с третьим и четветрым входами сумматора-вычитателя 7, управляющие входы блоков 8-11сдвига соединены с выходом Фопмирователя 13 сдвига, информационныевходы которого соединены соответ ственно с выходами дешифратора 14,.входы которого соединены с выходами счетчика 15, на вход счетчика 15поступают импульсы тактовой частоты с входа 16 устройства, выходыдешифратора 14 соединены с информационными входами блока 12 анализапеременных, первый выход которого 40соединен с управляющим входом формирователя 13 сдвига, а второй выход -с управляющими входами сумматороввычитателей б и 7, выход счетчика 5результата является выходом 17 устройства,Формирователь 13 сдвига фиг.2)содержит к групп из двух элементовИ 18 и 19 и элемента ИЛИ 20, причемпервые входы первого и второго эле рментов И 18 и 19 каждой группы объединены и являются информационнымивходами Формирователя 13 сдвига,. вторые входы первых элементов. И 18групп и вторые входы вторых элемен 55тов И 19 групп являются управляющими входами формирователя 13 сдвига,выходы второго элемента И 19 к-ойгруппы и первого элемента И 18к) -ой группы соединены соответст-.венно с первыми и вторыми входами элементов илй 20 к) -ой группы,выходы которых являются разрядными выходами формирователя 13 сдвига.Устройство работае следующимобразом,Деление выполняется в избыточнойсистеме счисления. Ь этой системелюбое к-разрядное число Х (1 Х 1 с 1)представляется в видеХ: Х+-Х-) -Р(ЦРф 1 Р Р 7где Хй0,1 - положительная цифра р-го разрядаеХ Е 0,1 - отрицательная цифра р-.го разряда;р=1,К - номер разряда.Процесс вычисления частного основывается на следующих равецствах,Лелитель представляется в видегде С е 0,1, Е.(-1,0,1; р=1,Кномер итерации.Тогда значение частного представляетсяв виде .Х/У=Х .б1+ЕР 21, 3)Иэ ,2) йолучаем тождествоу П +Е 2-(р-с(4).На основании (3) и ,4) процесСделения представится следующими рекуррентными выражениямиХ Р 2 11+Ер 2Р . (5)УР - 2 1+Е 2 Р Дгде Р=1,2. К; Е Е -1,0,+1;СЕ 0,13Начальные условия: Х =Х, У =У.Результат: ХК=Х/У, У =1.Переменные Ер и С на каждой р-ойитерации определяются по значениям старших разрядов Ур таким образом, чтобы первый после запятой разряд Ур в результате выполнения (6)принимал нулевое значение. При этомпеременная УР стремится к значениюУц=1, а переменная ХР - к значениюХ=Х/У.В табл. 1 приведена зависимость значения ЕР и С от значени старших разрядов переменной У . Ер,Ердвоичные переменные управления сумматорамиЕр=Ер-Ер,г Ер,г Ерш 0,1Чб 0,1- переменная номера итерации у =1 при р=1, ф =0 при р=2 К Прочерками в табл.1 обозначеныслучаи, когда значение переменной невлияет на выходные сигналы.В устройстве регистры 1 и 2 делимого и регистры 3 и,4 делителя предназначены соответственно для хранения переменных ХР, УР представленных в избыточной системе счисления. Каждый регистр содержит (:К+1) разрядов, к разрядов для дробной части и один разряд для целой части переменной. Каждый разряд регистров представляет собой обычный двоичный триггер. В регистре 1 хранятся поло жительные цифры Хр, в регистре 2 отрицательные цифры Х, р=1,К) пере менной Х, В регистре 3 и 4 соответственно хранятся цифры УР, Ур (Р=1,К) переменной У. 1 ЬВ табл. 2 приведено сортветствие между цифрами и значением разряда переменных Х и У.Таблица 2 20 х Ур У Р25 ЗО 0 С фцУ, Ч, ЧЧ Уч цУ, У, УУУ ЧчУГ 1 3 ) 65 Сумматор 5 предназначен для пре-,3образования результата деления,хранящегося в .конце вычислений нарегистрах 1 и 2, из избыточной системы счисления в двоичную и для хранения результата, выполнен в виде 40параллельного сумматора накапливающего типа с распространением переноса на всех к разрядов.Сумматоры-вычитатели б и 7 предназначены для выполнения сложениявычитания над числами в избыточной, системе счисления на каждом итерационном шаге вычислений.Блоки 8 - 11 сдвига предназначены для параллельного сдвига содер 50жимого регистров 1 - 4 на (р-с) разрядов влевоБлок анализа переменных предназначен для реализации логической функции,представленной в табл.1, т.е. для . 55определения по старшим разрядам переменной УР и номеру итерации управляющиМ переменных С, Ер Е накаждом итерационном шаге. Блок 12анализа реализует следующие логические Функции в соответствии с таблицей истинности 1; Е =СУ,У- чу 7; У,У",чс,УЧ-, ч чя 1 г 2 3 Уэй) чЧ ЧЧчц. М Блок 12 анализа выполнен на логических схемах И и ИЛИ. Значения пе+ - + - Ф ременных У, Ук У У, У, У 3 .поступают на первый вход блока анализа с регистров 3 и 4, а переменнаяна второй вход блока 12 анализа поступает с дешифратора 14.Формирователь 13 сдвига (Фиг.2) предназначен для формирования величины сдвига (р-с) Значениепоступает на первый вход Формирователя 13 с дешифратора 14, значение С поступает на второй вход с второго выхода блока 12 анализа. Укаэанное преобразование выполняется в формирователе 13 на элементах И 18 и 19 и элементе ИЛИ 20.Счетчик 15 и дешифратор 14 предназначены для счета номера итерации и его дешифрации.Деление производится над положительными числами, знак результата определяется по сочетанию знаков деделимого и делителя. Перед началом вычисления в регистры 1 и 3 заносятся сдвинутые влево на один разряд двоичные числа - делимое 2 Х и делитель 2 У. Далее производится выполнение к итераций в соответствии с уравнениями (5),(б).На каждой итерации производятсяследующие действия,В счетчике 15 тактов производится прибавление единицы по синхроимпульсу с входа 16, в дешифраторе 14производится дешифрирование кода номера итерации р, значение которогопоступает на первый вход формирователя 13 сдвига. Одновременно в блОке. 12 анализа переменных по значениям старших разрядов регистров3 и 4 фомируются значения переменных С, Е, Е значения Е Е поступают с второго выхода блока 12анализа на управляющие входы первого и второго сумматоров вычитателей,6 и 7 значение С - на второй входформирователя 13 сдвига. В формирователе,13 сдвига формируется величина р-с 1, которая поступает науправляющие входы блоков 8 - 11 сдвига. В.этих блоках производится сдвигсодержимого регистров 1 - 4 вправона р-с) разрядов, что равнозначноумножению переменных ХР и Ур на2 фЗатем в сумматорах-вычитателяхб и 7 производится алгебраическоесложение переменных ХР и Ур соответственно со сдвинутыми вправо пере1 О 1084785 менными Е Х роф 1 Ъ Е У 2 со-с 1 в соответствии с уравнениями 5 и б),Р Р, РРВ результате на выходах сумматоров вычитаталей 6 и 7 формируются переменнае 1/2 Хр+1 и 1/2 Ур в избыточной двоичной системе, которые записываются на регистрах 1 - 4 со сдвигом на один разряд, При этом в регистрах значенияпеременных ХР, У записываются на их новые значения ХР 1 Уро 1. вычисленные в данной10фитерации.При сдвигах влево в регистрах 3 и 4 старшие разряды переменной УР теряются. Однако оставшиеся раз-, ряды дробной части обеспечивают 15 правильное выполнение алгоритма деления.После выполнения к итераций в регистрах 1 и 2 хранится результат деления Х=Х/У, представленный в избыточной двоичной системе счисления. Преобоазование результата вобычную двоичную систему производится на сумматоре 5 результата с распро.странением переноса. Преобразование насумматоре 5 результата сводится .калгебраическому сложению двух двоичных чисел, представленных на регистрах 1 и 2,В табл.3 приведен пример деления двоичных чисел Х=0,10010,У=0,1011011. В конце таблицы прнведено преобразование ревульата из избыточной в обычную двоичную систему. счисления путем алгебраического сложения положительной и отрицательной частей избыточного результата,20 Та блица 3 9 ите- Переменраций ная ЕРР Значения разрядов Урпеременная У ) 0,10110111, 1011 0110000 0,1001001,0010000000 1,000-1-1-10Т,ооо 100001 оооо 1-110-11-11;ИТ-1-111 1,-111-10-1-11-1 1,0000 ОООЯ 0001,00000 ЯЯ 001,0000000000 1,-111-10-1-11-1 1,-111-10-1-11-1 Преобразование 1-011000010 0,100101101 0,110010101 Результат в предлагаемом устройстве по сравнению с, известным.Устройство для деления двоичных чисел выполнено на современных интегральных микросхемах для больших разрядностей при приемлемых аппаратурных затратах. Высокая регулярность и однородность структуры устройства позволяет эффективно реализовать его на интегральных микросхемах с повышенной степенью интеграции. Выполнение итераций в устройстве может быть прекращено на любой р-ой итерации, если все разряды УР окажутся нулевыми. Это позволяет дополнительно повысить среднее быстродействие устройстваИспользование новых элементов - регистров положи тельной и отрицательной частей делимого и,делителя, сумматоров-вычитателей, формирователя сдвига, блошка анализа и сумматора результата сокращает время выполнения итерации 65 Перемен.ная С 0т 1 -1 0 Значения разрядов ХР1084785 Составитель В.Гусерышева ТехрЕд А.Вабинец ск рректор Редактор Т,9ого,комитетний и открытРаушская на 11/43 Тираж б ВНИИПИ Государствен по делам изобрет 113035, Иосква, Ж, акаэ д. 4 город, ул. Проектная, 4 илиал ППП "Патентф,. г ПодписноСССР.й