Многоразрядный параллельный сумматор по модулю с последовательным переносом



Многоразрядный параллельный сумматор по модулю с последовательным переносом
Многоразрядный параллельный сумматор по модулю с последовательным переносом

 


Владельцы патента RU 2439661:

Государственное образовательное учреждение высшего профессионального образования "Ставропольский государственный университет" (RU)

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах цифровой обработки сигналов и в криптографических приложениях. Техническим результатом является расширение функциональных возможностей устройства за счет введения операции суммирования по модулю. Устройство содержит n+1 одноразрядных параллельных сумматоров по модулю, где n - количество разрядов чисел суммирования, при этом каждый одноразрядный сумматор по модулю состоит из двух одноразрядных сумматоров, двух логических элементов И, логического элемента ИЛИ, двух логических элементов НЕ. 1 з.п. ф-лы, 2 ил., 1 табл.

 

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

Известен последовательный многоразрядный сумматор, который содержит n-разрядные сдвиговые регистры операндов X и Y, регистр результата S, одноразрядный сумматор SM и двухступенчатый D-триггер для запоминания переноса. (Бабич Н.П., Жуков И.А. Основы цифровой схемотехники: Учебное пособие. - М.: Издательский дом «Додэка-XXI», Киев.: «МК-Пресс», 2007. - рисунок 4,45 с.176).

Недостатком данного сумматора являются ограниченные функциональные возможности, а именно невозможность суммирования по модулю.

Наиболее близким по технической сущности к заявляемому изобретению является многоразрядный параллельный сумматор с последовательным переносом, содержащий n одноразрядных параллельных сумматоров с соответствующими связями (см. Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. - М.: Радио и связь, 1990. Рисунок 3.45, с.133).

Недостатком данного сумматора являются ограниченные- функциональные возможности, а именно невозможность суммирования по модулю.

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

Для достижения поставленной цели в многоразрядный параллельный сумматор по модулю с последовательным переносом, состоящий из n одноразрядных параллельных сумматоров, где n - максимальный разряд чисел суммирования, причем на первые входы сумматоров подается двоичный код первого числа суммирования, на вторые входы сумматоров подается двоичный код второго числа суммирования, на вход переноса числа первого сумматора подается логический ноль, выход переноса числа i-го сумматора подключен ко входу переноса числа (i+1)-го сумматора, где i=1, … n-1 - номер сумматора, информационные выходы n сумматоров являются информационными выходами устройства, введен (n+1)-й одноразрядный параллельный сумматор по модулю, а первые n одноразрядных параллельных сумматоров выполнены в виде одноразрядных параллельных сумматоров по модулю, входы модуля всех одноразрядных параллельных сумматоров по модулю являются входами модуля устройства, управляющие входы которых подключены к выходу переноса модуля n+1-го одноразрядного параллельного сумматора, на вход первого и второго чисел суммирования (n+1)-го одноразрядного параллельного сумматора по модулю подаются логические нули, выход переноса числа n-го одноразрядного параллельного сумматора по модулю подключен ко входу переноса числа (n+1)-го одноразрядного параллельного сумматора по модулю, на вход переноса модуля первого одноразрядного параллельного сумматора по модулю подается логическая единица, выход переноса модуля i-го одноразрядного параллельного сумматора по модулю подключен ко входу переноса модуля (i+1)-го одноразрядного параллельного сумматора по модулю, где i=1, … n, информационный выход n+1 сумматора является информационным выходом устройства. При этом одноразрядный параллельный сумматор по модулю состоит из двух одноразрядных параллельных сумматоров, двух логических элементов НЕ, двух логических элементов И и одного логического элемента ИЛИ, причем первый вход первого одноразрядного параллельного сумматора является входом первого числа суммирования устройства, второй вход является входом второго числа суммирования устройства, третий вход является входом переноса числа устройства, информационный выход подключен ко второму входу второго одноразрядного параллельного сумматора и ко второму входу первого логического элемента И, а выход переноса является выходом переноса числа устройства, код модуля подается на вход первого логического элемента НЕ, выход которого подключен к первому входу второго одноразрядного параллельного сумматора, третий вход которого соединен со входом переноса модуля устройства, информационный выход подключен ко второму входу второго логического элемента И, а выход переноса является выходом переноса модуля устройства, управляющий вход устройства подключен к первому входу второго логического элемента И и ко входу второго логического элемента НЕ, выход которого подключен к первому входу первого логического элемента И, выходы первого и второго логических элементов И подключены ко входам логического элемента ИЛИ, выход которого является информационным выходом устройства. Одноразрядный параллельный сумматор по модулю состоит из двух одноразрядных параллельных сумматоров, двух логических элементов НЕ, двух логических элементов И и одного логического элемента ИЛИ, причем первый вход первого одноразрядного параллельного сумматора является входом первого числа суммирования устройства, второй вход является входом второго числа суммирования устройства, третий вход является входом переноса числа устройства, информационный выход подключен ко второму входу второго одноразрядного параллельного сумматора и ко второму входу первого логического элемента И, а выход переноса является выходом переноса числа устройства, код модуля подается на вход первого логического элемента НЕ, выход которого подключен к первому входу второго одноразрядного параллельного сумматора, третий вход которого соединен со входом переноса модуля устройства, информационный выход подключен ко второму входу второго логического элемента И, а выход переноса является выходом переноса модуля устройства, управляющий вход устройства подключен к первому входу второго логического элемента И и ко входу второго логического элемента НЕ, выход которого подключен к первому входу первого логического элемента И, выходы первого и второго логических элементов И подключены ко входам логического элемента ИЛИ, выход которого является информационным выходом устройства.

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

