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

 

Изобретение относится к вычислительной технике и может быть использовано в специализированных вычислительных устройствах. Цель изобретения - пов{ 1шение быстродействия операции деления двоичных чисел за счет исключения сдвига кода частного в регистре частного после определения всех 1ШФР частного. Устре йство для деления двоичных чисел содержит регистры делимого 1, делителя 2.и частного 3, сумматор 4, блок 5 сравнения кодов, блок 6 преобразования кода делителя, элемент НЕ 7, счетчик 8, блок 9 управления, триггер 10, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 11, демультиплексор 12, блок 13 элементов ИЛИ, соединенные мевду собой функционально . 2 ил. с S

СОЮЗ СОНЕТСНИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (51)4 C, 06 F 7 52

ОПИСАНИЕ ИЗОБРЕТЕНИЯ 4НОж в

ГОСУДАРСТНЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Н А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4250956/24-24 (22) 08.04,87 (46) 23, 10.88. Вюл, Р 39 (72) A.À.Äîáðûíèí и Д.Л.Nyxos .(53) 681 ° 325(088.8) (5б) Авторское свидетельство СССР я 646331, кл. G 06 Р 7!52, 1979.

Авторское свидетельство СССР

У 1103224, кл. С 06 F 7/52, 1982.

{54} УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ДВОИЧНЪП(ЧИСЕЛ (57) Изобретение относится к вычислительной технике и может быть использовано в специализированных вычисли„„SU„„1432508 А 1 тельных устройствах. Цель нэобратения — повЫпыние быстродействия операции деления двоичных чисел sa счет исключения сдвига кода частного в регистре частного после определения всех цифр частного. Устройство для деления двоичных чисел содержит регистры делимого 1, делителя 2 и частного 3, сумматор 4, блок 5 сравнения кодов, блок 6 преобразования кода делителя, элемент ЯЕ 7, счетчик 8, блок 9 управления„ триггер 10, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 11, демультиплексор 12, блок 13 элементов ИЛИ, соединенные между собой функциональ- . но. 2 ил.

1432508

Изобретение относится к вычислич1ельной технике и может быть использовано в специализированных вычислительных устройствах.

Цель изобретения — повышение быстродействия устройства для деления.

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

Устройство (фиг. 1) содержит реистры делимого 1, делителя 2, частого 3, сумматор 4, блок 5 сравнения, лок 6 преобразования кода, элемент

EE 7, счетчик 8, блок 9 управления, риггер 10, элемент ИСКЛЮЧАЮЩЕЕ

И 11, демультиплексор 12, блок 13 элементов ИЛИ с соответствующими связями, 20

Блок 9 управления (фиг. 2) соержит генератор )4 тактовых импульс он, первый 15, второй 16 и третий

1 7 элементы И, элемент НЕ 18, счетчик 19 циклов, первыи 20, второй 21 25

H третий 22 триггеры с соответствуюшими связями.

Устройство работает следующим об! разом.

До начала операции деления ре- 30 гистр 3 частного устанавливается в нулевое состояние, в регистр 2 делителя записывается п-разрядный делитель, п-разрядное делимое записываЦтся в регистр 1 делимого, причем в п + 1)-й разряды регистра 1 делимогп и регистра 2 делителя записываются сигналы логического нуля, счетчик 8, триггер 10 устройства, а также первый 20, второй 21, третий 22

a"ðèããåpû и счетчик 19 циклов блока

9 управления установлены в нулевое

Состояние.

На прямом: выходе триггера 21 присутствует сигнал логического нуля, на его инверсном выходе — сигнал логической единицы. Сигнал логического нуля с выхода счетчика 19 циклов поступает на вход элемента НЕ 18,,на выходе которого и втором входе первого элемента И 15 формируется сигнал логической единицы, разрешая прохождение импульсов с выхода генератора 14 тактовых импульсов через первый вход первого элемента И 15 на его выход.

Если код делимого, занесенный в регистр 1 делимого, больше кода делителя, записанного в регистре 2 делителя, на выходе блока 5 сравнения кодов формируется сигнап логического нуля, который через вход блока 9 управления поступает на тактовый вход

er о второго триггера 21„подтверждая его нулевое состояние, и сигналом логической единицы, поступающим с его инверсного выхода на второй вход третьего элемента И 17, разрешает прохождение импульсов с выхода элемента И 15 через элемент И 17 и через второй выход блока 9 управления на вход сдвига регистра 2 делителя и на счетный вход счетчика 8 устройства.

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

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

9 управления на вход сдвига регистра

2 делителя и счетный вход счетчика

8, Если код делимого меньше кода делителя, на выходе блока 5 сравнения кодов формируется сигнал логической единицы, который через вход блока 9 управления поступает на тактовый вход триггера 21 и переводит его в единичное состояние. В этом случае на выход элемента И 17 и на второй выход блока 9 управления не проходит ни один импульс и сдвига кода делителя в регистре 2 делителя не происходит, .

