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

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

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

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

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

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

В рекуррентный формирователь остатков по производному модулю, содержащий блок сумматоров, элемент задержки и регистр, выходы которого соединены с управляющими входами блока ключей, введены блок формирования частичных остатков и инвертор, а блок сумматоров выполнен в виде ярусов из N - 1 сумматоров по произвольному модулю, количество которых в каждом ярусе равно N/2ⁱ, где i - номер яруса блока, а N - разрядность входного числа формирователя, при этом первый и второй информационные входы сумматоров по произвольному модулю первого яруса являются информационными входами блока сумматоров, выходы сумматоров по произвольному модулю i-го яруса, кроме последнего, соединены соответственно с первыми и вторыми информационными входами сумматоров по произвольному модулю (i + 1)-го яруса, выход сумматора по произвольному модулю последнего яруса является выходом блока сумматоров, а третьи и четвертые информационные входы всех сумматоров по произвольному модулю соединены соответственно с входами прямого и инверсного значений модуля блока сумматоров, причем информационный вход формирователя соединен с информационным входом регистра, вход записи которого соединен с входом начала вычислений формирователя и входом элемента задержки, выход которого является выходом конца вычислений формирователя, вход модуля которого соединен с входом инвертора, первыми входами блока формирования частичных остатков и входом прямого значения модуля блока сумматоров, вход инверсного значения модуля которого соединен с выходом инвертора и вторыми входами блока формирования частичных остатков, выходы которого соединены с информационными входами блока ключей, выходы которого соединены с информационными входами блока сумматоров, выход которого является информационным выходом формирователя.

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

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

Формирователь частичных остатков содержит элемент ИЛИ, ключ, а также последовательно соединенные первый и второй сумматоры, причем второй вход второго сумматора соединен с выходом ключа, управляющий вход которого соединен с выходом элемента ИЛИ, а выход второго сумматора является информационным выходом формирователя, вход модуля соединен с информационным входом ключа, а вход модуля в инверсном виде - с первым входом первого сумматора, второй вход которого является информационным входом формирователя, разряд переноса соединен с первым входом элемента ИЛИ, второй вход которого соединен с выходом переноса первого сумматора, на вход переноса которого подается уровень логической "1".

Известно, что позиционные системы счисления строятся следующим образом. Выбирается некоторое число m - основание системы счисления, и каждое число А представляется в виде комбинации его степеней с коэффициентами a_i, i = , принимающими значения от 0 до m - 1. Для случая двоичной системы счисления (m = 2) всякое число А можно представить в виде
A = a_N2^N + a_N-12^N-1 + . . . + a₁2¹ + a_o, (1) где a_i, i = принимают значение "0" или "1".

Для вычисления остатка от числа А по модулю Р достаточно в выражении (1) просуммировать частичные остатки по модулю Р от чисел 2ⁱдля тех i, для которых коэффициент a_i = 1. Способ вычисления частичных остатков состоит в следующем. Частичный остаток от 2^о для любого модуля (Р ≥2) всегда равен единице. Частичный остаток от 2¹ в два раза превышает (с учетом операции приведения по модулю) частичный остаток от 2^о и т. д. , т. е. частичный остаток от 2ⁱ в два раза превышает частичный остаток от 2^i-1. Таким образом, вычисление частичного остатка от 2ⁱзаключается в умножении на два частичного остатка от 2^i-1 и приведения результата по модулю Р. Операция приведения по модулю Р для чисел, не превышающих величину 2Р - 1, реализуется следующим образом. Если значение частичного остатка не превышает величину Р, то оно остается без изменения, если число лежит в интервале от Р до 2Р - 1, то из него вычитается модуль Р, а результат является остатком. Операции умножения на два (как видно из выражения (1)) может быть реализована сдвигом всех разрядов умножаемого числа на один влево либо подачей разрядов множимого на выход результата, в такой последовательности: 2ⁱ разряд множимого на 2ⁱ⁺¹ разряд произведения, i = .

На фиг. 1 представлена функциональная электрическая схема рекуррентного формирователя остатков по произвольному модулю; на фиг. 2 - блока формирования частичных остатков; на фиг. 3 - блока ключей; на фиг. 4 - блока сумматоров по модулю; на фиг. 5 - сумматора по модулю; на фиг. 6 - формирователя частичных остатков.

