Устройство для деления чисел в модулярной системе счисления

 

Изобретение относится к вычислительной технике и предназначено для использованиявбыстродействующих непозиционных арифметических устройствах конвейерного типа для выполнения операции деления чисел, представленных в минимально избыточной модулярной системе счисления. Цель изобретения - повышение быстродействия за счет увеличения пропускной способности устройства. Поставленная цель достигается за счет применения конвейерного принципа обработки модулярных кодов делимого и делителя и обеспечения возможности совмещения во времени процессов выполнения Т + 6 операций деления (Т log2K. К - число оснований модулярной системы счисления; через х обозначается наименьшее целое число, не меньшее х). Для формирования приближения делителя и вычисления знака делителя используется не блок масштабирования, а отдельный блок параллельно-конвейерного типа для формирования интегральных характеристик модулярного кода, обращение к которому можно производить ежетактно, т.е. с частотой f 1/tM.T. (tMT. длительность модульного такта). Устройство содержит коммутаторы 5, б , блок управления 7, узлы 8, 9 задержки, формирователь 10 интегральных характеристик модулярного кода , блок модульного вычитания 11. блок модульного умножения 12, мультиплексор 13, узлы задержки, регистр, блок присвоения знака, коммутатор, блок модульного сложения, блок масштабирования и узлы задержки , 3 ил. сл с xj СЛ О со со

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

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