В этом случае на счетный вход счетчика 8 импульсы не поступают, и на его выходах сохраняется нулевое состояние.

1432508

Сигналы с выходов счетчика 8 поступают на адресные входыдемультинлексора 12, в котором в зависимости от сигналов на адресных входах произво5 дится коммутация сигнала с информационного входа на один из его выходов. Таким образом, если сдвига кода делителя в регистре 2 делителя не производится, на выходах счетчика 8 и 10 адресных входах демультиплексора 12 присутствует нулевая кодовая комбинация сигналов, и сигнал с информационного входа демультиплексора ком" мутируется на его первый выход. 15

Если сдвиг кода делителя в регистре 2 делителя производится на один, два или m разрядов, на выходах счетчика устанавливаются соответственно кодовые комбинации: 0001, соответствующая одному тактовому импульсу, поступившему на счетный вход счетчика 8, 0010, соответствующая двум тактовым импульсам и т.д. По этим кодо- . вым комбинациям на адресных входах демультиплексора 12 сигнал с его информационного входа коммутируется соответственно на второй, третий или ш и Выходые

Далее начинается пошаговый процесс определения цифр частного по алгоритму, согласно которому код делимого из регистра 1 делимого со сдвигом на один разряд в сторону старших разрядов подается на входы первой группы сумматора 4, причем на первый вход первого разряда сумматора подается сигнал логического нуля. Код делителя из регистра 2 делителя через блок

6 преобразования кода делителя поступает на входы второй группы сумматора 4 в дополнительном коде. В сумматоре 4 производится вычитание кода делителя из кода делимого. Результат вычитания определяется по выходу

"знакового" (п + 2)-ro разряда сумма тора 4, сигнал с которого инвертиру- ется элементом HF. 7, поступает через информационный вход демультиплексора 12 на соответствующий его выход и через блок 13 элементов ИЛИ на соответствующий информационный вход регистра 3 частного, тем самым исключая (после завершения операции деления) сдвиг кода частного в сторону старших разрядов на количество импульсов, равное числу импульсов сдвига кода делителя при его "нормализации".

Кроме того, "знаковый" (n + 2)-й разряд остатка с выхода (n + 2)-ro разряда сумматора запоминается в триггере 10, сигнал с выхода которого поступает на вход управления блока 6 преобразования кода делителя и управляет передачей кода делителя на входы второй группы сумматора 4 в следующем такте определения цифр частного. Остаток с выходов сумматора 4 одновременно с записью цифры частного в соответствующий разряд регистра 3 частного записывается в регистр 1 делимого. Далее процесс повторяется. Код остатка, записанный в регистре 1 делимого, поступает на входы первой группы сумматора 4 сдвинутым на один разряд в сторону старших разрядов, на первый вход первого разряда сумматора 4 поступает сигнал логического нуля. Если в соответствующий разряд регистра 3 частного и в триггер 10 в предыдущем цикле записан сигнал логической единицы, соответствующий положительному остатку, нормализованный код делителя из регистра 2 делителя через блок 6 преобразования кода делителя подается на вторые входы сумматора 4 в дополнительном коде, и в сумматоре 4 производится вычитание "нормализованного" кода делителя из кода остатка.

Если в регистр 3 частного и триггер 10 в предыдущем цикле записан сигнал логического нуля, соответствующий отрицательному остатку, нормализованный" код делителя из регистра 2 делителя подается на сумматор

4 в прямом коде, и в сумматоре 4 производится сложение кода остатка с

"нормализованным" кодом делителя.

Сигнал с выхода знакового (n + 2)-ro разряда сумматора 4 инвертируется элементом НЕ 7 и записывается через демультиплексор 12 и блок 13 элементов ИЛИ в тот же разряд регистра 3 частного, в который записана первая цифра частного в первом цикле процесса деления, а первая цифра частного в.момент записи второй цифры частного сдвигается на один разряд в сторону старших разрядов регистра

3 частного. Сигнал знакового (п+2)"го разряда остатка инвертируется и запоминается в триггере 10. Далее процесс повторяется.

Импульсы с элемента И 16 блока 9 управления поступают на счетный вход

32508

15 до пе

5 14 счетчика 19 циклов, на тактовый вход триггера 20 и на первый выход блока

9 упр а вл е ния .

Счетчик 19 циклов подсчитывает коЛичество циклов деления. Триггеры

20 и 22 образуют схему формирования имПульса, передний фронт которого со падает с передним фронтом первого из последовательности импульсов гене атора 14 тактовых импульсов, а сп д импульса совпадает с передним фррнтом второго импульса последовате льности генератора 14 тактовых импу ьсов, поступающих с выхода элеме та И 16. Сформированный сигнал чере третий выход блока 9 управления по тупает на второй вход элемента

