Устройство для деления двоичных чисел Советский патент 1988 года по МПК G06F7/52 

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

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

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

Устройство (фиг. 1) содержит регистры делимого 1, делителя 2, частного 3, сумматор 4, блок 5 сравнеиия блок 6 преобразования кода, элемент НЕ 7, счетчик 8, блок 9 управления, триггер 10, элемент ИСКЛЮЧАЮЩЕЕ I ЛИ 11, демультиплексор 12, блок 13 элементов ИЛИ с соответствующими связями.

Блок 9 управления (фиг. 2) со держит генератор 14 тактовых импуль- doB, первьй 15, второй 16 и третий 1i7 элементы И, элемент НЕ 18, счетчик. 19 циклов, первьй 20, второй 21 и третий 22 триггеры с соответствуго- вгами связями.

I Устройство работает следукщим об- pia3OM.

j До начала операции деления ре- iJHCTp 3 частного устанавливается в нулевое состояние, в регистр 2 делителя записывается п-разрядньй делитель, п-разрядное делимое записывается в регистр 1 делимого, причем в (п + 1)-й разряды регистра 1 делимого и регистра 2 делителя записываются сигналы логического нуля, счетчик 8, триггер 10 устройства, а так- це первый 20, второй- 21, третий 22 1 иггеры и счетчик 19 т.щклов блока 0 управления установлены в нулевое состояние.

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

Если код делимого,, занесенный в регистр 1 делимого, больше кода делителя, записанного в регистре 2 де0

5

0

5

0

5

0

5

0

5

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

По отрицательному фронту импульсной последовательности производится сдвиг содержимого регистра 2 делителя в сторону старших разрядов, т.е. увеличение кода делителя до тех пор, пока на выходе блока 5 сравнения кодов не появляется сигнал логической единицы, свидетельствующий о том, что делитель в регистре 2 делителя нормализован, т.е. стал больше кода делимого в регистре 1 делимого. Счетчик 8 подсчитывает количество импульсов, необходимых для сдвига кода делителя в регистре 2 делителя, и на его входах фop иpз eтcя двоичньй код, соответствующий числу импульсов сдвига кода делителя. Появление сигнала логической еди1та цы на выходе блока 5 сравнения и через вход, блока 9 управления на тактовом входе триггера 21 переводит его в противоположное состояние. На инверсном выходе триггера 21 формируется сигнал логического нуля, которьпЧ запрещает прохождение импульсов на выход элемента И и через второй выход блока 9 управления на вход сдвига регистра 2 делителя и счетный вход счетчика 8. Если код делимого меньше кода делителя, на выходе блока 5 сравнения кодов формируется сигнап логической единицы, который через вход блока 9 управления поступает, на тактовьй вход триггера 21 и переводит его в единичное состояние. В этом случае на выход элемента И 17 и на второй выход блока 9 управлеьшя не проходит ни один импульс и сдвига кода делителя в регистре 2 делителя не происходит. . В этом случае на счетньй вход счетчика 8 импульсы не поступают, и. на его выходах сохраняется нулевое состояние.

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

Кроме того, знаковый (п + 2)-й разряд остатка с выхода (п + 2)-го разряда cyTkfMaTopa запоминается в триггере 10, сигнал с выхода которого поступает на вход управления блока 6 преобразования кода делителя и управляет передачей кода делителя на входы второй группы сумматора 4 в

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

производится, на выходах счетчика 8 и |Q следуицем такте определения цифр

15

20

25

30

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

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

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

35

40

45

50

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

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

5

0

5

0

5

0

5

0

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

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

счетчика 19 цнклов, на тактовый вход триггера 20 и на первый выход блока 9 управления.

Счетчик 19 циклов подсчитьгаает ко|1ичество циклов деления. Триггеры 20| и 22 образуют схему формирования имтульса, передний фронт которого со зпадает с передним фронтом первого из последовательности импульсов гене затора 14 тактовых и myльcoв, а

СП

Фр

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

по ИС

ступает на второй вход элемента

КЛЮЧА10ЩЕЕ

11 для перевода ,11

нормализованного кода делителя в доюлнителънъй код при определении

первой цифры частного.

На первые входы сумматора 4 пода- ет|ся прямой код делимого с выходов регистра 1 депимого, сдвинутый на ОДИН разряд в сторону старших разрядов, причем на первый вход первого разряда сумматора 4 подается постоян но| сигнал логического нуля,

