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

 

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

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

Известно устройство (аналог) (патент РФ 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) имеем следующее распределение остатков:

Однако ввиду того, что при g≠2(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 составляет величину 3•3•2= 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₂.

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

Устройство для формирования остатка по модулю от числа, содержащее два элемента задержки, элемент запрета, с первого по третий регистры, блок элементов И, группу блоков элементов И, комбинационный сумматор по модулю, причем информационный вход кода числа соединен с информационным входом первого регистра, вход начала вычислений устройства соединен с входами записи первого и третьего регистров, информационный вход нулевого разряда которого соединен с входом записи третьего регистра, вторые входы блоков элементов И группы соединены с соответствующими разрядными выходами третьего регистра, а выходы - с первым информационным входом комбинационного сумматора по модулю, тактовый вход устройства соединен с информационным входом элемента запрета, выход которого соединен с входом второго элемента задержки и входом сдвига третьего регистра, (τ_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-х преобразователей кода двойственных пар периодов повторения остатков от числа в код остатка по модулю, выходы которых соединены с первыми входами соответствующих блоков элементов И группы.

РИСУНКИ

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