РЕСПУБЛИК (5П5 G 06 F 7/72

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

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

ПРИ ГКНТ СССР

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

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

6 (21) 4880868!24 (22) 02.11.90 (46) 23.08.92. Бюл. N 31 (71) Н аучно-исследовател ьс к ий и нститут прикладных физических проблем им.

А.Н.Севченко (72) А.А.Коляда, М.Ю,Селянинов, А.Ф;Чернявский и В.Н,Ахременко (56) АвТорское свидетельство СССР

¹ 579614, кл. G 06 F 7/38, 1977, Авторское свидетельство СССР

¹ 1287152, кл. 6 06 F 7/72, 1987, (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ЧИСЕЛ

B МОДУЛЯРНОЙ СИСТЕМЕ СЧИСЛЕНИЯ (57) Изобретение относится к вычислительной технике и предназначено для использования в . быстродействующих непозиционных арифметических устройст. вах конвЕйерного типа для выполнения операции деления чисел. представленных в минимально избыточной модулярной системе счисления. Цель изобретения — повышение быстродействия 3а счет увелиЧенйя пропускной способности устройства., По- ставленная цель достигается за счет приме,, Ы, 1756887 Al

2 нения конвейерного принципа обработки модулярных кодов делимого и делителя и обеспечения возможности совмещения во времени процессов выполнения Т+ 6 операций деления (T =)logzK(, К вЂ” число оснований модулярной системы счиСления; через )x( обозначается наименьшее целое число, не меньшее х). Для формирования приближения делителя и вычисления зйака делителя используется не блок масштабирования, а отдельный блок параллельйо-конвейерного тийа для формирования интегральных характеристик модулярного кода, обращение к которому можно производить ежетактно, т.е. с частотой К=: I/1ì,т. (м.т. — длительность модульного такта). Устройство содержит коммутаторы 5, 6, 6лрк:управления 7, узлы 8, 9 задержки, формирователь 10 интегральных характеристик модулярного кода, блок модульного вычитания 1 1, блок модульного умножения 12, мультйплексор

13, узлы задержки, регистр, блок:присвоения знака, коммутатор, блок модульного сложения, блок масштабирования и узлы задержки. 3 ил.

1756887

Изобретение относится к вычислитель- сложения, четыре регистра, два преобразоной технике и предназначено для использо- вателя прямого кода в дополнительный, вания в быстродействующихнепозиционных счетчик, узел задержки, блок масштабироарифметических устройствах конвейерного . вания, два коммутатора и блок управления, типа для выполнения операции деления чи- 5 в состав которого входят счетчик, два тригсел, представленных в модулярной системе гера, дешифратор, три элемента ИЛИ, элесчисления. мент задержки, элемент НЕ и элемент И, Известно устройство для деления, со- причем первые информационные входы редержащее регистр делителя, регистр дели- гистров делимого и делителя являются вхомого, сумматор, блок выбора 10 дами делимого и делителя устройства элементарного делителя, блок умножения, соответственно, выход регистра частного блок вычитания, блок анализа произведе- является выходомчастногоустройстваисония, блок конца итерации, блок ко!!ца деле- единен с первым информационным входом ния, блок режима работы сумматора, блок блока сложения, выход которого соединен с вычисления итерации, причем выход реги- 15 информационным входом регистра частностра делимого подключен к первому входу го,входзапускаустройстваявляетсявходом блока вычисления итерации, второй вход ко- элемента задержки блока управления и соторого подключен к шине позиционого при- единен с входом элемента НЕ, первыми вхознака делимого, выход регистра делителя дами первого и второго элементов ИЛИ, подключен к входу блока выбора элементар- g0 входом разрешения сброса счетчика и вхоного делителя, третьему входу блока вычис- дом установки в единицу триггера блока упления итерации и первому входу блока равления, входом разрешения записи умножения,выходблокавыбораэлементар- регистра делителя, тактовым входом узла ного делителя подключен к четвертому вхо- задержки и входом сброса счетчика устройду блока вычисления итерации, пятый вход 25 ства, выход регистра делимого соединен с которого подключен к шине позиционного входом уменьшаемого блока вычитания, выпризнака делителя и второму входу блока ход которого соединен с информационным умножения, третий вход которого подклю- входом первого регистра, выход которого чен к первому входу сумматора, первому соединен с входом первого преобразоватевходу блока вычитания, первому входу бло- 30 ля прямого кода в дополнительный, первой ка концаделения, выходу блока вычисления группой информационных входов первого итерации и входу блока конца итерации, коммутатора и вторым информационным выход которого подключен к второму входу входом регистра делимого, выход регистра блока конца деления и шестому входу блока делителя соединен с первым информационвычисления итерации, выход блока конца Э5 ным входом блока умножения, выход котоделения подключен к четвертому входу бло- рого соединен с информационным входом ка умножения, первому входу блока анализа второго регистра, выход которого соединен

-::: произведения, второму входу блока вычита- с входом вычитаемого блка вычитания, вход ния и второму входу сумматора, выход бло- делителя устройства соединен с первыми ка умножения подключен к второму входу 40 информационными входами третьего и четблока анализа произведения, выход которо- вертого регистров, выход третьего регистра го подкл!очен через блок режима работы является выходом остатка устройства исоесумматора к третьему входу сумматора и динен с входом остаточного кода блока мастретьему входу блока вычитания, выход ко- штабирования, первый и второй входы торого подключен к седьмому входу блока 45 номера масштаба которого соединены с вычисления итерации, выход сумматора со- первым выходом узла задержки и информаединен с выходом устройства, ционным выходом счетчика, второй выход . Недостатками данного устройства яв- узла задержки соединен с входом младших ляются невысокое быстродействие, обус- информационных разрядов счетчика, выход ловленное низкой эффективностью 0 которогосоединен с входомузлазадержки, применяемого способа выполнения базо- выход первого преобразователя прямого

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

55 ности к предлагаемому является устройство рыми информационными входами блоков для деления чисел в системе остаточных умножения и сложения, с первой группой классов, содержащее регистры делимого, информационных входов второго коммутаделителя и частного, блок вычитания, блок тора, входом второго преобразователя пря1756887 мого кода в дополнительный и входом де- тнойструктуройалгоритмаделения, f1pMMe шифратора блока управления, выход второ- нение общего блока масштабирования на го преобразователя прямого кода в этапах аппроксимации делителя и реализадополнительный соединен с вторым инфор- ции схемы Ферма не позволяет организомационным входом второго коммутатора, 5 вать в известном устройстве совмещение во выход которого соединен с входом старших времени процесса выполенния нескольких информационных разрядов счетчика;-выход операций деления. 3TQ не дает воэможноэлемента НЕ блока управления соединен с сти использования данного устройства в входом разрешения записи первого регйст- сверхбыстрых вычислительных устройстра и входом синхронизации блока масшта- 10 вах. бирования, выход BToporo элемента ИЛИ Цельизобретения — повышениебыстроблока управления соединен с входом разре- действия устройства. шения записи регистра делимого и третьего Поставленная цель достигается путем регистра, выход (T+ 4)-lo разряда счетчика применения конвейерного принципа обраблока управления, где T = )logzKf, где К вЂ” 15 боткимодулярныхкодовделимогоиделитечисло оснований системы счисления, ) f — ля и обеспечения возможности совмещения целая часть, соединен с входом разрешенйя во времени процессов выполнения Т+6 опезаписи регистра частного, выход первого раций деления (Т = )logzKf, где К вЂ” число элемента ИЛИ блока управления. соединен оснований модулярной ситемы счисления; с входом разрешения записи четвертого ре- gp )x(— наименьшее целое число, не меньше х), гистра, прямой выход первого триггера бло- в соответствии с чем в устройство для делека управления соединен с первым входом ния чисел в модулярной системе счисления, элемента И блока управления и счетным содержащее блок модульного вычитания, входом счетчика устройства. вход разреше- блок модульного умножения, регистр, блок ния записи которого соединен с входами р5 модульного сложения, блок масштабировасброса второго и четвертого регистров и ния, первый узел задержки. первый и втовыходом элемента И блока управления, вы- рой коммутаторы и блок управления, в ход второго триггера которого соединен с: состав которого входят дешифратор, элевходом управления первого коммутатора. мент ИЛИ, первый элемент И, первый вход выход элемента задержки блока управле- 3Q которого соединен с выходом дешифратора, ния соединен с информационным входом вход которого соединен с входом первого счетчика блока управления, счетный вход слагаемогоблокамодульногосложения, выкоторого соединен с выходом третьего эле- ходом блока масштабирования, с входом мента ИЛИ блока управления, первый и вто- первого сомножителя блока модульного умрой входы которого соединены 35 ножения,выходкоторогоСоединейсвходом соответственно с первым выходом дешиф- регистра, выход которого соединен с вхоратора и инверсным выходом первого триг- дом вычитаемого блока модульного вычитагера блока управления, выходы нулевого и ния, введены третий. коммутатор, (Т+3)-ro разрядов счетчика блока управле-. мультиплексор, с второго по шестой узлы ния соединены с вторыми входами соответ- 4р задержки, блок формирования интеграль-" ственно второго и первого элементов ИЛИ ных характеристик модулярного кода; блок блока управления, второй выход дешифра- присвоения знака, в блок управления дотора блока управления соединен с входом полнительно введены первый и второй региразрешения сброса первого триггера и вто- . стры сдвига, первый и второй кольцевые рым входом элемента И блока управления, 4 сдвиговые регистры, второй и третий weвторой выход дешифратора блока управле- менты И, причем входы делимого и делителя ния соединен с информационным входом устройства соединены с первыми информавторого триггера блока управления и вхо- ционными входами соответственно первого дом управления второго коммутатора, тре- и второго коммутаторов, выходы которых тий выход дешифратора блока управления соединены с входами первого и второго уэявляется выходом окончания деления уст- лов задержки соответственно, вторые ин50 ройства. формационные входы первого и второго