I В сумматоре 4 производится вычита ни|е нормализованного кода делителя из| кода делимого5 в первом цикле оп- ре|целения цифр частного вычитание яв|пяется обязательным в силу данного ал{горитма деления двоичных чисел „ На вь содах первого, второго, ,,„, (п + + :1)-го разрядов сумматора 4 форми- код остатка. Знак остатка фор мируется на выходе (п + 2)-го разряда; сумматора 4 и соответствует -сигналу логического нуля, если остаток положительный. Соответственно в первом случае в регистр 3 частного необходимо записать цифру частного в виде логической единицы, во втором сл;учае - логический нуль. Сигнал знака, остатка с выхода (и + 2)-го разряда сумматора 4 инвертируется элементом НЕ 7 и поступает на информационный вход триггера 10 и информа- цйонньй вход демультиплексора 12, По снтнала на адресных входах последнего сигнал с его информационного коммутируется на один из его выходов и через блок 13 элементов liniH записывается в регистр 3 частного. На остальных выходах демультиплексора 12 присутствуют сигналы по14325086

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

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

На втором входе элемента ИС1ШЮЧА- ЩЕЕ ИЛИ 11 после окончания формиро 5 вания первой цифры частного устанавливается сигнал логического нуля с третьего выхода блока 9 управления, таким образом, сигнал на выходе элемента ИС1ШЮЧАМЦЕЕ ИЛИ 11 до оконча2Q ьшя цикла деления повторяет сигнал на его первом входе, т.е. сигнал с выхода триггера 10, которьй характе- ризует знак остатка, полученный при определении первой цифры (в после25 дующих циклах - полученный при определении предыдущей цифры частного). Сигнал с выхода триггера 10 поступает на вход управления блока 6 преобразования кода делителя, на вход пе- 30 реноса и вход (п - 2)-го разряда

второй группы сумматора 4. Если остаток при форгдаровании первой цифры частного отрицателен, в тр иггер 10 записывается сигнал логического нуля, который постздтает на вход переноса и вход (п + 2)-го разряда второй грзшпы сумматора 4 и вход управления блока 6 преобразования кода

35

40

делителя, разрешая прохоткдение нормализованного кода делителя с.выводов регистра 2 делителя на входы второй группы сумматора 4 в прямом коде.

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

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

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

50

55

делителя, разрешая прохоткдение нормализованного кода делителя с.выводов регистра 2 делителя на входы второй группы сумматора 4 в прямом коде.

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

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

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

ток при формировании первой цифры

4 производится вычитание из остатка кода делителя.

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

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

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

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

По сравнению с известным устройством, в котором сдвиг кода частного после определения цифр частного производится всегда на количество разрядов, на которое был сдвинут код Делителя при нормализации, в предлагаемом устройстве сдвига кода частного после определения всех цифр частного не производится за счет того, что цифры частного в регистр частного за пи-С-ываются с учетом нормализагщи,

14325088

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

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

Формула изобретения

0

5

0

0

Устройство для деления двоит гных чисел, содержащее регистр делимого, регистр делителя, регистр частного, сумматор, блок сравнения кодов, счетчик и блок управления, причем разрядные выходы регистра делимого соединены соответственно с информационными входами первой грешны блока срав- не ния к од ов,и нфор мационные входы второй группы которого соединены со- ответственно с разрядными выходами регистра делителя, а выход блока сравнения кодов соединен с входом блока управления, первый выход которого соединен с входом разрешения 5 записи регистра делимого, информационные входы которого соединены соответственно с разрядными выходами сумматора, второй выход блока управления соединен с входом сдвига информации регистра д елителя и со счетным входом счетчика, а блок управления содержит генератор тактовых импульсов, выход которого соединен с первым входом первого элемента И, выход которого соединен с первыми входами второго и третьего элементов И, выход второго элемента И соединен с тактовым входом первого триггера, и счетчик циклов, выход которого соединен с.входом элемента НЕ, о т - личающееся тем, что, с целью повышения быстродействия, в устройство введень; демультиплексор, триггер, группа элементов ИЛИ, элемент ИСКЛЮЧАИЦЕЕ ИЛИ, элемент НЕ и блок преобразования кода, содержащий группу из (п + 1) элементов ИСКПКЯА- ЩЕЕ ИЛИ (где п - разрядность операндов), первые входы которых являются информационными входами блока преобразования кода, вторые входы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ объединены и являются управляющим входом, а выходы элементов ИСКЛЮЧАЮРЩЕ ИЖ являются разрядными вьпсодами блока преобразо-. вання кодов, причем разрядные выходы с первого по (п + 1)-й регистра делимого соединены соответственно с второго по {п + 2)-и разрядными вхо5

0

5

0

5

дами первой группы сумматора, первый разрядный вход которой соединен с тайной логического нуля, а разрядные входы с первого по (п + 1)й второй группы сумматора соединены соответственно с разрядными выходами блока преобразования кодов, информационные входы которого соединены соответственно с разрядными выходами fierHCTpa делителя, а управляющий |вход блока преобразования кодов сое- ,инен с входом переноса, (п + 2)-м разрядным входом второй группы сум- ; штора и с выходом элемента ИСКЛЮЧАЮ |ЦЕЕ ШШ, первый вход которого соеди |тен с выходам триггера, а второй - с Третьим выходом блока управления, 11 + 2)-и разрядньй выход сумматора |;оединен с входом элемента НЕ, выход Которого соединен с информационными ходами дем: льтиплексора и триггера, фактовый вход которого соединен с ikepBbiM выходом блока управления и тактовым входом регистра частного, азрядные выходы счетчика соединены Соответственно с адресными входами Демультиплексора, первый разрядный йыход которого соединен с первым входным разрядом регистра частного, 4 разрядный выход демуль- п иплексора (где i 2, „,„ га, m

10

д

43250810

число выходных разрядов демультиплек- сора) соединен с первым входом (i - - 1)-го элемента ИЛИ группы, выход которого соединен с i-м входным разрядом регистра частного, разрядные выходы которого с первого по (т-1)-й соединены соответственно с вторыми входами элементов ИЛИ группы, а в блок управления устройства введены второй и третий триггеры, причем выход элемента НЕ блока зтравления соединен с вторым входом первого элемента И, выход второго элемента И соединен со счетным входом счетчика циклов и с первым выходом блока управления, вход которого соединен с тактовым входом второго триггера, прямой и инверсный выходы которого соединены соответственно с вторыми входами второго и третьего элементов И, выход третьего элемента И соединен с вторым выходом блока зшравле- ния, третий выход которого соединен с прямым выходом первого триггера и тактовым входом третьего триггера, инверсный выход которого соединен с информационным входом первого триггера, а информационные входы второго .JQ и третьего триггеров соединены с шиной логической единицы.

20

25

v «SI X 25

fO

CM ft)