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

 

Изобретение относится к вычислительной технике и предназначено для использования в арифметических устройствах непозиционного типа для выполнения операции деления чисел, представленных в минимально избыточной модулярной системе счисления. Цель изобретения состоит в упрощении устройства при делении в модулярной системе счисления. Цель достигается за счет реализации итеративного алгоритма деления, базирующегося на операции умножения делителя на два и формирования знака числа в модулярном коде. Устройство для деления чисел содержит регистры 6 и 7, делимого и делителя, регистр. 9 сдвига, вспомогательный регистр 17, блок 11 вычитания, блок 12 умножения, блок 13 сложения, параллельно-конвейерный формирователь 20 интегральных характеристик модулярного кода для вычисления знака числа с частотой обращения fi 1/tMt (IMT длительность модульного такта), счетчик 8, элемент ИЛИ-НЕ 10, элементы И 14, 15, элемент 16 задержки, регистр 18 частного и элемент ИЛИ 19. 1 ил. сл с

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

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

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

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

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

ПРИ ГКНТ СССР

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

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

И (21) 4745603/24 (22) 03.10.89 (46) 07.10.91 Бюл. М 37 (71) Научно-исследовательский институт прикладных физических проблем им, А. Н. Севченко (72) В. Н. Ахременко, А. А. Коляда и M. Ю. Селянинов (53) 681.325(088.8) (56) Авторское свидетельство СССР

М 1287152, кл. G 06 F 7/72, 1985.

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

М 1241240, кл, G 06 F 7/72, 1984, (54) УСТРОЙСТВО ДЛЯ ДЕЛЕНИЯ ЧИСЕЛ (57) Изобретение относится к вычислительной технике и предназначено для использования в арифметических устройствах непоэиционного типа для выполнения операции деления чисел, представленных в ми,, SU „„1683013 А1 нимально избыточной модулярной системе счисления. Цель изобретения состоит в упрощении устройства при делении s модулярной системе счисления. Цель достигается за счет реализации итеративного алгоритма деления, базирующегося на операции умножения делителя на два и формирования знака числа в модулярном коде, Устройство для деления чисел содержит регистры 6 и 7, делимого и делителя, регистр

9 сдвига, вспомогательный регистр 17, блок

11 вычитания,. блок 12; блок 13 сложения, параллельно-конвейерный формирователь 20 интегральных характеристик модуляриого кода для вычисления знака числа с частотой обращения 0=1/Тмт (мт— длительность модульного такта), счетчик 8, элемент ИЛИ вЂ” НЕ 10, элементы И 14, 15, элемент 16 задержки, регистр 18 частного и элемент ИЛИ 19. 1 ил, 1683013

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

Цель изобретения состоит в упрощении устройства при делении в модулярной системе счисления.

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

Устройство содержит вход 1 делимого, вход 2 делителя, тактовый вход 3, первый и второй установочные входы 4 и 5 устройства, регистр 6 делимого, регистр 7 делителя, счетчик 8, регистр 9 сдвига, элемент ИЛИ—

НЕ 10, блок 11 вычитания, блок 12 умножения, блок 13 сложения, первыл и второй элементы И 14 и 15, элемент 16 задержки, вспомогательный регистр 17, регистр 18 частного, элемент ИЛИ 19, формирователь 20 интеграл ьных характеристик модуля рного кода, выход 21 остатка. выход 22 и выход 23 признака окончания работы устройства, Входы 1 и 2 устройства соединены с первыми информационными входами регистров делимого 6 и делителя 7 устройства.

Разрядность регистров делимого 6 и делителя 7 составляет L= bl бит, Здесь и ниже ! =1

bi=jIog2mi((I=1, 2,...k); m1, m2,...,П1 — основа ния модулярной системы счисления, являющиеся попарно простыми целыми числами, т. е, mi, mj=1; i, j=1, 2,...,К ihj; через )х(обозначается наименьшее целое число, не меньшее х. Все модули mi(I=1,2,...,k) выбираются нечетными, Счетный вход счетчика 8 и вход управления сдвигом регистра 9 сдвига объединены и подключены к тактовому входу 3 устройства, вход обнуления счетчика 8 обьединен с вторым входом второго элемента

И 15 и подключен к в1 1ходу старшего разряда регистра 9 сдвига, установочный вход которого соединен с первым установочным входом 4 устройства.

Разрядность регистра 9 сдвига составляет Т+3 бит, где Т=)!О92к(, k — число оснований модулярной системы счисления, Выходы разрядов регистра 9 сдвига с нулевого по (Т+2)-й я вля ются соответственно его выходами,с первого по (Т+3)-й, вход нулевого разряда регистра 9 сдвига является его информационным входом, j-й выход регистра 9 сдвига соединен с )-входом элемента

