Комбинационный рекуррентный формирователь остатков

 

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

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

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

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

Целью изобретения является повышение надежности функционирования за счет уменьшения объема оборудования.

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

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

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

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

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

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

Блок 3 сумматоров по модулю содержит сумматоры 9 по произвольному модулю. Каждый сумматор 9 содержит (фиг.2) последовательно соединенные комбинационный сумматор 10 и узел 11 формирования частичных остатков. В состав узла формирования частичных остатков (фиг.3) входят сумматор 12 и мультиплексор 13.

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

В исходном состоянии (фиг.1) на вход 4 модуля подается инверсный код модуля Р_j, по которому необходимо формировать остатки. Так как на вход первого узла 7 формирования частичных остатков подается код единицы, а выходы разрядов предыдущего узла формирования подключены к входам последующего узла формирования со сдвигом на один разряд в сторону старших, то на выходах формирователя 1 формируются частичные остатки по модулю Р_j от числа 2ⁱ, i = .

Число А_k через вход 5 поступает на управляющие входы блока 2 ключей. В зависимости от того на управляющий вход какого из ключей 8 поступает логическая "1", тот из ключей 8 оказывается открытым и коммутирует на свои выходы значения с информационных входов, на которые с информационных выходов формирователя 1 поступают частичные остатки по модулю Р_j. В результате на соответствующие входы блока 3 сумматоров по модулю поступают остатки от чисел 2ⁱ для тех i, для которых коэффициент а_i = 1 в представлении (1) числа A_k, записанного в формирователь 1. Блок 3 сумматоров по модулю суммирует по модулю Р_j частичные остатки, и результат суммирования выдается на информационные выходы 6 формирователя.

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

Для смены модуля на вход 4 формирователя подается очередной модуль Р_х, узлы 7 формирования формирователя 1 формируют частичные остатки от чисел 2ⁱ, а с подачи очередного числа А_m работа элементов и блоков формирователя повторяется.

Блок 3 сумматоров по модулю работает следующим образом. На управляющие входы каждого сумматора 9 поступает значение модуля в инверсном виде, а на информационные входы первого сумматора 9 поступают остатки от чисел 2⁰ и 2¹, если коэффициенты а₀ и а₁ при представлении (1) числа А равны единице. Результат суммирования поступает на вторые информационные входы второго сумматора, на первые информационные входы которого поступает остаток от числа 2² по модулю, если коэффициент а₂ = 1, и т.д. до тех пор, пока результат суммирования по модулю частичных остатков не появится на выходе последнего сумматора 9 по произвольному модулю. Этот результат и поступает на выход 6 формирователя. Время формирования остатка равно времени распространения сигнала с первого по последний сумматор 9 по произвольному модулю.

Сумматор 9 по произвольному модулю (фиг.2) работает следующим образом. Комбинационный сумматор 10 осуществляет суммирование остатков, поступающих на его информационные входы, а узел 11 формирования частичных остатков в зависимости от значения инверсного кода модуля, поступающего на его вход 4, приводит по модулю значение суммы.

Узел 7 (11) формирования остатков (фиг.3) работает следующим образом. Сумматор 12, на разряд переноса которого постоянно подан уровень логической "1", за счет подачи на его вход 4 кода модуля в инверсном виде выполняет функцию вычитания модуля из числа. Если поступившее на информационный вход сумматора 12 число меньше кода модуля, то на управляющем выходе (выходе переноса) остается нулевой потенциал и вторые информационные входы мультиплексора 13 остаются скоммутированными на его информационные выходы, и код числа поступает на выход формирователя без изменений. Если код числа меньше или равен коду модуля, то на выходе переноса сумматора 12 появляется единичный потенциал, который коммутирует первые входы мультиплексора 13 с его информационными выходами, и код разности поступает на выход мультиплексора 13.

Формула изобретения

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

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

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

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3