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

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

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

На фиг. 1 изображена структурная схема устройства для деления двоичных чисел i на фиг. 2 - функциональная схема блока управления; на фиг.3- диаграммы работы устройства деления двоичных чисел; на фиг. 4 - пример выполнения коммутатора.

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

Блок управления 10 состоит.из генератора 16 тактовых импульсов, элемента И 17, счетчика 18 циклов, элемента НЕ 19 и первого 20 и второго 21 триггеров.

Пусть А - делимое, В - делитель - двоичные числа, над которыми производится опера1№1я деления. До начала деления необходимо провести нормализацию делителя, т.е. умножить его на множитель нормализации 2 (или сдвинуть его в сторону старшего разряда k-раз), т.е. процесс нормализация делителя соответствует выполнению неравенстпа

А - Р. -ВьО . (1)

С/

с

ь

о

Неизвестным параметром полученного неравенства является показатель степени k, который и определяет множитель нормализации. Для определения показателя необходимо привести неравенство (1) к более удобному виду

(2)

полагая, что В 0;в противном случае операция деления невозможна. Логарифм по основанию два от обеих частей неравенства (2)

log(| )log(2 f)

Упрощая его, получают logjA - loggB k .

Таким образом, показатель стеИе- ни k множителя нормализации легко определяется по известным кодам делимого, и делителя. Если показатель k получается дробным, его округляют до ближайшего большего целого числа. Возводят два в степень, равную этому целому числу, и получают множитель нормализации делителя.

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

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

До начала операции деления регист З частного устанавливается в нулевое состояние, в регистр 2 делителя запи сывается п-разрядный делитель,п-раз- рядного делимое записывается в регистр 1 делимого, причем в (п+1) разряды регистра 1 делимого и регистра 2 делителя записываются сигналы триггер 7, счетчик 18 1щклов, первый 20 и второй 21 триггеры устанавливаются в нулевое состояние.

Код делимого,записанный в регистр 1 делимого поступает на входы первого 12 блока вычисления лограрифма, выполненного на блоке памяти, в каж- дои ячейке которого записано числа, соответствующее логарифму по основанию два в зависимости от адресного номера ячейки.

0

5

0

Таким образом, на выходе первого блока 12 формируется сигнал

(где А - код делимого в регистре 1 делимого), целая часть которого поступает на разрядные входы первой группы входов второго 14 сумматора. Код делителя, записанный в регистр 2 делителя, поступает На входы второго блока 13 вычисления логарифма, на выходе которого аналогично преобразованию кода делимого в первом блоке 12, формируется сигнал (где В - двоичный код делителя, причем результат логарифмирования представляется в дополнительном коде). Целая часть результата log В поступает на разрядные входы второй группы второго 14 сумматора, на вход переноса Сд которого поступает сигнал

1 . Таким образом, на выходах второго 14 сумматора формируется сигнал разности логарифмов кодов делимого и делителя плюс единица.

- loggB + 1 k .

Двоичный код результата k с выхода второго 14 сумматора поступает на управляющие разрядные входы коммута- 15 и соответствии с которым

сигнал кода делителя с информа1щонных . разрядных входов коммутатора 15 поступает на вход коммутатора 15 в виде 2 , т.е. операция нормализации кода делителя проводится сразу же после записи кодов делимого и дели- теля в регистры 1 делимого и 2 де- лителя.

Сигнал кода с выхода второго 14 сумматора поступает на адресные разрядные входы демультиплексора 8, в котором в зависимости от сигнала на адресных входах производится коммутация сигнала с информационного входа один из его выходов. Далее начинается пошаговый процесс определения цифр частного по алгоритму, согласно которому код делимого из регистра 1 делимого со сдвигом по один в сторону старшего разряда подается на разрядные входы первой группы входов первого 4 сумматора, причем на первый вход первых разрядных входов сумматора подается сигнал О. Код дели- теля из регистра 2 делителя, нормали - зованный с помощью коммутатора 15 через блок 11 преобразования кода, поступает на разрядные входы второй группы первого 4 сумматора в допол5161

