Устройство для формирования остатка по заданному модулю

Полезная модель относится к вычислительной технике и может быть использована в цифровых вычислительных устройствах для формирования кодовых последовательностей. Техническим результатом является повышение производительности выполнения операции формирования остатка по заданному модулю для потока чисел путем конвейеризации процесса вычисления частичных и итоговых остатков на основе предварительно вычисленных значений первичных остатков. Технический результат в устройстве для формирования остатков по заданному модулю, содержащем Т блоков формирования частичных остатков с информационным входом на n разрядов, входом первичных остатков на (n-p-1)·(p+1) разряд, входом инициализации, синхровходом и выходом на (p+q) разрядов соответственно, где Т - максимальное количество однотипных операций, требуемых для формирования остатков чисел по (p+1)-разрядному модулю, (p+1)<n, n - разрядность чисел, q=]log₂ (n-p)[, достигается тем, что в него введены два параллельных (p+2)- и (p+1)-разрядных регистра с синхровходом, входом и выходом данных соответственно, мультиплексор с двумя входами данных, управляющим входом и выходом, компаратор с двумя входами и выходом, блок вычитания с входами уменьшаемого и вычитаемого, а также с выходом разности, причем синхровходы блоков формирования частичных остатков соединены с синхровходом устройства, входы инициализации и первичных остатков блоков формирования частичных остатков соединены с входами инициализации и первичных остатков устройства соответственно, информационный вход первого из блоков формирования частичных остатков является входом чисел устройства, выход t-го блока формирования частичных остатков соединен с информационным входом (t+1)-го блока формирования частичных остатков, , вход данных (р+2)-разрядного параллельного регистра соединен с выходом Т-го блока формирования частичных остатков, его синхровход является синхровходом устройства, а его выход соединен с первым входом данных мультиплексора, с первым входом компаратора и с входом уменьшаемого блока вычитания; вход данных (p+1)-разрядного регистра с синхровходом является входом модуля устройства, его синхровход - входом инициализации устройства, а выход (p+1)-разрядного регистра с синхровходом соединен с вторым входом компаратора и входом вычитаемого блока вычитания; второй вход данных мультиплексора связан с выходом разности блока вычитания, а его управляющий вход - с выходом компаратора, выход мультиплексора является выходом устройства. 2 ил., 1 табл.

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

Известно устройство для формирования остатка по модулю от числа, содержащее два элемента задержки, элемент запрета, с первого по третий регистры, блок элементов И, группу блоков элементов И, комбинационный сумматор по модулю (см. патент РФ 2157589, кл. H03M 7/18, G06F 7/38, 10.10.2000).

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

Наиболее близким по технической сущности к заявляемой полезной модели является устройство для формирования остатка по произвольному модулю от числа, содержащее l=((k/N)-1) блоков формирования частичных остатков (где k - количество разрядов в двоичном представлении числа, от которого формируется остаток, с учетом добавленных для достижения кратности N разрядов), (l+1) блоков умножения по модулю, блока распределения коэффициентов и сумматора по модулю (см. патент РФ 2324972, кл. G06F 7/72, H03M 7/18, 20.05.2008).

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

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

Технический результат в устройстве для формирования остатков по заданному модулю, содержащем Т блоков формирования частичных остатков с информационным входом на n разрядов, входом первичных остатков на (n-p-1)·(p+1) разряд, входом инициализации, синхровходом и выходом на (р+q) разрядов соответственно, где Т - максимальное количество однотипных операций, требуемых для формирования остатков чисел по (р+1)-разрядному модулю, (p+1)<n, n - разрядность чисел, q=]log₂ (n-p)[, достигается тем, что в него введены два параллельных (р+2)- и (р+1)-разрядных регистра с синхровходом, входом и выходом данных соответственно, мультиплексор с двумя входами данных, управляющим входом и выходом, компаратор с двумя входами и выходом, блок вычитания с входами уменьшаемого и вычитаемого, а также с выходом разности, причем синхровходы блоков формирования частичных остатков соединены с синхровходом устройства, входы инициализации и первичных остатков блоков формирования частичных остатков соединены с входами инициализации и первичных остатков устройства соответственно, информационный вход первого из блоков формирования частичных остатков является входом чисел устройства, выход t-го блока формирования частичных остатков соединен с информационным входом (t+1)-го блока формирования частичных остатков, ; вход данных (р+2)-разрядного параллельного регистра соединен с выходом T-го блока формирования частичных остатков, его синхровход является синхровходом устройства, а его выход соединен с первым входом данных мультиплексора, с первым входом компаратора и с входом уменьшаемого блока вычитания; вход данных (p+1)-разрядного регистра с синхровходом является входом модуля устройства, его синхровход - входом инициализации устройства, а выход (р+1)-разрядного регистра с синхровходом соединен с вторым входом компаратора и входом вычитаемого блока вычитания; второй вход данных мультиплексора связан с выходом разности блока вычитания, а его управляющий вход - с выходом компаратора, выход мультиплексора является выходом устройства.

Блок формирования частичных остатков содержит параллельный n-разрядный регистр с синхровходом, а также входом и выходом данных соответственно, где n - разрядность чисел, (n-p-1) параллельных (p+1)-разрядных регистров с синхровходом, входом и выходом данных соответственно, где (p+1) - разрядность заданного модуля, (p+1)<n, (n-p-1) буферных элементов с управляющим входом и (p+1)-разрядными входом и выходом данных соответственно, а также комбинационный сумматор с (n-p) (р+1)-разрядными входами и (р+q)-разрядным выходом, причем вход данных параллельного n-разрядного регистра является информационным входом блока формирования частичных остатков, а его синхровход - синхровходом блока формирования частичных остатков, (р+1) разрядов с его выхода данных соединены с первым входом комбинационного сумматора, а его s-й выход связан с управляющим входом (s-p)-го буферного элемента, ; вход данных (s-p)-го (р+1)-разрядного регистра соединен с (s-р)-м элементом входа первичных остатков блока формирования частичных остатков, на который подается значение b_s =2^smodL, соответственно, его синхровход - входом инициализации блока формирования частичных остатков, а его выход - входом данных (s-р)-го буферного элемента, ; выходы данных каждого из (s-р)-х буферных элементов соединены с входами комбинационного сумматора под номерами (s-p+1), , соответственно, выход комбинационного сумматора является выходом блока формирования частичных остатков.

Схема устройства для формирования остатков по заданному модулю изображена на фиг.1, а схема блока формирования частичных остатков - на фиг.2.

Устройство для формирования остатков по заданному модулю содержит T блоков 1 формирования частичных остатков, параллельные (p+2)- и (p+1) -разрядные регистры 2 и 3 с синхровходом, входом и выходом данных соответственно, мультиплексор 4 с двумя входами данных, управляющим входом и выходом, компаратор 5 с двумя входами и выходом, блок 6 вычитания с входами уменьшаемого и вычитаемого, а также с выходом разности. Вход 7 является входом чисел устройства - n-разрядных чисел А, вход 8 - синхровходом устройства, вход 9 - входом модуля устройства, (р+1)-разрядного модуля L, вход 10 - входом инициализации устройства, а вход 11 - входом первичных остатков b_s=2^smodL устройства, . Выход 12 является выходом устройства, на который поступают значения остатков - G.

На фиг.2 представлен t-й блок 1 формирования частичных остатков, , который включает параллельный n-разрядный регистр 13 с синхровходом, входом и выходом данных, (n-p-1) параллельных (p+1)-разрядных регистров 14 с синхровходом, входом и выходом данных соответственно, (n-p-1) буферных элементов 15 с управляющим входом и (р+1)-разрядными входом и выходом данных соответственно, а также комбинационный сумматор 16 с (n-p) (p+1)-разрядными входами и (р+q) -разрядным выходом. Для t-го блока 1 формирования частичных остатков, , вход 8 является синхровходом устройства, вход 10 - входом инициализации устройства, а вход 11 - входом первичных остатков b_s, , соответственно. Информационный вход 17 первого блока 1 формирования частичных остатков (см. фиг.1) является входом 7 чисел устройства, а информационный вход 17 t-го блока 1 формирования частичных остатков является выходом 18 (t-1)-го блока 1 формирования частичных остатков, , соответственно. Выход 18 является выходом блока 1 формирования частичных остатков.

Рассмотрим устройство для формирования остатков по заданному модулю в работе.

В предлагаемом устройстве вычисление первичных остатков по модулю, одинаковых для всего потока чисел, реализуется на этапе предварительной подготовки данных. По сравнению с прототипом (см. патент РФ 2324972, кл. G06F 7/72, H03M 7/18, 20.05.2008), из устройства исключена операция умножения. Кроме того, в устройстве организована конвейеризация процесса вычисления остатков по заданному модулю для потока чисел на базе последовательного выполнения операций сложения (не по модулю) первичных остатков.

Сущность полезной модели в том, что предлагаемое устройство реализует процедуру последовательного вычисления значения остатков G по заданному модулю для потока n-разрядных чисел А на основе частичных остатков. Число А тождественно равно представлению в виде степеней числа два, просуммированных в соответствии с коэффициентами при каждой его степени:

Частичный остаток по модулю L, представленный (р+1)-разрядным вектором, вычисляется по формуле вида:

где первичные остатки вычисляются согласно выражению:

Значение p выбирается из условия: (2 ^p<L)&(2^p+1>L). Величина g есть сумма первичных остатков (3), каждый из которых является слагаемым, если a_s=1, , при этом АgmodL, и АGmodL.

При формировании первичных остатков согласно (3) на этапе предварительной подготовки данных используется следующая процедура (см. патент РФ 2324972, кл. G06F 7/72, Н03М 7/18, 20.05.2008). Величина z=2^s, , сравнивается со значением модуля L. Если zL, то из z вычитается значение модуля L, а полученное в результате значение z₁=z-L вновь сравнивается со значением L. Если и в этом случае значение z₁L, то из z₁ вновь вычитается значение L, а полученное в результате значение z₂=z₁-L сравнивается со значением L. Данные операции производятся до тех пор, пока значение z_y, полученное на этапе у, не станет меньше значения модуля L. В этом случае значение z_y является первичный остаток b_s. Если уже на первом этапе z<L, то в качестве b_s принимаем значение z=2^s .

В прототипе (см. см. патент РФ 2324972, кл. G06F 7/72, H03M 7/18, 20.05.2008) процедура (3) реализуется аппаратно, на каждой ступени. Это требует дополнительных затрат и не позволяет реализовать вычисления на каждой ступени независимо для потока чисел.

Количество выполняемых операций вида (2) - t, требуемых для получения частичного остатка g[0,2^p+1-1] на основе числа А заданной разрядности n и заданной величины модуля L, А[L+1,2ⁿ-1], определяется путем непосредственного машинного подсчета. Приведем пример, для чисел А разрядности n=8, 16 и 24, для которых L принимают значения 23, 263 и 4127 соответственно. Количество значений А, для которых частичный остаток g[0,2^p+1-1] при заданной величине модуля L вычисляется за t операций вида (2), , приведено в таблице. При этом величина Т - максимальное значение t для заданного n, принимает значение 2, 2 и 3 для n=8, 16 и 24 соответственно. Затем, после выполнения операций (2) T раз, остаток G определяется на основе g[0,2^p+1-1] по формуле:

Таблица. Количество значений A, A[L+1,2n-1], для которых значение частичного остатка вычисляется t раз
n	L	t=0	t=1	t=2	t=3	t=4
8	23	80	131	21	0	0
16	263	~9,10·103	~32,5·103	~23,6·103	0	0
24	4127	~734·10 3	~7,44·10 6	~8,45·10 6	~147·10 3	0

За счет вычисления первичных остатков на этапе предварительной подготовки данных согласно (3), а также параллельного вычисления значений частичных остатков g и G для различных чисел в потоке согласно (2) и (4) соответственно, достигается повышение производительности выполнения операции формирования остатков по заданному модулю L для потока чисел.

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

Значение числа а, поступившее на вход 7 чисел устройства, который является информационным входом 17 блока 1 формирования частичных остатков, по синхросигналу 8, поступившему на синхровход параллельного n-разрядного регистра 13, заносится в данный регистр. При этом (p+1) разрядов числа, занесенного в параллельный n-разрядный регистр 13, с номерами s, , поступают на первый вход комбинационного сумматора 16, а каждый s-й разряд из параллельного n-разрядного регистра 13 поступает на управляющий вход (s-р)-го буферного элемента 15 соответственно, . На этапе инициализации, в (s-р)-е параллельные (р+1)-разрядные регистры 14 через вход 11 первичных остатков по сигналу инициализации, подаваемому на вход 10 инициализации устройства, заносятся значения первичных остатков b_s, , соответственно, которые затем с выхода (s-p)-го параллельного (р+1)-разрядного регистра 14 поступают на вход (s-p)-го буферного элемента 15, , соответственно. Значения с выхода (s-p)-го буферного элемента 15 поступают на (s-p+1)-й вход комбинационного сумматора 16, , соответственно. На выход 18 блока 1 формирования частичных остатков, который является также выходом комбинационного сумматора 16, поступает (p+q)-разрядное значение частичного остатка g, вычисленного согласно (2).

На этапе инициализации по сигналу инициализации, подаваемому на вход 10 инициализации устройства, в параллельный (р+1)-разрядный регистр 3 (через (р+1)-разрядный вход 9 модуля устройства) заносится значение модуля L, а в параллельный (р+1)-разрядный регистр 14 (через (р+1)-разрядный вход 11 первичных остатков) - значение первичных остатков b_s, , соответственно.

На этапе функционирования на n-разрядный информационный вход 17 первого блока 1 формирования частичных остатков, который является также входом 7 чисел устройства, поступает значение А. На младшие (p+2) двоичных разряда информационного входа 17 второго блока 1 формирования частичных остатков поступает значение, снимаемое с выхода 18 первого блока 1 формирования частичных остатков, а на остальные (n-p-2) двоичных разряда информационного входа 17 второго блока 1 формирования частичных остатков подаются нулевые значения. Значение, снимаемое с выхода 18 t-го блока 1 формирования частичных остатков, поступает на младшие (p+2) двоичных разряда информационного входа 17 (t+1)-го блока 1 формирования частичных остатков, а на остальные (n-p-2) двоичных разряда информационного входа 17 (t+1)-го блока 1 формирования частичных остатков подаются нулевые значения, , соответственно. Значение, снимаемое с выхода 18 T-го блока 1 формирования частичных остатков, поступает на вход параллельного (р+2)-разрядного регистра 2, в котором сохраняется по синхросигналу, поступающему на синхровход 8 устройства. Информация, поступившая на информационные входы 17 блоков 1 формирования частичных остатков, записывается в параллельный n-разрядный регистр 13 внутри каждого из блоков 1 формирования частичных остатков по синхросигналу, поступающему на синхровход 8 устройства. Значение, снимаемое с выхода параллельного (p+2)-разрядного регистра 2, поступает на первые входы данных мультиплексора 4 и компаратора 5 соответственно, а также на вход уменьшаемого блока 6 вычитания. На вторые входы данных мультиплексора 4 и компаратора 5 поступают значения с выходов разности блока 6 вычитания и параллельного поразрядного регистра 3 соответственно. На вход вычитаемого блока 6 вычитания поступает значение с выхода параллельного (p+1)-разрядного регистра 3. На управляющий вход мультиплексора 4 поступает результат сравнения значений, формируемый на выходе компаратора 5. Выход мультиплексора 4 является (p+1)-разрядным выходом 12 устройства, на который поступает значение остатка G, вычисляемое согласно (4).

Вычисления N значений остатков по заданному модулю L-G₁ , G₂, , G_N для потока чисел А₁, A₂ , , A_N требует (N+Т) тактов работы устройства, причем время задержки выполнения операций на одном такте определяется как max(T₁₃+T₁₅+Т₁₆,Т₂ +max(T₅+Т₆)+Т₄), где T_i - время задержки функционирования i-го блока на фиг.1 и 2.

Порядок функционирования устройства отображен на примере нахождения остатков от деления по модулю 23 для потока из пяти чисел, представленных байтами (8 разрядов) - 72, 222, 247, 108, 255 или 01001000, 11011110, 11110111, 01101100, 11111111 соответственно. Для данного потока восьмиразрядных чисел величина T=2. В устройстве два блока 1 формирования частичных остатков выполняют операции вида (2), а мультиплексор 4, компаратор 5 и блок 6 вычитания, выполняют операции согласно (4). При инициализации устройства по сигналу инициализации, подаваемому на вход 10 устройства, в три параллельных пятиразрядных регистра 14 через вход 11 первичных остатков заносятся значения первичных остатков: 2⁵ mod23=9, 2⁶mod23=18 и 2⁷mod23=13, а в параллельный пятиразрядный регистр 3 заносится значение модуля, равное 23 ₁₀=10111₂. По первому синхросигналу в параллельный пятиразрядный регистр 13 первого блока 1 формирования частичных остатков заносится значение 72₁₀=01001000₂ (с входа 7 чисел устройства). На выходе 18 первого блока 1 формирования частичных остатков, через время ТЗ=Т₁₃+Т₁₅ +Т₁₆, формируется шестиразрядный частичный остаток по модулю 23, (частичный остаток номер 1 для числа 72), равный значению 26₁₀=011010₂ и поученный как сумма пяти младших двоичных разрядов числа 72₁₀=01001000 ₂ - 01000, а также первичного остатка 2⁶mod23=18 ₁₀=10010₂ (т.к. разряд номер 7 числа 72 ₁₀=01001000₂ равен «1»).

По второму синхросигналу, в первый блок 1 формирования частичных остатков заносится значение 222₁₀=11011110₂ , а во второй блок 1 формирования частичных остатков - частичный остаток номер 1 для числа 72, величина 26₁₀=00011010 ₂ (на два старших разряда входа второго блока 1 формирования частичных остатков поступают значения «0» как константы), и, через время ТЗ, на выходе 18 первого блока 1 формирования частичных остатков формируется значение частичного остатка номер 1 для числа 222 - значение 61₁₀=111101₂ (сумма пяти младших разрядов числа 222₁₀=11011110 ₂ - 11110, числа 2⁶mod23=18₁₀=10010 ₂ и числа 2⁷mod23=13₁₀=01101 ₂, так как разряды под номерами 7 и 8 числа 222₁₀ =11011110₂ равны «1»). На выходе 18 второго блока 1 формирования частичных остатков формируются значение частичного остатка номер 2 для числа 72, значение 26₁₀ =011010₂ (пять младших разрядов числа 26₁₀ =00011010₂ - 11010, старший разряд выхода 18 блока 1 формирования частичных остатков остается равным «0»).

Третий синхросигнал определяет момент занесения значения 247₁₀=11110111₂ в первый блок 1 формирования частичных остатков, частичного остатка номер 1 для числа 222 - во второй блок 1 формирования частичных остатков и частичного остатка номер 2 для числа 72 - в параллельный шестиразрядный регистр 2. Через время ТЗ, на выходе 18 первого блока 1 формирования частичных остатков формируется значение 63₁₀=111111 ₂ (частичный остаток номер 1 для числа 247, сумма пяти младших разрядов числа 247₁₀=11110111₂ - 10111, числа 2⁵mod23=9₁₀=01001₂ , значения 2⁶mod23=18₁₀=10010₂ и числа 2⁷mod23=13₁₀=01101₂ , т.к. разряды под номерами 6, 7 и 8 числа 247₁₀=11110111 ₂ равны «1»), на выходе 18 второго блока 1 формирования частичных остатков формируется значение 38₁₀=100110 ₂ (частичный остаток номер 2 для числа 222, сумма пяти младших разрядов числа 61₁₀=00111101₂ - 11101 и значения 2⁵mod23=9₁₀=01001 ₂, т.к. равен «1» разряд номер 6 числа 61 ₁₀=00111101₂), а через время, равное ТМ=Т ₂+max(T₅+Т₆)+T₄, на выходе 12 устройства формируется значение G₁=3₁₀ =00011₂. Так как значение частичного остатка номер 2 для числа 72, равное 26, больше, чем значение модуля L=23 (что определено при использовании компаратора 5), на выход компаратора 5 и на управляющий вход мультиплексора 4 поступает сигнал «1». В этом случае, на выход 12 устройства через мультиплексор 4 поступает разность чисел 26 и 23, равная трем, снимаемая с выхода блока 6 вычитания устройства.

По четвертому синхросигналу в первый блок 1 формирования частичных остатков заносится значение 108₁₀=01101100₂, частичный остаток номер 1 для числа 247 - во второй блок 1 формирования частичных остатков, а частичный остаток номер 2 для числа 222 - в параллельный шестиразрядный регистр 2. Через время ТЗ, на выходе 18 первого блока 1 формирования частичных остатков образуется значение 39₁₀=100111 ₂ (частичный остаток номер 1 для числа 247), на выходе 18 второго блока 1 формирования частичных остатков - значение 40₁₀=101000₂ (частичный остаток номер 2 для числа 222), а на выходе 12 устройства, через время ТМ, формируется значение - G₂=15₁₀=01111₂. Так как значение частичного остатка номер 2 для числа 222 будет меньше, чем значение модуля L=23, то на выход 12 устройства поступает значение, занесенное в параллельный шестиразрядный регистр 2, через мультиплексор 4, по управляющему сигналу, равному «0» и поступающему с выхода компаратора 5.

Пятый синхросигнал определяет моменты занесения в первый блок 1 формирования частичных остатков значения 255₁₀=11111111₂, частичного остатка номер 1 для числа 108 - во второй блок 1 формирования частичных остатков и частичного остатка номер 2 для числа 247 - в шестиразрядный параллельный регистр 2. Через время ТЗ, на выходе 18 первого блока 1 формирования частичных остатков устанавливается значение 39₁₀=100111₂ (частичный остаток номер 1 для числа 108), на выходе 18 второго блока 1 формирования частичных остатков - значение 16₁₀=00010000₂ (частичный остаток номер 2 для числа 247), а через время ТМ, на выходе 12 устройства устанавливается значение G₃ =17₁₀=10001₂.

По синхросигналу номер 6 во второй блок 1 формирования частичных остатков заносится частичный остаток номер 1 для числа 255, а в параллельный шестиразрядный регистр 2 - частичный остаток номер 2 для числа 108. Через время ТЗ, на выходе 18 второго блока 1 формирования частичных остатков устанавливается значение 25₁₀=00011001₂ , а на выходе 12 устройства, через время ТМ,-значение G₄ =16₁₀=10000₂.

По седьмому синхросигналу в параллельный шестиразрядный регистр 2 заносится частичный остаток номер 2 для числа 255. Через время ТМ на выходе 12 устройства устанавливается значение G₅=2₁₀ =00010₂.

1. Устройство для формирования остатков по заданному модулю, содержащее Т блоков формирования частичных остатков с информационным входом на n разрядов, входом первичных остатков на (n-p-1)·(p+1) разряд, входом инициализации, синхровходом и выходом на (p+q) разрядов соответственно, где Т - максимальное количество однотипных операций, требуемых для формирования остатков чисел по (p+1)-разрядному модулю, (p+1)<n, n - разрядность чисел, q=[log₂ (n-p)], отличающееся тем, что в него введены два параллельных (p+2)- и (p+1)-разрядных регистра с синхровходом, входом и выходом данных соответственно, мультиплексор с двумя входами данных, управляющим входом и выходом, компаратор с двумя входами и выходом, блок вычитания с входами уменьшаемого и вычитаемого, а также с выходом разности, причем синхровходы блоков формирования частичных остатков соединены с синхровходом устройства, входы инициализации и первичных остатков блоков формирования частичных остатков соединены с входами инициализации и первичных остатков устройства соответственно, информационный вход первого из блоков формирования частичных остатков является входом чисел устройства, выход t-го блока формирования частичных остатков соединен с информационным входом (t+1)-го блока формирования частичных остатков, где , вход данных (p+2)-разрядного параллельного регистра соединен с выходом T-го блока формирования частичных остатков, его синхровход является синхровходом устройства, а его выход соединен с первым входом данных мультиплексора, с первым входом компаратора и с входом уменьшаемого блока вычитания; вход данных (p+1)-разрядного регистра с синхровходом является входом модуля устройства, его синхровход - входом инициализации устройства, а выход (p+1)-разрядного регистра с синхровходом соединен с вторым входом компаратора и входом вычитаемого блока вычитания; второй вход данных мультиплексора связан с выходом разности блока вычитания, а его управляющий вход - с выходом компаратора, выход мультиплексора является выходом устройства.

2. Устройство для формирования остатков по заданному модулю по п.1, отличающееся тем, что t-й блок формирования частичных остатков, где , содержит параллельный n-разрядный регистр с синхровходом, а также входом и выходом данных соответственно, (n-p-1) параллельных (p+1)-разрядных регистров с синхровходом, входом и выходом данных соответственно, где (p+1) - разрядность заданного модуля, (p+1)<n, n - разрядность чисел, Т - максимальное количество однотипных операций, требуемых для формирования остатка числа по (p+1)-разрядному модулю, (n-p-1) буферных элементов с управляющим входом и (p+1)-разрядными входом и выходом данных соответственно, а также комбинационный сумматор с (n-p) (p+1)-разрядными входами и (p+q)-разрядным выходом, причем вход данных параллельного n-разрядного регистра является информационным входом блока формирования частичных остатков, а его синхровход - синхровходом блока формирования частичных остатков, (p+1) разрядов с его выхода данных соединены с первым входом комбинационного сумматора, а его s-й выход связан с управляющим входом (s-p)-го буферного элемента, где ; вход данных (s-p)-го (p+1)-разрядного регистра соединен с (s-p)-м элементом входа первичных остатков блока формирования частичных остатков, который является входом значения b_s =2^smodL соответственно, его синхровход - входом инициализации блока формирования частичных остатков, а его выход-входом данных (s-p)-го буферного элемента, где ; выходы данных каждого из (s-p)-х буферных элементов соединены с входами комбинационного сумматора под номерами (s-p+1), где , соответственно, выход комбинационного сумматора является выходом блока формирования частичных остатков.