Полный одноразрядный сумматор по модулю

Полный одноразрядный сумматор по модулю

Иллюстрации

Показать все

Реферат

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

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

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

Наиболее близким по технической сущности к заявляемому изобретению является полный одноразрядный сумматор по модулю, содержащий 7 логических элементов «НЕ», 7 двухвходовых логических элементов «И», 4 четырехвходовых логических элемента «И», 4 трехвходовых логических элемента «И», 2 трехвходовых логических элемента «ИЛИ», 1 четырехвходовый логический элемент «ИЛИ», 1 пятивходовый логический элемент «ИЛИ», соединенные между собой функционально (см. патент РФ №2427027, G06F 7/42, 20.08.2011, бюл. №23).

Недостатком данного устройства является низкое быстродействие.

Целью изобретения является повышение быстродействия.

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

Поставленная цель повышения быстродействия достигается за счет того, что сокращено количество элементов, через которые должен последовательно пройти сигнал при выполнении арифметической операции суммирования по модулю. В устройстве-прототипе (см. патент РФ №2427027, G06F 7/42, 20.08.2011, бюл. №23) количество последовательных элементов, через которые должен пройти сигнал при выполнении такой операции, составляет 6, а в предлагаемом устройстве количество таких элементов составляет 3, т.е. быстродействие устройства повышается в 2 раза.

Сущность изобретения заключается в реализации следующего способа суммирования двух чисел 0≤a<m и 0≤b<m по модулю m. Если (a+b)<m, то выполняется обычное суммирование S=a+b и эта сумма S является результатом. Если же (S=a+b)>m и по исходному условию сумма S при 0≤а<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 при наличии такового.

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

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

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

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