Сумматор по модулю @ - числа ферма Советский патент 1993 года по МПК G06F7/49 

Изобретение относится к вычислительной технике и может быть использовано для построения быстродействующих арифметических устройств, работающих в системе остаточных классов (СОК), в частности, в цифровых процессорах обработки сигналов (ЦОС), выполняющих теоретико-числовые преобразования по модулю чисел Ферма (ТЧПФ).

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

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

На фиг. 1 иллюстрируется метод перекодирования операндов в кольце целых чисел по модулю чисел Ферма с уменьшением на единицу (1); на фиг. 2 представлена функциональная схема сумматора по модулю чисел Ферма; на фиг. 3 приведен пример конкретного выполнения предложенного устройства.

Сумматор по модулю t числа Ферма содержит N элементов искл. ИЛИ 11-1м, первый блок 2 ускоренного переноса (СУШ) и второй блок 3 ускоренного переноса (СУП2), N полусумматоров , каждый из которых состоит из элементов SI-SN ИСКЛ. ИЛИ и элементов 61-бмИ, при этом в полусумматор введен элемент 7 ИЛИ, входы которого объединены со входами полусумматора 4i, а выход подключен ко входу переноса во второй разряд Пт в блоке 3 СУП2. Выходы

VJ

О

ел ел

элементов 5г-5м и 6i-бы ИСКЛ. ИЛИ и И подключены к соответствующим одинаковым входам разрешения распространения переносов RI и генерации переносов Gi в блоках 2 и 3 СУП 2, при этом выходы элементов ИСКЛ ИЛИ подключены к первым входам элементов ИСКЛ. ИЛИ , выходы которых являются первыми N разрядами результата. Выход переноса старшего разряда ON блока 2 СУШ подключен к первому входу элемента 8 ИЛИ, другие два входа которого присоединены ко входам (N+1)-x разрядов слагаемых, а к его выходу подключен вход инвертора 9, к выходу которого подключены второй вход элемента ИСКЛ. ИЛИ Н вход элемента 11 И и четвертые входы (N-1) элементов 12i 12w-i 2И-ИЛИ. Второй вход элемента 11 И подключен к выходу элемента 7 ИЛИ, а его выход - ко входу элемента 10 ИЛИ, второй вход которого подключен к выходу элемента 6iH и . входу переноса во второй разряд П i блока 2 СУШ, Выход элемента 10 ИЛИ присоединен ко второму входу элемента ИСКЛ. ИЛИ 12. Вторые входы элементов ИСКЛ. ИЛИ соединены соответственно с выходами элементов 12i-12i i-2 2И-ИЛИ, первые входы которых соединены с соответствующими выходами переносов блока 2 СУШ, вторые входы подключены к выходу элемента 8 ИЛИ, третьи - к соответствующим выходам переносов блока 3 СУШ. Второй вход элемента 12N-12И-ИЛИ подключен к выходу переноса старшего разряда п ы блока 3 СУП2, третий и четвертый входы подключены ко входам (N+1)-x разрядов слагаемых.

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

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

X-(X-1)modFt

достигается упрощение арифметических операций. На фиг. 1 показано соответствие чисел и их двоичных кодов для этого случая (внешнее кольцо двоичных кодов поворачивается на одно деление против часовой стрелки). При этом при сложении по модулю числа Ферма с помощью двоичного сумматора необходимо прибавить инвертированный перенос к двоичной сумме. Число нуль имеет особое представление с (N+1)-M разрядом: , .,.. Появление 1 в (N+1)-M разряде служит для прерывания операции. Ниже приведены четыре различных возможных.случая суммирования с при-- ведением результата по модулю чисел Ферма(см. таблицу 1.

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

.ИЛИ)

- и генерации переноса: GrAi Bi (И),

где А и Bi - разряды слагаемых; блок ускоренного переноса (СУП) со входами Re, GI каждого разряда и вход переноса По, а также выходами переносов П (,N) подключенными к соответствующим входам

N элементов ИСКЛ.ИЛИ, вторые входы которых присоединены к выходам элементов ИСКЛ.ИЛИ полусумматоров одноименного разряда.

в блоке СУП переносы образуются согласно рекурентной формуле:

fli+Gi (НО, N-1), которая определяет внутреннюю архитектуру СУП.

Элементы ИСКЛ. ИЛИ обеспечивают

поразрядное сложение полусумм с переносами:

.

Предлагаемое устройство функционирует следующим образом:

В блоке 3 СУП 2 вводится входной перенос П (при этом для блока 2 СУП1 входной перенос П 0).

с помощью управляющего сигнала

Р Пм+Ам+Вм,

образующегося на выходе элемента 8 ИЛИ, устанавливается, какие переносы необходимо прибавлять к полусуммам в элементах ИСКЛ. ИЛИ 1i+1w. В случае переносы выбираются из блока 2 СУП 1, при Р 0- из блока 3 СУП2.