Известное устройство реализует итера- коммутаторов соединены с первыми выхотивную процедуру деления по методу спу- дами второго и третьего узлов задержки соска Ферма с применением ответственно, выход первогоузлазадержки параллельно -конвейерного блока масшта- . соединен с входом уменьшаемого блока мо55 бирования чисел, ориентированного на не- дульного вычитания, выход которого соедикоторый набор масштабов. Однако нен с входом третьего узла задержки, пропускная способность устройства недо- второй выход которого соединен с первым статочновысока,чтообусловленорекуррен- . входом блока присвоения знака, второй

1756887 вход которого соединен с первым выходом четвертого узла задержки, второй выход которого соединен с первым информационным входом мультиплексора, выход которого соединен с входом четвертого узла задержки, второй информационный вход мультиплексора соединен с первым выходом блока формирования интегральных характеристйк модулярного кода, второй выход которого соединен с первым информационным входом третьего коммутатора, второй информационный вход которого соединен с выходом пятого узла задержки, вход которого соединен с выходом третьего коммутатора и первым входом блока масштабирования, второй вход которого соединен с выходом блока присвоения знака, выход блока модульного сложения соединен с входом шестого узла задержки, выход которого соединен с выходом частного устройства и входом второго слагаемого блока модульного сложения, второй выход второго узла задержки соединен с входом второго сомножителя блока модульного умножения, вход делителя устройства соединен с входом блока формирования интегральных характеристик модулярного кода, вход запуска устройства соединен с входом сброса шестого узла задержки и с установочными входами первого и второго регистров сдвига и входами сброса первого и второго кольцевых сдвиговых регистров, входы упра в л ения сдвигом к оторых соединены с одноименными входами первого и второго регистров сдвига и с тактовым входом устройства, выход старшего разряда первого регистра сдвига соединен с входом младшего разряда первого кольцевого сдвигаваго ре истра, выход которого соединен с первым входом второго элемента И, второй вход которОго соединен с выходом третьего элемента И, входы которого соединены с выходами разрядов второго кольцевого сдвигового регистра, вход младшего разряда которого соединен с выходом первого элемента И, первый выход второго регистра сдвига соединен с управляющими входами первого и второго коммутаторов, второй выход второго регистра сдвига соединен с первым входом элемента ИЛИ, второй вход кОторого соединен с выходом старшего разряда второго кольцевого сдвитового регистра, выход элемента ИЛИ соединен с входом блокировки блока масштабирования, третий"выход второго регистра сдвига соединен с вторым входом первого элемента И, четвертый и пятый выходы второго регистра сдвига соедйнены с управляющими входами третьегЬ кОммутатора и мультиплексора соответственно, выход второго элемента И

20 соединен с выходом признака окончания деления устройства.

Таким образом, существенное отличие предлагаемого устройства для деления чисел в модулярной системе счисления заключается в том, что для формирования приближения делителя и вычисления знака делителя используется не блок масштабирования, а отдельный блок параллельноконвейерного типа для формирования интегральных характеристик модулярнаго кода, обращение к которому можно производить ежетактно, т.е. с частотой f = 1/ту.т, где tM,т. — длительность модульного такта.

Это позволяет организовать совмещение во времени выполнения в устройстве да Т+6 операций деления, базирующихся на итеративной процедуре па методу спуска Ферма.

На фиг,1 и 2 представлена структурная схема устройства для деления чисел в модулярной системе счисления; на фиг,3 — структурная схема блока управления, Устройство содержит вход 1 делимого, вход 2 делителя, вход 3 запуска и тактовый вход 4 устройства, первый 5 и второй 6 коммутаторы, блок 7 управления, первый 8 и второй 9 узлы задержки, формирователь 10 интегральных характеристик мадулярнага кода, блок 11 модульного вычитания, блок

12 модульного умножения, мультиплексор

13, третий узел 14 задержки, регистр 15, четверытй узел 16 задержки, блок 17 присвоения знака, третий коммутатор 18, блок

19 модульного сложения, блок 20 масштабирования, пятый 21 и шестой 22 узлы задержки, выход 23 частного и выход 24 признака окончания деления устройства.

