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

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

Устройство для формирования остатка по модулю от числа, содержащее два элемента задержки, элемент запрета, с первого по третий регистры, блок элементов И, группу блоков элементов И, комбинационный сумматор по модулю, причем информационный вход кода числа соединен с информационным входом первого регистра, вход начала вычислений устройства соединен с входами записи первого и третьего регистров, информационный вход нулевого разряда которого соединен с входом записи третьего регистра, вторые входы блоков элементов И группы соединены с соответствующими разрядными выходами третьего регистра, а выходы - с первым информационным входом комбинационного сумматора по модулю, тактовый вход устройства соединен с информационным входом элемента запрета, выход которого соединен с входом второго элемента задержки и входом сдвига третьего регистра, (_m/2)-й выход которого (_m - период повторения остатков по модулю m весов разряда числа в двоичном коде) соединен с входом первого элемента задержки и управляющим входом элемента запрета, выходы первого и второго элементов задержки соединены соответственно со вторым входом блока элементов И и входом записи второго регистра, информационный вход которого соединен с выходом комбинационного сумматора по модулю, а выход - со вторым информационным входом комбинационного сумматора по модулю и первым входом блока элементов И, выход которого является выходом устройства, отличающееся тем, что в него введены _m/2 групп элементов И и группа преобразователей кода двойственных пар периодов повторения остатков от числа в код остатка по модулю, причем первые входы i-х элементов И j-й группы соединены с выходами (j+i_m)-x разрядов первого регистра, выходы (j+i_m+_m/2)-x разрядов которого соединены со вторыми входами i-х элементов И j-й группы, выходы которых соединены с входами установки в ноль (j+i_m)-x и (j+i_m+_m/2)-x разрядов первого регистра где k - число двоичных разрядов первого регистра), выходы которого соединены с n-ми входами j-х преобразователей кода двойственных пар периодов повторения остатков от числа в код остатка по модулю, выходы которых соединены с первыми входами соответствующих блоков элементов И группы.

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

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

Известно устройство (аналог) (патент РФ 2023346, МКИ Н 03 М 7/18, БИ 21, 1994), содержащее два регистра, накапливающий сумматор по модулю, генератор тактовых импульсов, счетчик, мультиплексор, триггер, два элемента И, элемент ИЛИ и элемент задержки. Недостаток устройства - низкое быстродействие формирования остатка.

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

Наиболее близким по технической сущности (прототипом к предполагаемому изобретению) является устройство (патент РФ 2110147, МКИ Н 03 М 7/18, G 06 F 7/12, 1998), содержащее три регистра, группу преобразователей кода числа единиц в код остатка по модулю, группу блоков элементов И, комбинационный сумматор по модулю, блок элементов И, элемент запрета и два элемента задержки. Время выполнения формирования остатка по модулю составляет _m(_m - период повторения остатков по модулю m), что обуславливает основной недостаток устройства.

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

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

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

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



соединены с выходами (j +i_m)-х разрядов первого регистра, выходы (j+i_m+_m/2)-x разрядов которого соединены со вторыми входами i-x элементов И j-й группы, выходы которых соединены с входами установки в ноль (j+i_m)-x и (j+i_m+_m/2)-x разрядов первого регистра,



k - число двоичных разрядов первого регистра) выходы которого соединены с n-ми входами j-x преобразователей кода двойственных пар периодов повторения остатков от числа в код остатка по модулю, выходы которых соединены с первыми входами соответствующих блоков элементов И группы.

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

Представим целое число А в двоичном виде:



где а_i - символы двоичных разрядов числа А, 2ⁱ- веса двоичных разрядов числа А. Из теории чисел известно, что последовательность чисел 2ⁱmodm имеет некоторый период повторения, равный _m Для его определения, используя теорию индексов, решим сравнение 1modm. Откуда получим _m=(m-1)/I₂, где I₂- индекс числа 2 по модулю устройства m. Однако этот результат является лишь частным решением сравнения при g=2 (g - первообразный корень по модулю m). В общем виде имеем:



