УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ЗАДАННОМУ МОДУЛЮ

Полезная модель относится к вычислительной технике и может быть использована в цифровых вычислительных устройствах для формирования кодовых последовательностей.
Известно устройство для формирования остатка по модулю от числа, содержащее два элемента задержки, элемент запрета, с первого по третий регистры, блок элементов И, группу блоков элементов И, комбинационный сумматор по модулю (см. патент РФ №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).
Недостатком данного устройства является низкое быстродействие при вычислении остатков по модулю для потока чисел, так как формирование частичного остатка и выполнение операций умножения и сложения по модулю производится заново для каждого из чисел в потоке, кроме того, вычисление остатка по модулю для очередного числа в потоке не может быть начато до тех пор, пока не завершено вычисление остатка по модулю для предыдущего числа. Эти недостатки устранены в предлагаемом устройстве.
Техническим результатом предлагаемой полезной модели является повышение быстродействия формирования остатков по заданному модулю для потока чисел за счет конвейеризации процесса вычисления частичных и итоговых остатков.
2
Технический результат в устройстве для формирования остатков по заданному модулю, содержащем Т блоков формирования частичных остатков с информационным входом на 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)-разрядного регистра с синхровходом соединен с вторым входом компаратора и входом вычитаемого блока вычитания; второй вход данных мультиплексора связан с выходом разности блока вычитания, а его управляющий вход - с выходом компаратора, выход мультиплексора является выходом устройства.
s
s
Блок формирования частичных остатков содержит параллельный 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=2modL, соответственно, его синхровход - входом инициализации блока формирования частичных остатков, а его выход - входом данных (s-р)-го буферного элемента, ; выходы данных каждого из (s-р)-х буферных элементов соединены с входами комбинационного сумматора под номерами (s-p+1), , соответственно, выход комбинационного сумматора является выходом блока формирования частичных остатков.
Схема устройства для формирования остатков по заданному модулю изображена на фиг.1, а схема блока формирования частичных остатков - на фиг.2.
s
s
Устройство для формирования остатков по заданному модулю содержит T блоков 1 формирования частичных остатков, параллельные (p+2)- и (p+1) -разрядные регистры 2 и 3 с синхровходом, входом и выходом данных соответственно, мультиплексор 4 с двумя входами данных, управляющим входом и выходом, компаратор 5 с двумя входами и выходом, блок 6 вычитания с входами уменьшаемого и вычитаемого, а также с выходом разности. Вход 7 является входом чисел устройства - n-разрядных чисел А, вход 8 - синхровходом устройства, вход 9 - входом модуля устройства, (р+1)-разрядного модуля L, вход 10 - входом инициализации устройства, а вход 11 - входом первичных остатков b=2modL устройства, . Выход 12 является выходом устройства, на который поступают значения остатков - G.
s
На фиг.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, , соответственно. Информационный вход 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
p+1
s
Значение p выбирается из условия: (2<L)&(2>L). Величина g есть сумма первичных остатков (3), каждый из которых является слагаемым, если a=1, , при этом А≡gmodL, и А≡GmodL.
s
s
1
1
1
2
1
y
y
s
s
При формировании первичных остатков согласно (3) на этапе предварительной подготовки данных используется следующая процедура (см. патент РФ №2324972, кл. G06F 7/72, Н03М 7/18, 20.05.2008). Величина z=2, , сравнивается со значением модуля L. Если z≥L, то из z вычитается значение модуля L, а полученное в результате значение z=z-L вновь сравнивается со значением L. Если и в этом случае значение z≥L, то из z вновь вычитается значение L, а полученное в результате значение z=z-L сравнивается со значением L. Данные операции производятся до тех пор, пока значение z, полученное на этапе у, не станет меньше значения модуля L. В этом случае значение z является первичный остаток b. Если уже на первом этапе z<L, то в качестве b принимаем значение z=2.
В прототипе (см. см. патент РФ №2324972, кл. G06F 7/72, H03M 7/18, 20.05.2008) процедура (3) реализуется аппаратно, на каждой ступени. Это требует дополнительных затрат и не позволяет реализовать вычисления на каждой ступени независимо для потока чисел.
p+1
n
p+1
p+1
Количество выполняемых операций вида (2) - t, требуемых для получения частичного остатка g∈[0,2-1] на основе числа А заданной разрядности n и заданной величины модуля L, А∈[L+1,2-1], определяется путем непосредственного машинного подсчета. Приведем пример, для чисел А разрядности n=8, 16 и 24, для которых L принимают значения 23, 263 и 4127 соответственно. Количество значений А, для которых частичный остаток g∈[0,2-1] при заданной величине модуля L вычисляется за t операций вида (2), , приведено в таблице. При этом величина Т - максимальное значение t для заданного n, принимает значение 2, 2 и 3 для n=8, 16 и 24 соответственно. Затем, после выполнения операций (2) T раз, остаток G определяется на основе g∈[0,2-1] по формуле:
Таблица. Количество значений A, A∈[L+1,2<sup>n</sup>-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<sup>3</sup>
~32,5·10<sup>3</sup>
~23,6·10<sup>3</sup>
0
0
24
4127
~734·10<sup>3</sup>
~7,44·10<sup>6</sup>
~8,45·10<sup>6</sup>
~147·10<sup>3</sup>
0
За счет вычисления первичных остатков на этапе предварительной подготовки данных согласно (3), а также параллельного вычисления значений частичных остатков g и G для различных чисел в потоке согласно (2) и (4) соответственно, достигается повышение производительности выполнения операции формирования остатков по заданному модулю L для потока чисел.
Технический результат выражен в увеличении производительности выполнения операции формирования остатков по заданному модулю для потока чисел путем конвейеризации процесса вычисления частичных и итоговых остатков на основе значений первичных остатков, полученных на этапе предварительной подготовки данных.
s
Значение числа а, поступившее на вход 7 чисел устройства, который является информационным входом 17 блока 1 формирования частичных остатков, по синхросигналу 8, поступившему на синхровход параллельного n-разрядного регистра 13, заносится в данный регистр. При этом (p+1) разрядов числа, занесенного в параллельный n-разрядный регистр 13, с номерами s, , поступают на первый вход комбинационного сумматора 16, а каждый s-й разряд из параллельного n-разрядного регистра 13 поступает на управляющий вход (s-р)-го буферного элемента 15 соответственно, . На этапе инициализации, в (s-р)-е параллельные (р+1)-разрядные регистры 14 через вход 11 первичных остатков по сигналу инициализации, подаваемому на вход 10 инициализации устройства, заносятся значения первичных остатков b, , соответственно, которые затем с выхода (s-p)-го параллельного (р+1)-разрядного регистра 14 поступают на вход (s-p)-го буферного элемента 15, , соответственно. Значения с выхода (s-p)-го буферного элемента 15 поступают на (s-p+1)-й вход комбинационного сумматора 16, , соответственно. На выход 18 блока 1 формирования частичных остатков, который является также выходом комбинационного сумматора 16, поступает (p+q)-разрядное значение частичного остатка g, вычисленного согласно (2).
s
На этапе инициализации по сигналу инициализации, подаваемому на вход 10 инициализации устройства, в параллельный (р+1)-разрядный регистр 3 (через (р+1)-разрядный вход 9 модуля устройства) заносится значение модуля L, а в параллельный (р+1)-разрядный регистр 14 (через (р+1)-разрядный вход 11 первичных остатков) - значение первичных остатков b, , соответственно.
На этапе функционирования на 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).
1
2
N
1
2
N
13
15
16
2
5
6
4
i
Вычисления N значений остатков по заданному модулю L-G, G, …, G для потока чисел А, A, …, A требует (N+Т) тактов работы устройства, причем время задержки выполнения операций на одном такте определяется как max(T+T+Т,Т+max(T+Т)+Т), где T - время задержки функционирования i-го блока на фиг.1 и 2.
5
6
7
6
10
2
10
2
13
15
16
10
2
10
2
10
2
10
2
Порядок функционирования устройства отображен на примере нахождения остатков от деления по модулю 23 для потока из пяти чисел, представленных байтами (8 разрядов) - 72, 222, 247, 108, 255 или 01001000, 11011110, 11110111, 01101100, 11111111 соответственно. Для данного потока восьмиразрядных чисел величина T=2. В устройстве два блока 1 формирования частичных остатков выполняют операции вида (2), а мультиплексор 4, компаратор 5 и блок 6 вычитания, выполняют операции согласно (4). При инициализации устройства по сигналу инициализации, подаваемому на вход 10 устройства, в три параллельных пятиразрядных регистра 14 через вход 11 первичных остатков заносятся значения первичных остатков: 2mod23=9, 2mod23=18 и 2mod23=13, а в параллельный пятиразрядный регистр 3 заносится значение модуля, равное 23=10111. По первому синхросигналу в параллельный пятиразрядный регистр 13 первого блока 1 формирования частичных остатков заносится значение 72=01001000 (с входа 7 чисел устройства). На выходе 18 первого блока 1 формирования частичных остатков, через время ТЗ=Т+Т+Т, формируется шестиразрядный частичный остаток по модулю 23, (частичный остаток номер 1 для числа 72), равный значению 26=011010 и поученный как сумма пяти младших двоичных разрядов числа 72=01001000 - 01000, а также первичного остатка 2mod23=18=10010 (т.к. разряд номер 7 числа 72=01001000 равен «1»).
10
2
10
2
10
2
10
2
10
2
10
2
10
2
10
2
10
2
6
7
По второму синхросигналу, в первый блок 1 формирования частичных остатков заносится значение 222=11011110, а во второй блок 1 формирования частичных остатков - частичный остаток номер 1 для числа 72, величина 26=00011010 (на два старших разряда входа второго блока 1 формирования частичных остатков поступают значения «0» как константы), и, через время ТЗ, на выходе 18 первого блока 1 формирования частичных остатков формируется значение частичного остатка номер 1 для числа 222 - значение 61=111101 (сумма пяти младших разрядов числа 222=11011110 - 11110, числа 2mod23=18=10010 и числа 2mod23=13=01101, так как разряды под номерами 7 и 8 числа 222=11011110 равны «1»). На выходе 18 второго блока 1 формирования частичных остатков формируются значение частичного остатка номер 2 для числа 72, значение 26=011010 (пять младших разрядов числа 26=00011010 - 11010, старший разряд выхода 18 блока 1 формирования частичных остатков остается равным «0»).
10
2
10
2
10
2
10
2
10
2
10
2
10
2
10
2
10
2
10
2
10
2
2
5
6
4
1
10
2
5
6
7
5
Третий синхросигнал определяет момент занесения значения 247=11110111 в первый блок 1 формирования частичных остатков, частичного остатка номер 1 для числа 222 - во второй блок 1 формирования частичных остатков и частичного остатка номер 2 для числа 72 - в параллельный шестиразрядный регистр 2. Через время ТЗ, на выходе 18 первого блока 1 формирования частичных остатков формируется значение 63=111111 (частичный остаток номер 1 для числа 247, сумма пяти младших разрядов числа 247=11110111 - 10111, числа 2mod23=9=01001, значения 2mod23=18=10010 и числа 2mod23=13=01101, т.к. разряды под номерами 6, 7 и 8 числа 247=11110111 равны «1»), на выходе 18 второго блока 1 формирования частичных остатков формируется значение 38=100110 (частичный остаток номер 2 для числа 222, сумма пяти младших разрядов числа 61=00111101 - 11101 и значения 2mod23=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 вычитания устройства.
10
2
10
2
10
2
2
10
2
По четвертому синхросигналу в первый блок 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.
10
2
10
2
10
2
3
10
2
Пятый синхросигнал определяет моменты занесения в первый блок 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.
10
2
4
10
2
По синхросигналу номер 6 во второй блок 1 формирования частичных остатков заносится частичный остаток номер 1 для числа 255, а в параллельный шестиразрядный регистр 2 - частичный остаток номер 2 для числа 108. Через время ТЗ, на выходе 18 второго блока 1 формирования частичных остатков устанавливается значение 25=00011001, а на выходе 12 устройства, через время ТМ,-значение G=16=10000.
5
10
2
По седьмому синхросигналу в параллельный шестиразрядный регистр 2 заносится частичный остаток номер 2 для числа 255. Через время ТМ на выходе 12 устройства устанавливается значение G=2=00010.