ИЛИ вЂ” НЕ 10 ()=1, 2,.„,Т+3), (Тч-4)-й вход элемента ИЛИ вЂ” Н: 10 объединен с вторым входом элемента ИЛИ 19, входом сброса

4Г

55 регистра 18 частного, управля ощим входом приема кода вспомогательного регистра 17 и подключен к второму установочному входу

5 устройства, выход элемента ИЛИ-НЕ 10 соединен с первым входом первого элемента И 14.

Блок 11 вычитания содержит вычитатели по модулям гп1,m2„„,mk системы счисле ния., Первый вход (вход уменьшаемого) и второй вход (вход вычитаемого) блока вычитания соединены с выходами регистров делимого 6 и делителя 7 устройства соответственно.

Блок 12 умножения содержит умножители по модулям m1,m2,...,111к системы счисления и выполняет операцию модульного умножения входного числа на два.

Блок 13 сложения по входным величинам: модулярному коду Ig1, ур... pi<) числа Х, подаваемому на первый вход, и константе v подаваемой на второй вход, формирует модулярный код (y1,) 2,.. yk ) числа

У = X + 21, т.е. y = gi + 2 I Ар 1,2...к. блок

13 сложения реализуется с помощью к долговременных запоминающих устройств, I — е из которьх обладает емкостью 2 1"2 "2 ( слов разрядностью bi бит и в память котоЬ! рого по адресу gi +2 записывается вычет 1 (i =1, 2,...,k), Злемент 16 задержки представляет собой цепочку из Т+3 последовательно соединенных регистров разрядностью L бит, вход перв; о и выход (Т+3)-го из которых являются соответственно входом и выходом элемента 16 задержки. Управляющий вход выдачи кода (Т+3)-го регистра является управляющим входом выдачи кода элемента 16, Разрядность вспомогательного регистра 17 и регистра 18 частного составляет L бит.

Формирователь 20 интегральных характеристик модулярного кода является известным устройством, представляющим собой упрощенный вариант параллельно-конвейерного устройства для формирования интегральных характеристик модулярного кода, быстродействие которого составля т Т+2 такта при пропускной способности одна операция в один такт, Формирователь 20 по входному модулярному. коду (g1, 72, Д<) числа Х из диапазона D модулярной системы счисления осуществляет формирование лишь одной характеристики. знака S(X)6 (0,1) числа Х; D=(— М+1, -M+2Ä, M-1), К-1

M=Mk-1 mo, Ml< — "= Д пц, где mg вспомо

l =1 гательный модуль, выбираемый из условий

5 i 683013 пц< > 2mp+k — 2, fAp k 1;Я =iXjrnil, l=1, ч

2,,к, через У 1 лу обозначается наименьший неотрицательный вычет, сравнимый с величиной Y по модулю m, Рассмотрим как работает устройство для деления чисел в модулярной системе счисления. По сигналам Гу т=1 и Г=1, подаваемым на первый 4 и второй 5 установочные входы устройства соответственно, в регистр 9 сдвига записывается (Т+3)-битовый двоичный код единицы, регистр 18 частного обнуляется, первый элемент И 14 и элемент ИЛИ 19 в соответствии с булевыми

-г (ГРВ ттс, ит )

Г2=Г ь" Г1, 15 где S — выходная величина формирователя

20 интегральных характеристик модулярного кода, а д — содержимое pro разряда регистра 9 сдвига (t.=0, 1„, Т+2), генерируют сигналы Г1=0 и Г2=1, блокируя поступление нулевой информации с выходов элемента 16 задержки, вспомогательного регистра 17 и блока 12 умножения, в регистр 6 делимого подается модулярный код (а1, Q2,... Qk ) делимого А, а в регистр 7 делителя и вспомогательный регистр 17 производится запись модулярного кода (P>, ®... Д) делителя В ( а =(А л), Pi =(Bp(l, l=1, 2,...,k; А = О, В> О).

На первом такте операции блок 11 вычитания получает модулярный код разности

R) )=A) — Bp=A В, который передается в элемент 16 задержки и формирователь 20 интегральных характеристик модулярного кода, В это же время блок 12 находит моду- 35 лярный код произведения В1=2В, который запоминается в регистре 7 делителя. Заметим, что благодаря равенствам Г=О и до =1 в данный момент Г1=Г2=0.

