КОНВЕЙЕРНЫЙ СУММАТОР ПО МОДУЛЮ Российский патент 2023 года по МПК G06F7/50 

Область техники, к которой относится изобретение

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

Уровень техники

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

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

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

Раскрытие сущности изобретения.

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

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

где A и B - целые положительные числа, называемые соответственно первым и вторым слагаемым, причем

P - целое положительное число, называемое модулем;

S - целое положительное число, являющееся суммой чисел A и B, приведенной по модулю P, при этом 0≤S <P.

Все числа представлены в позиционной двоичной системе счисления.

где a_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения числа A;

b_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения числа B;

p_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения модуля P;

s_i, - коэффициенты, принимающие значение 0 или 1 в зависимости от значения суммы S;

n - количество разрядов в представлении чисел.

Задача состоит в том, чтобы по известным A и B отыскать сумму S по модулю P.

Ввиду выполнения ограничения (2), сумма чисел A и B всегда будет находиться в диапазоне чисел от 0 до 2P-2. Диапазон от 0 до 2P-2 может быть разделен на первый диапазон от 0 до P-1 и второй диапазон от P до 2P-2. Если сумма чисел A и B попадает в первый диапазон, то она и будет являться результатом суммирования чисел A и B по модулю P. Если сумма чисел A и B попадает во второй диапазон, то для приведения ее по модулю P достаточно вычесть из нее модуль P. Операция вычитания может быть выполнена путем суммирования уменьшаемого с вычитаемым, представленном в дополнительном коде. При этом индикатором попадания суммы чисел A и B в первый или второй диапазон будет являться отсутствие или наличие сигнала на выходе переноса сумматора, реализующего операцию вычитания. Этот сигнал управляет мультиплексором, который выбирает нужный результат.

В результате вычисление суммы чисел A и B по модулю P в конвейерном режиме может быть сведено к следующим вычислительным действиям.

На первой ступени конвейера вычисляют сумму чисел A и B.

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

Описанная выше процедура определяет вычисление суммы от одной пары чисел A и B.

Рассмотрим реализацию вычисления сумм для потока чисел A_j, B_j и P_j поступающего потактово на вход конвейерного сумматора по модулю, j=1, 2, 3, …,.

Выражение (1) при этом примет следующий вид

На первом такте на первой ступени конвейера вычисляется значение суммы

для первой пары чисел. Вторая ступень конвейера при этом не задействована.

На втором такте на первой ступени конвейера вычисляется значение суммы

для второй пары чисел A₂ и B₂. На второй ступени конвейера на этом же такте вычисляется значение

и в качестве результата S₁ выбирается значение (8) или (10) в зависимости от значения сигнала переноса, образующегося при вычислении (10).

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

Краткое описание чертежей.

Сущность изобретения поясняется чертежами.

На фиг. 1 представлена схема конвейерного сумматора по модулю. Конвейерный сумматор по модулю содержит 2n-разрядный и (2n+1)-разрядный регистры 1 и 3, где n - разрядность обрабатываемых чисел, n-разрядный и (n+1)-разрядный сумматоры 2 и 4, мультиплексор 5, первые 6, вторые 7 и третьи 9 информационные входы устройства, информационные выходы устройства 10 и тактовый вход устройства 8, который соединён с тактовыми входами 2n-разрядного и (2n+1)-разрядного регистров 1 и 3. Младшие n разрядов информационных входов 2n-разрядного регистра 1 соединены с первыми информационными входами устройства 6, старшие n разрядов информационных входов соединены со вторыми информационными входами устройства 7, младшие n разрядов информационных выходов соединены с первыми информационными входами n-разрядного сумматора 2, а старшие n разрядов информационных выходов соединены со вторыми информационными входами n-разрядного сумматора 2. Информационные выходы n-разрядного сумматора 2 соединены с младшими n разрядами информационных входов (2n+1)-разрядного регистра 3, выход переноса соединен с (n+1)-м разрядом информационных входов (2n+1)-разрядного регистра 3, старшие n разрядов информационных входов которого соединены с третьими информационными входами устройства 9. Старшие n разрядов информационных выходов (2n+1)-разрядного регистра 3 соединены с первыми n разрядами вторых информационных входов (n+1)-разрядного сумматора 4, на (n+1)-й разряд которых и на вход переноса (n+1)-разрядного сумматора 4 подаётся сигнал логической единицы. Младшие n разрядов информационных выходов (2n+1)-разрядного регистра 3 соединены первыми n разрядами первых информационных входов (n+1)-разрядного сумматора 4 и с первыми информационными входами мультиплексора 5, а (n+1)-й разряд информационных выходов соединен с (n+1)-м разрядом первых информационных входов (n+1)-разрядного сумматора 4. Вторые информационные входы мультиплексора 5 соединены с первыми n разрядами информационных выходов (n+1)-разрядного сумматора 4, управляющий вход соединен с выходом переноса (n+1)-разрядного сумматора 4, а информационные выходы соединены с информационными выходами устройства 10.

