Сумматор по модулю @ - числа ферма

 

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

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

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

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4863493/24 (22) 03.09,90 (46) 15,02.93. Бюл. ¹ 6 (71) Научно-исследовательский институт радиотехнической аппаратуры (72) А. С. Горшков (56) Авторское свидетельство СССР

N 1170450, кл. G 06 F 7/49, 1985.

Захаров Ю. И„ Титков Б. В, Реализация конвольвера циклической дискретной свертки на основе теоретико-числового преобразования "Ферма", НТС "Техника средств связи", сер. "Техника телевидения", вып. 6, 1989, с. 58, (54) СУММАТОР ПО МОДУЛЮ t-ЧИСЛА

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

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

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

„„5U„„1795451 А1 зовано для построения быстродействующих арифметических устройств, работающих в системе остаточных классов, в частности в цифровых процессорах обработки сигналов, выполняющих теоретико-числовые преобразования по модулю чисел Ферма.

Целью изобретения является повышение быстродействия устройства, Сумматор по модулю t-числа Ферма содержит M элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй блоки ускоренного переноса, N полусумматоров, каждый из которых состоит из элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, элементов И, причем в первый полусумматор введены элементы ИЛИ, элемент НЕ, элемент И и N-1 элементов 2И вЂ” ИЛИ, соедиНа фиг, 1 иллюстрируется метод переко- а дирования операндов в кольце целых чисел по модулю чисел Ферма с уменьшением на единицу(1); на фиг. 2 представлена функци- ц ональная схема сумматора по модулю чисел

Ферма; на.фиг. 3 приведен пример конкрет- + ного выполнения предложенного устройства. ай

Сумматор па модулю t числа Ферма содержит M элементов искл. ИЛИ 11 1д, первый блок 2 ускоренного переноса (СУП1) и второй блок 3 ускоренного переноса (СУП2), M полусумматоров 41 — 4N, каждый из которых состоит из элементов 51 5N ИСКЛ. ИЛИ и элементов át — биИ, при этом в полусумматор 4t введен элемент 7 ИЛИ, входы которого объединены со входами полусумматора

41, а выход подключен ко входу переноса во второй разряд П1 в блоке 3 СУП2, Выходы

1795451

Go=At Bi (И), 20

6(=й9П Р=Пи+Аи+Вн.

X - {Х вЂ” 1)modF< элементов 5i-5g и 61 — -бц ИСКЛ. ИЛИ и И подключены к соответствующим одинаковым входам разрешения распространения переносов R и генерации переносов Gi в блоках 2 и 3 СУП 2, при этом выходы элементов 5>-5tu ИСКЛ ИЛИ подключены к первым входам элементов ИСКЛ. ИЛИ 1< — 1N, выходы которых являются первыми N разрядами результата. Выход переноса старшего разряда П блока 2 СУП1 подключен к первому входу элемента 8 ИЛИ, другие два входа которого присоединены ко входам (N+1)-õ разрядов слагаемых, а к его выходу подключен вход инвертора 9, к выходу которого подключены второй вход элемента ИСКЛ, ИЛИ 11, вход элемента 11 И и четвертые входы (N-1) элементов 121-12и-1 2И-ИЛИ.

Второй вход элемента 11 И подключен к выходу элемента 7 ИЛИ, а его выход — ко входу элемента 10 ИЛИ, второй вход которого подключен к выходу элемента 61И и . входу переноса во второй разряд П > блока 2

СУП1, Выход элемента 10 ИЛИ присоединен ко второму входу элемента ИСКЛ. ИЛИ

1 . Вторые входы элементов ИСКЛ. ИЛИ

1з-1ы соединены соответственно с выходами элементов 121 12и-2 2И-ИЛИ, первые входы которых соединены с соответствующими выходами переносов блока 2 СУП1, вторые входы подключены к выходу элемента 8 ИЛИ, третьи — к соответствующим выходам переносов блока 3 СУП2. Второй вход элемента 12п -12И-ИЛИ г1одключен к выходу переноса старшего разряда Пм блока 3

СУП2, третий и четвертый входы подключены ко входам (N+1)-х разрядов слагаемых.

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

Для приведения результата двоичного сложения по модулю числа Ферма F<=2 +1, N где N=2 — число разрядов двоичного сумматора необходимо вычитать выходной перенос, что существенно осложнило бы аппаратуру. При перекодировании представление чисел в кольце по модулю числа

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

Ферма(см. таблицу!, В устройстве прототипе каждый сумматор содержит N полусумматоров, состоящих

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

15 Р;=Ai i (ИСКЛ, ИЛИ) — и генерации переноса. где Ai u Bi — разряды слагаемых; блок ускоренного переноса (СУП) со входами Rc, Gi каждого разряда и вход переноса

Пс, а также выходами переносов П (i--1,N) подключенными к соответствующим входам

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

ИСКЛ.ИЛИ полусумматоров одноименного разряда.

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

Iii+1=Pi fli+Gi (i-0, N — 1), которая определяет внутреннюю архитектуру СУП.

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

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

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

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

45 С помощью управляющего сигнала образующегося на выходе элемента 8 ИЛИ, 50 устанавливается, какие переносы необходимо прибавлять к полусуммам в элементах

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

55 Коммутация переносов на входе элементов ИСКЛ.ИЛИ 11+1и обеспечивается посредством мультиплексных элементов

121+12м-1 2И вЂ” ИЛИ, инвертора 9, элемента

11 И, элемента 10 ИЛИ.

1795451

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

CN=P Пи+Ам ПМ

Перенос П1 во второй разряд блока 2

СУП 1 снимается непосредственно с элемента 6 И, поскольку: о Аз 6<> Aо Во 6о 10

Перенос П1 во второй разряд блока 3

СУП2 формируется на выходе элемента 7

ИЛИ:

П1=П R,„+G =R +G =A + В

С R +Р, 30 где

Р=А4+В4+ЙЗВ2В1 GO+R2RÇG1+RÇG2+GÇ

С>=R1@(A„+ Во +А„В х х (Aa+Ba+R3 R2G1+P3G2 G3)) 35

Ca=Re)+B)+Gi А +В +A В»+