Формирователь содержит (фиг. 1) регистр 1, блок 2 ключей, инвертор 3, блок 4 формирования частичных остатков, блок 5 сумматоров и элемент 6 задержки. Число А, от которого необходимо сформировать остаток, подается на вход 7 устройства. Вход 8 начала вычисления соединен с входом записи регистра 1 и входом элемента 6 задержки. Вход 9 модуля соединен с первыми информационными входами блока 4 формирования частичных остатков, блока 5 сумматора по модулю и с входами инвертора 3. Выход 10 блока 5 является информационным, а выход 11 элемента 6 задержки - выходом окончания процесса формирования остатка.

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

Блок 2 ключей (фиг. 3) содержит N ключей 13, на информационные входы которых подаются коды с выходов формирователей 12, управляющие входы соединены с информационными выходами регистра 1, а информационные выходы являются информационными выходами блока.

Блок 5 сумматоров содержит (фиг. 4) сумматоры 14 по произвольному модулю. На каждый сумматор 14 подается код модуля в прямом и в инверсном виде. Каждый сумматор 14 содержит (фиг. 5) последовательно соединенные комбинационный сумматор 15, информационные входы которого являются информационными входами сумматора 14, и формирователь 16 частичных остатков. В состав формирователя частичных остатков (фиг. 6) входит первый 17 и второй 18 сумматоры, элемент ИЛИ 19 и ключ 20.

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

В исходном состоянии на вход 9 модуля подается код модуля P_j, по которому необходимо формировать остатки. Поэтому на первые входы блоков 4 и 5 подается код модуля в прямом, а на вторые входы через инвертор 3 - в инверсном виде. Так как на вход первого формирователя 12 частичных остатков подается код единицы, а выходы разрядов предыдущего формирователя подключены на входы последующего формирователя со сдвигом на один разряд влево, на выходах блока 4 сформированы частичные остатки по модулю P_j от чисел 2ⁱ, i = .

Число А через вход 7 поступает на информационные входы регистра 1. Одновременно на вход 8 начала вычисления подается импульс, который поступает на вход элемента 6 задержки и на вход записи регистра 1. Поэтому код числа А записывается в регистр 1, появляется на его информационных выходах и поступает на управляющие входы блока 2 ключей. В зависимости от того, на управляющий вход какого из ключей 13 поступает логическая "1", тот из ключей 13 оказывается открытым и коммутирует на свои выходы значения с информационных входов, на которые с информационных выходов блока 2 поступают частичные остатки по модулю Р. В результате на соответствующие входы блока 5 сумматоров поступают остатки от чисел 2ⁱ для тех i, для которых коэффициент a_i = 1 в представлении (1) числа А, записанного в регистр 1. Блок 5 сумматоров суммирует по модулю P_j частичные остатки и результат суммирования выдается на информационный выход 10 устройства. Одновременно с выхода элемента 6, время задержки которого равно времени работы блоков 2 и 5, на выход 11 поступает импульс, сигнализирующий об окончании процесса формирования остатка.

При следующем цикле формирования остатка задается любое другое число А, которое поступает на вход 7, и работа всех элементов и блоков устройства повторяется.

Для смены модуля на вход 9 устройства подается очередной модуль P_j, формирователи 12 блока 4 формируют частичные остатки от чисел 2ⁱ, а с подачей очередного числа А работа элементов и блоков устройства повторяется.

Блок 5 сумматоров работает следующим образом. На управляющие входы каждого сумматора 14 блока 5 поступает значение модуля в прямом и инверсном виде, а на информационные входы сумматоров 14 первого ряда поступают остатки от чисел 2ⁱ для тех i, для которых a_i = 1. Остатки от суммирования по модулю попарно поступают на второй ряд сумматоров и т. д. , поэтому остаток от суммирования по модулю оказывается на выходах блока 5 и поступает на информационный выход 10 устройства.

Сумматор 14 по произвольному модулю работает следующим образом. Комбинационный сумматор 15 осуществляет суммирование остатков, поступающих на его информационные входы, а формирователь 16 частичных остатков в зависимости от значений кода модуля в прямом и инверсном виде, поступающих на его входы, приводит по модулю значение суммы.

Формирователь 12 (16) частичных остатков работает следующим образом. Сумматор 17, на разряд переноса которого постоянно подан уровень логической "1", за счет подачи на его вход кода модуля в инверсном виде выполняет функцию вычитания модуля из числа А, старший разряд которого подается на вход элемента ИЛИ 19. Если разность меньше нуля, то сумматор 18 добавляет к этой разности код модуля (т. е. входное число было меньше модуля), если разность больше нуля, то ключ 20, на вход которого подается код модуля, оказывается закрытым и эта разность поступает на выход без изменения через сумматор 18 формирователя. Таким образом, на выходе формирователя 12 частичных остатков сформирован остаток от числа, воздействующего на его входы, по модулю Р. (56) Авторское свидетельство СССР N 1396281, кл. H 03 M 7/18, 1986.