При сложении двух чисел, представленных в виде двоичных кодов А (а 1, …, a n) и В (b1, …, bn) образуется сумма С (с1, …, cn+1). Чтобы найти результат суммирования чисел А и В по модулю М (m1, … mn+1), необходимо найти решение разности С (с1, …, cn+1) - М(m1, …, mn+1). Если полученное значение отрицательно, то S(s1, …, sn+1)=С(с1, …, cn+1), если положительное, то S(s1, …, sn+l)=С(с1, …, cn+1) - М(m1, …, mn+l).

На фиг.1 представлена схема многоразрядного параллельного сумматора по модулю с последовательным переносом.

Многоразрядный параллельный сумматор по модулю с последовательным переносом содержит n+1 одноразрядных параллельных сумматоров 1 по модулю, где n количество разрядов чисел суммирования. На вход А n сумматоров 1 подается код числа А, на вход В n сумматоров 1 подается код числа В. На входы А и В n+1-ого сумматора 1 подаются логические нули. На вход М всех сумматоров 1 подается код числа М. На вход Рi первого сумматора 1 подается логический ноль, на вход РМi первого сумматора 1 - логическая единица. Выход Р0 j-го сумматора 1 соединен со входом Pi (j+1)-го сумматора 1, выход РМ0 j-го сумматора 1 соединен со входом PMi (j+1)-го сумматора 1, где j=1, …, n. Выход РМ0 (n+1)-го сумматора 1 является выходом переноса pmOut устройства, который соединен с управляющим входом W всех n+1 сумматоров 1. Выходы S всех сумматоров 1 являются информационными выходами устройства.

На фиг.2. представлена схема одноразрядного параллельного сумматора 1 по модулю.

