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

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

Известно устройство для деления двоичных чисел, содержащее регистры делимого и делителя, пирамиду сумматоров, элементы И, ИЛИ ij .

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

Наиболее близким по технической сущности к изобретению является устройство для деления, содержащее регистры делимого и делителя, два блока элементов И, два сумматора, блок управления;, причем поразрядные выходы регистра делимого подключены к соответствующим входам первого блока элементов И, выход которого подключен к первому входу первого сумматора, второй вход.которого подключен к выходу младшего разряда регистра делимого, старший разряд которого подключен к выходу первого сумматора, -третий вход которого подключен к выходу блока управления и к первому входу второго сумматора второй вход которого подключен к выходу младшего разряда регистра дел ителя, поразрядные выходы которого подключены к соответствукяцим входам второго бло.ка элементов И, выход которого подключен к третьему входу второго сумматора, выход которого подключен к входу старшего разряда регистра делителя, второй выход блока управления подключен к вторым входам блоков элементов И, выход второго сумматора подключен к входу блока определения переполнения, выход которого подключен к входу блока управления 2j .

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

Целью изобретения является повышение быстродействия устрюйства за счет сокращения времени выполнения каждой итерации.

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

мента ИЛИ, где первые выходы первого и второго элементов И каждой группы объединены и являются разрядными входами формирователя сдвига, вторые входы первых элементов И групп объединены и являются первым управляющим входом формирователя сдвига. Вторые входы вторых элементов И групп объединены и являются вторым управляющим входом формирователя сдвига, ВЫХОДЫ1 второго элемента И(к-1)-ой группы и первого элемента И к-ой группы соединены соответственно с первыми и вторыми, входами элементов ИЛИ (к-1)-ой rpyhпы, выходы которых являются разрядными выходами формирователя сдвига, причем первый и второй суммато устройства выполнены как сумматорывычитателн, регистры делимого и делителя выполнены в виде отдельных.регистров для положительной и отрицательной частей делимого и делителя соответственно, поступающих на них в избыточной двоичной системе счисления, выходы регистров делимого соединены соответственно с первым и вторым входами сумматора результата и с информационными входами первого и второго блоков сдвига, выходы крторыз& соединены соответственно с третьими и четвертыми входс1ми первого сумматора-вычитателя, выходы которого соединены соответственно с входами регистров делимого, выходы регистров делителя .соединены соответственно с информационными входами третьего и четвертого блоков сдвига, выходы которых соединены соответственно с третьим и четвертым входами второго cyMiviaTopa-вычитателя, выходы которого соединены соответственно с входами регистров делителя, выходы старших разрядов регистров делителя соединены с первым входом блока ана.аиза переменных, первый выход которого соединен с управляющими входами сумматороввычитателей, второй выход г с управляющим входом формирователя сдвига, разрядные входы формирователя сдвига и блока анализа переменных соединены с выходом дешифратора/ вход которого со.единен с выходом счетчика, вход счётчика соединен с тактовым входом устройства, а выход формирователя сдвига соединен с управляющими входгми первого, второго, третьего и четвертого блоков сдвига.

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

Устройство содержит регистры 1 5 и 2 делимого, регистры 3 и 4 делителя, сумматор 5 результата, первый и второй сумматоры-вычитатели б и 7, первый, второй, третий и четвертый блоки 8-11 сдвига, блок 12 анализа переменных, формирователь 13 сдвига, дешифратор 14, счетчик 15, тактовый вход 16 и выход 17 устройства, причем выходы регистров 1 и 2 делимого соединены соответственно с входами сумматора 5 результата, с входами блоков в и 9 сдвига и с первым и вторым входами первого сумматора-вычитателя Б, выходы которого соединены соответственно с входами регистров 1 и 2 делимого, выходы старших разрядов регистров 3 и 4 делителя соединены с первым входом блока 12 анализа переменных, выходы остальных разрядов регистров .3 и 4 делителя соединены соответственно с входами блоков 10 и 11 сдвига и с первым и вторым входами второго сумматора-вычитателя 7, выходы которого соединены соответственно с входами регистров 3 и 4 делителя, выходы блоков 8 и 9 сдвига соединены с третьим и четвертым входами сумма тора-вычитателя 6, выходы блоков 10j 11 сдвига соединены с третьим и четветрым входами сумматора-вычитателя 7, управляющие входы блоков 8-11 сдвига соединены с выходом фоцмирователя 13 сдвига, информационные входы которого соединены соответ- ственно с выходами дешифратора 14,. входы которого соединены с выходами счетчика 15, на вход счетчика 15 поступают импульсы тактовой частоты с входа 16 устройства, выходы, дешифратора 14 соединены с информационными входами блока 12 анализ-а переменных, первый выход которого соединен с управляющим входом формирователя 13 сдвига, а второй выход с управляющими входами сумматороввычитателей 6 и 7, выход счетчика 5 результата является выходом 17 уст ройства.

