Устройство для деления двоичных чисел
Патент 1283753
Авторы
Классы МПК
Устройство для деления двоичных чисел
Иллюстрации
Реферат
Изобретение относится к области вычислительной техники, в частности к электронным цифровым вычислительным машинам. Устройство содержит регистры делимого, делителя и частного, сумматор, блок управления, триггер. С целью повышения быстродействия в состав устройства включены коммутатор и формирователь сигнала сдвига. Устройство выполняет операцию деления без восстановления остатка с пропуском тактов сложения по сигналу сдвига, вырабатываемому в формирователе сигнала сдвига. Использованный в устройстве способ формирования сигнала сдвига обеспечивает максимально возможное при логических методах ускорение быстродействия: математическое ожидание количества сдвигов на. одно сложение равно 3, максимально возможное количество сложений не древьш1ает половины от общего количества разрядов частного. 3 йл, .1 табл. i (Л
СОЮЗ СОВЕТСКИХ . СОЦИАЛИСТИЧЕСКИХ
РЕСПУБЛИК (19) (Н) А1 (я) 4 G 06 F 7 52 ф ;;, Qj 2 EA Я
;: 1 !v.
ИИ»:.."-, А
ОПИСАНИЕ ИЗОБРЕТЕНИЯ
И АВТОРСКОМУ(СВИДЕТЕЛЬСТВУ
Ю
9 Ю
° Ю с
ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР
ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3915445!24-24 (22) 25,06.85 (46) 15.01,87. Бюл, Ф 2 (72) Б. А. Баклан (53) 681. 325 (088, 8) (56) Карцев М. А. Арифметика цифровых машин. — М.: Наука, 1969, Авторское свидетельство СССР
У 1048472, кл. G Об F. 7!52, 1980. (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ДВОИЧНЫХ
ЧИСЕЛ (57) Изобретение относится к области вычислительной техники, s частности к электронным цифровым вычислительным машинам. Устройство содержит регистры делимого, делителя и частного, сумматор, блок управления, триггер °
С целью повышения быстродействия в состав устройства включены коммутатор и формирователь сигнала сдвига.
Устройство выполняет операцию деления без восстановления остатка с пропуском тактов сложения по сигналу сдвига, вырабатываемому в форьырователе сигнала сдвига. Использованный в устройстве способ формирования сигнала сдвига обеспечивает максимально возможное при логических методах . ускорение быстродействия: математическое ожидание количества сдвигов на одно сложение равно 3, максимально возможное количество сложений не превышает половины от общего количе- Е
Ф ства разрядов частного, 3 ил, .1 табл.
1283753
Изобретение относится к вычислительной технике, в частности к электронным цифровым вычислительным машинам.
Цель изобретения — повышение быст- 5 родействия устройства, Пусть D — значение делителя, а
 — значение делимого (или очередного остатка), тогда частное (или младшая часть частного} В х
B = x ° D
Подставляя в выражение (1) значе- 15
2 «5 ние x = — и х = — имеют граничные
3 6 значения остатка:
D °
5
D I
В =zD
««
B=xD
Если текущий остаток В; по абсолютной величине меньше, чем В, т.е, 3
2 то в очередном цикле необходимо выполнить только сдвиг. а,, 5 и, (3) то необходимо выполнить цикл, содержащий сложение и сдвиг, Если выполняется неравенство
2 9 !В;1 2 В, (4)
40 то можно производить как сложение со сдвигом, так и только сдвиг.
Сравнивая в процессе деления текущий
« остаток со значениями В и В и выбирая тип очередного цикла в соот-. ветствии с условиями (2), (3) и (4), можно обеспечить минимально возможное количество суммирований дпя лю-. бых значений частного, Весь диапазон изменения делителя !
-<О 1 может быть разбит на несколь2 ко поддиапазонов, для каждого из которых можно указать значение остатка малой разрядности, начиная с которого выполняются циклы того или иного типа.
Все данные сведены в таблицу, отражающую состав выполняемых цик"
Если текущий остаток В . по абсо- 30
« лютной величине больше, чем В, т.е. лов в зависимости от значений В; и
D (слева — состав выполняемых действий при положительном остатке; справа — при отрицательном остатке).
Пользуясь данными таблицы, можно составить логическую формулу, охватывающую все случаи, когда должен выполняться цикл, содержащий только сдвиг, обозначив через Ь и с11 j-e разряды соответственно текущего остатка В; и делителя D, после минимизации получают формулы выполнения цикла сдвига для положительного остатка
Р -Ь,(Ь,(Ьчьч1 а Ь, 1,)ЧЬ 1 ° . (bE,чЬ,1,)j и для отрицательного остаткаF Ьо 1 b (Ь ЧЬ Ч d Чd b4 d,) b d ° (Ь ЧЬ d3)) °
Полученные формулы можно объединить в одну, если сделать замену а = Ь"ПКЧЬ ПК
> )
Тогда функция сдвига
Г а ja, (а,ч а vd,»d ÷àä d )»a d,» (апач a4d ъ)j (5)
На фиг. 1 представлена блок-схе- ма предлагаемого устройства; на фиг. 2 - функциональная схема блока управления; на фиг. 3 — функциональная схема формирователя сигнала сдви га, Устройство содержит регистр 1 делителя, регистр 2 делимого, регистр 3 частного, сумматор 4, блок
5 управления, триггер 6, коммутатор
7, формирователь 8 сигнала сдвига, вход 9 и выход 10 устройства.
Блок 5 управления образуют генератор 11 импульсов, распределители
12 - 14 импульсов, элементы ИЛИ 15 и 16, элементы И 17 и 18, счетчик
19 коммутатор 20, дешифр атор 21 нуля, первый 22 - пятый 26 выходы и первый 27, второй 28 и третий 29 входы, Формирователь сигнала сдвига содержит элементы И 30 — 34 и элементы ИЛИ 35-37, Устройство выполняет деление иразрядных нормализованных двоичных чисел, представленных в прямых кодах, частное образуется также в прямом коде. Регистры I и 3 имеют по одному дополнительному разряду, регистр 2 имеет два дополнительных
1283753
20 разряда, При этом регистры 2 и 3 содержат цепи сдвига влево, регистр
1, может быть не сдBHI osbIM Сумматор 4 является (n+2)-разрядным сумматором комбинационного типа. Триггер 6 является обычным D-триггером с дополнительным входом начальной установки и прямым и инверсным выходами. Если триггер 6 находится в единичном состоянии, то коммутатор 7 пропускает на свой выход инверсный код пяти старших разрядов регистра 2 делимого, в противном случае — их прямой код, Работа блока управления совпадaет с работой блока управления устройства-прототипа, .
Если Рс=1, то цикл деления содержит только совместный сдвиг регистров 2 и 3 влево по управляющему сигналу с выхода 22 блока 5., если Р„= О, то в цикле предварительно выполняется сложение кодов регистров 1 и 2, а затем совместный сдвиг содержимого регистров 2 и 3 влево. Поскольку регистр 2 содержит два дополнительных разряда, то код делимого в нем располагается сдвинутым вправо на один разряд относительно кода делителя в регистре 1, Это .объясняется тем, что при некоторых значениях остатка В ° и де1 лителя D сложение необходимо выполнять для кодов остатка, содержащих нули в двух старших разрядах, Если триггер 6 находится в единичном состоянии (как, например, в 1-м цикле деления) и Р = О, то импульс проходит через выход 23 блока 5 на вход управления выдачей дополнительного кода регистра 1 делителя (дополнительный код регистра 1 представляется как его инверсный код и единичный сигнал, подаваемый на вход переноса младшего разряда сумматора 4). Если триггер 6 находится в нулевом состоянии, на сумматоре 4 производится сложение поступившего из регистра 1 прямого кода с кодом из регистра 2. Через заданный промежуток времени появляется сигнал на втором выходе распределителя 13, который подается на вход управления приемом информации регистра 2 и на управляющий вход триггера 6, При поступлении этого сигнала производится запись в регистр 2 кода суммы, полученной на сумматоре 4, а
55 также установка триггера 6 старшим разрядом этой суммы., При этом триггер 6 устанавливается в единичное состояние, если старший разряд суммы равен единице, в противном случае триггер 6 устанавливается в нулевое состояние, В каждом цикле в старшем разряде регистра 2 образуется одна цифра частного, которая передается в младший разряд регистра
3 в результате совместного сдвига этих регистров.
Количество определяемых разрядов частного за одно сложение равно трем„ Число суммирований не превыn+2 шает — —.
2 формул а изобретения
Устройство для деления двоичных чисел, содержащее регистры делимого, делителя и частного, сумматор и блок управления, причем выход регистра частного является выходом устройства, вход устройства соединен с информационным входом регистра делителя, выход которого соединен с первым информационным входом сумматора, второй информационный вход которого соединен с выходом регистра делимого, информационный вход которого соединен с выходом результата сумматора, выход старшего разряда регистра делимого соединен со входом младшего разряда регистра. частного, первый выход блока управления соединен со входами управления сдвигом регистров делимого и частного, второй и третий выходы блока управления соединены со входами управления выдачей соответственно дополнительного и прямого кодов регистра делителя, четвертый выход блока управления соединен со входом управления приемом информации регистра делимого, пятый выход блока управления соединен со входом установки знакового разряда регистра делителя, о т л и ч а ю— щ е е с я тем, что, с целью повышения быстродействия, в него введе- ны коммутатор, триггер и формирователь сигнала сдвига, содержащий пять элементов И и три элемента ИЛИ, причем первый вход установки триггера в "1" соединен с пятым выходом блока управления, четвертый выход которого соединен с вторым входом установки триггера в "1",информа l283753 6 четвертого элемента И и с выходом третьего разряда регистра делителя, .выход четвертого разряда которого соединен с вторым входом третьего элемента И, выход первого элемента
ИЛИ соединен с вторым входом второго элемента И, выход которого соединен с первым входом второго элемента
ИЛИ, второй вход которого соединен
1О с выходом пятого элемента И, третий вход которого соединен с выходом третьего элемента ИЛИ, первый вход которого соединен с вторым входом первого элемента ИЛИ, выход четвертого элемента И соединен со вторым входом третьего элемента ИЛИ, выход второго элемента ИЛИ соединен со вторым входом первого элемента И, выход которого соединен с первым
20 входом блока управления, второй и третий входы которого соединены с первым и вторым управлявшими входами коммутатора и прямым и инверсным выходами триггера соответствен—
25,но. ционньш вход триггера соединен с выходом старшего разряда сумматора, пер вый и второй информационные входы коммутатора соединены с прямым и инверсным выходами пяти старших разрядов регистра делимого, первый и второй разряды выхода коммутатора соединены соответственно с первыми входами первого и второго элементов И формирователя сигнала сдвига, третий и четвертый разряды выхода коммутатора соединены с первым и вторым входами первого элемента ИЛИ, третий вход которого соединен с выходом третьего элемента И, первых вход которого соединен с пятым разрядом выхода коммутатора и первым входом четвертого элемента И, второй разряд выхода регистра делителя соединен с четвертым входом первого элемента ИЛИ и первым входом пятого элемента И, второй вход которого соединен с первым входом
nepaoro элемента ИЛИ, пятый вход которого соединен с вторым входом
Состав выполняемых в цикле действий в завнснмостн от эначенкй В; н D в 1
0,111 0 O, I I О 0, Ill О,!О! ав <0,11 0,10014 D
° «
С ÇK
С 3К
С ÇK
ДК ЗК
ДК ЗК
ДК ЗК
ДК ЗК
С ЗК
С ЗК
ДК ÇK
ДК ЗК
ДК ЗК
ДК
ЗК
3К
ЗК!
000» ДК ПК
3К
ЗК
1001 ДК ПК
10100 ДК ПК
1 010 l ДК С
ДК
ПК
ЗК
3К
3К
ПК
ПК
ПК!
011» ЗК С
3К
ЗК
ПК
1 1 000 ЗК С
ЗК
11001 ЗК . С ЗК
3К
000 C ÇK
0010 С ÇK
00110 С ÇK
00111 С ÇK
0100- С ЗК
01010 С ПК
01011 ДК IIK
O l IO ДК flK
0 l 11 ДК flK
С ЗК
С ЗК
С ЗК
С ЗК
С ЗК
gK 3K
ДК ÇK
ДК ПК
ДК ПК
С 34
С ЗК
С ÇK
С ЗК
ДК ЗК
ЦК ÇK
ДК ÇK
ДК ЗК
ДК ЗК
ЗК ПК
ЗК ПК
3К ПК
3К ПК
ЗК IIR
3К С
ЗК
ДК ЗК
ДК ЗК
ЗК ЗК
ЗК ÇK
3К 3К
ЗК ÇK
ЗК ПК
ЗК ПК
ЗК ПК
ЗК ПК
ЗК 11К
1283753
Продолжение таблицы
О,Ill « Ра1 0,11 еЛ с0,111 0,10! ED а0,11 0,1001 0 с0,101 0,16 Ос0,1001
1101- ЗК С 3К
ЗК С
ЗК С
ЗК С
ЗК С
ЗК
111 ЗК С 3К
П р и м е ч а н и е, ДК вЂ” цикл, содержащий сложение с дополнительным кодом делителя и сдвиг; ПК " цикл, содержащий сложение с прямым кодом делителя и сдвиг; С - цикл, содержащий только сдвиг, ЗК - эапрешенная комбинация, при этом если ЗК расположено с левой стороны, то он не может воэиикнуть при положительном остатке, а если с правой стороны — то при отрицательном остатке энаком - обоэнлчены раэряды, значения которых не покаэывают влияния на выбор типа цикла.
1283753
Составитель Н. Маркелова
Редактор Л. Пчелинская Техред Л.Сердюкова Корректор Л. Патай
Заказ 7442/47 Тираж 670 Подписное
ВНИИПИ Государственного комитета СССР по делам изобретений и открытий
113035, Москва, Ж-35, Раушская наб,, д. 4/5
Производственно-полиграфическое предприятие, г, Ужгород, ул. Проектная, 4