Устройство для деления чисел в модулярной системе счисления Советский патент 1992 года по МПК G06F7/72 

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

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

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

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

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

в состав которого входят счетчик, два триггера, дешифратор, три элемента ИЛИ, элемент задержки, элемент НЕ и элемент И, причем первые информационные входы регистров делимого и делителя являются вхо0 дами делимого и делителя устройства соответственно, выход регистра частного является выходом частного устройства и соединен с первым информационным входом блока сложения, выход которого соединен с

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

0 входом разрешения сброса счетчика и входом установки в единицу триггера блока управления, входом разрешения записи регистра делителя, тактовым входом узла задержки и входом сброса счетчика устрой5 ства, выход регистра делимого соединен с входом уменьшаемого блока вычитания, выход которого соединен с информационным входом первого регистра, выход которого соединен с входом первого преобразоватеQ ля прямого кода в дополнительный, первой группой информационных входов первого коммутатора и вторым информационным входом регистра делимого, выход регистра делителя соединен с первым информзцион5 ным входом блока умножения, выход которого соединен с информационным входом второго регистра, выход которого соединен с входом вычитаемого блка вычитания, вход делителя устройства соединен с первыми

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

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

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

мого кода в дополнительный и входом дешифратора блока управления, выход второго преобразователя прямого кода в дополнительный соединен с вторым информационным входом второго коммутатора, выход которого соединен с входом старших информационных разрядов счетчика, выход элемента НЕ блока управления соединен с входом разрешения записи первого регистра и входом синхронизации блока масштабирования, выход второго элемента ИЛИ блока управления соединен с входом разрешения записи регистра делимого и третьего регистра, выход (Т+ 4)-го разряда счетчика блока управления, где Т 1од2«, где К - число оснований системы счисления; - целая часть, соединен с входом разрешения записи регистра частного, выход первого элемента ИЛИ блока управления соединен с входом разрешения записи четвертого регистра, прямой выход первого триггера блока управления соединен с первым входом элемента И блока управления и счетным входом счетчика устройства, вход разрешения записи которого соединен с входами сброса второго и четвертого регистров и выходом элемента И блока управления, выход второго триггера которого соединен с входом управления первого коммутатора, выход элемента задержки блока управления соединен с информационным входом счетчика блока управления, счетный вход которого соединен с выходом третьего элемента ИЛИ блока управления, первый и второй входы которого соединены соответственно с первым выходом дешифратора и инверсным выходом первого триггера блока управления, выходы нулевого и (Т+3)-го разрядов счетчика блока управления соединены с вторыми входами соответственно второго и первого элементов ИЛИ блока управления, второй выход дешифратора блока управления соединен с входом разрешения сброса первого триггера и вторым входом элемента И блока управления, второй выход дешифратора блока управления соединен с информационным входом второго триггера блока управления и входом управления второго коммутатора, третий выход дешифратора блока управления является выходом окончания деления устройства.

Известное устройство реализует итеративную процедуру деления по методу спуска Ферма с применением параллельноЧсонвейерного блока масштабирования чисел, ориентированного на некоторый набор масштабов. Однако пропускная способность устройства недостаточно высока, что обусловлено рекуррентной структурой алгоритма деления. Применение общего блЪка масштабирования на этапах аппроксимации делителя и реализации схемы Ферма не позволяет организовать в известном устройстве совмещение во времени процесса выполенния нескольких операций деления. Это не дает возможности использования данного устройства в сверхбыстрых вычислительных устройст0 вах.

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

Поставленная цель достигается путем применения конвейерного принципа обра5 ботки модулярных кодов делимого и делителя и обеспечения возможности совмещения во времени процессов выполнения Т+б операций деления (Т JlogaKf, где К - число оснований модулярной ситемы счисления;

0 М наименьшее целое число, не меньше х), в соответствии с чем в устройство для деления чисел в модулярной системе счисления, содержащее блок модульного вычитания, блок модульного умножения, регистр, блок

5 модульного сложения, блок масштабирования, первый узел задержки, первый и второй коммутаторы и блок управления, в состав которого входят дешифратор, элемент ИЛИ, первый элемент И, первый вход

0 которого соединен с выходом дешифратора, вход которого соединен с входом первого слагаемого блока модульного сложения, выходом блока масштабирования, с входом первого сомножителя блока модульного ум5 ножения, выход которого соединен с входом регистра, выход которого соединен с входом вычитаемого блока модульного вычитания, введены третий коммутатор, мультиплексор, с второго по шестой узлы

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

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

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

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

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

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

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