ительном коде. В первом 4 сумматоре роизводится вычитание нормализованого кода делителя из кода делимого. Результат вычитания определяется по - (п+2)-разрядному выходу первого 4 сумматора, сигнал с которого инвертируется элементом НЕ 5, поступает через информационный вход демульти- плексора 8 на соответствуюищн его выход и через группу 9 элементов ИЛИ на соответствующий входной разряд регистра 3 частного. Кроме того, сигнал знакового (п+2)-го разряда остатка с разрядного (п+2)-го выхода первого 4 сумматора запоминается в триггере 7, сигнал с выхода которого через элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 6 поступает на управляющий вход блока 11 преобразования кода и управляет передачей нормализованного кода делителя на вторые разрядные входы первого 4 сумматора в следующем такте определения цифры частного. Остаток с разрядных выходов первого 4 сумматора одновременно с записью цифры частного в регистре 3 частного записывается в регистр 1 делимого. Далее процесс повторяется: код остатка поступает на первые разрядные входы первого 4 сумматора сдвинутым на один разряд в сторону старшего разря- да, на первый вход первой группы разрядных входов первого 4 сумматора поступает сигнал О. Если в соответствующий разряд регистра 3 частного и в триггер 7 в предыдущем 1Ц1кле был записан сигнал 1, соответствующий положительному остатку, то нормализованный в коммутаторе 15 код делителя через блок 11 преобразования кода подается на вторые разрядные вхоы первого 4 сумматора в дополнительном коде, в первом 4 сумматоре производится вычитание нормализованного кода делителя из кода остатка. Если в регистр 3 частного и триггер 7 в предьщущем цикле был записан сигнал О, соответствзаощий отрицательному остатку, то нормализованный код деителя подается на первый 4 сумматор в прямом коде в первом сумматоре производится сложение кода остатка с нормализованным кодом делителя. Сигнал с (п+2)-го разрядного выхода первого 4 сумматора инвертируется элеентом НЕ 5 и записывается через емультиплексор 8 и группу 9 элеменов ИЛИ в тот же разряд, регистра 3

0

5

0

5

0

5

0

5

0

5

376

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

Импульсы (фиг.За) с выхода генератора 16 тактовых импульсов через эле- И 17 поступают на счетный вход счётчика 18 циклов, на тактовьй вход первого 20 триггера и на первый выход блока 10 управления. Счетчик 18 циклов подсчитывает количество циклов деления. Первый 20 и второй 21 триггеры образуют схему фop пфoвaния импульсов (фиг.Зб), фронт которого совпадает с фронтом первого из последовательности импульсов (фиг.За), а спад им- пульса (фиг.З) совпадает с фронтом второго импульса последовательности импульсов (фиг.За),поступающей с выхода элемента И 17. Импульс (фиг.Зб) с прямого выхода первого 20 триггера поступат на второй выход блока 10 управления и на первый вход элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6, на втором входе которого присутствует сигнал О с выхода триггера 7, на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6 формируется сигнал 1, который поступает на вход уи-равпения блока 11, вход заема и (п+2)-разрядньй вход второй группы входов первого сумматора 4, переводя поступающий на вторую группу разрядных входов первого сумматора 4 нормализованный код делителя в дополнительный код. На первую группу разрядных входов первого сумматора 4 подается прямой код делимого с разрядных выходов регистра 1 делимого, сдвинутый на один разряд в сторону старшего разряда, причем на первьй разрядный вход первой группы входов первого с -мматора 4 подается постоянно сигнал О.

В первом сумматоре 4 производится вычитание нормализованного кода делителя из кода делимого, в первом цикле определения цифры частного вычитание является обязательным в силу данного алгоритма деления двоичных чисел. На разрядных выходах с первого по (п+1)-й первого сумматора 4 формируется код остатка. Знак остатка формируется на (п+2)-разрядном выходе первого сумматора А и соответствует сигналу О, если остаток положительный или сигналу 1, если остаток отрицательный. Соответственно, в первом случае в регистр 3 частного необходимо записат) сигнчл 1,во втором случае необходимо записать в регистр 3 частного О. Сигнал знака остатка с (п+2)- разрядного выхода сумматора 4 инверти руется элементом НЕ 5 и поступает на информационный вход триггера 7 и ин форма1щонныч вход демультиплексора 8, По сигналам на адресных разрядных входах демультиплексора 8 сигнал с его информационного входа коммутируется на один из его выходов, например, второй. На остальных выходах демультиплексора 8 присутствуют сигналы О во всех циклах определения цифр частного.

10