Авторское свидетельство СССР N 1633495, кл. H 03 M 7/18, 1989.

Изобретение относится к вычислительной технике и может быть использовано в устройствах для формирования элементов конечных полей, в устройствах для формирования кодовых последовательностей, построение которых основывается на теории конечных полей, а также в устройствах, функционирующих в СОК. Рекуррентный формирователь остатков по произвольному модулю содержит регистр, блок ключей, инвертор, блок формирования частичных остатков, блок сумматоров и элемент задержки, соединенные между собой функционально. 3 з. п. ф-лы, 6 ил.

1. РЕКУРРЕНТНЫЙ ФОРМИРОВАТЕЛЬ ОСТАТКОВ ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ, содержащий блок сумматоров, элемент задержки и регистр, выходы которого соединены с управляющими входами блока ключей, отличающийся тем, что в него введены блок формирования частичных остатков и инвертор, а блок сумматоров выполнен в виде ярусов из N - 1 сумматоров по произвольному модулю, количество которых в каждом ярусе равно N/2ⁱ, где i - номер яруса блока, а N - разрядность входного числа формирователя, первый и второй информационные входы сумматоров по произвольному модулю первого яруса являются информационными входами блока сумматоров, выходы сумматоров по произвольному модулю i-го яруса, кроме последнего, соединены соответственно с первыми и вторыми информационными входами сумматоров по произвольному модулю i + 1-го яруса, выход сумматора по произвольному модулю последнего яруса является выходом блока сумматоров, а третьи и четвертые информационные входы всех сумматоров по произвольному модулю соединены соответственно с входами прямого и инверсного значений модуля блока сумматоров, причем информационный вход формирователя соединен с информационным входом регистра, вход записи которого соединен с входом начала вычислений формирователя и входом элемента задержки, выход которого является выходом конца вычислений формирователя, вход модуля которого соединен с входом инвертора, первым входом блока формирования частичных остатков и входом прямого значения модуля блока сумматоров, вход инверсного значения модуля которого соединен с выходом инвертора и вторым входом блока формирования частичных остатков, информационные выходы которого соединены с информационными входами блока ключей, выходы которого соединены с информационными входами блока сумматоров, выход которого является информационным выходом формирователя. 2. Формирователь по п. 1, отличающийся тем, что блок формирования частичных остатков содержит N - 1 формирователей частичных остатков, входы прямого значения модуля которых соединены с первым входом блока формирования частичных остатков, второй вход которого соединен с входами инверсного значения модуля N - 1 формирователей частичных остатков, выход i-го формирователя частичных остатков, где i = 1, N - 1, является i-м информационным выходом блока формирования частичных остатков и соединен с информационным входом (i + 1)-го формирователя частичных остатков, информационный вход первого формирователя частичных остатков и первый выход блока формирования частичных остатков соединены с шиной кода единицы. 3. Формирователь по п. 1, отличающийся тем, что сумматор по произвольному модулю содержит последовательно соединенные комбинационный сумматор и формирователь частичных остатков, причем входы комбинационного сумматора являются первым и вторым информационными входами сумматора по произвольному модулю, выход которого соединен с выходом формирователя частичных остатков, входы прямого и инверсного значений модуля которого являются соответственно третьим и четвертым информационными входами сумматора по произвольному модулю. 4. Формирователь по пп. 2 и 3, отличающийся тем, что формирователь частичных остатков содержит последовательно соединенные сумматоры, элемент ИЛИ и ключ, причем вход прямого значения модуля формирователя частичных остатков соединен с информационным входом ключа, выход которого соединен с вторым входом второго комбинационного сумматора, выход которого является выходом формирователя частичных остатков, вход инверсного значения модуля которого соединен с первым входом первого комбинационного сумматора, второй вход которого соединен с информационным входом формирователя частичных остатков, разряд переноса которого соединен с первым входом элемента ИЛИ, второй вход которого соединен с выходом переноса первого комбинационного сумматора, вход переноса которого соединен с шиной логической единицы, а выход элемента ИЛИ - с управляющим входом ключа.