0 схема устройства для деления чисел в модулярной системе счисления; на фиг.З - структурная схема блока управления.

Устройство содержит вход 1 делимого, вход 2 делителя, вход 3 запуска и тактовый

5 вход 4 устройства, первый 5 и второй fi коммутаторы, блок 7 управления, первый 8 и второй 9 узлы задержки, формирователь 10 интегральных характеристик модулярного кода, блок 11 модульного вычитания, блок

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

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

1 Л

1 I

bi одгт, (I , 2к), где гги, m2,...,mk 5 основания модулярной системы счисления, являкщиеся попарно простыми целыми

числами, т.е. (mi, mj) 1; I, j 1, 2k; I & j.

В состав блока 7 управленяи входят первый 25 и второй 26 регистры сдвига, 0 дешифратор 27, первый 28 и второй 29 кольцевые сдвиговые регистры, первый 30, второй 31 и третий 32 элементы И и элемент ИЛИ 33.

Разрядность первого 25 и второго 26 5 регистров сдвига составляет соответственно Т + 1 и 2Т + 8 бит.

Инверсный выход (Т-:4)-го разряда, прямой и иноерсный выходы (2Т+5)-го разряда, прямой выход (2Т-4б)-го и инверсный выход

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

Г 1,еслиХе{-1.0, 1},

е(Х)О)

0 в остальных случаях

где X - входная переменная, заданная своим МОДУЛЯРНЫМ КОДОМ (XI, Х2Xk) И

принадлежащая диапазону D {-m0 Mk-1, -m0 x хМы + 1,...,т0Мы- 1} модулярной системы счисления;

xi- IX |m-(i 1,2k);

rn0 - вспомогательный модуль, выбира- емый из условий mo k-1;

mk 2m0 + k-2;

Mk-1 П

mi;

. f

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

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

Установочные входы первого 25 и второго 26 регистров сдвига и входы сброса первого 28 и второго 29 кольцевых сдвиговых регистров объединены и подключены к входу 3 запуска устройства, входы управления сдвигом первого 25 и второго 26 регистров сдвига, первого 28 и второго 29 кольцевых сдвиговых регистров объединены и подключены к тактовому входу 4 устройства, выход старшего разряда первого регистра 25 сдвига соединен с входом младшего разряда первого кольцевого сдвигово- го регистра 28, выход дешифратора 27 и третий выход второго регистра 26 сдвига подключены соответственно к первому и второму входам первого элемента И 30, выход которого соединен с входом младшего разряда второго кольцевого сдвигового регистра 29. Второй выход второго регистра 26 сдвига и выход старшего разряда второго кольцевого сдвигового регистра 29 соединены соответственно с первым и вторым вхо- дами элемента ИЛИ 33. Выходы всех разрядов (с нулевого по (Т+ 5)-й) второго кольцевого сдвигового регистра 29 подключены к входам третьего элемента И 32, вы5

10

5

0

5

0

5 }Q 5 Q е

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

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

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

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

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

Формирователь 10 интегральных характеристик модулярного кода является известным устройством, представляющим собой усеченный вариант параллельно-конвейер- ного устройства для формирования интегральных характеристик модулярного кода, быстродействие которого составляет Т+ 3 такта при пропускной способности одна операция в один такт. Формирователь 10 по входному модулярному оду (XL X2Xk) числа X из диапазона D модулярной системы счисления осуществялет формирование лишь двух характеристик: знака S(X)€Ј{0,1} числа X и номера I масштаба Si, аппроксимирующего абсолютную величину/Х/числа X: f 0, если X О,

S(X)-M(2)

11,еслиХ 0.

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

Xy+vx 2 ,

v - Г v 1

где Ху - -ycf5j

О, если Ху А-/, ду 1зе.- А + 1 в остальных случаях;

v - номер старшей ненулевой цифры симметрического полиадического представления + Х2 Мн ... H#k Mk-1 числа XeD;

.- -ЗЧ+1....

1 -у- Г- 1} 0 1. 2k); у - целая часть

действительного числа у;

(.

М П mj;

номер старшего ненулевого разряда в двоичном представлении числа

Ху Ix + х mv-il- Mjr2;

А-количество старших двоичных разрядов числа Х-), используемых для определения масштаба Si, который имеет вид

Si Xv 2

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

соответствующего ( v -1)-го ( v 2, 3k)

формирователя номера нрмирующего множителя по адресу 2 величина

х„записывается

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

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

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

наборов вычитателей, умножителей и сумматоров по модулям mi, ГП2mk и слухсат