(5

20

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

Сигнал с второго выхода Q демуль- 25 цифры частного был положительный, то

типлексора 8 поступает на второй вход первого элемента группы 9 элементов ИЛИ и с его выхода поступает на второй разрядный вход регистра 3 частного,

С первого выхода блока 10 управления импульсы (фиг,За) поступают на вход разрешения записи регистра 1 делимого, тактовый вход триггера 7 и тактовый вход регистра 3 частного.

По спаду первого из последовательности импульсов (фиг,За) сигнал с второго разрядного входа регистра 3 .частного записьгаается на второй разрядный выход регистра 3 частного, в остальные разрядные выходы регистра 3 частного записываются сигналы О, Одновременно с записью информации в регистр 3 частного производится за-- пись информации о знаке остатка в триггер 7, Кроме того, в регистр 1 делимого по спаду первого импульса последовательности (фиг,За) записывается код остатка с разрядных выходов первого сумматора 4, Этим заканчивается формирование первой цифры частного.

На первом входе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6 после окончания формирования первой цифры частного устанавливается сигнал О (фиг.36) со второго выхода блока 10 управления. Таким образом, сигнал на вьпсоде элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6 до окончания 1щкла

30

35

40

45

50

55

в триггер 7 записывается сигнал 1,ко- торьм поступает на вход заема и (п+2)- разрядный вход второй группы входов первого 4 сумматора и на вход управления блока 11 преобразования кода и переводит код делителя, нормали- зованный в коммутаторе 15, в допол - нительный код.

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

Знак очередного остатка формируется на (п+2)-разрядном выходе первого 4 сумматора, инвертируется элементом НЕ 5 и через демультиплексор 8 поступает на второй его выход и второй вход первого элемента ИЛИ группы 9 элементов ИЛИ, с выхода которого поступает на вход второго разряда регистра 3 частного. Кроме то- го, знак очередного остатка с выхода элемента НЕ 5 записывается в триггер 7, Сигнал с первого элемента ИЛИ группы 9 элементов ИЛИ через вход второго разряда регистра 3 частного и сигнал с второго разрядного выходго регистра 3 частного через второй элемент ИЛИ группы 9 элемен

5

0

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

5 цифры частного был положительный, то

0

5

0

5

0

5

в триггер 7 записывается сигнал 1,ко- торьм поступает на вход заема и (п+2)- разрядный вход второй группы входов первого 4 сумматора и на вход управления блока 11 преобразования кода и переводит код делителя, нормали- зованный в коммутаторе 15, в допол - нительный код.

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

Знак очередного остатка формируется на (п+2)-разрядном выходе первого 4 сумматора, инвертируется элементом НЕ 5 и через демультиплексор 8 поступает на второй его выход и второй вход первого элемента ИЛИ группы 9 элементов ИЛИ, с выхода которого поступает на вход второго разряда регистра 3 частного. Кроме то- го, знак очередного остатка с выхода элемента НЕ 5 записывается в триг гер 7, Сигнал с первого элемента ИЛИ группы 9 элементов ИЛИ через вход второго разряда регистра 3 частного и сигнал с второго разрядного выходго регистра 3 частного через второй элемент ИЛИ группы 9 элемен916

та ИЛИ по спаду второго импульса последовательности импульсов (фиг.За) записывается на второй и третий разрядные выходы регистра 3 частного. В остальные разрядные выходы регистра 3 частного записываются сигналы О.

Одновременно с записью второй цифры частного в регистр 3 частного знак остатка записывается в триггер 7, а код очередного остатка с первого по (п+1)-й разрядных выходов первого 4 сумматора записывается в регистр 1 делимого. Так происходит формирование второй цифры частного и запись ее в регистр 3 частного, а также сдвиг в регистре 3 частного первой цифры частного на один в сторону старшего разряда.

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

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

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

Если на адресные входы коммутатора 15 поступает отрицательный код (в сл чае превышения кодом делителя кода делимого, т.е. - ), сдв га кода делителя не происходит. Это может быть достигнуто, например, блокировкой адресных входов коммутатора.

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

Устройство для деления двоичных чисел, содержащее регистры делимого.

43710

делителя и чйстного, первый сумматор, элементы НЕ и ИСКЛЮЧАЮШЕЕ ИЛИ, блок преобразования кода делителя, триггер, демупьтиплексор, группу элементов ИЛИ и блок управления, первый выход которого соединен с синхровходами триггера, регистров делимого и частного, выходы разрядов с первого по (п+1)-й ,. регистра делимого соединены с первым информационным входом разрядов с втр- рого по (п+2)-й первого сумматора, информационный вход первого разряда которого соединен с входом логическо- 5 го нуля устройства, выход суммы первого сумматора соединен с информационным входом регистра делимого, выход знакового разряда первого сумматора соединен с входом элемента НЕ, выход 0 которого соединен с информационными входами демультиплексора и триггера, выход которого соединен с первым входом элемента ИСКЛЮЧАЮШЕЕ ИЛИ, выход которого соединен с управляющим 5 входом блока преобразователя кода делителя и вторым информационным входом (п+2)-го разряда и входом переноса первого сумматора, второй информа1щонный вход с первого по 0 (п+1)-й разрядов первого сумматора соединен с выходом разрядов блока преобразования кода делителя, второй выход блока управления соединен с вторым входом элемента ИСКЛЮЧАЮШЕЕ ИЛИ, выход первого разряда демультиплексора соединен с информационным входом первого разряда регистра частного, информационные входы разрядов с второго по т-й которого сое- Q динены с выходами элементов ИЛИ группы, первые входы которых соединены с выходами разрядов с второго по т-й соответственно демультиплексора, вторые входы элементов ИЛИ группы .с соединены с выходами разрядов с первого по (тп-О-й регистра частного, отличающееся тем, что, с целью повьш1ения быстродействия, в него введены два блока вычисления ло- гп гарифмов, коммутатор и второй сумматор, выход которого соединен с управляющими входами демультиплексора и коммутатора, выход которого соединен с информационным входом блока преобразования кода делителя, выход регистра делимого соединен с входом первого блока вычисления логарифма, выход которого соединен с первым информационным входом второго суммато5

5

1161743712

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

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

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

/5

- -

п

D

J

0

20

L.

Ufi)

Щ

пппппппп

18

19

вшf -

г/

1

Л/х/

Щуг5

Фиг.