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

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

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

l = i_m + j K,





где К - число двоичных разрядов первого регистра;

_m - период повторения остатков по модулю m весов разрядов числа в двоичном коде,

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

Описание изобретения к патенту

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

Известное устройство (аналог) (авт. св. СССР N 1658388, кл. H 03 M 7/18, 1991), содержащее счетчик, два формирователя импульсов, пять элементов ИЛИ, элемент сравнения, вычислитель, семь регистров, три элемента И и мультиплексор.

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

Известно также устройство (аналог) (патент РФ N 2023346, кл. H 03 M 7/18, 1994), содержащее два регистра, накапливающий сумматор по модулю, генератор тактовых импульсов, счетчик, мультиплексор, триггер, два элемента И, элемент ИЛИ и элемент задержки.

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

Наиболее близким к предлагаемому по технической сущности (прототипом) является устройство (патент РФ N 2029434, кл. H 03 M 7/18, 1995), содержащее два регистра, группу элементов И, накапливающий сумматор по модулю, два дешифратора, группу ключевых элементов, два счетчика, два элемента И, два элемента ИЛИ, триггер и элемент запрета. Время выполнения формирования остатка по модулю составляет (n-_m) , где n - число двоичных разрядов числа, _m - период повторения остатков по модулю m, что обуславливает основной недостаток устройства.

Недостаток прототипа - низкое быстродействие формирования остатка ввиду того, что эта операция проводится путем последовательного (поразрядного) сдвига обрабатываемого числа в младшие разряды входного регистра. Другим недостатком прототипа является невозможность формирования остатка по произвольному модулю, а только для строго определенных модулей, таких, что

.

Рассмотрим подробнее этот вопрос, отобразив последовательность чередования остатков для модулей m = 3, 5 и 7 в ( 2-4).

.

Рассматривая функционирование прототипа при m = 5 согласно последовательности (3), можно отметить, что уже на первом цикле работы в регистр поступает число большее, чем модуль (при произвольном числе A).

В дальнейшем это несоответствие нарастает. При m = 11 сумма поразрядных модульных остатков внутри периода повторения превышает величину модуля в пять раз. Возможно при определенной величине m либо числе A устройство будет правильно функционировать, однако сомнение в этом вызывает описание работы накапливающего сумматора по модулю. В частности, комбинационный сумматор производит сложение двух двоичных чисел, число разрядов которых равно длине периода, однако, как следует из (3), например, веса двоичных разрядов числа A не соответствуют весам модульных остатков, поэтому сложение будет производиться неправильно. Это положение относится и к вычислителю. Вызывает интерес построение и функционирование в этом случае элемента сравнения. Если же предположить, что комбинационный сумматор является специализированным (этого не следует из описания прототипа) и производит поразрядную обработку числа A (с перекодировкой значений разрядных модульных остатков в двоичный код), то это обстоятельство вызывает дальнейшее уменьшение быстродействия формирования остатка и, что самое главное, обуславливает жесткую схемотехническую привязку его к модулю.

Задача, на решение которой направлено заявляемое устройство, состоит в повышении производительности перспективных образцов специализированной вычислительной техники.

Технический результат выражается в повышении быстродействия (уменьшении временных затрат) формирования остатка.

Технический результат достигается тем, что в устройство, содержащее два элемента задержки, элемент запрета, первый и второй регистры, причем информационный вход кода числа соединен с информационным входом первого регистра, вход начала вычислений устройства соединен с входом записи первого регистра, введены третий регистр, группа преобразователей кода числа единиц в код остатка по модулю, группа блоков элементов И, комбинационный сумматор по модулю и блок элементов И, причем информационный вход нулевого разряда третьего регистра соединен с входами записи третьего и первого регистров, 1-е выходы разрядов которых ; где: k - число двоичных разрядов первого регистра, _m - период повторения остатков по модулю m весов разрядов числа в двоичном виде) соединены с i-ми входами j-х преобразователей кода числа единиц в код остатка по модулю, выходы которых соединены с первыми входами соответствующих блоков элементов И группы, вторые входы которых соединены с соответствующими разрядными выходами третьего регистра, а выходы - с информационным входом первой группы комбинационного сумматора по модулю, тактовый вход устройства соединен с информационным входом элемента запрета, выход которого соединен с входом второго элемента задержки и входом сдвига третьего регистра, _m -й выход которого соединен с входом первого элемента задержки и управляющим входом элемента запрета, выходы первого и второго элементов задержки соединены соответственно с вторым входом блока элементов И и входом записи второго регистра, информационный вход которого соединен с выходом комбинационного сумматора по модулю, а выход - с информационным входом второй группы комбинационного сумматора по модулю и первым входом блока элементов И, выход которого является выходом устройства.