для выполнения соответствующих операций над модулярными кодами целых чисел

из диапазона D модулярной системы счисления.

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

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

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

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

вторым выходами узла задержки.

Блок 17 присвоения знака осуществляет преобразование модулярного кода числа X eD в модулярный код числа Х1 X-(-1)s(Y), где S(Y)e {0,1} - знак числа

Ye D. Модулярный код (xi, X2xk) числа X и

величина S(Y) поступают на первый и второй входы блока 17 соответственно. Елок 17 присвоения знака реализуется с помощью k долговременных запоминающих устройств,

- 1-е из которых обладает емкостью 2Ь(1 слов разрядностью bi бит и в память которого по адресу xi + 2bl-SfY) записывается вычет

XrlX lm lxK-IJ M1 1-2k)

Третий коммутатор 18 содержит од2Ц мультиплексоров, где I. -- число масштабов, на которые рассчитан блок 20 масштабирования.

Блок 20 масштабирования представляет собой известное устройство для масштабирования параллельно-конвейерного гипз, быстродействие которого составляет Т+3 такта при пропускной способности одна операция масштабирования в один такт. Блок 20 масштабирования осуществляет деление входного числа X € D на некоторый

положительный масштаб Si g D, причем это число ограничено и равно L. Номер

le {0, 1L-1} масштаба Si и модулярный код

числа X подаются соответственно на первый и второй входы блока 20. Результатом операции масштабирования является оценка (ближайшее целое число) дроби X/Si. В блоке 20 функция блокировки выдачи ненулевой информации реализуется стандартным образом путем подключения к выходу выходного регистра блока группы элементов запрета, управляемой посредством входа блокировки.

Выход блока 17 присвоения знака соединен с вторым входом блока 20 масштабирования, первый вход которого объединен с входом пятого узла 21 задержки и подключен к выходу третьего коммутатора 18; вход дешифратора 27 блока 7 управления, вход первого сомножителя блока 12 модульного умножения и вход первого слагаемого блока 19 модульного сложения объединены и подключены к выходу блока 20 масштабирования, вход блокировки которого соединен с выходом элемента ИЛИ 33 блока 7 управления, второй информационный вход третьего коммутатора 18 соединен с выходом пятого узла 21 задержки

Пятый 21 и шестой 22 узлы задержки осуществляют задержку информации на Т+ 6 тактов. Разрядность регистров, входящих в состав пятого 21 и шестого 22 узлов задержки, состаляет соответственно log2L и Л бит. Входы сброса регистров шестого узла 22 задержки в совокупности составляют вход сброса узла задержки.

Вход сброса шестого узла 22 задержки подключен к входу 3 запуска устройства; вход второго слагаемого и выход блока 19 модульного сложения соединены соответственно с выходом и входом шестого узла 22 задержки, выходы шестого узла 22 задержки и второго элемента И 31 блока 7 управления являются выходом 23 частного и выходом 24 признака окончания деления устройства соответственно.

Рассмотрим, как работает предлагаемое устройство для деления чисел в модулярной системе счисления.

На начальном (нулевом) такте по сигналу Гупр 1, подаваемому на вход 3 запуска устройства, регистры, входящие в состав шестого узла 22 задержки, а также первый 28 и второй 29 кольцевые сдвиговые регистры блока 7 управления обнуляются; в первом регистре 25 сдвига блока 7 управления устанавливается (Т+ 1)-разрядный двоичный код числа 1, во втором регистре 26 сдвига блока 7 управления устанавливается (2Т+ 8)-разрядный дополнительный двоичный код чилса -1, На первом выходе второго регистра 26 сдвига вырабатывается сигнал дг, 0 (где о - содержимое J-ro разряда второго регистра 26 сдвига, j О,

5 12Т-7; а - отрицание булевой величины

О), который поступает на управляющие входы первого 5 и второго 6 коммутаторов. В результатемодулярныйкод

(«1 , (Xi,,.., «k) делимого А, поступающий

0 на вход 1 делимого устройства, через первый коммутатор 5 передается в первй узел 8 задержки, а модулярный код

( , jhД) делителя В, поступающий

на вход делителя 2 устройства, через второй

5 коммутатор 6 передается во второй узел 9

задержки (о,- IA mi,/, IB m-L, i 1,2k; A.

Bet), В 0). Одновременно с этим модулярный код делителя В с входа 2 делителя устройства поступает на вход формирователя

0 Ю интегральных характеристик модулярного кода После этого начинается выполнение операции деления числа А на В.