После аналогичных действий в ходе 40 (l+1)-го такта O >О) в элемент 16 задержки и формирователь 20 интегральных характеристик модулярного кода с выхода блока 11 вычитания поступает модулярный код разности Rj =At — Bt, а е регистре 7 делителя, 45 формируется модулярный код числа

В +1=2 В

На каждом такте работы устройства по сигналу Гт=1, подаваемому на тактовый вход 3 устройства, содержимое счетчика 8 увеличивается на единицу, а содержимое регистра 9 сдвига сдвигается на один бит в сторону старших разрядов, при этом выдвинутое значение дт+г (Т+2}-ro разряда поступает на вход сброса счетчика 8, обнуляя

55 его в случае, когда дт+г =1. Впервые это происходит на (Т+3)-м такте. В этом же такте формирователь 20 интегральных характеристик модуля рного кода завершает формирование знака 5Р— — S (Rb )) числа R(, котоб11 рый передается на соответствующие входи первого 14 и второго 15 элементов И. Если г Т1

S3 )-=1, то на выходе второго элемента И 15 вырабатывается признак конца операции

Ep = 5 1) дт +г = 1,Искомые частные С=-О и остаток R=-А от деления А и В снимаются с выходов регистров делимого 6 и частного

18, а соответственно и с выходов 21 остатка

22 частного устройства. Если же$ 1) =-О, то описанный циклический процесс продолжается до тех пор, пока на некотором такте (обозначим его номер через T+Jq+4 (J1 > О)) на выходе формирователя 20 интегральных характеристик модулярного кода не появится знак S +1=1 отрицательной разности

Rltk1. тогда а силу того, что до =д1 =д,... =дт+2=0, в ходе (Т+)1+4)-ro такта на выходах первого элемента И 14 и элемента ИЛИ 19 формируются единичные сигналы (Г1=Г2=1), вследствие чего в регистр

6 делимого из элемента 16 задержки передается модулярный код числа Ay=Re), в ре(1) гистр 7 делителя пересылается содержимое вспомогательного регистра 17 (модулярный код делителя В), а в младший разряд регистра 9 сдвига записывается единица. Параллельно с этим блок 13 сложения по входным величинам СО=О и j1, поступающим соответственно из регистра 18 частного и счетчика

8, получает модулярный код первого прил; ближения С1=СО+2 1 = 211 частного С=(А/В), который по сигналу Г1=1 запоминается в регистре 18 частного.

На этом заканчивается первая итерация операции деления. Каждая из последующих итераций выполняется так же, как и первая.

Итеративный процесс продолжается до тех пор, пока в ходе (Т+3)-го такта некоторой (г+1)-й итерации (r О) на выходе второго элемента И 15 не появится единичный сигнал Ея =1, указывающий на то, -что формирование частного гО, если г= О

1 г

С=,, 2л, если r>0

l t=1 и остатка В= t A)B=Ar+1 соответственно в регистрах частного 18 и делимого 6 завершено, Формула изобретения

Устройство для деления чисел в модулярной системе счисления, содержащее регистры делимого и делителя, счетчик, регистр сдвига, элемент ИЛИ вЂ” HE, два элемента И, элемент задержки, вспомогательСоставитель Н. Маркелова

Редактор Т. Юрчикова Техред M.Ìoðãåíòàë Корректор С. Шевкун

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

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

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

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

Элемента ИЛИ и входом блокировки блока умножения на два, информационный вход которого соединен с входом вычитания блока вычитания и выходом регистра делителя, информационный вход которого соединен с входом делителя устройства и информационным входом вспомогательного регистра, Выход которого соединен с вторым информационным входом регистра делителя, третий информационный вход которого соединен с выходом блока умножения на два, тактовый вход устройства соединен со

Счетным входом счетчика и входом управления сдвигом регистра сдвига, установочный вход которого соединен с первым устано.Вочным выходом устройства, J-й выход региСтра сдвига соединен с j-м входом элемента

ИЛИ-Н Е ()=1, 2... Т+3; Т=)1 од Я, где к — число модулей системы счисления), (Т+4)-й вход которого соединен с вторым установочным входом устройства, с первым входом we,мента ИЛИ и с управляющим входом приема кода вспомогательного регист э, управляющиЙ Вход выдачи кода B| à (2ÌÎÃß t е "iüÐ0ro регистра соединен с одноименным входом элемента задержки, с информацион5 ным входом регистра сдвига. с вторым входом элемента ИЛИ и выходом первого элемента И, первый вход которого соединен с выходом элемента ИЛИ вЂ” HE, (Т+3)-й вход которого соединен с входом обнуления

10 счетчика и первым входом второго элемента

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