Устройство для умножения s-ичных цифр в позиционно- остаточной системе счисления

 

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

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

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

Недостатки устройства - большой объем оборудования и низкое быстродействие.

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

Недостатками устройства являются большой объем оборудования и низкое быстродействие.

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

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

На фиг. 1 представлена структурная схема предлагаемого устройства для умножения S-ичных цифр в позиционно-остаточной системе счисления, где 1 - первый блок хранения констант, 2 - второй блок хранения констант, 3 - третий блок хранения констант, 4 - первый блок умножения, 5 - второй блок умножения, 6 - третий блок умножения, 7 - четвертый блок умножения, 8 - первый сумматор, 9 - второй сумматор, 10 - третий сумматор, 11 - выход старшего разряда произведения устройства, 12 - выход младшего разряда произведения устройства, 13 - вход первого операнда устройства, 14 - вход второго операнда устройства; на фиг. 2 - структурная схема первого сумматора 8, где 15 - дешифратор первого операнда, 16 - дешифратор второго операнда, 17 - матрица сумматоров по модулям P_j, 18 - первый шифратор, 19 - второй шифратор, 20 - мультиплексор; на фиг. 3 - структурная схема второго сумматора 9, где 21 - блок сравнения с константой.

Выходы первого и второго сумматоров 8 и 9 являются соответственно выходами 11 и 12 старшего и младшего разрядов произведения устройства. Вход переноса первого сумматора 8 соединены с выходом переноса второго сумматора 9. Входы первых слагаемых первого и второго сумматоров 8 и 9 соединены через третий блок 3 хранения констант с выходом третьего сумматора 10, а их входы вторых слагаемых - с выходами соответственно первого и четвертого блоков 4 и 7 умножения. Входы слагаемых третьего сумматора 10 соединены соответственно с выходами второго и третьего блоков 5 и 6 умножения. Первые входы первого и второго блоков 4 и 5 умножения объединены и подключены к первому выходу первого блока 1 хранения констант, второй выход которого подключен к объединенным первым входам третьего и четвертого блоков 6 и 7 умножения. Первый выход второго блока 2 хранения констант подключен к объединенным вторым входам первого и третьего блоков 4 и 6 умножения, а его второй выход - к объединенным вторым входам второго и четвертого блоков 5 и 7 умножения. Входы первого и второго блоков 1 и 2 хранения констант являются соответственно входами 13 и 14 первого и второго операндов устройства.

Первый сумматор 8 конструктивно представляет собой S-ичный сумматор на три входа без формирования переноса, результат которого всегда меньше S, и содержит дешифратор 15 первого операнда и дешифратор 16 второго операнда, входы которых являются соответственно входами первого и второго слагаемых сумматора 8. Выходы дешифраторов 15 и 16 подключены к соответствующим входам матрицы 17 сумматоров по модулям P_j, подключенной входом к объединенным входам шифраторов 18, 19, выходы Σ и Σ+1 которых подключены к соответствующим входам мультиплексора 20, выход которого является выходом сумматора 8.

Второй сумматор 9 конструктивно представляет собой S-ичный сумматор на два входа с формированием сигнала переноса и содержит дешифратор 15 первого операнда и дешифратор 16 второго операнда, входы которых являются соответственно входами первого и второго слагаемых сумматора 9. Выходы дешифраторов 15 и 16 подключены к соответствующим входам матрицы 17 сумматоров по модулям P_j. Выход матрицы 17 подключен к объединенным входам блока 21 сравнения с константой и шифраторов 18, 19, выходы Σ и Σ-S которых подключены к соответствующим входам мультиплексора 20, выход которого является выходом сумматора 9. Управляющий вход мультиплексора 20 объединен с выходом блока 21 сравнения с константой и является выходом переноса сумматора 9.

Блок 21 сравнения с константой представляет собой блок постоянной памяти объемом (S-1)x1 бит. Блок 3 хранения констант аналогичен блокам 1, 2 хранения констант и конструктивно представляет собой блоки постоянной памяти на (l_j-2l)-разрядных слов каждый, где l= l_j - двоичная разрядность вычета α_j или β_j .

В основу работы устройства для умножения S-ичных цифр в позиционно-остаточной системе счисления положено следующее.

Произведение двух S-ичных цифр имеет вид a·b= (a+a_o)(b+b_o)= a₁b₁S+a₁b+a_ob+a_ob_o. (1) Второе и третье слагаемые имеют вид a₁b+a_ob+a_ob_o= C. (2) Представляют С в виде C = c₁S + c_o, где c₁ = ent (C/ √ ); c_o = rest(C/). (3) В результате a ˙b = a₁b₁S + c₁S + a_ob_o + c_o (4) или a˙ b = d₁S¹ + d_oS^o, где d₁ = a₁b₁ + c₁; d_o = a_ob_o + c_o.