Входы делимого 1 и делителя 2 устройства подключены к первым информационным входам соответственно nepaoro 5 и второго 6 коммутаторов, которые содержат по Л= bi мультиплексоров, где

i =1

Ь! = ) а92гп!((! = 1, 2„...k), где m>, гп2,...,mg—

45 основания модулярной системы счисления, являющиеся попарно простыми целыми числами, т.е. (гль mi) = 1; I, j = 1, 2 „...k; i Ф j.

В состав блока 7 управленяи входят первый 25 и второй 26 регистры сдвига, 50 дешифратор 27, первый 28 и второй 29 кольцевые сдвигавые регистры, первый

30, второй 31 и третий 32 элементы И и элемент ИЛИ 33, Разрядность первого 25 и второго 26

55 регистров сдвига составляет соответственно Т+ 1 и 2Т+ 8 бит, Инверсный выход (Т+4)-ro разряда, прямой и инверсный выходы (2T+5)-го разряда, прямой выход {2Т+6)-го и инверсный выход

1756887

10 ход старшего разряда первого кольцевого сдвигового регистра 28 и выход третьего элемента И 32 соединены с первым и вторым входами второго элемента И 31.

5 Выходы первого 5 и второго 6 коммутаторов соединены соответственно с входами первого 8 и второго 9 узлов задержки, вторые информационные входы первого 5 и второго 6 коммутаторов подключены к пер10 вым выходам соответственно третьего 14 и второго 9 узлов задержки.

Первый узел 8 задержки представляет собой цепочку из Т+2 последовательно соединенных регистров разрядностью Лбит, 15 вход первого и выход последнего иэ которых являются соответственно входом и выходом узла задержки.

Второй узел 9 задержки представляет собой цепочку из Т+6 последовательно сое20 диненных регистров разрядностью Лбит; вход первого регистра является входом узла задержки, выходы (Т+6)-го и Т+1)-ro регистров являются соответственно первым и вторым выходами узла Задержки.

Управляющие входы первого 5 и второго 6 коммутаторов объединены и подключены к первому выходу второго регистра 26 сдвига блока 7 управления, Выход первого узла 8 задержки подключен к входу уменьр шаемого блока 11 модульного вычитания, вход вычитаемого которого Соединен с выходом регистра 15. Второй выход второго узла 9 задержки соединен с входом второго сомножителя блока 12 модульного.умноже5 ния, выход которого подключен к входу регистра 15.

Формирователь 10 интегральных характеристик модулярного кода является известным устройством, представляющим собой

О усеченный вариант параллельно-конвейер- ного устройства для формирования интегральных характеристик модулярйого кода, быстродействие которого составляет Т+ 3 такта при пропускной способности одна

5 операция в один такт. Формирователь 10 по входному модулярному оду (х1, Хг,...,хk) числа Х из диапазона 0 модулярной системы счисления осуществялет формирование лишь двух характеристик: знака S(X) E(0,1) числа Х и номера I масштаба St, апп роксимирующего абсолютную величину Х(числа Х: е(Х) = х = I Х I,; (3 = 1, 2,. „, );

mk 2mp+k — 2; к-<

Ми= U mi; 2 а Х

IV Im обозначается наименьший неотрицательный вычет, сравнимый с величиной У по модулю m, Дешифратор 27 реализуется, xaic в известном устройстве.

Разрядность первого 28 и второго 29 кольцевых сдвиговых регистров составляет

Т+ 6 бит.

Установочные входы первого 25 и второго 26 регистров сдвига и входы сброса 3 первого 28 и второго 29 кольцевых сдвиговых регистров объединены и подключены к входу 3 запуска устройства, входы управления сдвигом первого 25 и второго 26. регистров сдвига, первого 28 и второго 29 4 кольцевых сдвиговых регистров объединены и подключены к тактовому входу 4 устройства, выход старшего разряда первого регистра 25 сдвига соединен с входом млад-. шего разряда первого кольцевого сдвигово- 4

ro регистра.28, выход дешифратора 27 и третий выход второго регистра 26 сдвига подключены соответственно к первому и второму входам первого элемента И 30, выход которого соединен с входом младшего 50 разряда второго кольцевого сдвигового регистра 29. Второй выход второго регистра

26 сдвига и выход старшего разряда второго кольцевого сдвигового регистра 29 соединены соответственно с первым и вторым входами элемента ИЛИ 33, Выходы всех разрядов (с нулевого по (T+ 5)-й) второго кольцевого сдвиговаго регистра 29 подключены к входам третьего элемента И 32, выО, если Х 0, $(Х) =

1, если Х< О. (2) 55 (2Т+7)-го разрядов второго регистра 26 сдвига (разряды номеруются начиная с О) являются его выходами с первого по пятый, Дешифратор 27 предназначен для формирования сигнала е (Х), задаваемого соотношением

1, если ХЕ(-1, О, 1), (1)

О в остальных случаях где Х вЂ” входная переменная, заданная своим модулярным кодом (х1, x2,...,х ) и принадлежащая диапазону D =(-mp М -f, -mp x хМ -1+ 1,;.,гло М 1 — 1) модулярной системы счисления; п1Π— вспомогательный модуль, выбираемый из условий m< > k— - 1;

Номер I масштаба Sl определяется по правилу

1756887 где Х>

25 л

Sl = Х, 2 ."

)Хат з+ Хаз П1аз-s! у!зт-2