Одноразрядный параллельный сумматор 1 по модулю состоит из двух одноразрядных параллельных сумматоров 2, двух логических элементов НЕ 5, двух логических элементов И 3 и одного логического элемента ИЛИ 4, причем первый вход первого одноразрядного параллельного сумматора 2 является входом первого числа суммирования устройства, второй вход является входом второго числа суммирования устройства, третий вход является входом переноса числа устройства, информационный выход подключен ко второму входу второго одноразрядного параллельного сумматора 2 и ко второму входу первого логического элемента И 3, а выход переноса является выходом переноса числа устройства, код модуля подается на вход первого логического элемента НЕ 5, выход которого подключен к первому входу второго одноразрядного параллельного сумматора 2, третий вход которого соединен со входом переноса модуля устройства, информационный выход подключен ко второму входу второго логического элемента И 3, а выход переноса является выходом переноса модуля устройства, управляющий вход устройства подключен к первому входу второго логического элемента И 3 и ко входу второго логического элемента НЕ 5, выход которого подключен к первому входу первого логического элемента И 3, выходы первого и второго логических элементов И 3 подключены ко входам логического элемента ИЛИ 4, выход которого является информационным выходом устройства.

Многоразрядный параллельный сумматор по модулю с последовательным переносом работает следующим образом. На информационные входы сумматоров 1 подаются в двоичном виде коды чисел суммирования А(а1, …, an) и В(b1, …, bn) и код модуля М(m1, …, mn+1). Последовательно для каждого разряда каждым одноразрядным параллельным сумматором по модулю 1 формируется перенос числа и перенос модуля. Если сигнал на выходе переноса модуля (n+1)-го одноразрядного параллельного сумматора 1 по модулю равен единице, то из суммы (А+В) вычитается значение модуля, в противном случае два числа А(а1, …, an) и В(b1, …, bn) суммируются обычным способом. При этом последовательно поразрядно формируется результат суммирования двух чисел А(а1, …, an) и В(b1, …, bn) по модулю М(m1, …, mn+1).

Рассмотрим работу сумматора на примере.

Пусть А=610=1102, В=410=1102, M=910=10012. Воспользовавшись таблицей истинности полного одноразрядного сумматора 1 по модулю (табл.1), найдем промежуточные и конечный результаты суммирования по модулю. Устройство для данного примера будет содержать четыре одноразрядных параллельных сумматора по модулю.

На входы четырех сумматоров подаются коды чисел А=1102, В=1102, М=10012. На выходе первого сумматора Р0=0, РМ0=0. На выходе второго сумматора Р0=0, РМ0=1. На выходе третьего сумматора Р0=1, РМ0=1. На выходе четвертого сумматора РМ0=1 эта единица поступает на все входы W всех четырех сумматоров. В результате на выходе первого сумматора S=1, на выходе второго сумматора S=0, на выходе третьего сумматора S=0, на выходе четвертого сумматора S=0, на выходе устройства появляется число 00012=110.

Проверим: 6+4=10, 10≡1 mod 9.

Одноразрядный параллельный сумматор 1 по модулю работает следующим образом. На вход А подается разряд первого числа суммирования А, на вход В - второго числа суммирования В. Вход Pi служит входом переноса числа Pi, вход PMi - входом переноса модуля PMi. На вход М подается разряд модуля М. Вход W является управляющим входом W. Выход P0 является выходом переноса P0, выход PM0 - выходом переноса модуля PM0. Выход S является информационным выходом. Устройство работает в соответствии с таблицей истинности (Табл.1). Если на вход W поступает логический ноль, то в результате S=A+B, если логическая единица, то S=(A+B)-M.

