Конвейерный формирователь остатков по произвольному модулю

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

 

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

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

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

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

Из существующего уровня техники известно устройство для формирования остатка по произвольному модулю от числа, содержащее l=((k/N)-1) блоков формирования частичных остатков (где k - количество разрядов в двоичном представлении числа, от которого формируется остаток, с учетом добавленных для достижения кратности N разрядов), (l+1) блоков умножения по модулю, блока распределения коэффициентов и сумматора по модулю [4]. Недостатком данного технического решения является низкое быстродействие при вычислении остатков по модулю для потока чисел, так как формирование частичного остатка и выполнение операций умножения и сложения по модулю производится заново для каждого из чисел в потоке, кроме того, вычисление остатка по модулю для очередного числа в потоке не может быть начато до тех пор, пока не завершено вычисление остатка по модулю для предыдущего числа.

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

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

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

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

A = Q⋅P +R, (1)

где A - целое положительное число, от которого необходимо вычислить остаток;

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

Q - целое положительное число, являющееся неполным частным от деления A на P;

R - целое положительное число, являющееся остатком от деления A на P.

Причем

A = a_n-₁·2ⁿ-¹+a_n-₂·2ⁿ-²+ . . . +a₁·2¹+a₀, (2)

P = p_m-₁·2^m-¹+p_m-₂·2^m-²+ . . . +p₁·2¹+p₀, (3)

Q = q_n-₂·2ⁿ-²+ q_n-₃·2ⁿ-³+ . . . +q₁·2¹+q₀, (4)

R = r_m-₁·2^m-¹+ r_m-₂·2^m-²+ . . . +r₁·2¹+r₀, (5)

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

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

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

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

n - количество разрядов в представлении числа A, m - количество разрядов в представлении модуля P, .

Задача состоит в том, чтобы по известным A и P отыскать остаток R. Остаток R является в терминах теории чисел вычетом числа A по модулю P, поэтому говорят, что A сравнимо с R:

A R (mod P). (6)

Значение остатка R может быть вычислено следующим образом:

R = A (mod P) = (a_n-₁·2ⁿ-¹+a_n-₂·2ⁿ-²+ … +a₁·2¹+a₀)mod P. (7)

Перепишем выражение (7) в следующем виде:

R = (2(2(…(2(a_n-₁·2+a_n-₂)+ a_n-₃) …) +a₁)+a₀)mod P. (8)

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

Поэтому выражение (8) может быть представлено в следующем виде

R = (2(2(…(2(a_n-₁·2+a_n-₂) mod P + a_n-₃) mod P+ …)mod P +…+a₁) mod P +a₀)mod P. (9)

В таком виде значительно облегчается задача нахождения остатка R от числа А по модулю P с использованием конвейерного режима.

Вначале на первом такте в первом слое конвейера от первого числа вычисляют первый частичный остаток t₁:

t ₁ = (2·t₀+a_n-₂) mod P, где t₀=a_n-1. (10)

На втором такте во втором слое конвейера от первого числа вычисляют второй частичный остаток t₂:

t ₂ = (2·t₁+a_n-₃) mod P, (11)

а от второго числа в первом слое конвейера вычисляют первый частичный остаток t₁ в соответствии с (10).

На третьем такте в третьем слое конвейера от первого числа вычисляют третий частичный остаток t₃:

t ₃ = (2·t₂+a_n-₄) mod P, (12)

от второго числа во втором слое конвейера вычисляют второй частичный остаток t₂ в соответствии с (11), а от третьего числа в первом слое конвейера вычисляют первый частичный остаток t₁ в соответствии с (10).

На (n-1)-м такте в (n-1)-м слое конвейера от первого числа вычисляют (n-1)-й частичный остаток t_n-1:

t _{n = 1} (2·t_n-₂+a₀) mod P, (13)

который и является искомым остатком R от первого числа A по модулю P, поступившего на вход конвейера на первом такте. При этом в (1…(n-2))-м слоях конвейера будут находиться соответствующие частичные остатки, согласно вышеприведенным выражениям, от поступивших на его вход чисел. Соответственно на каждом следующем такте будем в (n-1)-м слое конвейера получать остатки от чисел, поступающих на вход по модулю P.

Операция приведения по модулю P в каждом слое конвейеризации выполняется исходя из следующих соображений.

По определению величина t_i-₁ лежит в диапазоне 0≤t_i-₁≤P-1, поэтому в соответствии с выражениями (10) - (13) величина

t _i = 2 t_i-₁ +a _n-_i-₁, (14)

до приведения ее по модулю может принимать значения в диапазоне от 0 до 2P-1, так как a_n-_i-₁ может принимать значение 0 или 1. Приведение по модулю величины t_i осуществляется по следующим правилам:

t_i (mod P)=t_i, если 0 ≤ t_i < P, (15)

t_i (mod P)=t_i - P, если P ≤ t_i < 2P.

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