+G1(А4+Вa+В362+63)) Сз=Вз Аг Вг+Аг Вг G>+Gt+Gz г 40 х (А„+В + A.,  (Aa+Ba+63))) С4=А4+ В4 Рз Р2 Р1РО+А4В 4, По сравнению с серийными четырехраз- 45 рядными сумматорами со схемами ускоренного переноса, например, ТТЛ вЂ” серий 155, 555 и т.п, типа ИМЗ, ИМ6 данная схема имеет одинаковый с ними порядок архитектурной сложности и быстродействия. 50

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

Сумматор по модулю 1-числа Ферма

F)=2 +1. где N=2, содержащий N элементов 55

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

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

В примере конкретного выполнения предложенного устройства на фиг. 3 приведена принципиальная схема сумматора по модулю второго числа Ферма F2=17 для пятиразрядного кодирования с уменьшением 25 на единицу, Разряды Cc ...С4 результата формируются согласно уравнениям; являются входами соответствующих N разрядов слагаемых сумматора, выход суммы

i-го полусумматора (i=1, N) соединен с первым входом i-го элемента ИСКЛЮЧАЮЩЕЕ

ИЛИ, выход которого является выходом i-го разряда сумматора, выходы суммы полусумматоров с второго по N-й соединены соответственно с входами с второго по N-й разрешения распространения переноса первого блока ускоренного переноса, входы с второго по N-й генерации переноса которого соединены соответственно с выходами переноса полусумматоров с второго по N-й, отличающийся тем. что, с целью повышения быстродействия, в него введены (N-1) элементов 2И вЂ” ИЛИ, второй и третий элементы ИЛИ, элемент НЕ и второй блок ускоренного переноса, причем (К+1)-й выход переноса первого блока ускоренного переноса соединен с первым входом первого элемента ИЛИ, второй и третий входы которого соединены соответственно с входами (И+1)-го разряда слагаемых сумматора, а выход первого элемента ИЛИ соединен с входом элемента НЕ и с первыми входами элементов 2И вЂ” ИЛИ с первого по (N — 2)-й, вторые входы которых соединены соответственно с выходами переноса с третьего по

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

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

2И вЂ” ИЛИ с первого по (N — 2)-й и с первым входом (N — 1)-го элемента 2И-ИЛИ, второй вход которого соединен с (N+1)-м выходом переноса второго блока ускоренного перекоса, выходы переноса с третьего по N-й которого соединены соответственно с четвертыми входами элементов 2И-ИЛИ с первого no (N — 2)-й, выходы которых соединены соответственно с вторыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ с третьего по

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

1795451

Gr,n«a- ускоренного переноса, входы с второ-о по N-й генерации переноса которого соединены соответственно с входами с второго по Ч-й генерации переноса второго блока ускоренного переноса, входы (И+1)-ro разряда слагаемых сумматора соединены соответственно с третьим и четвертым входами (М вЂ” 1)-го элемента 2И-ИЛИ, выход которого является выходом (M+1)-го разряда суммато5 ра, 1795451

1795451 в, Составитель А.Горшков

Техред М.Моргентэл Корректор Н,Слободяник

Редактор

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

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

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

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