УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ЗАДАННОМУ МОДУЛЮ Российский патент 2011 года по МПК G06F7/72 H03M7/18 

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

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

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

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

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

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

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

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

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

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

На фиг.2 представлен t-й блок 1 формирования частичных остатков, , который включает параллельный n-разрядный регистр 13 с синхровходом, входом и выходом данных, (n-p-1) параллельных (р+1)-разрядных регистров 14 с синхровходом, входом и выходом данных соответственно, (n-p-1) буферных элементов 15 с управляющим входом и (р+1)-разрядными входом и выходом данных соответственно, а также комбинационный сумматор 16 с (n-p) (р+1)-разрядными входами и (p+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, H03M 7/18, 20.05.2008). Величина z=2^s, , сравнивается со значением модуля L. Если z≥L, то из z вычитается значение модуля L, а полученное в результате значение z₁=z-L вновь сравнивается со значением L. Если и в этом случае значение z₁≥L, то из z₁ вновь вычитается значение L, а полученное в результате значение z₂=z₁-L сравнивается со значением L. Данные операции производятся до тех пор, пока значение z_y, полученное на этапе 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+l-1] на основе числа А заданной разрядности n и заданной величины модуля L, A∈[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) Т раз остаток G определяется на основе q∈[0,2^p+1-1] по формуле:

Таблица. Количество значений А, А∈[L+1,2ⁿ-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·10³ ~32,5·10³ ~23,6·10³ 0 0 24 4127 ~734·10³ ~7,44·10⁶ ~8,45·10⁶ ~147·10³ 0

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

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

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

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

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

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

Порядок функционирования устройства отображен на примере нахождения остатков от деления по модулю 23 для потока из пяти чисел, представленных байтами (8 разрядов) - 72, 222, 247, 108, 255 или 01001000, 11011110, 11110111, 01101100, 11111111 соответственно. Для данного потока восьмиразрядных чисел величина Т=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₂), а через время, равное ТМ=T₂+max(T₅+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 устройства через время TM формируется значение 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₂.

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

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

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