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

 

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

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

Цель изобретения - сокращение объема оборудования.

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

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

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

Частичные остатки для всех 2ⁱ(i=) записываются в регистр. Длина регистра сдвига равна количеству ячеек памяти, занимаемых по одному адресу в блоке памяти устройства-прототипа. На практике довольно часто (например, при формировании сигнально-кодовых конструкций, кодировании и декодировании и др. ) устройство для формирования остатка формирует остатки по одному и тому же модулю (т.е. без его смены) в течение довольно большого количества циклов формирования остатков (> 10000). В таких случаях целесообразно вычислять частичные остатки по модулю Р, а не хранить их для всех возможно применяемых модулей в блоке памяти. Потери быстродействия в работе устройства при этом практически незаметны при существенном (в количество раз), равном количеству используемых модулей уменьшении оборудования блока памяти.

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

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

Блок 2 формирования остатков содержит (фиг. 2) счетчик 10, элемент 11 задержки, узел 12 формирования частичных остатков, регистр 13, 14, мультиплексоры 15, 16, генератор 17 тактовых импульсов, элемент И 18 и триггер 19.

Блок 4 суммирования по модулю содержит (фиг. 3) элемент НЕ 20 и матрицу сумматоров 21 по модуля, построенную по древовидной схеме.

Узел формирования частичных остатков (фиг. 4) содержит элемент И 22, ключ 23, элемент НЕ 24, сумматоры 25, 26.

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

В исходном состоянии (фиг. 1) на вход 8 модуля подан код модуля Р_i, по которому формируются остатки. На вход 9 подается управляющий импульс, по которому в блоке 2 происходит вычисление частичных остатков по модулю Р.

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

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

При смене модуля на вход 8 устройства подается очередной модуль Р_j, а на вход 9 - управляющий импульс, за счет чего в блоке 2 происходит вычисление частичных остатков по модулю Р_j.

Блок 2 формирования остатков работает следующим образом (фиг. 2). Управляющий сигнал, поступающий на вход 9, обеспечивает перевод триггера 19 в единичное состояние, запись единицы в счетчик 10 и в первые разряды регистров 13 и 14, а также обнуление остальных разрядов регистров 13 и 14. Единица с выхода регистра 13 поступает на вход мультиплексора 16 и на второй информационный вход узла 12 формирования частичных остатков. Перевод триггера 19 в единичное состояние обеспечивает прохождение импульсов с выхода генератора 17 тактовых импульсов через элемент И 18.

Как только в регистре 13 будет записана единица, осуществляется формирование частичного остатка в узле 12. Причем выходы регистра 13 соединены с входами узла 12 со сдвигом на один разряд влево, т.е. число на его входах всегда в 2 раза больше числа, записанного в регистре 13. Поэтому узел 12 формирует частичный остаток по модулю Рi от числа 2¹. Следовательно, первым импульсом с выхода генератора 17 в регистр 13 записывается частичный остаток по модулю Р_i от числа 2¹ и увеличивается содержимое счетчика 10 на единицу. Информационные выходы счетчика 10 подключены к адресным входам мультиплексоров 15 и 16. Поэтому на вторые выходы мультиплексора 16 поступает код частичного остатка от числа 2¹ по модулю Р_i, который поступает на информационный вход второго разряда регистра 14, а с элемента 11 задержки через мельтиплексор 15 поступает импульс записи на вход записи второго разряда регистра 14. Период тактовых импульсов генератора 17 превышает время распространения сигнала через элемент 11 задержки, мультиплексор 15 и время записи в регистр 14. По каждому тактовому импульсу осуществляются запись очередного частичного остатка в регистр 13, увеличение содержимого счетчика 10 на единицу и запись очередного частичного остатка в соответствующие разряды регистра 14. После того, как будет сформирован самый старший частичный остаток, счетчик 10 выдает на свой выход переполнения импульс (объем счетчика 10 равен количеству разрядов регистра 1), который обнуляет триггер 19 и поступает на выход 5 сигнализации об окончании формирования. Количество остатков регистра 14, выделяемых для записи одного частичного остатка, равно максимально возможной разрядности частичных остатков для используемых модулей. Поэтому на выходах регистра 14 оказываются сформированными частичные остатки от чисел 2ⁱ(i=), которые поступают на информационные входы соответствующих блоков 3 элементов И.

Блок 4 суммирования по модулю работает следующим образом (фиг. 3). На управляющие входы каждого сумматора 21 блока поступает значение модуля в прямом, а через элемент НЕ 20 в инверсном коде. Блок 4 суммирования осуществляет суммирование по модулю P, поступающих с выходов элементов И 3 частичных остатков. Эта сумма в двоичном параллельном коде оказывается на его выходах и поступает на информационные выходы устройства. Сумматор 21 по модулю может быть выполнен по схеме, описанной в книге Пухальского Г.И., Новосельцевой Т.Ч. Проектирование дискретных устройств на интегральных микросхемах: Справочник. М.: Радио и связь, 1990, с. 202-204.

Узел 12 формирования частичных остатков (фиг. 4) работает следующим образом. Сумматор 25, на разряд переноса которого постоянно подан уровень логической "1", совместно с элементом НE 24 выполняет функцию вычитания модуля из числа, старший разряд которого подается на вход элемента И 22. Если разность меньше нуля, то сумматор 26 добавляет к этой разности код модуля (т.е. входное число было меньше модуля), если разность больше нуля, то ключ 23 оказывается закрытым и эта разность поступает на выход без изменения через сумматор 26. Таким образом, на выходе узла формирования частичных остатков сформирован остаток от числа, воздействующего на его входы, по модулю Р.

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

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

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

3. Устройство по п.1, отличающееся тем, что блок суммирования по модулю содержит элемент НЕ и матрицу из n рядов сумматоров по модулю, построенную по древовидной схеме, причем первый ряд матрицы состоит из [ N/2 ] сумматоров по модулю, информационные входы которых соединены с соответствующими N входами блока, выходы сумматоров по модулю i-го ряда матрицы попарно соединены с информационными входами сумматоров по модулю (i + 1)-го ряда матрицы (i = 1, ...n - 1), выход сумматора по модулю n-го ряда матрицы соединен с выходом блока, (N + 1)-й вход которого соединен с первым управляющим входом каждого сумматора по модулю и входом элемента НЕ, выход которого соединен с вторым управляющим входом каждого сумматора по модулю.

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

РИСУНКИ

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