2 "

+v ж„2

О, если Х„ .Л-1, д>,= K ii+1 в остальных случаях; и — номер старшей ненулевой цифры симметрического полиадического представления х. + x2 M1 + „. +> k Mk-1 числа Хе0;

" l ("и ) — ("" ) а- з (- 1l (i = 1. 2...„k); (у) — целая часть действительного числа у;

Mi-- Г1 пц;

4=1 зе,— номер старшего ненулевого разряда в двоичном представлении числа

Х =!х 1+x, „-1! Мг;

il — количество старших двоичных разря дов числа Х 1, используемых для определения масштаба Sl, который имеет вид

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

" характеристик модулярного кода в память соответствующего (v — 1)-го (v = 2, З,...,k) формирователя номера номирующего множителя по адресу х -1+ 2 ""х„записывается величина г х1, есл и x) 0, х1 + m 1, если х! < О.

Величины S(X) и снимаются с первого и второго выходов формирователя 10 интеграЛьнызях характеристик модулярного кодаз собтвечтственно на (Т+ 2)-м и (Т+ 3)-м такт ах

Вход 10 формирователя интеральных характеристик модулярного кода подключен к входу делителя 2 устройства, первый и второй выходы формирователя 10 соединены с первыми информационными входами мультиплексора 13 и третьего коммутатора

18 соответственно.

Блоки модульного вычитания 11, модульного умножения 12 и модульного сложения 19 состоят соответственно из

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

Выход блока !1 модульного вычитания соединен с входом третьего узла 14 задержки, второй выход которого подключен к первому входу блока i7 присвоения знака, Первый информационный вход и выход мультиплексора 13 соединены соответственно с вторым выходом и входом четвертого узла 16 задержки. Управляющие входы мультиплексора 13 и третьего коммутатора

18 подключены соответственно к четвертому и пятому выходам второго регистра 26 сдвига блока 7 управления. Первый выход четвертого узла 16 задер>кки соединен с вторым входом блока 17 присвоения знака.

Третий узел 14 задер>кки представляет собой цепочку из четырех последовательно соединенных регwcTpoB разрядностью

Лбит; вход первого регистра является входом узла задержки, выходы четвертого и первого регистров являются соответственно первым и вторым выходами узла задержки.

ЧетвертьlA узел 16 задержки представляет собой цепочку из Т+6 последовательно соединенных одноразрядных регистров, вход первого регистра является входом узла задержки, выходы первого и последнего регистров являются соответственно первым и вторым выходами узла задержки.

Блок 17 присвоения знака осуществляет преобразование модулярного кода числа Х е0 в модулярный код числа

X = X (-1) ), где S(Y)c:(0,1) — знак числа

Уе D. !у1одулярный код (x1, хг,...,х ) числа X u величина S(Y) поступают на первый и второй входы блока 17 соответственно, Блок 17 присвоения знака реализуется с помощью k долговременных запомйна1ощих устройств, Ь;+1 „

i-e из которых обладает емкостью 2 слов разрядность)0 Ь! бит и в память которого ПО адресу х; ч 2с" S!ó) записывается вычет хая !Х im;=- !х! (-1) ipg (i - 1, 2,...,k). ()

Третий коммутатор 18 содержит )!ОугЦ мультиплексоров, где L — число масштабов, на которые рассчитан блок 20 масштабирования.

Блок 20 масштабирования представляет собой известное устройство для масштабирования параллельно-конвейерного типа, быстродействие которого составляет

Т+3 такта при пропускной способности одна операция масштабирования в один такт.

Блок 20 масштабирования осуществляет деление входного числа Х q 0 на некоторый

1756887 положительный масштаб Si q D, причем ичный код чилса -1, На первом выходе втоэто число ограничено и равно L. Номер рого регистра 26 сдвига вырабатывается е(0, 1,...,L-1) масштаба Sl и модулярный код сигнал 0,. 0 (где о) — содержимое J-ro разчисла Х подаются соответственно на пер- ряда второго регистра 26 сдвига, J = О, вый и второй входы блока 20. Результатом 5 1„,2Т-7; cd — отрицание булевой величины операции масштабирования является оцен- а ). который поступает на управляющие вхока (ближайшее целое число) дроби X/Sj B ды первого 5 и второго 6 коммутаторов; В блоке 20 функция блокировки выдачи нену- результате модулярный к дулярный код левой информации реализуется стандарт- (а1, а ...., а )делимогоА, пОступающий ным образом путем подключения к выходу 10 на вход 1 делимого устройства, ерез на вход делимого устройства, через первыходного регистра блока группы элемен- вый коммутатор 5 передается в е тов запрета, управляемой посредством вхо- 8 задержки а модул р задержки, а модулярный код да блокировки. динен с вторым входом блока 20 масштаби- 15 коммутатор 6 пере а C " 9 на вход делителя уст ойства, через второй коммутатор передается во второй узел 9