При вычислении выражения a_ob_o + c_o результат может превысить величину S, поэтому
d₁ = a₁b₁ + c₁ + f, (6) где f - сигнал переноса из сумматора 9, вычисляющего d_o, в сумматор 8, вычисляющий d₁.

Известно, что цифры в S-ичной позиционно-остаточной системе счисления представляются по модулям COK в виде
а = (α₁, α₂, . . . , α_К); b = (β₁, β₂, . . . , β_К) , где α_j = rest (a/P_j); β_j = rest (b/P_j), j = j= ,
P_j - модули СОК, удовлетворяющие условию
P_j≥2S, P_j взаимно просты.

Для согласования с устройствами, работающими в двоичной системе счисления, в позиционно-остаточных устройствах обычно выбирают S = 2^m. Удобнее всего в настоящее время принять m = 8 и соответственно S = 2⁸ = 256, а среди модулей СОК иметь один, равный . В частном случае, пусть Р₁ = = 16. Это позволяет при аппаратной реализации блоков 1, 2 и 3 получить экономичные решения.

Устройство для умножения S-ичных цифр в позиционно-остаточной системе счисления работает следующим образом.

Операнды а = (α₁, α₂, . . . , α_К); и b = = (β₁, β₂, . . . , β_К), представленные кодом СОК по модулям Р₁, Р₂, . . . , Р_К, по входам 13 и 14 поступают на входы соответствующих блоков 1 и 2 хранения констант. В этих блоках в соответствии с выражением (1) формируются величины a₁, a_o, b₁, b_o соответственно, которые поступают на первые и вторые входы блоков 4, 5, 6, 7 умножения. В этих блоках в соответствии с выражением (1) формируются величины a₁b₁S, a₁b, a_ob, a_ob_o. Величины a₁b₁S и a_ob_o поступают на вторые входы слагаемых соответственно первого и второго сумматоров 8 и 9. Величины a_ob и a₁b выходов соответствующих блоков 6 и 5 умножения поступают на входы третьего сумматора 10, где в соответствии с выражением (2) формируется сумма С, которая поступает на вход блока 3 хранения констант, где в соответствии с выражениями (3) и (4) формируются величины с₁ и с_о. С выходов блока 3 величины с₁ и с_о поступают на первые входы слагаемых соответственно первого и второго сумматоров 8 и 9. На сумматоре 9 в соответствии с выражением (5) формируются величины d_o и f. Величина d_o поступает на выход 12 и является младшим разрядом произведения. На сумматоре 8 в соответствии с выражением (6) формируется величина d₁, которая поступает на выход 11 и является старшим разрядом произведения.

Блок 8 формирует результат в соответствии с табл. 1.

Блок 9 формирует результат в соответствии с табл. 2.

Таким образом, предлагаемое устройство может быть использовано в качестве разрядного умножителя S-ичных цифр в позиционно-остаточной системе счисления для умножения чисел в СОК в диапазоне P_j, а также в качестве байтового умножителя в позиционных системах счисления. (56) 1. Авторское свидетельство СССР N 1236472, кл. G 06 F 7/72, 1984.

2. Авторское свидетельство СССР N 1633401, кл. G 06 F 7/72, 1989.

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

УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ S-ИЧНЫХ ЦИФР В ПОЗИЦИОННО-ОСТАТОЧНОЙ СИСТЕМЕ СЧИСЛЕНИЯ, содержащее первый и второй блоки хранения констант, первый - четвертый блоки умножения и первый и второй сумматоры, выходы которых являются соответственно выходами старшего и младшего разрядов произведения устройства, входы первого блока умножения соединены с первыми выходами соответственно первого и второго блоков хранения констант, вторые выходы которых соединены с соответствующими входами четвертого блока умножения, отличающееся тем, что оно дополнительно содержит третий сумматор и третий блок хранения констант, первый и второй выходы которого соединены соответственно с входами первых слагаемых первого и второго сумматоров, входы вторых слагаемых которых соединены соответственно с выходами первого и четвертого блоков умножения, вход переноса первого сумматора соединен с выходом переноса второго сумматора, вход третьего блока хранения констант соединен с выходом третьего сумматора, входы слагаемых которого соединены соответственно с выходами второго и третьего блоков умножения, при этом входы второго блока умножения соединены соответственно с первым выходом первого блока хранения констант и вторым выходом второго блока хранения констант, входы третьего блока умножения соединены соответственно с вторым выходом первого блока хранения констант и с первым выходом второго блока хранения констант, а входы первого и второго блоков хранения констант являются соответственно входами первого и второго операндов устройства.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4