ИС ОЧАЮЩЕЕ ИЛИ 11 для перевода

"н рмализованного" кода делителя в олнительный код при определении вой цифры частного.

На первые входы сумматора 4 подает я прямой код делимого с выходов ре истра 1 делимого, сдвинутый на од н разряд в сторону старших разрядо, причем на первый вход первого разряда сумматора 4 подается постоянно, сигнал логического нуля. гического нуля во всех циклах определения цифр частного. Одновременно с записью информации в регистр 3 частного производится запись информации о знаке остатка в триггер 10.

Кроме этого, в регистр 1 делимого по спаду первого импульса последовательности записывается код остатка с выходов разрядов сумматора 4. Этим заканчивается формирование первой цифры частного.

На втором входе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 после окончания формирования первой цифры частного устанавливается сигнал логического нуля с третьего выхода блока 9 управления, таким образом, сигнал на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 до окончания цикла деления повторяет сигнал на его первом входе, т.е. сигнал с выхода триггера 10, который характе-ризует знак остатка„полученный при определении первой цифры (в последующих циклах — полученный при определенни предыдущей цифры частного) .

Сигнал с выхода триггера 10 поступает на вход управления блока 6 преобразования кода делителя, на вход пе1, :В сумматоре 4 производится вычитание нормализованного" кода делителя из. кода делимого, в первом цикле опрецеления цифр частного вычитание является обязательным в силу данного алгоритма деления двоичных чисел, На вЫходах первого, второго, ..., (n +

+ 1)-го разрядов сумматора *: формируется код остатка. Знак остатка формируется на выходе (n + 2}-ro разряда сумматора 4 и соответствует сигналу логического нуля, если остаток положительный. Соответственно в первом случае в регистр 3 частного необ" ходимо записать цифру частного в виде логической единицы, во втором случае — логический нуль. Сигнал знака, остатка с выхода (п + 2)-ro разряда сумматора 4 инвертируется элементом НЕ 7 и поступает на информационный вход триггера 10 и информационный вход,цемультиплексора 12. По сигналам на адресных входах последнего сигнал с его информационного входа коммутируется на один из его выходов и через блок 13 элементов

ИЛИ записывается в регистр 3 частного. На остальных выходах демультиплексора 12 присутствуют сигналы лоЗ0 реноса и вход (п + 2}-ro разряда второй группы сумматора 4. Если остаток при формировании первой цифры частного отрицателен, в триггер 10 записывается сигнал логического нуля, который поступает на вход пере35 носа и вход (n + 2)-го разряда второй группы сумматора 4 и вход управления блока 6 преобразования кода делителя, р азр ешая прохождение "нор40 мализованного" кода делителя с выходов регистра 2 делителя на входы второй группы сумматора 4 в прямом коде.

Если остаток при формировании первой цифры частного положителен, в

45 триггер 10 записывается сигнал логической единицы, который поступает на вход переноса и вход (n. + 2)-ro разряда второй группы сумматора 4 и на вход управления блока 6 преобраэова50 ния кода делителя и переводит код делителя, поступающий на входы второй группы сумматора 4, в дополнительный код.

Таким образом, если остаток при

:формировании первой цифры частного отрицательный, в сумматоре 4 роизводится сложение остатка с "нормализованным" кодом делителя, если оста

1432508 8 т.е. сдвига кода делителя. Тем самым быстродействие предлагаемого устройства увеличивается на время, равное

5 сдвигу кода делителя при его "нормализации".

7 ток при формировании первой цифры частного положительный, в сумматоре

4 производится вычитание из остатка кода делит еля, Знак очередного остатка формируется на выходе (п + 2)-ro разряда сумматора 4, инвертируется элементом

НЕ 7 и через демультиплексор 12 поступает на ега соответствующий выход и через блок 13 элементов ИЛИ на соответствующий информационный вход регистра 3 частного. Кроме того, знак очередного остатка с выхода элемента

НЕ 7 записывается в триггер 10.

Таким образом, происходят формирование сигнала второй цифры частного и запись его в регистр 3 частного а также сдвиг в регистре 3 част. ного сигнала первой цифры частного на один в сторону старших разрядов, В триггере 10 производится запоминание сигнала знака остатка для последующего цикла деления.

После определения всех цифр частного последний импульс из последовательности импульсов поступает на счетный вход -счетчика 19 циклов, на выходе которого формируется сигнал логической единицы, который инвертируется элементом НЕ 18 и поступает на второй вход элемента И 15, блокируя поступление импульсов с выхода генератора 14 тактовых импульсов на выход элемента И 15. Этим заканчивается операция деления двоичных чисел.