РованиЯ, пеРвый вход котоРого объединен с за,е,ки (+ = Я(" . P =" Igj, 1 2 . Я входом пятого узла 21 задержки и подклею- Вв В p) g

). дновременно с этим модулярчен к выходу третьего коммутатора .18; вход дешифратора 27 блока 7 управления:, вход ро ный код делителя В с входа 2 делителя устройства поступает на вход формирователя пеРвого сомножителЯ блока 12 модУльного 20 р р р ду р

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

19 модУльного сложениЯ обьеди ены и под- опер„ци операции деления числа Я на В, ключены к выходу блока 20 масштабирова- Ввиду обеспечения в устройстве конния, вход блокировки которого соединен с вейерного режима выполнения не одной, а выходом элемента ИЛИ 33 блока 7 управлеИЛИ 33 б у р 25 целой последовательности Операций деле ния, второй информационный входтретьего ния, начиная с и-го такта рассматриваемой коммутатора 18 соединен с выходом пятого узла 21 задержки, операции, в устройстве может быть инициировано (n+ 1) операций деления (и = О, Пятый 21 и шестой 22 узлы задержки 1 Т+5) тметим, что на каждом такте работы осуществляют задержку информации на Т+ 3р

6 тактов. Разрядность регистров, входящих в состав пятого 21 и шестого 22 узлов задерустройства по сигналу Гт = 1, подаваемому, на тактовый вход 4 устройства, содержижки, состалЯет соответственно )!о92 -(и мое пер о 25 р о 26 р с ров мое первого 25 и второго 26 регистров

Л бит. Входы сброса регистров шестого сдвига, первого 28 и второго 29 кольцевых узла 22 задеРжки в совокупности состав- 35 сдвиговь ре с р б 7 у р сдвиговых регистров блока 7.управления ляют вход сброса узла задержки. сдвигается на один бит в сторону старших

Вход сброса шестого узла 22 задержки разрядов. подключен к входу 3 запуска устройства; На первом такте реализуемой процедувход второго слагаемого и выход блока 19 ры деления формирователь 10 интегральмодульногосложениясоединенысоответст- 4р „ых харак ери

40 ных характеристик модулярного кода" венно с выходом и входом шестого зла 22 задержки, выходы шестого узла 22 задерж- мас а б с; В ки и второго элемента И 31 блока 7 управлемасшат а = В, аппроксимирующего абсолютнуюю величину I BI делителя В. ния являются выходом 23 частного и ™Н (T+1) а (+ 1)-м такте содержимое ) = 1 старвыходом 24 признака окончания деления д .. 45 шего разряда первого регистра 25 сдвига устройства соответственно, блока 7 управления передается в младший

Рассмотрим, как работает предлагаеразряд первого кольцевого сдвигового регимое УстРойство длЯ делениЯ чисел в модУ- р 28 Q 7 у стра лока 7 управления. лярной систЕме счисления, Начиная с (Т+1)-ro такта реализуемая

На начальном (нулевом) такте по сигналу Гупр = 1, подаваемому на вход 3 запуска

50 процедура деления носит итеративнйй характер, Все итерации имеют одинаковую шестого Узла 22 задеРжки, а также пеРвый Н р р р ц длительность, а именно Т+ тактов.

На первом такте первой итерации моду28 и второй 29 кольцевые сдвиговые регист- лярный код делителя В с второго выхода ры блока 7 управления обнуляются; в первом регистре 25 сдвига блока 7 управления второго узла 9 задержки поступает на вход второго сомножителя блока 12 модульного устанавливается (Т+ 1)-разрядный двоичумножения, на вход первого сомножителя ный код числа 1, во втором регист е 26 д Р Р с Ре 26 которого с выхода блока 20 масштабировасдвига блока 7 управления устанавливается (2Т+ 8)-разрядный дополнительный двония подается модулярный код числа Оо = 0

1756887 входы уменьшаемого и вычитаемого блока, 40

5r (Гбл = ст „фа„ = 1, где 0 — содержимое

4 2

t-го разряда (i =- О, 1,...,Т+5) второго кольцевого сдвигового регистра 29 блока 7 управления. В результате блок 12 модульного умножения получает произведение В.О = О, код которого передается в регистр 15. Кроме этого, модулярный код числа Qo = 0 с выхода блока 20 масштабирования подается на вход первого слагаемого блока 19 модульного сложения, на вход второго слагаемого которого с выхода шестого узла

22 задержки поступает модулярный код числа Q-1 = О. Блок 19 модульного сложения формирует модулярный код суммы

Qo+ 0-1= О, который записывается в первый регистр шестого узла 22 задержки. Одновременно с этим модупярный код числа

О»= 0 поступает на вход дешифратора 27 блока 7 управления. В соответствии с соотношением (1) на выходе дешифратора 27 генерируется сигнал e(Qp) = 1, поступающий на первый вход первого элемента ИЛИ 30 блока 7 управления, на второй вход которого с третьего выхода второго регистра 26 сдвига подается нулевой сигнал o zz+g = О. В результате в младший разряд второго коль цевого сдвигового регистра 29 блока 7 управления с выхода первого элемента И 30 поступает сигнал Г1= e(Qp } и,-5-=- 0 и, таким образом, на данной итерации процедуры деления не происходит изменения содержимого второго кольцевого сдвигового регистра 29..

На втором такте первой итерации модулярный код делимого A =- A с выхода первого узла 8 задержки и содержимое регистра

15 (код числа О) подаются соответственно на

11 модульного вычитания, Блок 11 формирует разность A1 = Ao — 0 = А, которая передается в третий узел 14 задержки;

Одновременно с этим формирователь 10 интегральных характеристик модулярного кода завершает вычисление знака S(B) делителя В, Двухзначная величины $(В) с первого выхода формирователя 10 через мультиплексор 13, на управляющий вход коtoporo подается сигнал сто„ = 1, поступает в четвертый узел 16 задержки.

На третьем такте первой итерации модулярный код числа А1 с второго выхода третьего узла 14 задержки и знак S(B) делителя В с первого выхода четвертого узла

16 задержки подаются на первый и второй входы блока 17 присвоения знака. Полученный блоком 17 модулярный код числа

R1 = А1 (-1) ) поступает в блок 20 масштабирования через еторой его вход, Кроме этого, на данном такте формирователь 10

35 интеграл ьных хара ктеристи к модуля рного кода завершает вычисление номера I масштаба Si = В. Величина с второго выхода формирователя 10, проходя через третий коммутатор 18. на управляющий вход которого подается сигнал (т2„»= О, поступает в блок 20 масштабирования через первый его вход, а также записывается в пятый узел 21 задержки.

На четвертом такте первой итерации блок 20 масштабирования начинает вычисление модулярного кода оценки Q1 дроби

R1/A.

На шестом такте первой итерации модулярный код числа А1 с первого выхода третьего узла 14 зэдер>кки поступает на второй информационный вход первого коммутатора 5, íà управляющий вход которого подается сигнал о „ = 1, в результате код числа

Л1 передается в первый узел 8 задержки.

Одновременно с этим модуля рный кодделителя В с первого выхода второго узла 9 задержки через второй коммутатор 6 (от.„= 1) передается во второй узел 9 задержки.

На последнем (Т+6)-м такте первой итерации блок 20 масштабирования завершает вычисление модулярного кода оценки Qj дроби Р1/В.

На первом такте /-й итерации (j - 2, 3„..) модуля рный код числа Qj-1 с выхопа блока 20

1Р.) масштабирования (Гбл= о2т.5 V ог+ = О) подается на вход первого сомножителя блока 12 модулярного умножения и вход первого слагаемого блока 19 модульного сложения, на входы второго сомножителя и второго слагаемого которых поступают соответственно модулярный код делителя В с второго выхода второго узла 9 задержки и модулярный

J — 2 j — 2 код суммы g Q = Х Qt (Q-1= 00= 0) с

1= — 1 1=1 выхода шестого узла 22 задержки. В результате блок 12 модульного умножения получает произведение Qj-1 В, модулярный код которого записывается в регистр 15, а на выходе блока 19 модульного сложения форj — 1 мируется код суммы » Qi который переI =1 дается в шестой узел 22 задержки.

На втором такте j-й итерации модупярный код числа А1-1 с выхода первого узла 8 задержки и содержимое регистра 15 (код числа Qj-1 В) подаются соответственно на входы уменьшаемого и вычитаемого блока

11 модульного вычитания, в результате чего на выходе блока 11 формируется разность

Л1 = Aj-1 — Qj-1 В, модулярный код которой передается е третий узел 14 задержки. Одновременно с этим знак S(H) делителя В с

1756887 второго выхода четвертого узла 16 задержки поступает на первый информационный вход мультиплексора 13, на управляющий вход которого подается сигнал о,"„ = О, поэтому величина S(B) передается на вход четвертого узла 16 задержки.

На третьем такте J-й итерации модулярный код числа А1 с второго выхода третьего элемента 14 задержки и знак S(B) с первого выхода четвертого узла 16 задержки подаются на первый и второй входы блока 17 присвоения знака, Получаемый блоком 17 модулярный код числа Rj = А (-1) поступает в блок 20 масштабирования через второй его вход. Кроме этого, номер 1масштабэ

Sl= B с выхода пятого узла 21 задержки поступает на второй информационный вход третьего коммутатора 18, на управляющий вход которого подается сигнал cr> + = 1. В результате величина 1 поступает в пятый узел 21 задержки, а также в блок 20 масштабирования, который со следующего такта итерации начнет вычисление модулярного кода оценки Q дроби В уИ, На шестом такте J-й итерации модуляркые коды числа А1 с первого выхода третьего узла 14 задержки и делителя В с первого, выхода второго узла 9 задержки через первый 5 и второй 6 коммутаторы, на управляющие входы которых поступает сигнал о,,= 1, пеоедаются на входы первого 8 и второго 9 узлов задержки соответственно.

На заключительном, Т+ 6-м, такте )-й итерации блок 20 масштабирования получа. ет модулярный код оценки Q дроби R /В.

