ПОЛНЫЙ ОДНОРАЗРЯДНЫЙ СУММАТОР ПО МОДУЛЮ Российский патент 2011 года по МПК G06F7/42 

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

Известен сумматор, содержащий 2 логических элемента «Исключающее ИЛИ», 3 двухвходовых логических элемента «И» и 1 трехвходовый логический элемент «И» (см. Пухальский Г.И., Новосельцева Т.Я. Проектирование дискретных устройств на интегральных микросхемах: Справочник. - М.: Радио и связь, 1990. Рисунок 3.44а, с.132).

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

Наиболее близким по технической сущности к заявляемому изобретению является одноразрядный сумматор К155ИМ1, содержащий 4 двухвходовых логических элемента «И-НЕ», 2 двухвходовых логических элемента «ИЛИ», 6 двухвходовых логических элементов «И», 1 трехвходовый логический элемент «И», 1 четырехвходовый логический элемент «ИЛИ», 1 трехвходовый логический элемент «ИЛИ», 1 логический элемент «НЕ», соединенные между собой функционально (см. Справочник по интегральным микросхемам / Б.В.Тарабрин, С.В.Якубовский, Н.А.Барканов и др. Под ред. Б.В.Тарабрина. - 2-е изд., перераб. и доп. - М: Энергия, 1981, с.144).

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

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

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

Сущность изобретения заключается в реализации следующего способа суммирования двух чисел 0≤a<m и 0≤b<m по модулю m. Если (a+b)m, то выполняется обычное суммирование S=a+b и эта сумма S является результатом. Если же (S=a+b)>m и по исходному условию сумма S при 0≤a<m и 0≤b<m не может превышать 2m-2, то из суммы S вычитается значение m и результат является суммой (a+b) mod m. При этом на выходе переноса сумматора, осуществляющего вычитание, появляется сигнал. Данный сигнал является признаком превышения суммы S значения m и используется для выбора результата (a+b) или (a+b)-m. В соответствии с этим полный одноразрядный сумматор по модулю, из которого затем может быть составлен сумматор по модулю для произвольного числа разрядов, должен выполнить суммирование a_i и b_i разрядов с учетом разряда переноса p_Ini из младших разрядов и полученную сумму S_i выдать на выход устройства при отсутствии сигнала переноса модуля со старшего разряда или вычесть из нее разряд модуля m_i при наличии такового.

На чертеже представлена схема полного одноразрядного сумматора по модулю.

Полный одноразрядный сумматор по модулю содержит 7 логических элементов «НЕ», 7 двухвходовых логических элементов «И», 4 четырехвходовых логических элементов «И», 4 трехвходовых логических элементов «И», 2 трехвходовых логических элементов «ИЛИ», 1 четырехвходовый логический элемент «ИЛИ», 1 пятивходовый логический элемент «ИЛИ». На вход 1 подается разряд первого числа суммирования a_i, на вход 2 - второго числа суммирования b_i. Вход 3 служит входом переноса числа p_Ini, вход 4 - входом переноса модуля pm_Ini. На вход 5 подается разряд модуля m_i. Вход 6 является управляющим входом W. Выход 7 является выходом переноса p_Outi, выход 8 - выходом переноса модуля pm_Outi. Выход 9 является информационным выходом S_i.

Одноразрядный сумматор по модулю работает следующим образом. Полный одноразрядный сумматор по модулю состоит из логических элементов «НЕ», «И», «ИЛИ», соединенных таким образом, чтобы выполнялись следующие вычисления:

где i=0, …, n. Данные выражения составлены в соответствии с таблицей истинности:

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

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