Коммутация переносов на входе элементов ИСКЛ.ИЛИ 1i+1w обеспечивается посредством мультиплексных элементов 121+12м-1 2И-ИЛИ, инвертора 9, элемента 11 И, элемента 10 ИЛИ.

N-й разряд суммы формируется на элементе 12м-1 согласно выражению:

ON+AN -Пм

Перенос Пт во второй разряд блока 2 СУП 1 снимается непосредственно с элемента 6il/l, поскольку:

-R0+G0 A0

Перенос П-i во второй разряд блока 3 СУП2 формируется, на выходе элемента 7 ИЛИ:

-R0+Go Ro+Go A0+Bo

Таким образом, блоки 2 и 3 СУП 1 и СУП2 короче на один разряд по сравнению с блоком СУП обычного двоичного сумматора.

В примере конкретного выполнения предложенного устройства на фиг. 3 приведена принципиальная схема сумматора по модулю второго числа Ферма для пятиразрядного кодирования с уменьшением на единицу. Разряды Со ...Сз результата формируются согласно уравнениям:

с0 RO

+р.

где

P A4+B4+RsR2Ri -Go+R2R3Gi-i-R3G2+G3

+ B0 +A0B0 x

X (A4+B4+R3feGl+P3G2+G3)

C2 R2 Aj+Bi+Gi -Aft +B0-+A0-B0+ +Gi(A4+B4+R3G2+G3)

.3+tA2+B2+Ai+Bi Gi+Gi+G2 x +Bj + Ae- B0 (A4+B4+G3)}

C4 A4+B4 РзР2 PlPo+A4B4.

Посравнению с серийными четырехраз- 45 рядными сумматорами со схемами ускоренного переноса, например, ТТЛ - серий 155, 555 и т.п. типа ИМЗ, ИМ6 данная схема имеет одинаковый с ними порядок архитектурной сложности и быстродействия.50

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

40

Сумматор по модулю t-числа Ферма , где , содержащий N элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, первый блок ускоренного переноса, N полусумматоров, элементов И и первый элемент ИЛИ, причем информационные входы полусумматоров

0

5

5 0

являются входами соответствующих N разрядов слагаемых сумматора, выход суммы i-ro полусумматора (, N) соединен с первым входом 1-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого является выходом i-ro разряда сумматора, выходы суммы полусумматоров с второго по N-й соединены соответственно с входами с второго по N-й разрешения распространения переноса

0 первого блока ускоренного переноса, входы с второго по N-й генерации переноса которого соединены соответственно с выходами переноса полусумматоров с второго по N-й, отличающийся тем, что, с целью

5 повышения быстродействия, в него введены (N-1) элементов 2И-ИЛИ, второй и третий элементы ИЛИ, элемент НЕ и второй блок ускоренного переноса, причем (N+1)-n выход переноса первого блока ускоренного переноса соединен с первым входом первого элемента ИЛИ, второй и третий входы которого соединены соответственно с входами (N+1)-ro разряда слагаемых сумматора, а выход первого .-элемента ИЛ И соединен с входом элемента НЕ и с первыми входами элементов 2И-ИЛИ с первого по (№-2)-й, вторые входы которых соединены соответственно с выходами переноса с третьего по N-й первого блока ускоренного переноса,

0 вход переноса которого соединен с выходом переноса первого полусумматора и с первым входом второго элемента ИЛИ, вы- ход которого соединен с вторым входом второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ,

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

0 переноса и с первым входом элемента И, выход которого соединен с вторым входом второго элемента ИЛИ, выход элемента НЕ соединен с вторым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, вторым входом элемента И, третьими входами элементов 2И-ИЛИ с первого по (N-2) и с первым входом (N-1)-ro элемента 2И-ИЛИ, второй вход которого соединен с (N+1)M выходом переноса второго блока ускоренного перекоса, выходы переноса с третьего по N-й которого соединены соответственно с четвертыми входами элементов 2И-ИЛИ с первого no(N-2)-u, выходы которых соединены соответственно с вторыми входами элемен5 тов ИСКЛЮЧАЮЩЕЕ ИЛИ с третьего по N-й, входы с второго по N-й разрешения распространения переноса второго блока ускоренного переноса соединены соответственно с входами с второго по N-й разрешения распространения переноса первого

блока ускоренного переноса/входы с второго по N-й генерации переноса которого соединены соответственное входами с второго по N-й генерации переноса второго блока

ускоренного переноса, входы (N+1)-ro раз-

ряда слагаемых сумматора соединены соответственно с третьим и четвертым входами (N1)-ro элемента 21/1-ИЛИ, выход которого является выходом (N+1)-ro разряда суммато

Х-+(х-- )лю0fy ; /V А/, &Ј/& 1