Описанная последовательность действий повторяется до тех пор, пока по окончан ии н е кото рой r-й итера ци и (r 1) н а выходе блока 20 масштабирования не будет получен модулярный код числа Q

В этом случае нэ первом такте (г+1)-й итерации в соответствии с соотношением (1) на выходе дешифратора 27 блока 7 управления генерируется сигнал r. (О ) = 1, поступающий на первый вход первого элемента ИЛИ 30, на второй вход которого с третьего выхода второго регистра 26 сдвига подается единичный сигнал Oa„. 1. В результате младший разряд второго кольцевого сдвигового регистра 29 установится в единичное состояние, так как в него с выхода первого элемента И 30 поступает сигнал

Гi= e(Q<} o »,=1. Одновременно с этим блок 19 модульного сложения получает модулярный код искомого част-..

I ного Q= Я О, который передается в

I=1 шестой узел 22 задержки, Процесс выполнения инициированной группы из Т+6 операций деления продолжается до тех пор, пока все они не завершатся.

В момент получения блоком 19 модульного

5 сложения соответствующего чаСткого во втором кольцевом сдвиговом регистре 29 блока 7 управления все разряды будутустановлены в единичное состояние. Предположим, что последняя завершенная оперэция

10 деления инициировалась на и-м такте работы устройства (n = 0, 1,...,T+5). Тогда в целях получения результатов реализованных операций деления в порядке их инициации работа устройства продолжается еще Т - п+ 5