Таблица 1.
Таблица истинности полного одноразрядного сумматора по модулю.
А B Pi PO M PMi W PM0 S
0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 1 1
1 0 0 0 0 0 0 1 1
1 1 0 1 0 0 0 0 0
0 0 1 0 0 0 0 1 1
0 1 1 1 0 0 0 0 0
1 0 1 1 0 0 0 0 0
1 1 1 1 0 0 0 1 1
0 0 0 0 1 0 0 0 0
0 1 0 0 1 0 0 0 1
1 0 0 0 1 0 0 0 1
1 1 0 1 1 0 0 0 0
0 0 1 0 1 0 0 0 1
0 1 1 1 1 0 0 0 0
1 0 1 1 1 0 0 0 0
1 1 1 1 1 0 0 0 1
0 0 0 0 0 1 0 1 0
0 1 0 0 0 1 0 1 1
1 0 0 0 0 1 0 1 1
1 1 0 1 0 1 0 1 0
0 0 1 0 0 1 0 1 1
0 1 1 1 0 1 0 1 0
1 0 1 1 0 1 0 1 0
1 1 1 1 0 1 0 1 1
0 0 0 0 1 1 0 0 0
0 1 0 0 1 1 0 1 1
1 0 0 0 1 1 0 1 1
1 1 0 1 1 1 0 0 0
0 0 1 0 1 1 0 1 1
0 1 1 1 1 1 0 0 0
1 0 1 1 1 1 0 0 0
1 1 1 1 1 1 0 1 1
0 0 0 0 0 0 1 0 1
0 1 0 0 0 0 1 " Г 0
1 0 0 0 0 0 1 1 0
1 1 0 1 0 0 1 0 1
0 0 1 0 0 0 1 1 0
0 1 1 1 0 0 1 0 1
1 0 1 1 0 0 1 0 1
А B Pi PO M PMi W PMO S
1 1 1 1 0 0 1 1 0
0 0 0 0 1 0 1 0 0
0 1 0 0 1 0 1 0 1
1 0 0 0 1 0 1 0 1
1 1 0 1 1 0 1 0 0
0 0 1 0 1 0 1 0 1
0 1 1 1 1 0 1 0 0
1 0 1 1 1 0 1 0 0
1 1 1 1 1 0 1 0 1
0 0 0 0 0 1 1 1 0
0 1 0 0 0 1 1 1 1
1 0 0 0 0 1 1 1 1
1 1 0 1 0 1 1 1 0
0 0 1 0 0 1 1 1 1
0 1 1 1 0 1 1 1 0
1 0 1 1 0 1 1 1 0
1 1 1 1 0 1 1 1 1
0 0 0 0 1 1 1 0 1
0 1 0 0 1 1 1 1 0
1 0 0 0 1 1 1 1 0
1 1 0 1 1 1 1 0 1
0 0 1 0 1 1 1 1 0
0 1 1 1 1 1 1 0 1
1 0 1 1 1 1 1 0 1
1 1 1 1 1 1 1 1 0

1. Многоразрядный параллельный сумматор по модулю с последовательным переносом, состоящий из n одноразрядных параллельных сумматоров, где n - максимальный разряд чисел суммирования, причем на первые входы сумматоров подается двоичный код первого числа суммирования, на вторые входы сумматоров подается двоичный код второго числа суммирования, на вход переноса числа первого сумматора подается логический ноль, выход переноса числа i-го сумматора подключен ко входу переноса числа (i+1)-го сумматора, где i=1, … n-1 номер сумматора, информационные выходы n сумматоров являются информационными выходами устройства, отличающийся тем, что в него введен (n+1)-ый одноразрядный параллельный сумматор по модулю, а первые n одноразрядных параллельных сумматоров выполнены в виде одноразрядных параллельных сумматоров по модулю, входы модуля всех одноразрядных параллельных сумматоров по модулю являются входами модуля устройства, управляющие входы которых подключены к выходу переноса модуля n+1-го одноразрядного параллельного сумматора, на вход первого и второго чисел суммирования (n+1)-го одноразрядного параллельного сумматора по модулю подаются логические нули, выход переноса числа n-го одноразрядного параллельного сумматора по модулю подключен ко входу переноса числа (n+1)-го одноразрядного параллельного сумматора по модулю, на вход переноса модуля первого одноразрядного параллельного сумматора по модулю подается логическая единица, выход переноса модуля i-го одноразрядного параллельного сумматора по модулю подключен ко входу переноса модуля (i+1)-го одноразрядного параллельного сумматора по модулю, где i=1, … n, информационный выход n+1 сумматора является информационным выходом устройства.

