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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК

„„Я0„„1617 (S1)5 С 06 F 7 52 с

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

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР (21) 4612077/24 (22) 28.11,88 (46) 30.12.90. Бюл. У 48 (72) В.Н.Батищев, А.А.Добрынин и А.А.Косой (53) 681.325(088.8) (56) Авторское свидетельство СССР

N9 1361545, кл. G 06 Е 7/52, 1986.

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

У 1432508, кл. G 06 F 7/52, 1987. (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНА ДВОИЧНЫХ

ЧИСЕЛ (57) Изобретение относится к вычислительной технике, в частности к устройствам для деления двоичных чисел.

Целью изобретения является повышение

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

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

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

Устройство для деления двоичных чисел содержит регистр 1 делимого, регистр 2 делителя, регистр 3 частного, первый сумматор 4, элемент НЕ 5, элемент ИСКЛЮЧАЮ!ПЕЕ ИЛИ 6, триггер 7, демультиплексор 8, группу элементов

ИЛИ 9, блок 10 управления, блок 11 преобразования кода делителя, пербыстродействия операции деления двоичных чисел за счет нормализации кода делителя, .исключающий последовательный многотактовый сдвиг этого кода. Устройство для деления двоичных чисел содержит регистр 1 делимого, регистр 2 делителя, регистр 3 частного, первый сумматор 4, элемент

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

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

21 триггеров.

Пусть A — делимое,  — делитель— двоичные числа, над которыми производится операция деления. Jlо начала деления необходимо провести нормализацию делителя, т.е. умножить

его на множитель нормализации 2 (или сдвинуть его в сторону старшего разряда k-раз), т.е. процесс нормализация делителя соответствует выполнению неравенстл

А — ? В О, (1) 1617437

10 5

20 — 2

А

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

Виду полагая, что В 0;в противном случае операция деления невозможна.

Логарифм по основанию два от обеих

t частей неравенства (2)

log (- ) 1о8 (2 ) Упрощая его, получают

log

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

Возводят два в степень, равную этому целому числу, и получают множитель нормализации делителя.

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

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

До начала операции деления регистр

3 частного устанавливается в нулевое состояние, в регистр 2 делителя записывается п-разрядный делитель,п-разрядного делимое записывается в регистр 1 делимого, причем в (и+1) разряды регистра 1 делимого и регистра

2 делителя записываются сигналы "0"; триггер 7, счетчик 18 циклов, первый

20 и второй 21 триггеры устанавливаются в нулевое состояние.

Код делимого, записанный в регистр

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

Таким образом, на выходе первого блока 12 формируется сигнал 1ор А (где A — код делимого в регистре 1 делимого), целая часть которого поступает на разрядные входы первой группы входов второго 14 сумматора.

Код делителя, записанный в регистр 2 делителя, поступает на входы второго блока 13 вычисления логарифма, на выходе которого аналогично преобразованию кода делимого в первом блокв 12, формируется сигнал log В (где  — двоичный код делителя, причем результат логарифмирования представляется в дополнительном коде) °

Целая часть результата lор В поступает на разрядные входы второй группы второго 14 сумматора, на вход переноса СО которого поступает сигнал

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

log А — log В + 1 = k

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

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

k кода делителя проводится сразу же после записи кодов делимого и дели теля в регистры 1 делимого и 2 делителя.

Сигнал кода с выхода второго 14

40 сумматора поступает на адресные разрядные входы демультиплексора 8, в котором в зависимости от сигнала на адресных входах производится коммутация сигнала с информационного входа

45 на один из его выходов. Далее начинается пошаговый процесс определения цифр частного по алгоритму, согласно которому код делимого из регистра 1 делимого со сдвигом по один в сторону старшего разряда подается на разрядные входы первой группы входов первого 4 сумматора, причем на первый вход первых разрядных входов сумматора подается сигнал "0". Код делителя из регистра 2 делителя, нормали зованный с помощью коммутатора 15 через блок 11 преобразования кода, поступает на разрядные входы второй группы первого 4 сутытора в допол5 16174 нительном коде. В первом 4 сумматоре производится вычитание нормализованного кода делителя из кода делимого.

Результат вычитания определяется по (п+2)-разрядному выходу первого 4 сумматора, сигнал с которого инвертируется элементом HE 5, поступает через информационный вход демультиплексора 8 на соответствующий его выход и через группу 9 элементов

ИЛИ на соответствующий входной разряд регистра 3 частного. Кроме того, сигнал знакового (n+2)-rn разряда остатка с разрядного (и+2)-ro выхода первого 4 сумматора запоминается в триггере 7, сигнал с выхода которо— го через элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 6 поступает на управляющий вход блока

11 преобразования кода и управляет 20 передачей нормализованного кода делителя на вторые разрядные входы первого 4 сумматора в следующем такте определения цифры частного. Остаток с разрядных выходов первого 4 25 сумматора одновременно с записью цифры частного в регистре 3 частного записывается в регистр 1 делимого.

Далее процесс повторяется: код остатка поступает на первые разрядные вхо- 30 ды первого 4 сумматора сдвинутым на один разряд в сторону старшего разря, да, на первый вход первой группы разрядных входов первого 4 сумматора поступает сигнал "0". Если в соот35 ветствующий разряд регистра 3 частного и в триггер У в предыдущем цикле был записан сигнал "1", соответствуюший положительному остатку, то нормализованный в коммутаторе 15 код де- 40 лителя через блок 11 преобразования кода подается на вторые разрядные входы первого 4 сумматора в дополнительном коде, в первом 4 сумматоре производится вычитание нормализован- 45 ного кода делителя из кода остатка, Если в регистр 3 частного и триггер 7 в предыдущем цикле был записан сигнал

1! 11

0, соответствующий отрицательному остатку, то нормализованный код де 50 лителя подается на первый 4 сумматор в прямом коде и в первом сумматоре производится сложение кода остатка с нормализованным кодом делителя. Сигнал с (n+2)-го разрядного выхода пер55 вого 4 сумматора инвертируется элементом НЕ 5 и записывается через демультиплексор 8 и группу 9 элементов ИЛИ в тот же разряд. регистра 3

37 6 частного, в который была записана первая цифра частного в первом циклЬ процесса деления, а первая циАра частногс в момент записи второй циАры частного сдвигается на один разряд в сторону старшего разряда в регистре 3 частного. Сигнал знакового (и+2)-ro разрядного выхода первого

4 сумматора инвертируется и запоминается в триггере 7. Далее процесс повторяется.

Импульсы (фиг.3а) с выхода генератора 16 тактовых импульсов через элемент И 17 поступают на счетный вход счетчика 18 циклов, на тактовый вход первого 20 триггера и на первый выход блока 10 управления. Счетчик 18 циклов подсчитывает количество циклов деления. Первый 20 и второй 21 триггеры образуют схему формирования импульсов (фиг.3б), Аронт которого совпадает с фронтом первого из последовательности импульсов (Аиг.3а), а спад импульса (фиг.3) совпадает с Аронтом второго импульса последовательности импульсов (фиг.3а),поступающей с выхода элемента И 17. Импульс (фиг.3б) с прямого выхода первого 20 триггера постулат на второй выход блока 10 управления и на первый вход элемента

ИСКЛЮЧАЮЩЕЕ ИЛИ 6, на втором входе которого присутствует сигнал "0" с выхода триггера 7, на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 6 формируется сигнал "1", который поступает на вход управления блока 11, вход заема и (n+2)-разрядный вход второй группы входов первого сумматора 4, переводя поступающий на вторую группу разрядных входов первого сумматора 4 нормализованный код делителя в дополнительный код. На первую группу разрядных входов первого сумматора 4 подается прямой код делимого с разрядных выходов регистра 1 делимого, сдвинутый на один разряд в сторону старшего разряда, причем на первый разрядный вход первой группы входов первого сумматора 4 подается постоянно сигнал "0".

В первом сумматоре 4 производится вычитание нормализованного кода делителя иэ кода делимого, в первом цикле определения циАры частного вычитание является обязательным в силу данного алгоритма деления двоичных чисел. На разрядных выходах с первого по (n+1) — и первого сумма1617437 тора 4 формируется код остатка, Знак остатка формируется на (n+2)-разрядном выходе первого сумматора 4 и соответствует сигналу "0", если остаток положительный или сигналу "1", 5 если остаток отрицательный, Соответственно, в первом случае в регистр 3 чагтногв необходимо записать сигнал "1",во втором случае необходимо записать в регистр 3 частного

"0". Сигнал знака остатка с (n+2)разрядного выхода сумматора 4 инвертируется элементом НЕ 5 и поступает на информационный вход триггера 7 и ин" формационный вход демультиплексора

8. По сигналам на адресных разрядных входах демультиплексора 8 сигнал с его информационного входа коммутируется на один иэ его выходов, например, второй. На остальных выходах демультиплексора 8 присутствуют сигналы "0" во всех циклах определения цифр. частного.

Сигнал с второго выхода g< демуль- >5 типлексора 8 поступает на второй вход первого элемента группы 9 элементов ИЛИ и с его выхода поступает на второй разрядный вход регистра 3 частного. 30

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

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

На первом входе элемента ИСКЛЮЧАЮlIlEE ИЛИ 6 после окончания формирования первой цифры частного устанавливается сигнал "0" (фиг.Зб) со второго выхода блока 10 управления. Таким

I образом, сигнал на выходе элемента

ИСКЛЮЧАЮШЕЕ ИЛИ 6 до окончания цикла деления повторяет сигнал на его втором входе, т.е. сигнал с выхода триггера 7, который характеризует знак остатка, полученный при формировании первой цифры частного (в последующих циклах — полученной при определении предыдущей цифры частного).

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

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

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

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

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

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

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

3 частного записываются сигналы "О".

Одновременно с записью второй цифры частного в регистр 3 частного знак остатка записынается н триггер

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

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

После определения всех цифр частного последний из последовательности импульсов (фиг.3а) поступает на счет- 25 ный вход счетчика 18 циклов, на выхоII n де которого формируется сигнал 1 . который инвертируется элементом НЕ 19 и поступает на первый нход элемента

И 17, блокируя поступление импульсов 30 с выхода генератора 16 тактовых импульсов на выход элемента И 17, Этим операция деления двоичных чисел заканчивается.

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

ИЛИ и записан н триггер одновременно с записью кодов делимого и делителя соответственно в регистры делимого и 45 делителя.

Если на адресные входы коммутатора

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

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

Устройство для деления двоичных чисел, содержащее регистры делимого, 7 10 делителя и частного, первый "умматор, элементы HE и ИСКЛЮЧАЮ!11ЕЕ ИЛИ, блок преобразования кода делителя, триггер, демупьтиплексор, группу элементов ИЛИ и блок управления, первый выход которого соединен с синхровходами триггера, регистров делимого и частного, выходы разрядов с первого по (и+1)-й регистра делимого соединены с первым информационным входом разрядов с второго по (n+2)-й первого сумматора, информационный вход первого разряда которого соединен с входом логического нуля устройства, выход суммы перI ного сумматора соединен с информационным входом регистра делимого, выход знакового разряда первого сумматора соединен с входом элемента НЕ, выход которого соединен с информационными входами демультиплексора и триггера, выход которого соединен с первым входом элемента ИСКЛЮЧАЮ1ЧЕЕ ИЛИ, выход которого соединен с управляющим входом блока преобразователя кода делителя и вторым информационным входом (n+2)-ro разряда и входом переноса первого сумматора, второй информационный вход с первого по (п+1)-й разрядов первого сумматора соединен с выходом разрядов блока преобразования кода делителя, второй выход блока управления соединен с вторым входом элемента ИСКЛЮЧАЮ111ЕЕ

ИЛИ, выход первого разряда демультиплексора соединен с информационным входом первого разряда регистра частного, информационные входы разрядов с второго по m-й которого соединены с выходами элементов ИЛИ группы, первые входы которых соединены с выходами разрядов с второго по m-й соответственно демультиплексора, вторые входы элементов ИЛИ группы соединены с выходами разрядов с первого по (m-1)-й регистра частного, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены два блока вычисления логарифмов, коммутатор и второй сумматор, выход которого соединен с управляющими входами демультиплексора и коммутатора, выход которого соединен с информационным входом блока преобразования кода делителя, выход регистра делимого соединен с входом первого блока вычисления логарифма, выход которого соединен с первым информационным входом второго суммато11

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

1617437

pV2 . 2

1617437

Р)

Р

Р

С

Czz

С ос тави тель H . .Мар кел ова

Тех ре, JI. Олийнык

Редактор Л.Пчолинская

Корректор Э.Лончакова

Заказ 4119 Тираж 5б4 Подписное

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

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

Производственно-издательский комбинат "Патент", г. Ужгород, ул. Гагарина, 101