15 тактов, т.е. до момента появления на выходе

23 признака окончания деления устройства единичного сигнала. В течение очередных

Т+6 тактов полученные частные последовательно снимаются с выхода 24 устройства и

2р на этом процесс выполненйя группы операций деления заканчивается, В такте сьема последнего частного в устройстве может быть начата инициация новой группы операций, Из прйведенного описания видно, что включение в состав предлагаемого устройства отдельного блока для аппроксимации делителя (параллельно-конвейерного формирователя интегральных характери30 стик модулярного кода с частотой обращения f= 1/tM.T) дает возможность совмещать во времени процессы выполнения Т+6 операций деления, Таким образом, предлагаемое решение йозволяет увели35 чить быстродействие предлагаемого устройства в сравнении с известным в Т+6 раз.

Если, например, используется модулярная система счисления с числом оснований K= 8, то достигается девятикратное увеличение

40 быстродействия.

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

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

1756887

20 щ е е с я тем, что, с целью повышения быстродействия, устройство содержит третий коммутатор, мультиплексор, с второго по шестой узлы задержки, блок формирования интегральных характеристик модуляр- 5 ного кода, блок присвоения знака, в блок управления дополнительно введены первый и второй регистры сдвига, первый и второй кольцевые сдвиговые регистры, второй и третий элементы И, причем входы делимого и делителя устройства соедийены с первым информационным входом соответ- ственно первого и второго коммутаторов, выходы которых соединены с входами первого и второго узлов задержки соответст- 15 венно, вторые информационные входы первого и второго коммутаторов соединены с первыми выходами второго и третьего узлов задержки соответственно, выход первого узла задержки соединен с входом 20 уменьшаемого блока модульного вычитания, выход которого соединен с входом третьего узла задержки, второй выход кото- рого соединен с первым входом блока присвоения знака, второй вход которого 25 соединен с первым выходом четвертого узла задержки, второй выход которого соединен с первым информационным. входом мультиплексора, выход которого соединен с входом четвертого узла задержки, второй 30 информационный вход мультиплексора соединен с первым выходом блока формирования интегральных характеристик модулярного кода, второй выход которого соединен с первым информационным вхо- g5 дом третьего коммутатора, второй информационный вход которого соединен с выходом пятого узла задержки, вход которого соединен с выходом третьего коммутатора и первым входом блока масштабирования, 4О второй вход которого соединен с выходом блока присвоения знака, выход блока модульного сложения соединен с входом шестого узла задержки, выход которого соединен с выходом частного устройства и входом второго слагаемого блока модульного сложения, второй выход второго узла задержки соединен с входом второго сомножителя блока модульного умножения, вход делителя устройства соединен с входом блока формирования интегральных характеристик модулярного кода, вход запуска устройства соединен с входом сброса шестого узла задержки и с установочными входами первого и второго регистров сдвига и входами сброса первого и второго кольцевых сдвиговых регистров, входы управления сдвигом которых соединены с одноименными входами первого и второго регистров сдвига и тактовым входом устройства, выход старшего разряда первого регистра сдвига соединен с входом младшего разряда первого кольцевого сдвигового регистра, выход которого. соединен с первым входом второго элемента И, второй вход которого соединен с выходом третьего элемента И, входы которого соединены с выходами разрядов BTopoi кольцевого сдвигового регистра, вход младшего разряда которого соединен с выходом первого элемента И, первый выход второго регистра сдвига соединен с управляющими входами первого и второго коммутаторов, второй выход второго регистра сдвига соединен с первым входом элемента ИЛИ, второй вход которого соединен с выходом старшего разряда второго кольцевого сдвигового регистра, выход элемента ИЛИ соединен с входом блокировки блока масштабирования, третий выход второго регистра сдвига соединен с вторым входом первого элемента И, четвертый и пятый выходы второго регистра сдвига соединены с управляющими входами третьего коммутатора и мультиплексора соответственно, выход второго элемента И соединен с выходом признака окончания деления устройства.

1756887

Фиг. 3

Составитель М.Селянинов

Техред ММоргентал Корректор М.Петрова

Редактор И.Дербак

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

Заказ 3089 Тираж Подписное

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

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