2. Устройство по п.1, отличающееся тем, что одноразрядный параллельный сумматор по модулю состоит из двух одноразрядных параллельных сумматоров, двух логических элементов «НЕ», двух логических элементов «И» и одного логического элемента «ИЛИ», причем первый вход первого одноразрядного параллельного сумматора является входом первого числа суммирования устройства, второй вход является входом второго числа суммирования устройства, третий вход является входом переноса числа устройства, информационный выход подключен ко второму входу второго одноразрядного параллельного сумматора и ко второму входу первого логического элемента «И», а выход переноса является выходом переноса числа устройства, код модуля подается на вход первого логического элемента «НЕ», выход которого подключен к первому входу второго одноразрядного параллельного сумматора, третий вход которого соединен со входом переноса модуля устройства, информационный выход подключен ко второму входу второго логического элемента «И», а выход переноса является выходом переноса модуля устройства, управляющий вход устройства подключен к первому входу второго логического элемента «И» и ко входу второго логического элемента «НЕ», выход которого подключен к первому входу первого логического элемента «И», выходы первого и второго логических элементов «И» подключены ко входам логического элемента «ИЛИ», выход которого является информационным выходом устройства.



 

Похожие патенты:

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

Изобретение относится к области вычислительной техники и может быть использовано в вычислительных системах для преобразования двоичных кодов в коды системы остаточных классов (СОК).

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

Изобретение относится к вычислительной технике и, в частности, к модулярным нейрокомпьютерным средствам и предназначено для определения ошибок в кодовых конструкциях непозиционного кода полиномиальной системы классов вычетов (ПСКВ), представленных в расширенных полях Галуа GF(2v).

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике

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

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

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

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

Изобретение относится к вычислительной технике и может быть использовано в цифровых вычислительных устройствах, а также в устройствах цифровой обработки сигналов и в криптографических приложениях. Техническим результатом является расширение функциональных возможностей за счет введения операции суммирования по модулю. Устройство содержит n-разрядный и (n+1)-разрядный сумматоры, мультиплексор и регистр. 1 ил.

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих параллельно-конвейерных умножителей. Техническим результатом является повышение скорости вычисления. Способ содержит этапы: осуществляют параллельную запись остатка по основанию p1 множимого в элементы памяти, параллельно выполняют подсчет количества единиц bi в каждом столбце i-ой матрицы, сдвигают двоичное число b1 на один разряд вправо, суммируют с числом b2, полученную сумму b 2 s сдвигают на один разряд вправо и суммируют с числом b3. Аналогичным образом осуществляют сдвиг полученных сумм и суммирование их с последующими числами до получения суммы b 2 * m − 1 s , при этом младший разряд числа b1 является первым разрядом s1 произведения, младший разряд каждой полученной суммы b i s является i-ым разрядом произведения. Сдвигают двоичное число b 2 * m − 1 s , младший разряд полученного числа является (2*m)-м разрядом искомого произведения S2*m. В случае если s больше p1, производится коррекция полученного произведения s путем последовательного вычитания из s основания p1 до тех пор, пока s не станет меньше p1, иначе коррекция не производится, аналогично вычисляются и корректируются произведения m-разрядных остатков по остальным основаниям, одновременно суммируют порядки сомножителей, полученная сумма является порядком искомого произведения. 2 ил.

Изобретение относится к вычислительной технике и может быть использовано в вычислительных системах, функционирующих в системе остаточных классов. Техническим результатом является повышение быстродействия устройства и сокращение аппаратных затрат. Устройство содержит входные регистры, схемы определения знака, схемы сдвига полярности чисел, просмотровые таблицы (память) для хранения констант и , сумматор и логический элемент «исключающее или», схему анализа знаков чисел. 3 ил.

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