Ввиду обеспечения в устройстве конвейерного режима выполнения не одной, а

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

0 Отметим, что на каждом такте работы устройства по сигналу Гт 1, подаваемому на тактовый вход 4 устройства, содержимое первого 25 и второго 26 регистров сдвига, первого 28 и второго 29 кольцевых

5 сдвиговых регистров блока 7 управления сдвигается на один бит в сторону старших разрядов.

На первом такте реализуемой процедуры деления формирователь 10 интеграль0 ных характеристик модулярного кода начинает вычисление знака S(B) и номера I масшатбз Si В, аппроксимирующего абсолютную величину IBI делителя В.

На (Т+ 1)-м такте содержимое у - 1 стар5 шего разряда первого регистра 25 сдвига блока 7 управления передается в младший разряд первого кольцевого сдвигового регистра 28 блока 7 управления.

Начиная с (Т+1)-го такта реализуемая

0 процедура деления носит итеративный характер. Все итерации имеют одинаковую длительность, а именно Т+6 тактов.

На первом такте первой итерации модулярный код делителя В с второго выхода

5 второго узла 9 задержки поступает на вход второго сомножителя блока 12 модульного умножения, на вход первого сомножителя которого с выхода блока 20 масштабирования подается модулярный код числа Q0 О

ш

Q)/,

(Гбл 1,где о) -содержимое 1-го разряда (I 0, 1Т+5) второго кольцевого сдвигового регистра 29 блока 7 управления. В результате блок 12 модульного умножения получает произведение В -0 О, код которого передается в регистр 15. Кроме этого, модулярный код числа Q0 0 с выхода блока 20 масштабирования подается на вход первого слагаемого блока 19 модульного сложения, на вход второго слагаемого которого с выхода шестого узла 22 задержки поступает модулярный код числа Q-1 0. Блок 19 модульного сложения формирует модулярный код суммы Qo + Q-1 0, который записывается в первый регистр шестого узла 22 задержки. Одновременно с этим модулярный код числа Qo 0 поступает на вход дешифратора 27 блока 7 управления. В соответствии с соотношением (1) на выходе дешифратора 27 re- нерируется сигнал e(Qo) 1, поступающий на первый вход первого элемента ИЛИ 30 блока 7 управления, на второй вход которого с третьего выхода второго регистра 26 сдвига подается нулевой сигнал а2Т+5 0. В результате в младший разряд второго кольцевого сдвигового регистра 29 блока 7 управления с выхода первого элемента И 30 поступает сигнал fi е ( Qo ) 0 и, таким образом, на данной итерации процедуры деления не происходит изменения содержимого второго кольцевого сдвигового регистра 29.

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

15(код числа 0) подаются соответственно на входы уменьшаемого и вычитаемого блока 11 модульного вычитания. Блок 11 формирует разность At АО - 0 А, которая переда- ется в третий узел 14 задержки. Одновременно с этим формирователь 10 интегральных характеристик модулярного кода завершает вычисление знака S(B) делителя В, Двухзначная величины S(B) с первого выхода формирователя 10 через мультиплексор 13, на управляющий вход которого подается сигнал 1. поступает в четвертый узел 16 задержки.

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

16задержки подаются на первый и второй входы блока 17 присвоения знака. Полученный блоком 17 модулярный код числа Ri Ai (-l)5 поступает в блок 20 масштабирования через второй его вход. Кроме этого, на данном такте формирователь 10

10

15

20

f- 4045

т

5

30

35

50

55

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

На четвертом такте первой итерации блок 20 масштабирования начинает вычисление модулярного кода оценки QI дроби R.1/B.

На шестом такте первой итерации модулярный код числа Ai с первого выхода третьего узла 14 задержки поступает на второй информационный оход первого коммутагора 5, на управляющий вход которого подается сигнал 1, в результате код числа AI передается в первый узел 8 задержки. Одновременно с этим модулярный коддели- теля В с первого выхода второго уз/iaj) задержки через второй коммутатор 6 (ow/, 1} передается во второй узел 9 задержки.

На последнем ()-м такте первой итерации блок 20 масштабирования завершает вычисление модулярного кода оценки СИ дроби Ri/B.

На первом такте j-й итерации (j - 2, 3,...) модулярный код числа QJ-I с выхода блока 20 масштабирования (Гбл Л м V 0) подается на вход первого сомножителя блока 12 модулярного умножения и вход первого слагаемого блока 19 модульного сложения, на входы второго сомножителя и второго слагаемого которых поступают соответственно модулярный код делителя В с второго выхода второго узла 9 задержки и модулярный j -2 j -2