Так как операция деления производится с модулями двоичных чисел, знаки делимого и делителя в процессе деления участия не принимают, поэтому знак частного может быть определен, например, в результате сравнения сигналов знаков делителя и делимого на логическом элементе ИСКЛЮЧАЮЩЕЕ ИЛИ и записи полученного результата в триггер одновременно с записью кодов делимого и делителя соответственно в регистры делимого и делителя.

По сравнению с известным устройствам, в котором сдвиг кода частного после определения цифр частного производится всегда на количество разрядов, на которое был сдвинут код делителя при "нормализации", в предлагаемом устройстве сдвига кода частного после определения всех цифр частного не производится за счет того, что цифры частного в регистр частного эапц:ываются с учетом "нормализации", Формула изобретения

1О Устройство для деления двоичных чисел, содержащее регистр делимого, регистр делителя, регистр частного, сумматор, блок сравнения кодов, счетчик и блок управления, причем разрядные выходы регистра делимого соединены соответственно с информационными входами первой группы блока сравнения кодов, информационные входы второй группы которого соединены соответственно с разрядными выходами регистра делителя, а выход блока сравнения кодов соединен с входом блока управления, первый выход которого соединен с входом разрешения

25 записи регистра делимого, информационные входы которого соединены соответственно с разрядными выходами сумматора, второй выход блока управ-ления соединен с входом сдвига инЗ0 формации регистра делителя и са счетным входам счетчика, а блок управления содержит генератор тактовых импульсов, выход которого соединен с первым входом первого элемента И, выход которого соединен с первыми входами второго и третьего элементов

И, выход второго элемента И соединен с тактовым входом первого триггера, и счетчик циклов, выход которого

40 соединен с входам элемента НЕ, о т— л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в устройство введены демультиплексор, триггер, группа элементов ИЛИ, элемент ИСКЛЮЧАЗХ1!ЕЕ ИЛИ, элемент НЕ и

45 блок преобразования кода, содержащий группу из (и + 1) элементов ИСКЛЮЧАЮЩЕЕ ИЛИ (где n — разрядность операндов), первые входы которых являются информационными входами блока преобразования кода, вторые входы элементов ИСКЛЮЧА1И1ЕЕ ИЛИ объединены и являются управляющим входом, а выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ являются разрядными выходами блока преобразования кодов, причем разрядные выходы с первого по (и + 1) é регистра делимого соединены соответственно с второго па (n + 2)-й разрядными вхо9 1ч32508 1О дами первой группы сумматора, пер" число выходных разрядов демультиплеквый разрядный вход которой соединен сора) соединен с первым входом (i с шиной логического нуля, а разряд- 1)-ro элемента ИЛИ группы, выход ные входы с первого по (n + 1)-й которого соединен с i-и входным развторой группы сумматора соединены

5 рядом регистра частного, разрядные соответственно с разрядными выходами выходы которого с первого по (m-1)-й блока преобразования кодов, информа- соединены соответственно с вторыми ционные входы которого соединены со- входами элементов ИЛИ группы, а в ответственно с разрядными выходами 1О блок управления устройства введены регистра делителя, а управляющий второй и третий триггеры, причем вывход блока преобразования кодов сое- ход элемента НК блока управления сое динен с входом переноса, (n + 2)-м динен с вторым входом первого эле1 азрядным входом второй группы сум- мента И, выход второго элемента И

II ° матора и с выходом элемента ИСИПОЧАЮ- 15 соединен со счетным входом счетчика

l3E ИЛИ, первый вход которого соеди- циклов и с первым выходом блока упНен с выходом триггера, а второй — с равления, вход которого соединен с третьим выходом блока управления, тактовым входом второго триггера, In + 2)-й разрядный выход сумматора прямой и инверсный выходы которого

Соединен с входом элемента НЕ, выход 2О соединены соответственно с вторыми которого соединен с информационными входами второго и третьего элементов

5ходами демультиплексора и триггера, И, выход третьего элемента И соедитактовый вход которого соединен с нен с вторым выходом блока управлеЙервым выходом блока управления и ния, третий выход которого соединен тактовым входом регистра частного, 25 с прямым выходом первого триггера и разрядные выходы счетчика соединены тактовым входом третьего триггера, соответственно с адресными входами инверсный выход которого соединен с 1емультиплексора, первый разрядный информационным входом первого тригге6ыход которсго соединен с первым ра, а информационные входы второго входным разрядом регистра частного, Зо и третьего триггеров соединены с шиа ка-кдый i-f разрядный выход демуль- ной логической единицы.

,"иплексора (где i "— 2„..., m, m—

1432508

Составитель В.Гусев

Техред Л.Сердюкова Корректор Л.Патай

Редактор И.Горная

Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

1)3035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 5441/4 1

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная,