Устройство для деления двоичных чисел
Патент 1084785
Авторы
Классы МПК
Устройство для деления двоичных чисел
Иллюстрации
Реферат
УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ДВОИЧНЫХ ЧИСЕЛ, содержащее регистры делимого и делителя, первый и вто- . рой сумматоры, причем выходы регистров делимого и делителя соединены соответственно с первыми и вторыми входами первого и второго сумматоров, отличающееся тем, что, с целью повышения быстродействия путем сокращения времени выполнения каждой итерации, в него введены сумматор результата, блок анализа переменных,первый,второй,третий и четвертый блоки сдвига,дешифратор , счетчик и формирователь сдвига , содержащий к групп из дэух элементов И и элементов ИЛИ,, где первые входы первого и второго элементов И каждой группы объединены и являются разрядными входами формирователя сдвига, вторые входы первых элементов И групп объединены и являются первым управляющим входом формирователя сдвига, вторые входы вторых элементов И групп объединены и являются вторым управляющим входом формирователя сдвига, выходы второго элемента И(к-1) -ой группы и первого элемента И к-ой группы соединены соответственно с первыми и вторыми входами элементов ИЛИ .(к-1)-ой группы, выходы которых являются разрядными выходами формирователя сдвига, причем первый и второй сумматоры устройства выдолнены как сумМаторы-вьгчнтатели, регистры делимого и делителя выполнены в виде Ьтдельных регистров для положительной и отрицательной частей делимого и делителя соответственно, поступающих на них в избыточной двоичной системе счисления, выходы регистров делимого соединены соответственно спервым и вторым входами сумматора результата и информационными входами первого и второго блоков сдвига, выходы которых соединеi ны соответственно с третьими и четвертыми входами первого сумматора (Л вычитателя, выходы которого соединены соответственно с входами регистров делимого, выходы регистров делителя соединены соответственно с информационными входами третьего и четвертого блоков сдвига, выходы которых соединены соответственно с третьим и четвертым входами второго сумматора-вычитателя, выходы коСХ ) торого соединены соответственно С входами регистров делителя, выходы старших разрядов регистров делителя соединены с первым входом блокаанализа переменных, первый выход котоСХ СП рого соединен с управляющими входами сумматороввычитателей, второй выходс управляквдим входом формирователя сдвига, разрядные входы формирователя сдвига и блока анализа переменных соединены с выходом дешифратора, вход которого соединен с выходом счетчика, вход счетчика соединен с тактовым входом устройства, а выход формирователя сдвига соединен с управляющими входами первого, второго , третьего и четвертого блоков сдвига.
(19) (11) СОЮЗ СОВЕТСКИХ
СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК
3(51) G 06 F 7/52
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
К ABTOPCHOMV СВИДЕТЕЛЬСТВУ
-с
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
IlO ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫЛИ (21) 3514625/18-24 (22) 25.10.82 (46) 07.04.84.. Вюл. В 13 (72) С.И.Гаврилин
71) Кировский политехнический институт (53) 325(088.8) (56Y 1. Авторское свидетельство СССР
9 331386, . G 06 F 7/52, 1971.
2. Авторское свидетельство СССР
)) 570054, кл. G 06 F 7/52, 1977 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ДВОИЧНЫХ ЧИСЕЛ, содержащее регистры делимого и делителя, первый и вто- . рой сумматоры, причем выходы регистров делимого и делителя соединены соответственно с первыми и вторыми. входами первого и второго сумматоров, о т л и ч а ю щ е е с я . тем, что, с целью повышения быстродействия путем сокращения времени выполнения каждой итерации, в него введены сумматор результата, блок анализа переменных, первый, второй,третий и четвертый блоки сдвига,дешифратор, счетчик и формирователь сдвига, содержащий к групп из двух элементов И и элементов ИЛИ,, где первые входы первого и второго элементов И каждой группы объединены и являются разрядными входами формирователя сдвига, вторые входы первых элементов И групп объединены и являются первым управляющим входом формирователя сдвига, вторые входы вторых элементов И групп объединены и являются вторым управляющим входом формирователя сдвига, выходы второго элемента И(к-1) -ой группы и первого элемента И к-ой группы соединены соответственно с первыми и вторыми входами элементов ИЛИ (к-1) -ой группы, выходы которых являются разрядными выходами формирователя сдвига, причем первый и второй сумматоры устройства выполнены как сумматоры-вычитатели,, регистры делимого и делителя выполнены в виде отдельных регистров для положительной и отрицательной частей делимого и.делителя соответственно, поступающих на них в избыточной двоичной системе счисления, выходы регистров делимого соединены соответственно с первым и вторым входами сумматора результата и информационными входами первого и второго блоков сдвига, выходы которых соединены.соответственно с третьими и четвертыми входами первого сумматора вычитателя, выходы которого соединены соответственно с входами ре- гистров делимого, выходы регистров делителя соединены соответственно с информационными входами третьего и четвертого блоков сдвига, выходы которых соединены соответственно с третьим и четвертым входами второго сумматора-вычитателя, выходы которого соединены соответственно с входами регистров делителя, выходы старших разрядов регистров делителя соединены с первым входом блока анализа переменных, первый выход которого соединен с управляющими входами сумматоров-вычитателей, второй выходс управляющим входом формирователя сдвига; разрядные входы формирователя сдвига и блока анализа переменных соединены с выходом дешифратора, вход которого соединен с выходом счетчика, вход счетчика соединен с .тактовым входом устройства, а выход формирователя сдвига соединен с управляющими входами первого, второго, третьего и .четвертого блоков сдвига.
1084785
Изобретение относится к вычислительной технике и может быть использовано при построении специальных .вычислительных систем.
Известно устройство для деления двоичных чисел, содержащее регист- . ры делимого и делителя, пирамиду сумматоров, элементы И, ИЛИ (1 .
Недостатком данного устройства является его конструктивная сложность, т.к. количество используемых 1О сумматоров с разделением цепей суммы и переносов пропорционалвно квадрату разрядности устройства.
Наиболее близким по технической сущности к изобретению является уст- 5 ройство для деления, содержащее регистры делимого и делителя, два блока элементов И, два сумматора, блок управления, причем поразрядные выходы регистра делимого подключены к соответствующим входам первого блока элементов И, выход которого подключен к первому входу первого сумматора, второй. вход .которого подключен к выходу младшего Разряда регистра делимого, старший разряд которого подключен к выходу первого сумматора, третий вход которого .подключен к выходу блока управления и к первому входу второго сумматора, второй вход которого подключен к выходу младшего разряда регистра де- щ теля, поразрядные выходы которого подключены к соответствующим входам второго блока элементов И, выход которого подключен к третьему входу второго сумматора, выход которого подключен к входу старшего раз ряда регистра делителя, второй выход блока управления подключен к вторым входам блоков элементов И, 40 выход второго сумматора подключен к входу блока определения переполнения, выход которого подключен к входу блока управления (2) .
Недостатком, известного устройства является его низкое быстродействие.
Целью изобретения является позышение быстродействия устройства за счет сокращения времени выполнения каждой итерации.
Поставленная цель достигается тем, что в устройство для деления двоичных чисел, содержащее регистры делимот о и делителя, первый и вто- 55 рой сумматоры, причем выходы регистров делимого и делителя соединена соответственно с первыми и вторыми входами первого и второго сумма- . торов, введены сумматор результата, 60 блок анализа переменных, первый, второй, третий и четвертый блоки . сдвига, дешифратор, счетчик и формирователь сдвига, содержащий к групп .из двух элементов И и эле- " мента ИЛИ, где первые входы первого и второго элементов И каждой группы объединены и являются разрядными входами формирователя сдвига, вторые входы первых элементов И групп объединены и являются первым управляющим входом формирователя сдвига, вторые входы вторых элементов И групп объединены и являются вторым управляющим входом формирователя сдвига, выходы второго элемента И (к-1) -ой группы и первого элемента И к-ой группы соединены соответственно с первыми и вторымц входами элементов ИЛИ (к-1)-ой rpyhпы, выходы которых являются разрядными выходами формирователя сдвига, причем первый и второй сумматоры устройства выполнены как сумматорывычитатели, регистры делимого и делителя выполнены в виде отдельных .Регистров для положительной и отрица- тельной частей делимого и делителя соответственно, поступающих на них в избыточной двоичной системе счисления, выходы регистров делимого соединены соответственно с первым и вторым входами сумматора результата и с информационными входами первого и второго блоков сдвига, выходы которыа соединены соответственно с третьими и четвертыми входами первого сумматора-вычитателя, выходы которого соединены соответственно с входами регистров делимого, выходы регистров делителя .соединены соответственно с информационными входами третьего и четвертого блоков сдвига, выходы которых соединены соответственно с третьим и четвертым входами. второго сумматора-вычитателя, выходы которого соединены соответственно с входами регистров делителя, выходы старших разрядов регистров делителя соединены с первым входом блока анализа переменных, первый выход которого соединен с управляющими входами сумматороввычитателей, второй выход -, c управляющим входом формирователя сдвига, разрядные входы формирователя сдвига и блока анализа переменных соединены с выходом дешифратора, вход которого соединен с выходом счетчика, вход счетчика соединен с тактовым входом устрцйства, а выход формирователя сдвига соединен с. управляющими входами первого, второго, третьего и четвертого блоков сдвига.
На фиг.1 представлена функциональная схема устройства для деления двоичных: чисел; на фиг.2 - функциональная схема формироваееля сдвига для трех разрядов.
Устройство содержит регистры 1 и 2 делимого, регистры 3 и 4 делите1084785!
О ля, сумматор 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 сдви- 2!) га и с первым и вторым входами второго сумматора-вычитателя 7", выходы которого соединены соответственно с входами регистров 3 и 4 делителя, выходы блоков 8 и 9 сдвига соединены с третьим и четвертым входами сумма тора-вычитателя 6, выходы блоков 10;
11 сдвига соединены с третьим и четветрым входами сумматора-вычитателя 7, управляющие входы блоков 8-11 сдвига соединены с выходом фопмирователя 13 сдвига, информационные входы которого соединены соответ-ственно с выходами дешифратора 14,. входы которого соединены с выходами счетчика 15, на вход счетчика 15 поступают импульсы тактовой частоты с входа 16 устройства, выходы дешифратора 14 соединены с информационными входами блока 12 анализа переменных, первый выход которого 4О соединен с управляющим входом формирователя 13 сдвига, а второй выход— с управляющими входами сумматороввычитателей б и 7, выход счетчика 5 результата является выходом 17 уст- 45 ройства. формирователь 13 сдвига (фиг.2) содержит к групп из двух элементов
И 18 и 19 и элемента ИЛИ 20, причем первые входы .первого и второго элементов И 18 и 19 каждой группы объединены и являются информационными входами формирователя 13 сдвига, . вторые входы первых элементов- И 18 групп и вторые входы вторых элементов И 19 групп являются управляющими входами формирователя 13 сдвига, выходы второго элемента И 19 к-ой группы и первого элемента И 18 (к-1) -nA группы соединены,соответст-. венно с первыми и вторыми входами элементов иЛЙ 20 (к-1) -ой группы, выходы которых являются разрядными выходами формирователя 13 сдвига. Устройство работае следующим образом.
Деление выполняется в избыточной системе счисления. Ь этой системе любое к-разрядное число Х (1X1(1j представляется в виде
Х=K,(K -Х ) 2 . (1) рф Р P где X+@ (0,1) - положительная цифра р-ro разрядае
Х Е (0,1) — отрицательная цифра р-. ro разряда;
p=T,K — номер разряда.
Процесс вычисления частного основывается на следующих равецствах.
Лелитель представляется в виде где С е !0,1, Е g(-1,0,1) р=1,K номер итерации.
Тогда значение частного представляется...в виде .
Х/У=Х ° 1+Ер 2 1 .. (3)
Иэ (2) йолучаем тождество
П (!+ Е2-(р-с ) q (4). ъ, На основании (3) и (4) процесС деления представится следующими рекуррентными выражениями
=-2„ 51+Eр2 ) (5)
У, =2 j1+E 2 < )) где P=1,2,...,К; Е Е(-1,0,+1,СЕ 0,13
Начальные условия: XI=XI yl =У. Результат: Хк=Х/У, < =1.
Переменные Ер и С на каждой р-ой итерации определяются по значениям старших разрядов Ур таким образом, чтобы первый после запятой разряд Ур в результате выполнения (6) принимал нулевое значение. При этом переменная У стремится к значению
Уц=1, а переменная X> — к значению
Х„=Х/V.
В табл. 1 приведена зависимость значения Ер и С от значений старших разрядов переменной У . E!,,Ердвоичные переменные управления сумматорами
Ер=Ер-Ер Ер,г Кр 6 0, 1 (0,1 — переменная номера итерации (у =1 при р=1, (p =0 при р=2К ..
Прочерками в табл.1 обозначены случаи, когда значение переменной не влияет на выходные сигналы.
1084785
О
0
О
О
О
О
О
О
О
О
О
О
О
О
О
О
0
О.0
0
О
0
О.
0
0
О
О
О °
О
О
О.О
О
0
° Переменная номера нтерарин ц
О О
О О
О, 1
Таблица 1
1084785
ХР
P х
Ур
1---.25
ЗО
Сумматор 5 предназначен для пре- ". З5 образования результата деления, хранящегося в .конце вычислений на регистрах 1 и 2, из избыточной системы счисления в двоичную и для хранения результата, выполнен в виде 40 параллельного сумматора накапливающего типа с распространением переноса на всех к разрядов.
Сумматоры-вычитатели 6 и 7 предназначены для выполнения сложения- 45 вычитания над числами в избыточной., системе счисления на каждом итера » ционном шаге вычислений.
Блоки 8 - 11 сдвига предназначены для параллельного сдвига содер« 50 жимого регистров 1 — 4 на (р-с) разрядов влево., Блок анализа переменных предназначен для реализации логической функции, представленной в табл.1, т.е. для . 55 определения по старшим разрядам переменной Ур и номеру итерации управляющиМ переменных С, Ер Е на каждом итерационном шаге. Блок 12 анализа реализует следующие логические функции в соответствии с таблицей истинности 1:
С ЦУ, Y< Y>>Y>V
Ч У, Г, 1 Ч у, () 65
В устройстве регистры 1 и 2 делимого и регистры 3 и,4 делителя предназначены соответственно для хранения переменных Хр, У> представленных в избыточной системе счисления. . Каждый регистр содержит (К+1) разрядов, к разрядов для дробной части и один разряд.для целой части переменной. Кажцый разряд регистров представляет собой обычный двоичный триггер. В регистре 1 хранятся поло- 10 жительные цифры Xp s регистре 2 отрицательные цифры Хр, р=1,K) пере менной Х, В регистре 3 и 4 соответственно хранятся цифры У, Ур
Ф (Р=1,К) переменной У . 15
В табл. 2 приведено сортветствие между цифрами и значением разряда переменных Х и У.
Таблица 2
Ер . Y Y1 Y у ч р Y, Y Y> q11 У< 3 Ч 3 ч(f Y Y z Y Y g Y з, (8) чY ЧgY Yq>tf (g)
Блок 12 анализа выполнен на логических схемах И и ИЛИ. Значения пе+ + Ф ременных У, Ук У,, У2, У, У3 . поступают на первый вход блока анализа с регистров 3 и 4, а переменная (на второй вход блока 12 анализа поступает с дешифратора 14.
Формирователь 13 сдвига (фиг.2) предназначен для формирования величины сдвига (р-с) Значение поступает на первый вход формирователя
13 с дешифратора 14, значение С поступает на второй вход с второго выхода блока 12 анализа. Укаэанное преобразование выполняется в формирователе 13 на элементах И 18 и 19 и элементе ИЛИ 20.
Счетчик 15 и дешифратор 14 предназначены для счета номера итерации и его дешифрации.
Деление производится над положительными числами, знак результата определяется по сочетанию знаков деделимого и делителя. Перед началом вычисления в регистры 1 и 3 заносятся сдвинутые влево на один разряд двоичные числа — делимое 2 Х и делитель 2У. Далее производится выполнение к итераций в соответствии с уравнениями (5),(6).
На каждой итерации производятся следующие действия.
В счетчике 15 тактов производится прибавление единицы по синхроимпульсу с входа 16, в дешифраторе 14 производится дешифрирование кода номера итерации р, значение которого поступает на первый вход формирователя 13 сдвига. Одновременно в блОке. 12 анализа переменных по значениям старших разрядов регистров
3 и 4 формируются значения переменных С, Ер, Е, значения Е» Ер поступают с второго выхода блока 12 анализа на управляющие входы первого и второго сумматоров вычитателей, 6 и 7 значение С -„ на второй вход формирователя 13 сдвига. В формирователе.13 сдвига формируется величина (р-с), которая поступает на управляющие входы блоков 8 — 11 сдви га. В.этих блоках производится сдвиг содержимого регистров 1 — 4 вправо на р-с) разрядов, что равнозначно умножению переменных Х и Ур на
2(P Затем в сумматорах-вычитателях
6 и 7 производится алгебраическое сложение переменных Хр и Ур соответственно со сдвинутыми вправо пере1084785
Та блица 3
Перемен.ная С
Значения разрядов Ур (переменная У ) В ите- Переменраций ная Е
0,1011011
1, 1 011 0110000
0,100100
1,001000000
- 10-1-10-1-100
-100-100000
О ТООТ00000
1,0- О- 000
0,1000000
1 100-11-1000
1i0-100-10-10 х,oOoô- -ф-ioo- o
1,000- 1-1-10
Т,ООО 0000) 0000
1-110-11-1
1;ИТ-10-1-111
1,OOOO LooJo ooO
1,00000 L00l 00
1 i000000000o
1,-111-10-1-11-1
1,-111-10-1-11-1 1,-111-10-1-11-1
Преобразование
S-O11OOOO1O
О, 100101101
0,110010101
Результат менными E Х у у"с1 и E У 2 ð-с1 в соответствии с уравнениями (5) и (б) .
Р t. РР
В результате на выходах сумматоров вычитаталей 6 и 7 формируются пере менные 1/2 ХР+ и 1/2 УР в избыточной двоичной системе, которые запи:сываются на регистрах 1 - 4 со сдвигом на один разряд. При этом в регистрах значения переменных ХР, У записываются на их новые значения
Х УР 1- вычисленные в данной
10 ю итерации.
При сдвигах влево в регистрах 3 и 4 старшие разряды переменной
У теряются. Однако оставшиеся раз-, ряды дробной части обеспечивают 15 правильное выполнение алгоритма деления.
После выполнения к итераций в регистрах 1 и 2 хранится результат
Выполнение итераций в устройстве может быть прекращено на любой р-ой итерации, если все разряды Ур окажутся нулевыми. Это позволяет дополнительно повысить среднее быстродействие устройства. Использование новых элементов — регистров положи- 60 тельной и отрицательной частей делимого и.делителя, сумматоров-вычитателей, формирователя сдвига, бл ка анализа и сумматора результата сокращает время выполнения итерации 65 деления X =X/У, представленный в избыточной двоичной системе счисления. Преобразование результата в обычную двоичную систему производится на сумматоре 5 результата с распространением переноса. Преобразование на сумматоре 5 результата сводится .к алгебраическому сложению двух двоичных чисел, представленных на регистрах 1 и 2.
В табл.3 приведен пример деления двоичных чисел Х=0,10010,У=0,1011011.
В конце таблицы прнведено преобразование ревульата из избыточной в обычную двоичную систему. счисления путем алгебраического сложения положительной и отрицательной частей избыточного результата.
Значения разр дов Хр (переменная Х ). в предлагаемом устройстве по сравнению с. известным.
Устройство для деления двоичных чисел выполнено на современных ин-тегральных микросхемах для больших разрядностей при приемлемых аппаратурных .затратах. Высокая регулярность и однородность структуры устройства позволяет эффективно реализовать его на интегральных микросхемах с повышенной степенью интеграции.
1084785
Составитель В.Гусев
Редактор Т. Кугрышева Техред A.Âàáêíåö Корректор екто А.Тяско
Заказ 2011/43 Тираж 699 Подписное
ВНИИПИ Государственного, комитета СССР по делам изобретений и открытий
113035, Иосква, Ж-35, Раушская наб., д. 4/5
Филиал ППП "Патент",. г. Ужгород, ул. Проектная, 4