Сущность изобретения состоит в том, что число A (начиная с младшего разряда) для определения модуля m разбивается на числа, длина которых равна периоду повторения остатков от чисел наложению этих периодов и последовательному суммированию промежуточных модульных остатков периода по модулю.

Представим число A в двоичной системе счисления

A = a₀2⁰ + a₁2¹ + ... + a_k-12^k-1.

Как следует из малой теории Ферма, всегда существует такой наименьший показатель степени _m, , что

Это положение свидетельствует о цикличности остатков по модулю m в разложении (5) числа A. Для определения периода повторения применим теорию индексов, откуда

_m=(m-1)/I₂,

где I₂ - индекс числа 2 по модулю устройства m. Отметим, что если число 2 является первообразным корнем по модулю m, то I₂ = 1 и _m = m-1.

Очевидно, что если количество двоичного представления числа A разбить на числа (начиная с младшего разряда) с периодом повторения _m , то алгоритм приведения чисел по модулю заключается в следующем:

1) определяется число единиц одноименных элементов каждого периода по всей длине двоичного представления числа A;

2) вычисляются значения частичных модульных остатков;

3) суммируются по модулю значения частичных модульных остатков внутри периода повторения.

Иначе это можно записать в виде

,

где k - число разрядов входного регистра. Выражение из (5), заключенное в скобках, реализуется аппаратным путем (пункты 1 и 2 алгоритма), поэтому число тактов операции формирования остатка по модулю от числа равно периоду повторения остатков _m, что в k/_m меньше аналогичного времени прототипа.

Рассмотрим построение устройства при k = 10 и m = 5. В этом случае ₅=(5-1)/1=4, [k/₅]=2. . Преобразователи 3 кода числа единиц в код остатка по модулю группы с j-м номером функционируют согласно соответствующим табл. 1-4.

Третий 2 регистр содержит ₅ =4 разрядов. Комбинационный сумматор 5 по модулю представляет устройство сложения двоичных числе по модулю m = 5 табличного типа. Второй 7 элемент задержки производит задержку на время, равное времени проведения модульной операции сложения в сумматоре 5. Первый 8 элемент задержки производит задержку на время, равно проведению модульной операции сложения в сумматоре 5 плюс время записи информации в регистр 10. Группа преобразователей 3 кода числа единиц в код остатка по модулю реализована на программируемых логических матрицах.

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

Данная разрядность входного регистра 1 позволяет формировать остаток по модулю от числа

Возможность достижения положительного эффекта от использования данного изобретения состоит в k/_m -м уменьшении времени формирования остатка по модулю, т.е. это время в предлагаемом устройстве составляет величину периода повторения остатков _m и не зависит от разрядности исходного числа, подлежащего преобразованию в остаток по модулю.

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

Информационный вход кода числа соединен с информационным входом первого регистра 1, вход начала вычислений устройства соединен с информационным входом нулевого разряда и входом записи третьего регистра 2, а также входом записи первого регистра 1, l-е выходы разрядов которого ; где k-число двоичных разрядов первого 1 регистра, _m -период повторения остатков по модулю m весов разрядов числа в двоичном коде) соединены с i-ми входами j-х преобразователей 3 кода числа единиц в код остатка по модулю, выход которых соединены с первыми входами соответствующих блоков 4 элементов И группы, вторые входы которых соединены с соответствующими разрядными выходами третьего регистра 2, а выходы - с информационным входом первой группы комбинационного сумматора 5 по модулю, тактовый вход устройства соединен с информационным входом элемента 6 запрета, выход которого соединен с входом второго элемента 7 задержки и входом сдвига третьего регистра 2, _m -й выход которого соединен с входом первого элемента 8 задержки и управляющим входом элемента запрета 6, выходы первого 8 и второго 7 элементов задержки соединены соответственно с вторым входом блока 9 элементов И и входом записи второго регистра 10, информационный вход которого соединен с выходом комбинационного сумматора 5 по модулю, а выход - с информационным входом второй группы комбинационного сумматора 5 по модулю и первым входом блока 9 элементов И, выход которого является выходом устройства.

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

