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

)5 606 Р 7/ ОСУДАРСТВЕННОЕ ПАТЕНЕДОМСТВО СССРГОСПАТЕНТ СССР) АНИЕ ИЗОБРЕТЕНИЯКОМУ СВИДЕТЕЛЬСТВУ ПИС АВ зовано для построения быстродействующих арифметических устройств, работающих в системе остаточных классов, в частности в цифровых процессорах обработки сигналов, выполняющих теоретико-числовые преобразования по модулю чисел Ферма, Целью изобретения является повышение быстродействия устройства, Сумматор по модулю 1-числа Ферма содержит К элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второйблоки ускоренного переноса, й полусумматоров, каждый из которых состоит из элементов ИСКЛЮЧАЮЩЕЕ ИЛИ, элементов И, причем в первый полусумматор введены элементы ИЛИ, элемент НЕ,ии институт рао СССР1985.В Реализация искретной сверлового преобраехника средств идения", вып, 6, УЛ.Ю 1-ЧИСЛА элемент И иненные межд к области выт быть испольНа фиг, 1 иллюстрируется метод переко- адирования операндов в кольце целых чисел спо модулю чисел Ферма с уменьшением на Оединицу(1); на фиг. 2 представлена функци- цональная схема сумматора по модулю чиселФерма; на.фиг, 3 приведен пример конкрет- +ного выполнения предложенного устройст- Сва,аеасСумматор по модулю 1 числа Ферма содержит й элементов искл. ИЛИ 11-1 и, первый блок 2 ускоренного переноса (СУП 1) ивторой блок 3 ускоренного переноса (СУП 2),К полусумматоров 41 - 4 н, каждый из которых состоит из элементов 51-5 и ИСКЛ. ИЛИ. и элементов 61 - биИ, при этом в полусумматор 41 введен элемент 7 ИЛИ, входы которого объединены со входами полусумматора41, а выход подключен ко входу переноса вовторой разряд П 1 в блоке 3 СУП 2, Выходы(72) А. С. Горшков56) Авторское свидетельствМ 1170450, кл, С 06 Р 7/49,Захаров Ю. ИТитков Бконвольвера циклической дтки на основе теоретико-чисзования "Ферма", НТС "Тсвязи", сер, "Техника телев1989, с. 58,(54) СУММАТОР ПО МОДФЕРМА(57) Изобретение относитсячислительной техники и мож Изобретение относится к вычислительной технике и может быть использовано для построения быстродействующих арифметических устройств, работающих в системе остаточных классов (СОК), в частности, в цифровых процессорах обработки сигналов (ЦОС), выполняющих теоретико-числовые преобразования по модулю чисел Ферма (ТЧ ПФ).Цель изобретения - повышение быстродействия устройства.Соответствие критерию существенные отличия подтверждается тем, что благодаря введению новых признаков в устройстве появилось новое свойство - повышение быстродействия, достигаемое за счет исключения операции последовательного дополнительного суммирования,э лементов 2 И - ИЛИ, соедиобой функционально, 3 ил. З1795451 О=А В 1 (И),20 Р=Пи+Аи+Вн,Х -+ (Х - 1)проб Г элементов 51-5 и и 61 - -бц ИСКЛ. ИЛИ и И подключены к соответствующим одинаковым входам разрешения распространения переносов В и генерации переносов Ь в блоках 2 и 3 СУП 2, при этом выходы элементов 51-5 и ИСКЛ ИЛИ подключены к первым входам элементов ИСКЛ. ИЛИ 11 - 1 и, выходы которцх являются первцми Й разрядами результата. Выход переноса старшего разряда Пи блока 2 СУП 1 подключен к первому входу элемента 8 ИЛИ, другие два входа которого присоединены ко входам (И+1)-х разрядов слагаемых, а к его выходу подключен вход инвертора 9, к вцходу которого подключенц второй вход элемента ИСКЛ, ИЛИ 11, вход элемента 11 И и четвертые входы (М) элементов 121-12 и2 И-ИЛИ. Второй вход элемента 11 И подключен к выходу элемента 7 ИЛИ, а его выход - ко входу элемента 10 ИЛИ, второй вход которого подключен к выходу элемента 61 И и. входу переноса во второй разряд П 1 блока 2 СУП 1, Выход элемента 10 ИЛИ присоединен ко второму входу элемента ИСКЛ. ИЛИ 12, Вторые входы элементов ИСКЛ. ИЛИ 1 зы соединены соответственно с выходами элементов 121-12 и2 И-ИЛИ, первце входы которых соединены с соответствующими выходами переносов блока 2 СУП 1, вторые входц подключены к выходу элемента 8 ИЛИ, третьи - к соответствующим выходам переносов блока 3 СУП 2. Второй вход элемента 12 иИ-ИЛИ подключен к выходу переноса старшего разряда Пи блока 3 СУП 2, третий и четвертый входы подключенц ко входам (И+1)-х разрядов слагаемых.Сложение двоичной информации по модулю чисел Ферма в предложенном решении выполняется следующим образом,Для приведения результата двоичного сложения по модулю числа Ферма Р=2 +1,М где И=2 - число разрядов двоичного сумматора необходимо вычитать выходной перенос, что существенно осложнило бы аппаратуру. При перекодировании представление чисел в кольце по модулю. числа Ферма с уменьшением на единицу: достигается упрощение арифметических операций, На фиг, 1 показано соответствие чисел и их двоичных кодов для этого случая (внешнее кольцо двоичных кодов "поворачивается на одно деление" против часовой стрелки). При этом при сложении по модулю числа Ферма с помощью двоичного сумматора необходимо прибавить инвертированный перенос к двоичной сумме. Число нуль имеет особое представление с (И+1)-м разрядом: Ли=1, Ъ)=Ъ=,=Ъч=0. Появление 1 в (И+1)-м разряде служит для прерывания операции. Ниже приведены четыре различных возможных.случая суммирования с при ведением результата по модулю чиселФерма(см. таблицу),В устройстве прототипе каждый сумматор содержит И полусумматоров, состоящих 10 из элементов ИСКЛ,ИЛИ и И с объединенными входами, который формируют сигналы- разрешения распространения переноса полусумматора: 15 Ру=АфЭВ (ИСКЛ. ИЛИ)- и генерации переноса. где А и В 3 - разряды слагаемых;блок ускоренного переноса (СУП) со входами Р 6 каждого разряда и вход переноса По, а также выходами переносов П (=1,й) подключенными к соответствующим входам Н элементов ИСКЛ.ИЛИ, вторые входы которых присоединенц к вцходам элементов ИСКЛ.ИЛИ полусумматоров одноименного разряда,30 В блоке СУП переносы образуются согласно рекурентной формуле;Пн 1=Р П 1+Ь (1-О, й - 1), которая определяет внутреннюю архитектуру СУП.Элементы ИСКЛ, ИЛИ обеспечивают 35 поразрядное сложение полусумм с переносами: 40 Предлагаемое устройство функционирует следующим образом:В блоке 3 СУП 2 вводится входной перенос П о=1 (при этом для блока 2 СУП 1 входной перенос П =0),45 С помощью управляющего сигнала образующегося на выходе элемента 8 ИЛИ, 50 устанавливается, какие переносы необходимо прибавлять к полусуммам в элементах ИСКЛ, ИЛИ 11+Ъ. В случае Р=1 переносы вцбираются иэ блока 2 СУП 1, при Р= 0- из блока 3 СУП 2.55 Коммутация переносов на входе элементов ИСКЛ.ИЛИ 11+1 и обеспечивается посредством мультиплексных элементов 121+12 ы 2 И - ИЛИ, инвертора 9, элемента 11 И, элемента 10 ИЛИ.К-й разряд суммы формируется на элементе 12 исогласно выражению: См=Р Пи+Аы Пм5Перенос П 1 во второй разряд блока 2 СУП 1 снимается непосредственно с элемента 6 И, поскольку: П 1-1 о Во+о - Ао Во - о10 Перенос П 1 во второй разряд блока 3СУП 2 формируется на выходе элемента 7ИЛИ:15П 1=ПВ+О =В +О, =А,+ В С В +Р,30гдеР=А 4+В 4+В 3 В 2 В 1 (30+В 2 В 361+ВЗС 2+63 С 1=В 1 еА+ В. +АВ, х х (А 4+В 4+ВЗ к 261+Р 302+63)1 35 Сг=ВЯА 1+Вг+01 А, +В, АВ+Сз=йзАгВг+АВ 61+ОгСг г 40х Ао +Во + АВ(А 4+В 4+03)1) С 4=А 4+В 4 РЗР 2 Р 1 РО+А 4 В 4,По сравнению с серийными четырехрэз рядными сумматорами со схемами ускоренного переноса, например, ТТЛ - серий 155, 555 и т,п, типа ИМЗ, ИМ 6 данная схема имеет одинаковый с ними порядок архитектурной сложности и быстродействия. 50 Формула изобретения Сумматор по модулю 1-числа Ферма Ес=2 +1. где И=2, содержащий й элементов 55йИСКЛЮЧАЮЩЕЕ ИЛИ, первый блок ускоренного переноса, М полусумматоров, элементов И и первый элемент ИЛИ, причем информационные входы полусумматоров Таким образом, блоки 2 и 3 СУП 1 и СУП 2 короче на один разряд по сравнению с блоком СУП обычного двоичного сумматора, 20В примере конкретного выполнения предложенного устройства на фиг. 3 приведена принципиальная схема сумматора по модулю второго числа Ферма Е 2=17 для пятиразрядного кодирования с уменьшением 25 на единицу, Разряды Со С 4 результата формируются согласно уравнениям; являются входами соответствующих М разрядов слагаемых сумматора, выход суммы -го полусумматора (=1, М) соединен с первым входом 1-го элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, выход которого является выходом -го разряда сумматора, выходы суммы полусумматоров с второго по К-й соединены соответственно с входами с второго по И-й разрешения распространения переноса первого блока ускоренного переноса, входы с второго по И-й генерации переноса которого соединены соответственно с выходами переноса полусумматоров с второго по й-й, о т л и ч а ю щ и й с я тем. что, с целью повышения быстродействия, в него введены (И) элементов 2 И - ИЛИ, второй и третий элементы ИЛИ, элемент НЕ и второй блок ускоренного переноса, причем (К+1)-й выход переноса первого блока ускоренного переноса соединен с первым входом первого элемента ИЛИ, второй и третий входы которого соединены соответственно с входами (И+1)-го разряда слагаемых сумматора, а выход первого элемента ИЛИ соединен с входом элемента НЕ и с первыми входами элементов 2 И - ИЛИ с первого по (М - 2)-й, вторые входы которых соединены соответственно с выходами переноса с третьего по М-й первого блока ускоренного переноса, вход переноса которого соединен с выходом переноса первого полусумматора и с первым входом второго элемента ИЛИ, вы ход которого соединен с вторым входом второго элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, первый и второй входы третьего элемента ИЛИ соединены соответственно с входами первого разряда слагаемых сумматора, выход третьего элемента ИЛИ соединен с входом переноса второго блока ускоренного переноса и с первым входом элемента И, выход которого соединен с вторым входом второго элемента ИЛИ, выход элемента НЕ соединен с вторым входом первого элемента ИСКЛЮЧАЮЩЕЕ ИЛИ, вторым входом элемента И, третьими входами элементов 2 И - ИЛИ с первого по (й - 2)-й и с первым входом (М - 1)-го элемента 2 И-ИЛИ, второй вход которого соединен с (К+1)-м выходом переноса второго блока ускоренного перекоса, выходы переноса с третьего по М-й которого соединены соответственно с четвертыми входами элементов 2 И-ИЛИ с первого по (Н - 2)-й, выходы которых соединены соответственно с вторыми входами элементов ИСКЛЮЧАЮЩЕЕ ИЛИ с третьего по М-й, входы с второго по М-й разрешения распространения переноса второго блока ускоренного переноса соединены соответственно с входами с второго по М-й разрешения распространения переноса первогоблока ускоренного переноса, входы с второго по М-й генерации переноса которого соединены соответственно с входами с второго по Ч-й генерации переноса второго блока ускоренного переноса, входы (8+1)-го разряда слагаемых сумматора соединены соответственно с третьим и четвертым входами (М - 1)-го элемента 2 И-ИЛИ, выход которого является выходом (И+1)-го разряда суммато ра,1795451 Составитель А,ГоршкТехред М.Моргентэл Реда Р Н,Слободяник о Прои к аз 431 ВНИИП сударственного комитета 113035, Москва, Ж енно-издательский ко Подписноезобретениям и открытиям при ГКНТ СССРРаушская нэб 4/5 нат "Патент", г, Ужгород, ул.Гагарина, 101