Формирователь 13 сдвига (фиг.2) содержит к групп из двух элементов И 18 и 19 и элемента ИЛИ 20 причем первые входы первого и второго элементов И 18 и 19 каждой группы объединены и являются информационными входами формирователя 13 сдвига,

вторые входы первых элементов- И 18 групп и вторые входы вторых элементов И 19 групп являются управляющими входами форкшрователя 13 сдвига, выходы второго элемента И 19 к-ой группы и первого элемента И 18

к-1) -ой группы соединены соответственно с первыми и вторыми входами

элементов ИЛИ 20 (к-1)-ой группы, выходы которых являются разрядными выходами формирователя 13 сдвига.

Устройство работает следукяцим образом.

Деление выполняется в избыточной системе счисления. Вз этой системе . любое к-разрядное число X ( представляется в виде

- -(1)

Хр€ 0,lZ - положительная циф. ра р-го разряда;

Хр е Го,1 - отрицательная циф ра РГ-ГО разряда;

5

,K - номер разряда. Процесс вычисления частного основывается на следующих равенствах. Делитель представляется в виде

V. ..,

0

где С е 0,1 , E;p,e(-l,0,l3 , ,K номер итерации.

Тогда значение частного представ5ляется в виде ,«., / .J, С 1-НЕр2 - 3 . (3) Из (2) получаем тождество

У

0

На основании (3) и (4) процесс деления представится следующими рекуррентными :выражениями

ри --2,, (5)

V, 2, С1+Ер2-1Р- 1 ,

5

где ,2,;.. ,к- Epe{;-i,o,+iJ ;се{о,Л

Начальные условия: X, Х, Уц У. Результат: , .

Переменные Ер и С на каждой р-ой

0 итерации определяются по значениям старших разр5шов Ур таким образом, чтобы первый после запятой разряд Ур . в результате выполнения (6) принимал нулевое значение. При этом переменная Ур стремится к значению

5 У1,1, а переменная Хп - к значению .

г

в табл. 1 приведена зависимость значения Ер и С от значений старших

0 разрядовпеременной Ур. Et,Ep двоичные переменные уЬравления сумматорами f

Ер Е р-Ер; , EpefO,l| Ye 0, переменная номера итера5ции Ц) 1 при , Cf 0 при ..

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

0 влияет на выходные сигналы.

Таблица 1

УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ДВОИЧНЫХ ЧИСЕЛ, содержащее регистры делимого и делителя, первый и вто- . рой сумматоры, причем выходы регистров делимого и делителя соединены соответственно с первыми и вторыми входами первого и второго сумматоров, отличающееся тем, что, с целью повышения быстродействия путем сокращения времени выполнения каждой итерации, в него введены сумматор результата, блок анализа переменных,первый,второй,третий и четвертый блоки сдвига,дешифратор, счетчик и формирователь сдвига, содержащий к групп из дэух элементов И и элементов ИЛИ,, где первые входы первого и второго элементов И каждой группы объединены и являются разрядными входами формирователя сдвига, вторые входы первых элементов И групп объединены и являются первым управляющим входом формирователя сдвига, вторые входы вторых элементов И групп объединены и являются вторым управляющим входом формирователя сдвига, выходы второго элемента И(к-1) -ой группы и первого элемента И к-ой группы соединены соответственно с первыми и вторыми входами элементов ИЛИ .(к-1)-ой группы, выходы которых являются разрядными выходами формирователя сдвига, причем первый и второй сумматоры устройства выдолнены как сумМаторы-вьгчнтатели, регистры делимого и делителя выполнены в виде Ьтдельных регистров для положительной и отрицательной частей делимого и делителя соответственно, поступающих на них в избыточной двоичной системе счисления, выходы регистров делимого соединены соответственно спервым и вторым входами сумматора результата и информационными входами первого и второго блоков сдвига, выходы которых соединеi ны соответственно с третьими и четвертыми входами первого сумматора(Л вычитателя, выходы которого соединены соответственно с входами регистров делимого, выходы регистров делителя соединены соответственно с информационными входами третьего и четвертого блоков сдвига, выходы которых соединены соответственно с третьим и четвертым входами второго сумматора-вычитателя, выходы коСХ) торого соединены соответственно С входами регистров делителя, выходы старших разрядов регистров делителя соединены с первым входом блокаанализа переменных, первый выход котоСХ СП рого соединен с управляющими входами сумматоров- вычитателей, второй выходс управляквдим входом формирователя сдвига, разрядные входы формирователя сдвига и блока анализа переменных соединены с выходом дешифратора, вход которого соединен с выходом счетчика, вход счетчика соединен с тактовым входом устройства, а выход формирователя сдвига соединен с управляющими входами первого, второго, третьего и четвертого блоков сдвига.

1 1 1 1 1 Л 1 1 О О О

о о о о о о о о о о о о о о о о о о В устройстве регистры 1 и2 дели мого и регистры 3 и.4 делителя пред назначены соответственно для хранения переменных , Ур представленных в избыточной системе счисления Каждый регистр содержит (;К-+-1) разря дов, к разрядов для дробной части и один разряд для целой части перемен ной. .Каждый разряд регистров представляет собой обычный двоичный триггер. В регистре 1 хранятся поло жительные цифры Хр в регистре 2 отрицательные цифры хй, ,К) пере менной Xj,, В регистре 3 и 4 соответственно хранятся цифры Ур, Ур (,К) переменной Vf. В табл. 2 приведено рортветствие между цифрами и значением разряда переменных X и У. Таблица 2 Сумматор 5 предназначен для преобразования результата деления, хранящегося в конце вычислений на регистрах 1 и 2, из избыточной системы счисления в двоичную и для хра нения результата, выполнен в виде параллельного сумматора накапливающего типа с распространением перено са на всех к разрядов. Сумматоры-вычитатели 6 и 7 предназначены для выполнения сложениявычитания над числами в избыточной системе счисления на каждом итера ционном шаге вычислений. Блоки 8-11 СДВИГ9 предназначены для параллельного сдвига содержимого регистров 1 - 4 на (р-с) раз рядов влево. Блок анализа переменных предназн чен для реализации логической функц представленной в табл.1, т.е. для определения по стасшим разрядам переменной Ур и номеру итерации управлякхци переменных С, Ер Е на каждом итерационном шаге. Блок 12 анализа реализует следукхцие логические функции в соответствии с таблицей истинности 1: C Q M jY-jY vCpX YA Y X-jV , V E; c Ytv;4 2 44t ;v;v Y;Y;v;4-,4 ,,(8 fcf ; 1 : ;ч у л-л ч:у;у; V vY;4 2Y2f3vVV,,Y v. .w Блок 12 анализа выполнен на логических схемах И и ИЛИ. Значения переменных У|, У,7 У, у, У, УЗ поступают на первый вход блока анализа с регистров 3 и 4, а переменная Cf на второй вход блока 12 анализа поступает с дешифратора 14. Формирователь 13 сдвига (фиг.2) предназначен для формирования величины сдвига (р-с) Значение р поступает на первый вход формирователя 13 с дешифратора 14, значение С поступает на второй вход с второго выхода блока 12 анализа. Указанное преобразование выполняется в формирователе 13 на элементах И 18 и 19 и элементе ИЛИ 20. счетчик 15 и дешифратор 14 предназначены для счета номера итерации и его дешифрации. Деление производится над положительными числами, знак результата определяется по сочетанию знаков деделимого и делителя. Перед началом вычисления в регистры 1 и 3 заносятся сдвинутые влево на один разряд двоичные числа - делимое 2 X и делитель 2У. Далее производится выполнение к итераций в соответствии с уравнениями (5), (.6). На каждой итерации производятся следующие действия. В счетчике 15 тактов производится прибавление единицы по синхроимпульсу с входа 16, в дешифраторе 14 производится дешифрирование кода номера итерации р, значение которого поступает на первый вход формирователя 13 сдвига. Одновременно в блоке. 12 анализа переменных по значениям старших разр51дов регистров 3 и 4 формируются значения переменных С, Ер, Ер}, значения Ер Ер поступают с второго выхода блока 12 анализа на управляющие входы первого и второго сумматоров вычитателей . 6 и 7 значение С - на второй вход формирователя 13 сдвига. В формирователе.13 сдвига формируется величина (р-с1, которая Аоступает на управляющие входы-блоков 8-11 сдви« га. В.этих блоках производится сдвиг содержимого регистров 1-4 вправо на р-с) разрядов, что равнозначно умножению переменных и Ур на 21), Затем в сум латорах-вычитателях 6 и 7 производится алгебраическое сложение переменных Хр и Ур соответственно со сдвинутыми вправо переменными Е- Х.и ЕрУ 2lP-c и соответствии с Уравнениями (5 и (6). В результате на выходах сумматоров вычитаталей 6 и 7 формируются переменные 1/2 Хр«. и 1/2 Ур+|| в избыточной двоичной системе, которые записываются на регистрах 1-4со сдви гом на один разряд. При этом в регистрах значения переменных Хр, записываются на их новые значения ХР+, У вычисленные в данной итерации. При сдвигах влево в регистрах 3 и 4 ста Н11ие разряды переменной УЙ теряются. Однако оставшиеся раз-, ряды дробной части обеспечивают правильное выполнение алгоритма д еления.. После выполнения к итераций в регистрах 1 и 2 хранится результат

-1

+1 +1

Выполнение итераций в устройстве может быть прекращено на любой р-ой итерации, если все разряды У окажутся нулевьои1и. Это позволяет, дополнительно повысить среднее быстродействие устройства..Использование новых элементов - регистров положительной и отрицательной частей делимого и.делителя, сумматоров-вычитателей, формирователя сдвига анализа и сумматора результата сокращает время выполнения итерации

0,1011011

0,100100 1, I01H 0110000, 1,001000000 -10-1-10-1-1QO -100-100000

оТТооГоМоо

1,0-g.ogf-io-iooo

1,0-100-10-10

0,100000

i,ooB-i-ii-ioo-i о 1,-100-11-1бОО

1,000-1-1-10

1-110-11-1

ТТОоо МбГоо о

1рПТ о 1-111

Преобразование

f-011000010 О, 100101101 0,110010101

в предлагаемом устройстве по сравнению с. известным.

Устройство для деления двоичных чисел выполнено на современных интегральных микросхемах для больших разрядностей при приемлемых аппаратурных -затратах. Высокая регулярность и однородность структуры устройства позволяет эффективно реализовать его на интегральных микросхемах с повышенной степенью интеграции. деления Х|,Х/У, представленный в из быточной двоичной системе счисления. Прео бразование результата в обычную двоичную систему производится на сумматоре 5 результата; с распространением переноса.Преобразование на сумматоре 5 результата сводится к алгебраическому сложению двух двоичных чисел, представленных на регистрах 1 и 2. В табл.3 приведен пример деления двоичных чисел ,10010,,1011011. В конце таблицы приведено преобразование резульата из избыточной в обычную двоичную систему счисления путем алгебраического сложения положительной и отрицательной частей избыточного результата. ТаблицаЗ

/f/7