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

ОСУДАРСТНЕННЫЙ КОМИТЕТ ССС ОДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫ К АВТОРСКОМУ СИИ(5 б) Авторское свид Оф 646331, кл. С 06 Авторское свидет 9 1103224, кл. С 06(54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ДВОИЧНЫХЧИСЕЛ 57) Изобретение относится к вычисли ельной технике и может быть исполь" оваио в специализированных вычисли 801432508 А 1 тельных устройствах. Цель нэобратения - повЫюение быстродействия операции деления двоичных чисел эа счетисключения сдвига кода частного врегистре частного после определениявсех цифр частного. Устройство дляделения двоичных чисел содержит регистры делимого 1, делителя 2 и частного 3, сумматор 4, блок 5 сравнениякодов, блок 6 преобразования кодаделителя, элемент НЕ 7, счетчик 8,блок 9 управления триггер 10, элемент ИСКЛЮЧАЮЩЕЕ ИЛИ 11, демультиплексор 12, блок 13 элементов ИЛИ,соединенные между собой функционально. 2 ил.Изобретение относится к вычислич 1 ельной технике и может быть использовано в специализированных вычислительных устройствах.11 ель изобретения - повышение быстродействия устройства для деления,На фиг, 1 представлена Функциональная схема устройства для деления двоичных чисел, на Фиг. 2 - функцио 1 альная схема блока управления.Устройство (фиг. 1) содержит реистры делимого 1, делителя 2, частого 3, сумматор 4, блок 5 сравнения, лок 6 преобразования кода, элемент 1 Е 7, счетчик 8, блок 9 управления, риггер 10, элемент ИСКЛЮЧАЮЩЕЕИ 11, демультиплексор 12, блок 13 элементов ИЛИ с соответствующими связями, 20Блок 9 управления (Фиг. 2) соержит генератор 14 тактовых импульсон, первый 15, второй 16 и третий 17 элементы И, элемент НЕ 18, счетчик 19 циклов, первыи 20, второй 21 25третий 22 триггеры с соответствующими связями,Устройство работает следующим образом.До начала операции деления ре- ЗО гистр 3 частного устанавливается в нулевое состояние, в регистр 2 делителя записывается п-разрядный делитель, п-разрядное делимое записыва 4 тся в регистр 1 делимого, причем в п + 1)-й разряды регистра 1 делимого и регистра 2 делителя записываются сигналы логического нуля, счетчик 8, триггер 10 устройства, а также первый 20, второй 21, третий 22 "риггеры и счетчик 19 циклов блока 9 управления установлены в нулевое Состояние,На прямом: выходе триггера 21 присутствует сигнал логического нуля, на его инверсном выходе - сигнал логической единицы. Сигнал логического нуля с выхода счетчика 19 циклов поступает на вход элемента НЕ 18, ,на выходе которого и втором входе первого элемента И 15 Формируется сигнал логической единицы, разрешая прохожцение импульсов с выхода генератора 14 тактовых импульсов через первый вход первого элемента И 15 на его выход,Если код делимого, занесенный в регистр 1 делимого, больше кода делителя, записанного в регистре 2 делителя, на выходе блока 5 сравнениякодов формируется сигнап логическогонуля, который через вход блока 9 управления поступает на тактовый входего второго триггера 21 подтверждаяего нулевое состояние, и сигналомлогической единицы, поступающим сего инверсного выхода на второй входтретьего элемента И 17, разрешаетпрохождение импульсов с выхода элемента И 15 через элемент И 1 и через второй выход блока 9 управленияна вход сдвига регистра 2 делителя ина счетный вход счетчика 8 устройства,По отрицательному Фронту импульсной последовательности производитсясдвиг содержимого регистра 2 делителя в сторону старших разрядов, т.е,увеличение кода делителя до тех пор,пока на выходе блока 5 сравнениякодов не появляется сигнал логической единицы, свидетельствующий отом, что делитель в регистре 2 делителя "нормализован", т.е. стал больше кода делимого в регистре 1 делимого. Счетчик 8 подсчитывает количество импульсов, необходимых для сдвигакода делителя в регистре 2 делителя,и на его входах Формируется двоичныйкод, соответствующий числу импульсовсдвига кода делителя. Появление сигнала логической единицы на выходеблока 5 сравнения и через вход блока9 управления на тактовом входе триггера 21 переводит его в противоположное состояние, На инверсном выходетриггера 21 формируется сигнал логического нуля, который запрещаетпрохождение импульсов на выход элемента И и через второй выход блока9 управления на вход сдвига регистра2 делителя и счетный вход счетчика8, Если код делимого меньше кода делителя, на выходе блока 5 сравнениякодов Формируется сигнал логическойединицы, который через вход блока 9управления поступает на тактовый входтриггера 21 и переводит его в единичное состояние, В этом случае на выход элемента И 17 и на второй выходблока 9 управления не проходит ниодин импульс и сдвига кода делителяв регистре 2 делителя не происходит, .В этом случае на счетный вход счетчика 8 импульсы не поступают, и наего выходах сохраняется нулевое состояние.Сигналы с выходов счетчика 8 пос"тупают на адресные входыдемультинлексора 12, в котором в зависимости отсигналов на адресных входах произво 5дится коммутация сигнала с информационного входа на один из его выходов. Таким образом, если сдвига кодаделителя в регистре 2 делителя непроизводится, на выходах счетчика 8 и 10адресных входах демультиплексора 12присутствует нулевая кодовая комбинация сигналов, и сигнал с информационного входа демультиплексора ком"мутируется на его первый выход. 15Если сдвиг кода делителя в регистре 2 делителя производится на один,два или к разрядов, на выходах счетчика устанавливаются соответственнокодовые комбинации: 0001, соответствующая одному тактовому импульсу,поступившему на счетный вход счетчика 8, 0010, соответствующая двум тактовым импульсам и т.д. По этим кодо-. вым комбинациям на адресных входах , 25демультиплексора 12 сигнал с его информационного входа коммутируетсясоответственно на второй, третий илиш-й выходы,30Далее начинается пошаговый процессопределения цифр частного по алгоритму, согласно которому код делимогоиз регистра 1 делимого со сдвигом наодин разряд в сторону старших разрядов подается на входы первой группысумматора 4, причем на первый входпервого разряда сумматора подаетсясигнал логического нуля. Код делителя из регистра 2 делителя через блок6 преобразования кода делителя поступает на входы второй группы сумматора 4 в дополнительном коде, В сумматоре 4 производится вычитание кодаделителя из кода делимого. Результат вычитания определяется по выходу"знакового" (п + 2)-го разряда сумматора 4, сигнал с которого инвертиру-ется элементом НЕ 7, поступает черезинформационный вход демультиплексора 12 на соответствующий его выход ичерез блок 13 элементов ИЛИ на соответствующий информационный вход регистра 3 частного, тем самым исключая(после завершения операции деления)сдвиг кода частного в сторону старших разрядов на количество импульсов,равное числу импульсов сдвига кодаделителя при его "нормализации",Кроме того, "знаковый" (и + 2)-й разряд остатка с выхода (и + 2)-го разряда сумматора запоминается в триггере 10, сигнал с выхода которого поступает на вход управления блока 6 преобразования кода делителя и управляет передачей кода делителя на входы второй группы сумматора 4 в следующем такте определения цифр частного. Остаток с выходов сумматора 4 одновременно с записью цифры частного в соответствующий разряд регистра 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 управления поступают на счетный входгического нуля во всех циклах определения цифр частного. Одновременнос записью информации в регистр 3частного производится запись инфор 5мации о знаке остатка в триггер 10.Кроме этого, в регистр 1 делимогопо спаду первого импульса последовательности записывается код остатка10 с выходов разрядов сумматора 4, Этимзаканчивается Формирование первойцифры частного,На втором входе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 после окончания формирования первой цифрь частного устанавливается сигнал логического нуля стретьего выхода блока 9 управления,таким образом, сигнал на выходе элемента ИСКЛЮЧАЮЩЕЕ ИЛИ 11 до окончания цикла деления повторяет сигнална его первом входе, т.е, сигнал свыхода триггера 10, который характеризует знак остатка полученный приопределении первой цифры (в после 2 Б дующих циклах - полученный при определении предыдущей цифры частного),Сигнал с выхода триггера 10 поступает на вход управления блока б преобразования кода делителя, на вход пеЗ 0 реноса и вход (п + 2)-го разрядавторой группы сумматора 4. Если остаток при Формировании первой цифрычастного отрицателен, в триггер 10записывается сигнал логического нуля, который поступает на вход пере 35носа и вход (и + 2)-го разряда второй группы сумматора 4 и вход управления блока б преобразования кодаделителя, разрешая прохождение "нор 40мализованного" кода делителя с выходов регистра 2 делителя на входывторой группы сумматора 4 в прямомкоде,е Если остаток при Формировании первой цифры частного положителен, в45триггер 10 записывается сигнал логической единицы, который поступает навход переноса и вход (и + 2)-го разряда второй группы сумматора 4 и навход управления блока б преобраэова 50ния кода делителя и переводит кодделителя, поступающий на входы второй группы сумматора 4, в дополнительный код.Таким образом, если остаток при:Формировании первой цифры частногоотрицательный, в сумматоре 4 производится сложение остатка с "нормализованным" кодом делителя, если оста"и еоб ви 5 1432508 счетчика 19 циклов, на тактовый вход триггера 20 и на первый выход блока 9 управления.Счетчик 19 циклов подсчитывает количество циклов деления. Триггеры 20 и 22 образуют схему Формирования импульса, передний Фронт которого сопадает с передним фронтом первого изпоследовательности импульсов гене атора 14 тактовых импульсов, а сп д импульса совпадает с передним Фррнтом второго импульса последоватеньности генератора 14 тактовых импу ьсов, поступающих с выхода элеме та И 16. Сформированный сигнал че ре третий выход блока 9 управления по тупает на второй вход элемента ИС 0 ЧЛОЩЕЕ ИЛИ 11 для перевода "н рмализованного" кода делителя в до олнительный код при определении пе вой цифры частного.На первые входы сумматора 4 подает я прямой код делимого с выходов ре истра 1 движимого, сдвинутый на од н разряд в сторону старших разрядо , причем на первый вход первого разряда сумматора 4 подается постоянно, сигнал логического нуля., В сумматоре 4 производится вычита ние нормализованного" кода делителя из кода делимого, в первом цикле опрецеления цифр частного вычитание является обязательным в силу данного алгоритма деления двоичных чисел, На выходах первого, второго, , (и + + 1)-го разрядов сумматора : Формируется код остатка. Знак остатка Фор мнруется на выходе (и + 2)-го разряда сумматора 4 и соответствует сигналу логического нуля, если остаток положительный. Соответственно в первом случае в регистр 3 частного н ходимо записать цифру частного в де логической единицы, во втором случае - логический нуль, Сигнал зна ка, остатка с выхода (п + 2)-го разряда сумматора 4 инвертируется элементом НЕ 7 и поступает на информационный вход триггера 10 и информационный вход,цемультиплексора 12. По сигналам на адресных входах послед" него сигнал с его информационного входа коммутируется на один из его выходов и через блок 13 элементов ИЛИ записывается в регистр 3 частного. На остальных выходах демультиплексора 12 присутствуют сигналы ло 7ток при формировании первой цифрычастного положительный, в сумматоре4 производится вычитание из остаткакода делителя,Знак очередного остатка формируется на выходе (п + 2)-го разрядасумматора 4, инвертируется элементомНЕ 7 и через демультиплексор 12 поступает на его соответствующий выходи через блок 13 элементов ИЛИ насоответствующий информационный входрегистра 3 частного. Кроме того, знакочередного остатка с выхода элементаНЕ 7 записывается в триггер 10.Таким образом, происходят формирование сигнала второй цифры частного и запись его в регистр 3 частного, а также сдвиг в регистре 3 частного сигнала первой цифры частногона один в сторону старших разрядов,В триггере 10 производится запоминание сигнала знака остатка для последующего цикла деления,После определения всех цифр частного последний импульс из последовательности импульсов поступает насчетный вход счетчика 19 циклов, навыходе которого формируется сигналлогической единицы, который инвертируется элементом НЕ 18 и поступаетна второй вход элемента И 15, блокируя поступление импульсов с выходагенератора 14 тактовых импульсов навыход элемента И 15. Этим заканчивается операция деления двоичных чисел.Так как операция деления производится с модулями двоичных чисел, знакиделимого и делителя в процессе деления участия не принимают, поэтомузнак частного может быть определен,например, в результате сравнения сигналов знаков делителя и делимого налогическом элементе ИСКЛЮЧАЮЩЕЕ ИЛИи записи полученного результата втриггер одновременно с записью кодовделимого и делителя соответственнов регистры делимого и делителя.По сравнению с известным устройством, в котором сдвиг кода частногопосле определения цифр частного производится всегда на количество разрядов, на которое был сдвинут код делителя при "нормализации", в предлагаемом устройстве сдвига кода частногопосле определения всех цифр частногоне производится за счет того, чтоцифры частного в регистрчастного записываются с учетом нормализации 8т.е. сдвига кода делителя. Тем самым быстродействие предлагаемого устройства увеличивается на время, равное 5сдвигу кода делителя при его "норма.лизации".Формула изобретенияУстройство для деления двоичныхчисел, содержащее регистр делимого,регистр делителя, регистр частного,сумматор, блок сравнения кодов, счетчик и блок управления, причем разрядные выходы регистра делимого соединены соответственно с информационнымивходами первой группы блока сравнения кодов, информационные входывторой группы которого соединены соответственно с разрядными выходамирегистра делителя, а выход блокасравнения кодов соединен с входомблока управления, первый выход которого соединен с входом разрешения 25 записи регистра делимого, информационные входы которого соединены соответственно с разрядными выходамисумматора, второй выход блока управ"ления соединен с входом сдвига ин формации регистра делителя и со счетным входам счетчика, а блок управления содержит генератор тактовых импульсов, выход которого соединен спервым входом первого элемента И,выход которого соединен с первымивходами второго и третьего элементовИ, выход второго элемента И соединенс тактовым входом первого триггера,и счетчик циклов, выход которого 40соединен с входом элемента НЕ, о т -л и ч а ю щ е е с я тем, что, сцелью повышения быстродействия, вустройство введены демультиплексор,триггер, группа элементов ИЛИ, элемент ИСКЛЮЧАЗХ 1 ЕЕ ИЛИ, элемент НЕ иблок преобразования кода, содержащийгруппу из (и + 1) элементов ИСКЛЮЧАЛИЕЕ ИЛИ (где и - разрядность операндов), первые входы которых являютсяинформационными входами блока преобразования кода, вторые входы элементов ИСКЛЮЧЖИЕЕ ИЛИ объединены и являются управляющим входом, а выходы элементов ИСКЛЮЧАЮЩЕЕ ИЛИ являются разрядными выходами блока преобразования кодов, причем разрядные выходы с первого по (и + 1)-й регистра делимого соединены соответственно свторого по (и + 2)-й разрядными вхо 9 1 ч 32508 1 О дами первой группы сумматора, пер" число выходных разрядов демультиплеквый разрядный вход которой соединен сора) соединен с первым входом с шиной логического нуля, а разряд)-го элемента ИЛИ группы, выход ные входы с первого по (и + 1)-й которого соединен с 1-и входным развторой группы сумматора соединены5рядом регистра частного, разрядные соответственно с разрядными выходами выходы которого с первого по (щ)-й блока преобразования кодов, информа- соединены соответственно с вторыми ционные входы которого соединены со- входами элементов ИЛИ группы, а в ответственно с разрядными выходами 1 О блок управления устройства введены регистра делителя, а управляющий второй и третий триггеры, причем вывход блока преобразования кодов сое- ход элемента НК блока управления соединенс входом переноса, (п + 2)-м динен с вторым входом первого элеазрядным входом второй группы сум- мента И, выход второго элемента И 1матора и с выходом элемента ИСИПОЧАЮ соединен со счетным входом счетчика БЕ ИЛИ, первый вход которого соеди- циклов и с первым выходом блока упоен с выходом триггера, а второй - с равления, вход которого соединен с третьим выходом блока управления, тактовым входом второго триггера, п + 2)-й разрядный выход сумматора прямой и инверсный выходы которого соединен с входом элемента НЕ, выход 2 О соединены соответственно с вторыми которого соединен с информационными входами второго и третьего элементов Ьходами демультиплексора и триггера, И, выход третьего элемента И соедитактовый вход которого соединен с нен с вторым выходом блока управлеЙервым выходом блока управления и ния, третий выход которого соединен тактовым входом регистра частного, 25 с прямым выходом первого триггера и 1 азрядные выходы счетчика соединены тактовым входом третьего триггера, соответственно с адресными входами инверсный выход которого соединен с 4 емультиплексора, первый разрядный информационным входом первого тригге 6 ыход которсго соединен с первым ра, а информационные входы второго входным разрядом регистра частногозО и третьего триггеров соединены с щиа каждый -й разрядный выход демуль- ной логической единицы. ч,"иплексора (где з. " - 2, т, щ -.Сердюкова 1 оррек Патай ехр Тираж 704 ВНИИПИ Государственного по делам изобретений 113035, Москва, Ж, РаушЗаказ 544 1 предприятие, г. Ужг ул. Проектная,едактор И.Горная Производственно-полиграфическ Подписноекомитета СССРи открытийкая наб., д. 4/