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

 

, СОЮЗ СО8ЕТСКИХ

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

РЕСПУБЛИК (я)з G 06 F 7/72

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ. (21) 4730453/24 (22) 18.08,89 (46) 30.05.92. Бюл. М 20 (72) Ю.И.Захаров и И.В,Оноков (53) 681.325(088.8) (56) Авторское свидетельство СССР

М 1251074, кл. G 06 F 7/72, 1984. !

ЕЕЕ Trans. Acoust. Speech Signal

Pracess ASSP-24. 1976, р. 216 — 225. (54) СУММАТОР ПО МОДУЛЮ ЧИСЕЛ ФЕРМА

„„ЯЦ„„1737446 А1 (57) Изобретение относится к вычислительной технике и может быть использовано в устройствах цифровой обработки сигналов, специализированных вычислителях. Целью изобретения является повышение надежности. Сумматор по модулю чисел Ферма содержит двоичный сумматор 1, элемент И 2, блок 3 задания режима, первый 4 и второй 7 элементы ИЛИ-НЕ, элемент ИЛИ5итриггер

8 с соответствующими связями. которые обеспечивают устранение процесса генерации при равенстве результата нулю(или модула) при ненулевых значениях слагаемых.

2 ил., 1 табл.

1737446

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

На фиг. 1 представлена схема сумматора по модулю чисел Ферма; на фиг. 2- схема блока задания режима.

Сумматор содержит двоичный сумматор 1, элемент И 2, блок 3 задания режима, первый элемент ИЛИ-НЕ №, элемент ИЛИ 5, регистр 6, второй элемент ИЛИ-НЕ 7 и триггер 8.

Блок 3 задания режима состоит из первого 9 и второго 10 элементов НЕ, а также первого 11 и второго 12 элементов И, причем первый вход блока 3 задания режима соединен с первым входом второго элемента И 12 и через первый элемент НЕ 9 с первым вхрдом первого элемента И 11, второй вход блока 3 задания режима. соединен через второй элемент НЕ 10 с вторыми входами элементов И 11 и 12, выходы разрядов выхода блока 3 задания режима соединены с выходами элементов И 11 и 12, входом нулевого потенциала сумматора, выходом второго элемента HE 10 и выходом второго элемента И 12.

В соответствии с правилами выполнения арифметических операций в кольце чи сел по модулю чисел Ферма суммирование двух операндов производится по следующему алгоритму: если старший разряд одного из слагаемых равен единице, то сумме присваивается значение другого слагаемого; если старшие разряды обоих слагаемых равны единице, то сумме присваивается значение нуль и в старший разряд(п) записывается единица; в противном случае сум-, мируются (n - 1) значащих разрядов, дополняется значение переноса и суммиру, ется со значащими разрядами суммы, при этом старший разряд является переносом из последнего значащего разряда.

При выполнении суммирования по этому алгоритму может возникнуть ситуация, когда результат суммирования равен нулю (или модулю) при ненулевих значениях сла гаемых. В этом случае сумматор переходит в режим генерации, период которой определяется временем задержки сигнала на элементах внутри микросхем, Этот процесс можно пояснить примером сложения двух чисел в кольце по модулю четвертого числа

Ферме Р№ 2+ 1:

0 1101 01 00 11 01 00 10 000101011 00 1011 01

1 0 00

0 ОООО 00 00 00 0000 00

5,, .. ° .., ... и т.д.

Поскольку на последнем этапе суммирования в и-м разряде результата появляется единица, она в инвертированном виде поступает на вход переноса двоичного сум10 матора и цикл операции суммирования повторяется, т.е. сумматор переходит в режим генерации.

Двоичный сумматор 1 обеспечивает суммирование двух (n - 1) разрядных one- .

15; Он выполнен по типовой схеме сумматора с ускоренным переносом.

Блок 3 задания режима формирует управляющие сигналы для двоичного сумматора 1 согласно таблице.

20 Триггер 8 выставляет на выходе едини. цу по положительному фронту импульса, формируемого по наличию всех выходных переносов двоичного сумматора 1.

Двоичный сумматор 1 может быть реа25 лизован на микросхемах К555ИПЗ и

К555ИП4; т.е. имеет инверсные входы и выходы переноса, Сумматор работает следующим образом.

30 Когда старшие разряды обоих слагаемых равны единице, на выходе элемента И

2 формируется единица, поступающая на вход элемента ИЛИ 5. На выходе элемента

ИЛИ 5 также появляется единица, которая

35 фиксируется в регистре 6 по положительному перепаду тактового импульса, что в сооТветствии с алгоритмом суммирования является достаточным признаком нулевого результата суммирования. Когда старший

40 разряд одного из слагаемых не равен единице, выход элемента И 2 находится в нулевом состоянии, выход элемента ИЛИ-НЕ 4также в нулевом состоянии, на входе элемента ИЛИ-НЕ 7присутствуетлибоустойчи45 вое состояние единицы, либо устойчивое состояние нуля в зависимости от значений выходных переносов сумматора 1. И в той, и в другой ситуации после перевода триггера 8 в исходное состояние на его тактовом

50 входе нет перепада из одного состояния в другов, а значит,на выходе триггера 8 сохраняется значение нуля, это приводит к появлению на выходе элемента ИЛИ S значения нуля, которое фиксируется в регистре 6 в

55 .момент прихода тактового импульса.

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

1737446 переносы присутствуют, что соответствует получению нулевого результата, Как видно из приведенного числового примера, на первом этапе все младшие (n -1) разрядов результата суммирования принимают значение "1". При . этом выходы переносов равны единице(переносы отсутствуют), Старший разряд переноса, равный единице, инвертируется элементом ИЛИ-НЕ 4 и поступает на вход йереноса сумматора 1. Это приводит к тому; что все младшие (и - 1) разрядов суммы принимают значение "0" и появляются все тетрадные переносы (становятся.равными нулю).

Старший разряд переноса инвертируется на элементе ИЛИ-НЕ 4 и поступает на вход переноса сумматора 1. При этом сумматор 1 переходит в состояние, аналогичное исходному.

Таким образом, возникает ситуация, приводящая к возбуждению схемы. Однако равенство нулю всех тетрадных переносов сумматора 1 приводит к переключению из нуля в единицу выхода элемента ИЛИ-НЕ 7. По фронту этого импульса переключения триггер

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

Возникающие в процессе генерации новые перепады уровня на выходе.элемента

ИЛИ-НЕ 7 не вызывают изменения состояния триггера 8. В исходное состояние он переводится лишь при переходе íà его вход обнуления импульса начальной установки.

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

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

Сумматор по модулю чисел Ферма, содержащий двоичный сумматор, элемент И, блок задания режима, первый элемент

ИЛИ-HE и элемент ИЛИ, причем входы разрядов, кроме старших, входов первого и второго слагаемых сумматора соединены с

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

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

15 входами элемента И, первого элемента

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

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

1737446

Составитель А. Клюев

Редактор Л, Пчолинская Техред М.Моргентал

Корректор С. Черни

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

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

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

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