На фиг. 1 представлена схема конвейерного формирователя остатков по произвольному модулю. Конвейерный формирователь остатков по произвольному модулю содержит (n-1) параллельных регистров 1.1÷1.n-1, (n-1) блоков формирования частичных остатков 2.1÷2.n-1, первые информационные входы 3 устройства, вторые информационные входы 4 устройства, информационные выходы 5 устройства, тактовый вход 6 устройства. Тактовый вход 6 устройства соединен с тактовыми входами (n-1) параллельных регистров 1.1÷1.n-1. Первые информационные входы 3 устройства соединены с информационными входами первого параллельного регистра 1.1, два старших разряда информационных выходов которого соединены с первыми информационными входами первого блока формирования частичных остатков 2.1, вторые информационные входы устройства соединены со вторыми информационными входами блоков формирования частичных остатков 2.1÷2.n-1, информационные выходы (n-1)-го блока формирования частичных остатков 2.n-1 соединены с информационными выходами 5 устройства, информационные выходы i-го блока формирования частичных остатков 2.i, i=(1, …, (n-2)) соединены с m младшими разрядами информационных входов (i+1)-го параллельного регистра 1.i+1, где m - разрядность модуля, m младших разрядов информационных выходов которого соединены со (2, … , (m+1))-ми разрядами первых информационных входов (i+1)-го блока формирования частичных остатков 2.i+1, с первым разрядом первых информационных входов которого соединён самый старший (n-i+m)-й разряд информационных выходов (i+1)-го параллельного регистра 1.i+1, (n-i-1) старших разрядов информационных входов которого соединены с (n-i-1) старшими разрядами информационных выходов i-го параллельного регистра 1.i, разрядность первого параллельного регистра 1.1 равна n, а i-го параллельного регистра 1.i равна (m+n-i).

На фиг. 2 представлена схема блока формирования частичных остатков 2.i, i=(1, …, (n-1)). Блок формирования частичных остатков 2.i содержит сумматор 7 и мультиплексор 8. Первые информационные входы сумматора 7 и мультиплексора 8 соединены и являются первыми информационными входами блока формирования частичных остатков 2.i, вторые информационные входы сумматора 7 соединены со вторыми информационными входами блока формирования частичных остатков 2.i, информационные выходы сумматора 7 соединены со вторыми информационными входами мультиплексора 8, а выход переноса соединён с управляющим входом мультиплексора 8, выходы которого являются информационными выходами блока формирования частичных остатков 2.i, а на вход переноса сумматора 7 подаётся сигнал логической единицы.

На фиг. 3 представлено распределение разрядности параллельных регистров 1.1÷1.n-1. Первый параллельный регистр 1.1 имеет разрядность n, равную разрядности входных чисел, а i-й (i=2, …, (n-1)) параллельный регистр 1.i имеет разрядность (m+n-i), где n - разрядность входных чисел, а m - разрядность модуля.

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

В исходном состоянии параллельные регистры 1.1÷1. n-1 обнулены. На тактовый вход 6 устройства поступают тактовые импульсы. На первые информационные входы 3 устройства с каждым тактовым импульсом подаются числа A_i, от которых необходимо вычислить остаток по модулю P. На вторые информационные входы 4 устройства, в течение всего цикла формирования остатков, подаётся инверсный код модуля P.

На первом такте первое число A записывается в параллельный регистр 1.1. При этом два старших разряда первого числа A с выходов параллельного регистра 1.1 поступают на первые информационные входы блока формирования частичных остатков 2.1, который вычисляет значение первого частичного остатка в соответствии с выражением (10). С информационных выходов блока формирования частичных остатков 2.1 m - разрядное значение первого частичного остатка первого числа поступает на (1…m)-ые разряды информационных входов второго параллельного регистра 1.2. На ((m+1)…(m+n-2))-ые разряды информационных входов этого же регистра поступают значения (1, …, (n-3))-ых разрядов первого входного числа с информационных выходов первого параллельного регистра 1.1.

На втором такте в первый параллельный регистр 1.1 записывается второе число, а во второй параллельный регистр 1.2 записывается первый частичный остаток первого числа с выхода блока формирования частичных остатков 2.1 и значения (1, …, (n-2))-ых разрядов первого числа с информационных выходов параллельного регистра 1.1. В результате на первый разряд первых информационных входов блока формирования частичных остатков 2.2 с информационного выхода второго параллельного регистра 1.2 поступит значение (n-3) разряда первого числа, а на остальные разряды поступит значение первого частичного остатка от первого числа с информационных выходов первого блока формирования частичных остатков 2.1. В результате на информационном выходе блока формирования частичных остатков 2.1 будет сформирован первый частичный остаток от второго числа, а на информационном выходе блока формирования частичных остатков 2.2 будет сформирован второй частичный остаток от первого числа.

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

Блок формирования частичных остатков 2.i, i=(1, …, (n-1)) реализует выражение (15) следующим образом (см. Фиг. 2). Так как на вторые информационные входы сумматора 7 поступает инверсный код модуля P, а на вход переноса сигнал логической единицы, то сумматор 7 реализует операцию вычитания t_i-P. В случае, если t_i≥P на выходе переноса сумматора 7 появляется сигнал логической единицы, который, поступая на управляющий вход мультиплексора 8, скоммутирует с его выходами вторые информационные входы, если же t_i<P, то на выходе переноса сумматора 7 будет сигнал логического нуля и на выходы мультиплексора 8 будет скоммутирован его первые информационные входы. В результате на выходах мультиплексора 8 всегда будет значение t_i mod P, которое поступает на первые информационные выходы блока формирования частичных остатков 2.i.

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

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

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

1. Патент на изобретение RU 2012137 C1. Устройство для формирования остатка по произвольному модулю от числа. Опубл. 30.04.1994.

2. Патент на изобретение RU 2348965 C1. Вычислительное устройство. Опубл. 10.03.2009, Бюл. №7.

3. Патент на изобретение RU 2029435 C1. Комбинационный рекуррентный формирователь остатков. Опубл. 20.02.1995.

4. Патент на изобретение RU 2324972 C2. Устройство для формирования остатка по произвольному модулю от числа. Опубл. 20.05.2008. Бюл. №14.

5. Патент на изобретение RU 2421781 C1. Устройство для формирования остатка по заданному модулю. Опубл. 20.06.2011. Бюл. №17.

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