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

 

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

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

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

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

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

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

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

Известно также, что сравнения можно почленно складывать, т. е.

A₁ ≡ B₁(modP), A₂ ≡ B₂(modP) . . . A_k ≡ B_k(modP), тогда справедливо следующее выражение: A₁ + A₂ + . . . A_k ≡ B₁ + B₂ + . . . + + B_k (nodP). (3) Учитывая выражения (2) и (3), можно записать (a_k2^k + a_k-12^k-1 + . . . a₁2 + a_o)modP ≡ a_k2^k(mod P) + a_k-12^k-1(modP) + . . . + +a₁2(modP) + a_o(modP).

Так как для двоичной системы счисления коэффициенты a_i, i= , где k - разрядность представляемого числа А, принимают только два значения 0 или 1, то, суммируя заранее вычисленные остатки по модулю Р от чисел 2ⁱ, i= , для тех i, для которых коэффициенты ai = 1, получают остаток по модулю Р от числа А. Для модулей P_i, с которыми предполагается работа устройства, в постоянном запоминающем устройстве запоминаются заранее вычисленные остатки от чисел 2ⁱ, i= , где k - разрядность чисел, от которых необходимо формировать остатки.

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

Устройство содержит (фиг. 1) первый регистр 1, информационные входы которого являются входами кода числа, последовательно соединенные блок 2 постоянной памяти, группу 3 блоков элементов И, блок 4 сумматоров по произвольному модулю и второй регистр 5, а также элемент 6 задержки и блок 7 инверторов. Код модуля подается на адресный вход блока 2 постоянной памяти, на первые входы блока 4 сумматоров по произвольному модулю и вход блока 7 инверторов, выходы которого соединены с вторыми входами блока 4 сумматоров по произвольному модулю. Вход начала вычисления соединен с входами элемента 6 задержки, входом разрешения записи блока 2 постоянной памяти и входом разрешения записи регистра 1, информационные выходы которого подсоединены к вторым входам группы 3 блоков элементов И, а выход элемента 6 задержки соединен с управляющим входом второго регистра 5, информационные выходы которого являются информационными выходами устройства, и является управляющими выходами устройства.

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

Сумматор 8 по произвольному модулю содержит (фиг. 3) первый 9 и второй 10 комбинационные сумматоры, схему 11 сравнения и мультиплексор 12. На вход переноса сумматора 10 подан код единицы.

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

В исходном состоянии регистры 1 и 5 обнулены. В блоке 2 постоянной памяти 2 предварительно записаны заранее вычисленные остатки от чисел 2ⁱ, i= , где k - максимальная разрядность числа A_k, по модулям P_j, с которыми предполагается работа устройства. Модуль P_i, по которому осуществляется формирование остатков чисел, задается параллельным двоичным кодом, подаваемым на вход модуля устройства. На информационные входы регистра 1 поступает число A_k в параллельном двоичном коде. После подачи кодов числа A_k и модуля P_i на входы устройства на вход "Начало вычисления" подается импульс, который, поступая на вход записи регистра 1, записывает в него код числа A_k и поступает на вход разрешения чтения блока 2. В результате на выходе блока 2 появляются остатки от чисел 2ⁱ, i= по модулю P_i. Импульс с входа "Начало вычисления" поступает также на вход элемента 6 задержки. Одновременно с информационных выходов регистра 1 на группу 3 блоков элементов И поступает код числа A_k, открывая те блоки группы, на которые поступает единица. В результате на соответствующие входы блока 4 сумматоров поступают остатки от чисел 2ⁱ, i= , для тех i, для которых a_i = 1 для числа A_k. На управляющие входы блока 4 поступает значение модуля в прямом и инверсном коде. Блок 4 осуществляет суммирование по модулю P_i поступающих на его входы чисел, эта сумма оказывается на его выходах и поступает на информационные входы регистра 5. Время задержки элемента 6 равно времени формирования остатка, поэтому по окончанию процесса формирования остатка по заданному модулю на выходе элемента 6 задержки появляется импульс, который записывает код остатка в регистр 5 и поступает на выход окончания работы устройства.

Сумматор 8 по произвольному модулю работает следующим образом. На входы сумматора 9 подаются слагаемые в диапазоне чисел от 0 до Р - 1, на второй вход схемы 11 сравнения подается прямой код модуля Р, а на второй вход сумматора 10 - инверсный код модуля Р. Если сумма слагаемых меньше модуля Р, то на выходе "Меньше" схемы 11 сравнения появляется потенциал, который поступает на управляющий вход мультиплексора 12. Последний в результате воздействия управляющего импульса коммутирует со своим выходом свой первый вход и на выходе сумматора 8 по модулю оказывается сумма слагаемых, поступающих на его входы. Если эта сумма превышает величину модуля (или равна ей), то потенциала на управляющем входе мультиплексора 12 нет и мультиплексор 12 коммутирует со своим выходом свой второй вход. При этом на втором входе оказывается код числа, равного сумме слагаемых, поступающих на вход сумматора 8, приведенный по модулю Р.

При следующем цикле формирования остатка может быть выбран любой другой модуль Р_а и задано любое другое число А_е. (56) Авторское свидетельство СССР N 1396281, кл. H 03 M 7/18, 1986.

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

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

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

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

РИСУНКИ

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