код суммы 2 QI - Е Qi (Q-1 Qo 0) с I -1 1 1

выхода шестого узла 22 задержки. В результате блок 12 модульного умножения получает произведение Qj-ГВ, модулярный код которого записывается в регистр 15, а на выходе блока 19 модульного сложения форJ-1мируется код суммы 2) QI который переi 1 дается в шестой узел 22 задержки.

На втором такте j-й итерации модулярный код числа AJ-I с выхода первого узла 8 задержки и содержимое регистра 15 (код числа Qj-i B) подаются соответственно на входы уменьшаемого и вычитаемого блока 11 модульного вычитания, в результате чего на выходе блока 11 формируется разность Aj Aj-1 - Qj-rB, модулярный код которой передается в третий узел 14 задержки. Одновременно с этим знак S(B) делителя В с

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

На третьем такте j-й итерации модулярный код числа А с второго выхода третьего элемента 14 задержки и знак S(B) с первого выхода четвертого узла 16 задержки подаются на первый и второй входы блока 17 присвоения знака. Получаемый блоком 17 модулярный код числа Rj Aj(-1) поступает в блок 20 масштабирования через второй его вход. Кроме этого, номер I масштаба Sr В с выхода пятого узла 21 задержки поступает на второй информационный вход третьего коммутатора 18, на управляющий вход которого подается сигнал 7гг+7 1. В результате величина I поступает в пятый узел 21 задержки, а также в блок 20 масштабирования, который со следующего такта итерации начнет вычисление модулярного кода оценки QJ дроби Rj/B.

На шестом такте j-й итерации модулярные коды числа А с первого выхода третьего узла 14 задержки и делителя В с первого выхода второго узла 9 задержки через первый 5 и второй 6 коммутаторы, на управляющие входы которых поступает сигнал оу 1, передаются на входы первого 8 и второго 9 узлов задержки соответственно.

На заключительном, Л 6-м, такте J-й итерации блок 20 масштабирования получает модулярный код оценки QJ дроби Rj/B,

Описанная последовательность действий повторяется до тех пор, пока по окончании некоторой r-й итерации () на выходе блока 20 масштабирования не будет получен модулярный код числа Qre{-1, 0, 1}. В этом случае на первом такте (г+1)-й итерации 6 соответствии с соотношением (1) на выходе дешифратора 27 блока 7 управления генерируется сигнал е (СЬ) 1, поступающий на первый вход первого элемента ИЛИ 30, на второй вход которого с третьего выхода второго регистоа 26 сдвига подается единичный сигнал ( 1. В результате младший разряд второго кольцевого сдвигового регистра 29 установится в единичное состояние, так как в него с выхода первого элемента И 30 поступает сигнал Гч е ( Qr) ait,5 1. Одновременно с этим блок 19 модульного сложения получает модулярный код искомого част--

t ного Q 2) Qi который передается в

1 1 шестой узел 22 задержки.

Процесс выполнения инициированной группы из Т+6 операций деления продолжается до тех пор, пока все они не завершатся. В момент получения блоком 19 модульного

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

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

получения результатов реализованных операций деления в порядке их инициации работа устройства продолжается еще Т - п + 5

5 тактов, т.е. до момента появления на выходе 23 признака окончания деления устройства единичного сигнала. В течение очередных Т+6 тактов полученные частные последовательно снимаются с выхода 24 устройства и

0 на этом процесс выполнения группы операций деления заканчивается, В такте съема последнего частного в устройстве может быть начата инициация новой группы операций.

5 Из приведенного описания видно, что включение в состав предлагаемого устройства отдельного блока для аппроксимации делителя (параллельно-конвейерного формирователя интегральных х эрактери0 стик модулярного кода с частотой обращения f 1 Лм.т) дает возможность совмещать во времени процессы выполнения Т+б операций деления. Таким образом, предлагаемое решение пйзволяет увели5 чить быстродействие предлагаемого устройства в сравнении с известным в Т+6 раз. Если, например, используется модулярная система счисления с числом оснований К 8, то достигается девятикратное увеличение

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

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

Устройс во для деления чисел в модуе лярной системе счисления, содержащее блок модульного вычитания, блок модульного умножения, регистр, блок модульного сложения, блок масштабирования, первый узел задержки, первый и второй коммутато0

5

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

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

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

кольцевого сдвигового регистра, вход младшего разряда которого соединен с выходом первого элемента И, первый выход второго регистра сдвига соединен с управляющими входами первого и второго коммутаторов,

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

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

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

for. г