где (m - 1, I₂)- наибольший общий делитель чисел (m-1) и I₂. Число тактов проведения операции прототипа с учетом этого составляет величину _m. Рассмотрим возможность дальнейшего повышения быстродействия приведения числа по простому модулю, связанную с закономерностями распределения остатков внутри периода. Ввиду того, что:



как это следует из малой теоремы Ферма, сумма остатков внутри периода _m кратна величине модуля. В частности при m=5 имеем:



Горизонтальными линиями отмечены остатки, парные суммы которых равны m, что позволяет исключать соответствующие разряды в двоичном представлении числа А для уменьшения тактов проведения операции.

Определим расстояние t_m между двоичными разрядами, модульные остатки которых в сумме составляют величину m путем решения сравнения modm. Откуда:



где (I_m-1, I₂), подобно (1), - наибольший общий делитель I_m-1 и I₂, I_m-1-индекс числа (m-1) по модулю m. Неравенство _m t_m является удобным критерием двойственности остатков в периоде. Он позволяет уточнить, что g=2 не является существенным условием симметрии относительно модуля распределения остатков периода _m. Например, при m=17 (g=3) имеем следующее распределение остатков:



Однако ввиду того, что при g2(m-1, I₂)(1, то в этом случае _m<(m-1) и позволяет использовать подобные числа в высокопроизводительных устройствах формирования конечных полей.

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

1) производится сброс в ноль единиц двойственных разрядов, что равносильно вычитанию величины m из суммы остатков периода;

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

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

Рассмотрим построение устройства при k=10 и m=5. В этом случае ₅/2=2. Элементы И 10 составляют две группы по два элемента в каждой. Преобразователи 11 кода двойственных пар периодов повторения остатков от числа в код остатка по модулю с j-ми номерами 0 и 1 имеют на парных входах возможные комбинации 00, 01 и 10. При этом число входных комбинаций при m=5 составляет величину 332= 18<2= 32. Обработка двоичного десятиразрядного числа А по модулю 5 схематично изображено на фиг.2, где вертикальные линии отображают соединение выходов регистра 1 с входами преобразователей 11 кода. В таблице представлено в десятичном коде преобразование входной комбинации "Вх" в выходные значения "Пр0" и "Пр1" преобразователей 11 кода с номерами соответственно ноль и один.

Третий 2 регистр содержит ₅/2 =2 разряда. Комбинационный сумматор 4 представляет устройство сложения двоичных чисел табличного типа по модулю m= 5. Второй 6 элемент задержки производит задержку на время, равное времени проведения модульной операции сложения в сумматоре 4. Первый 7 элемент задержки производит задержку на время, равное времени проведения модульной операции сложения в сумматоре 4 плюс время записи информации в регистр 9. Отсутствие парных комбинаций вида 11₂ на входах группы преобразователей 11 кода упрощает их схемную реализацию на программируемых логических матрицах.

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

Дополнительным положительным эффектом является уменьшение в два раза числа разрядов третьего 2 регистра и блоков 3 элементов И группы.

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

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

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



соединены с выходами (j+i_m) разрядов первого 1 регистра, выходы (j+i_m+_m/2) разрядов которого соединены со вторыми входами i-x элементов И 10 j-й группы, выходы которых соединены с входами установки в ноль (j+i_m)-x и (j+i_m+_m/2)-х разрядов первого 1 регистра,



k - число двоичных разрядов первого 1 регистра) выходы которого соединены с n-ми входами j-x преобразователей 11 кода двойственных пар периодов повторения остатков от числа в код остатка по модулю, выходы которых соединены с первыми входами соответствующих блоков 3 элементов И группы.

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

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

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

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

Отметим, что, проводя второй этап обнуления двойственных пар в двух периодах можно получить число А=0000_0000_01, т.е. также а=010₂.