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

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

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

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

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

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

Наиболее близким по технической сущности к заявляемому изобретению является многоразрядный параллельный сумматор по модулю с последовательным переносом, содержащий n+1 параллельных сумматоров по модулю с соответствующими связями, осуществляющий суммирование чисел A и B по модулю M (Многоразрядный параллельный сумматор по модулю с последовательным переносом // Патент России №2439661. 10.08.2011. Бюл. №22. / Копытов В.В., Петренко В.И., Сидорчук А.В.).

Недостатком данного сумматора являются ограниченные функциональные возможности, а именно некорректное вычисление суммы по модулю во всех случаях, кроме (A+B)>M, при значении M=F, так как при (A+B)≤M сумматор перейдет в режим вычисления (A+B-M), что не соответствует требуемому результату.

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

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

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

Пусть и где n-разрядность устройства, соответственно первый и второй операнды суммирования, пусть модуль, по которому проводится суммирование, - сумма операндов A и B по модулю M.

В результате выполнения операции необходимо получить сумму

При сложении двух чисел, представленных в виде двоичных кодов A(a₀, …, a_n-1) и B(b₀, …, b_n-1) образуется сумма С(с₀, …, c_n), равная Способ суммирования двух чисел A и B по модулю M заключается в том, что вначале находят решение разности С(с₀, …, c_n) - M(m₀, …, m_n-1). Если полученное значение больше или равно нулю, то оно и является искомой суммой S(s₀, …, s_n-1). Если же полученное значение меньше нуля, то осуществляется повторное суммирование чисел A и B и искомой суммой S является сумма этих чисел S(s₀, …, s_n-1)=A(a₀, …, a_n-1)+B(b₀, …, b_n-1). В качестве индикатора превышения нуля используется старший разряд переноса сумматора.

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

Многоразрядный параллельный сумматор по модулю с последовательным переносом содержит n одноразрядных параллельных сумматоров 1 по модулю, где n-разрядность устройства, элемент задержки 2, элемент «2И» 3, элемент «НЕ» 4, RS-триггер 5, элемент «2ИЛИ» 6, входы 7 и 8 второго и первого чисел суммирования соответственно, вход 9 модуля устройства, информационные выходы 10 устройства, вход 11 переноса числа устройства, вход 12 установки в начальное состояние. На вход 8 устройства подается код операнда А, на вход 7 устройства подается код операнда B. На вход 9 устройства подается код модуля M. На вход 11 устройства подается логический ноль, вход переноса модуля PM_i первого одноразрядного параллельного сумматора по модулю соединен с управляющими входами W устройства и входом элемента задержки 2, на вход 12 установки в начальное состояние подается исходный сигнал. Выход P_o переноса числа j-го одноразрядного параллельного сумматора 1 по модулю соединен с входом P_i переноса числа (j+1)-го одноразрядного параллельного сумматора 1 по модулю, выход PM_o переноса модуля j-го одноразрядного параллельного сумматора 1 по модулю соединен с входом PM_i переноса модуля (j+1)-го одноразрядного параллельного сумматора 1 по модулю, где j=1, …, n-1. Выход PM_o переноса модуля n-го одноразрядного параллельного сумматора 1 по модулю соединен со вторым входом элемента «2ИЛИ» 6, выход P_o переноса числа n-го одноразрядного параллельного сумматора 1 по модулю соединен с первым входом элемента «2ИЛИ» 6. Выход элемента «2ИЛИ» 6 соединен с входом элемента «НЕ» 4, выход которого подключен к первому входу элемента «2И» 3, выход которого подключен к R-входу RS-триггера 5, S-вход RS-триггера 5 является входом установки устройства в начальное состояние 12, выход RS-триггера 5 соединен с управляющими входами W всех n одноразрядных параллельных сумматоров 1 по модулю, со входом PM_i переноса модуля первого одноразрядного параллельного сумматора по модулю и входом элемента задержки 2, выход которого подключен ко второму входу элемента «2И» 3. Выходы S одноразрядных параллельных сумматоров 1 по модулю соединены с информационными выходами 10 устройства.

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

Одноразрядный параллельный сумматор 1 по модулю содержит управляющий вход W, вход модуля M устройства, входы A и B первого и второго чисел суммирования соответственно, входы P_i и PM_i, которые являются входами переноса числа и модуля устройства соответственно, выходы P_o и PM_o, являющиеся выходами переноса числа и модуля устройства соответственно, выход S, являющийся информационным выходом устройства, два одноразрядных параллельных сумматора 13, элемент «НЕ» 14 и элемент «2И» 15, причем первый вход первого одноразрядного параллельного сумматора 13 соединен с первым информационным входом одноразрядного параллельного сумматора 1 по модулю, второй вход соединен со вторым информационным входом одноразрядного параллельного сумматора 1 по модулю, вход переноса соединен с соединен с входом переноса числа первого одноразрядного параллельного сумматора 1 по модулю, выход переноса соединен с выходом переноса числа одноразрядного параллельного сумматора 1 по модулю, выход суммы соединен со вторым входом второго одноразрядного параллельного сумматора 13, вход переноса которого соединен со входом переноса модуля одноразрядного параллельного сумматора 1 по модулю, выход переноса соединен с выходом переноса модуля одноразрядного параллельного сумматора 1 по модулю, выход суммы соединен с информационным выходом одноразрядного параллельного сумматора 1 по модулю, вход элемента «НЕ» 14 соединен с третьим информационным входом одноразрядного параллельного сумматора 1 по модулю, а первый вход элемента «2И» 15 соединен с управляющим входом одноразрядного параллельного сумматора 1 по модулю, причем выход элемента «НЕ» 14 соединен со вторым входом элемента «2И» 15, выход которого соединен с первым входом второго одноразрядного параллельного сумматора 13, выход которого подключен к информационному выходу 10 одноразрядного параллельного сумматора 1 по модулю.

Многоразрядный параллельный сумматор 1 по модулю с последовательным переносом работает следующим образом. Перед началом работы устройство устанавливается в начальное состояние подачей на вход 12 управляющего сигнала. Дальше на информационные входы 8, 7 и 9 устройства подаются в двоичном виде коды операндов суммирования A(a₀, …, a_n-1) и B (b₀, …, b_n-1) и код модуля M (m₀, …, m_n-1) соответственно. Последовательно для каждого разряда каждым одноразрядным параллельным сумматором по модулю 1 в соответствии с табл.1 формируется сигнал суммы S и сигналы переноса числа P_o и переноса модуля PM_o. Если на выходе элемента «2ИЛИ» 6 образуется единица, то из суммы (А+В) вычитается значение модуля M. В том случае, когда сигнал на выходе элемента «2ИЛИ» 6 равен нулю оба операнда A(a₀, …, a_n-1) и B (b₀, …, b_n-1) суммируются обычным способом. При этом последовательно поразрядно на информационных выходах устройства 10 формируется результат суммирования двух чисел A(a₀, …, a_n-1) и B (b₀, …, b_n-1) по модулю M (m₀, …, m_n-1).

Рассмотрим работу устройства на примере, когда (см. фиг. 1).

В исходном состоянии RS-триггер 5 находится в нулевом состоянии, на все входы устройства воздействуют логические нули.

Пусть A=6₁₀=0110₂, B=4₁₀=0100₂, M=9₁₀=1001₂. Устройство для данного примера будет содержать четыре одноразрядных параллельных сумматора по модулю.

На входы A, B и M четырех сумматоров подаются коды чисел A=0110₂, B=0100₂, M=1001₂. На вход P_i переноса числа устройства подается сигнал логического 0, на вход 12 установки в начальное состояние, который соединен с S-входом RS-триггера 5, подается единица, которая переводит RS-триггер 5 в единичное состояние. Сигнал с выхода RS-триггера 5 поступает на управляющие входы W устройства. На выходе первого одноразрядного параллельного сумматора 1 по модулю получаем следующие значения P_o=0, PM_o=0. На выходе второго одноразрядного параллельного сумматора 1 по модулю получаем значения P_o=0, PM_o=1. На выходе третьего одноразрядного параллельного сумматора 1 по модулю получаем значения P_o=1, PM_o=1. На выходе четвертого одноразрядного параллельного сумматора 1 по модулю получаем значения P_o=0, PM_o=1, которые поступают на логический элемент «2ИЛИ» 6 и далее на вход элемента «НЕ» 4, где полученное значение инвертируется. После этого сигнал поступает на первый вход элемента «2И» 3, запрещая прохождение сигнала через его первый вход. Состояние RS-триггера 5 при этом не изменяется. Суммирование чисел A и B по модулю M считается законченным. В результате на информационном выходе первого одноразрядного параллельного сумматора в соответствии с таблицей 1 получаем S=1 (57 строка), на информационном выходе второго одноразрядного параллельного сумматора в соответствии с таблицей 1 получаем S=0 (35 строка), на информационном выходе третьего одноразрядного параллельного сумматора в соответствии с таблицей 1 получаем S=0 (52 строка), на информационном выходе четвертого одноразрядного параллельного сумматора в соответствии с таблицей 1 получаем S=0 (61 строка). На выходе устройства появляется число 0001₂=1₁₀.

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

Рассмотрим работу устройства на примере, когда (см. фиг. 1).

В исходном состоянии RS-триггер 5 находится в нулевом состоянии, на все входы устройства воздействуют логические нули.

Пусть A=3₁₀=0011₂, B=4₁₀=0100₂, M=9₁₀=1001₂. Воспользуемся таблицей истинности полного одноразрядного сумматора 1 по модулю (табл.1). Устройство для данного примера будет содержать четыре одноразрядных параллельных сумматора по модулю.

На входы четырех сумматоров подаются коды чисел A=0011₂, B=0100₂, M=1001₂. На вход P_i переноса числа устройства подается сигнал логического 0, на вход 12 установки в начальное состояние, который соединен с S-входом RS-триггера 5, подается единица, которая переводит RS-триггер 5 в единичное состояние. Сигнал с выхода RS-триггера 5 поступает на управляющие входы W устройства. На выходе первого одноразрядного параллельного сумматора 1 по модулю получаем следующие значения P_o=0, PM_o=1. На выходе второго одноразрядного параллельного сумматора 1 по модулю получаем значения P_o=0, PM_o=1. На выходе третьего одноразрядного параллельного сумматора 1 по модулю получаем значения P_o=0, PM_o=1. На выходе четвертого одноразрядного параллельного сумматора 1 по модулю получаем значения P_o=0, PM_o=0, которые поступают на логический элемент «2ИЛИ» 6 на выходе которого остается логический ноль, а на выходе логического элемента «НЕ» 4 остается логическая единица, которая воздействует на первый вход элемента «2И» 3, на его второй вход которого через элемент задержки 2 поступает задержанный на время суммирования устройством сигнал с выхода RS-триггера 5. Сигнал логической единицы с выхода элемента «2И» 3 поступает на R-вход RS-триггера 5, переводя его в нулевое состояние. После чего сигнал с выхода RS-триггера 5 перестает подаваться на управляющие входы W устройства и начинается второй круг суммирования. В результате на информационном выходе первого одноразрядного параллельного сумматора получаем S=1, на информационном выходе второго одноразрядного параллельного сумматора получаем S=1, на информационном выходе третьего одноразрядного параллельного сумматора получаем S=1, на информационном выходе четвертого одноразрядного параллельного сумматора получаем S=0. На выходе устройства появляется число 0111₂=7₁₀.

Проверим: 3+4=7, 7≡7 mod 9.

Одноразрядный параллельный сумматор 1 по модулю работает следующим образом (см. фиг.2). На вход A подается разряд первого операнда суммирования A, на вход B - второго операнда суммирования B. Вход P_i служит входом переноса числа P_i, вход PM_i - входом переноса модуля PM_i. На вход M подается разряд модуля M. Вход W является управляющим входом W. Выход P_o является выходом переноса числа P_o, выход PM_o - выходом переноса модуля PM_o. Выход S является информационным выходом S устройства. Устройство работает в соответствии с таблицей истинности (Табл. 1), исходя из которой следует, что в случае, когда на вход W поступает логический ноль, то сумма будет равна S=A+B, если поступит логическая единица, то получим сумму S=(A+B)-M.

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

Таблица 1. Таблица истинности полного одноразрядного сумматора по модулю.