Многоразрядный параллельный сумматор по модулю с последовательным переносом
Владельцы патента 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, отличающееся тем, что одноразрядный параллельный сумматор по модулю состоит из двух одноразрядных параллельных сумматоров, двух логических элементов «НЕ», двух логических элементов «И» и одного логического элемента «ИЛИ», причем первый вход первого одноразрядного параллельного сумматора является входом первого числа суммирования устройства, второй вход является входом второго числа суммирования устройства, третий вход является входом переноса числа устройства, информационный выход подключен ко второму входу второго одноразрядного параллельного сумматора и ко второму входу первого логического элемента «И», а выход переноса является выходом переноса числа устройства, код модуля подается на вход первого логического элемента «НЕ», выход которого подключен к первому входу второго одноразрядного параллельного сумматора, третий вход которого соединен со входом переноса модуля устройства, информационный выход подключен ко второму входу второго логического элемента «И», а выход переноса является выходом переноса модуля устройства, управляющий вход устройства подключен к первому входу второго логического элемента «И» и ко входу второго логического элемента «НЕ», выход которого подключен к первому входу первого логического элемента «И», выходы первого и второго логических элементов «И» подключены ко входам логического элемента «ИЛИ», выход которого является информационным выходом устройства.