Осуществление изобретения.

Конвейерный сумматор работает следующим образом (см. Фиг. 1).

В исходном состоянии 2n-разрядный и (2n+1)-разрядный регистры 1 и 3 обнулены. На тактовый вход устройства 8 поступают тактовые импульсы j=1, 2, 3, …,. На первые информационные входы устройства 6 и вторые информационные входы устройства 7 с каждым тактовым импульсом подаются числа A_j и B_j, для которых необходимо вычислить сумму S_j по модулю P_j. На третьи информационные входы устройства 9, на (j+1)-ом такте подаётся инверсный код модуля P_j. Сумма S_j по модулю P_j чисел A_j и B_j снимается с информационных выходов устройства 10. Длина конвейера составляет две ступени. Латентный период работы конвейера равен одному такту.

На первом такте работы устройства первые два n-разрядных числа A₁ и B₁ записываются в 2n-разрядный регистр 1. При этом число A₁ записывается в младшие n разрядов 2n-разрядного регистра 1, а число B₁ записывается в его старшие n разрядов. С информационных выходов 2n-разрядного регистра 1 числа A₁ и B₁ поступают на первые и вторые информационные входы n-разрядного сумматора 2. На информационных выходах n-разрядного сумматора 2, в соответствии с (8) образуется значение суммы . При этом, если окажется, что

то на выходе переноса n-разрядного сумматора 2 окажется сигнал переноса.

На втором такте работы устройства в старшие n разрядов (2n+1)-разрядного регистра 3 с третьих информационных входов устройства 9 записывается инверсный код модуля , а в младшие (n+1) разрядов с информационных выходов и выхода переноса n-разрядного сумматора 2 записывается значение суммы . В результате на первые информационные входы (n+1)-разрядного сумматора 4 поступит (n+1)-разрядное значение суммы , а на младшие n разрядов вторых информационных входов поступит n-разрядный инверсный код модуля , который дополняется до (n+1)-го разряда значением логической единицы, поступающей на (n+1)-й разряд вторых информационных входов (n+1)-разрядного сумматора 4. Так как на вход переноса (n+1)-разрядного сумматора 4 поступает сигнал логической единицы, то в соответствии с (10), этим сумматором по существу выполняется операция вычитания . В случае, если значение , то на выходе переноса (n+1)-разрядного сумматора 4 образуется сигнал переноса, который поступит на управляющий вход мультиплексора 5, а на младших n разрядах информационных выходов (n+1)-разрядного сумматора 4 образуется значение , которое и будет являться искомой суммой Мультиплексор 5, под воздействием управляющего сигнала, скоммутирует свои вторые информационные входы на свои информационные выходы и результат вычислений поступит на информационные выходы устройства 10. Если же значение , то на выходе переноса (n+1)-разрядного сумматора 4 сигнал переноса отсутствует и мультиплексор 5 скоммутирует свои первые информационные входы на свои информационные выходы. В результате на информационные выходы устройства 10 поступит значение , которое и будет в этом случае являться искомой суммой

Также на втором такте устройства вторые два n-разрядных числа A₂ и B₂ записываются в 2n-разрядный регистр 1. При этом число A₂ также записывается в младшие n разрядов 2n-разрядного регистра 1, а число B₂ записывается в его старшие n разрядов. С информационных выходов 2n-разрядного регистра 1 числа A₂ и B₂ поступают на первые и вторые информационные входы n-разрядного сумматора 2. На информационных выходах n-разрядного сумматора 2 образуется значение суммы :

На третьем такте работы устройства в старшие n разрядов (2n+1)-разрядного регистра 3 с третьих информационных входов устройства 9 записывается инверсный код модуля , а в младшие (n+1) разрядов с информационных выходов и выхода переноса n-разрядного сумматора 2 записывается значение суммы . Далее работа устройства осуществляется аналогичным образом. В результате на информационных выходах устройства 10 будет сформирована сумма

Также на третьем такте устройства следующие два n-разрядных числа A₃ и B₃ записываются в 2n-разрядный регистр 1 и работа устройства осуществляется аналогичным образом.

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

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

Источники информации

1. Пухальский, Г.И. Проектирование дискретных устройств на интегральных микросхемах / Г.И. Пухальский, Т.Я. Новосельцева. - М.: Радио и связь, 1990. - 304 c.

2. Патент США US 4722067. Int. Cl⁴ G06F 7/72, U.S. Cl. 364/746. Method and apparatus for implementing modulo arithmetic calculations. Опубликован 26.01.1988.

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

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