В исходном состоянии все регистры обнулены. После подачи кода числа A на информационный вход первого регистра 1 на вход начала вычислений (НВ) подают импульс, который поступает на информационный вход нулевого разряда регистра 2 и входы записи регистров 1 и 2. Производится запись кода числа A в регистр 1 и единицы в нулевой разряд регистра 2, сигнал с выхода нулевого разряда которого поступает на второй вход нулевого блока 4 элементов И группы. Модульный остаток нулевых элементов периодов повторения остатков с выхода нулевого преобразователя 3 кода числа единиц в код остатка по модулю группы поступает на информационный вход первой группы комбинационного сумматора 5 по модулю, с выхода которого данный модульный остаток поступает на информационный вход второго регистра 10 (на этом цикле комбинационный сумматор 5 по модулю производит сложение с нулем). Тактовый импульс, поступающий с тактового входа устройства (ТИ) на информационный вход элемента 6 запрета, производит сдвиг единицы из нулевого разряда регистра 2 в первый и, поступая через второй элемент 7 задержки на вход записи регистра 2, производит запись кода модульного остатка. Сигнал с выхода первого разряда регистра 2 поступает на второй вход первого блока 4 элементов И группы, и модульный остаток первых элементов периодов повторения остатков с выхода первого преобразователя 3 кода числа единиц в код остатка по модулю группы поступает на информационный вход первой группы комбинационного сумматора 5 по модулю, на информационный вход второй группы которого поступает число с выхода регистра 10. Результат суммирования по модулю устройства заносится в регистр 10. Процесс повторяется до тех пор, пока единица не окажется в ( _m -1)-м разряде регистра 2. Сигнал с выхода этого разряда поступает на управляющий вход элемента 6 запрета, прекращая поступление тактовых импульсов, и открывает ( _m -1) блок 4 элементов И группы. Модульный остаток ( _m -1)-х элементов периодов повторения остатков с выхода соответствующего преобразователя 3 кода числа единиц в код остатка по модулю поступает на информационный вход первой группы комбинационного сумматора 5 по модулю, на информационный вход второй группы которого поступает двоичный код результата предыдущей операции. Результат операции формирования остатка по модулю устройства от числа A заносится в регистр 10 и по сигналу с выхода второго 7 элемента задержки поступает через блок 9 элементов И на выход устройства.

Рассмотрим пример выполнения операции формирования остатка по модулю m=5 от числа A=727₁₀ при k=10.

В исходном состоянии все регистры обнулены. После подачи кода числа A= 1110_ 1011_ 01 (начиная с младших разрядов) на информационный вход первого регистра 1 на вход начала вычислений (НВ) подают импульс, который поступает на информационный вход нулевого разряда регистра 2 и входы записи регистров 1 и 2. Производится запись кода числа A в регистр 1 и единицы в нулевой разряд регистра 2, сигнал с выхода нулевого разряда которого поступает на второй вход нулевого блока 4 элементов И группы. На вход нулевого преобразователя 3 кода числа единиц в код остатка по модулю группы поступает значение 110, а с его выхода код 010₂ (табл. 1) поступает на информационный вход первой группы комбинационного сумматора 5 по модулю, с выхода которого величина 010₂ поступает на информационный вход второго регистра 10. Импульс, поступающий с тактового входа устройства (ТИ) на информационный вход элемента 6 запрета, производит сдвиг единицы из нулевого разряда регистра 2 в первый и, поступая через второй элемент 7 задержки на вход записи регистра 2, производит запись кода 010₂. Сигнал с выхода первого разряда регистра 2 поступает на второй вход первого блока 4 элементов И группы, открывая его. На вход первого преобразователя 3 кода числа единиц в код остатка по модулю группы поступает значение 101, а с его выхода код 100₂ (табл. 2) поступает на информационный вход первой группы комбинационного сумматора 5 по модулю, на информационный вход второй группы которого с выхода регистра 10 поступает код 010₂. Результат сложения по модулю пять, равный 001₂, заносится в регистр 10. На следующем цикле на вход второго преобразователя 3 кода числа единиц в код остатка по модулю поступает величина 11, а на выходе его будет код 011₂. В комбинацонном сумматоре 5 по модулю произойдет модульное сложение значений 011₂ и 001₂. Результат, равный 100₂, вновь поступит в регистр 10. После поступления четвертого тактового импульса единица из второго разряда регистра 2 переходит в третий (последний) разряд, сигнал с выхода которого поступает на управляющий вход элемента 6 запрета, прекращая поступление тактовых импульсов. На входе третьего преобразователя 3 кода числа единиц в код остатка по модулю будет значение 01, а на выходе 011₂ (табл. 4). Последний цикл работы комбинационного 5 сумматора по модулю заключается в модульном сложении кодов 100₂ и 011₂. Результат операции Amod5=a=010₂ заносится в регистр 10. С выхода первого элемента 8 задержки сигнал поступает на второй вход блока 9 элементов И, открывая его. Остаток числа A по модулю 5, равный 010₂, поступает на выход устройства. Проверка: 727(mod5)=2(mod5).