УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ЧИСЛА Российский патент 2003 года по МПК G06F7/72 H03M7/18 

Описание патента на изобретение RU2209460C2

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Однако ввиду того, что при g≠2(m-1, I2)(1, то в этом случае τm<(m-1) и позволяет использовать подобные числа в высокопроизводительных устройствах формирования конечных полей.

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

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

Третий 2 регистр содержит τ5/2 =2 разряда. Комбинационный сумматор 4 представляет устройство сложения двоичных чисел табличного типа по модулю m= 5. Второй 6 элемент задержки производит задержку на время, равное времени проведения модульной операции сложения в сумматоре 4. Первый 7 элемент задержки производит задержку на время, равное времени проведения модульной операции сложения в сумматоре 4 плюс время записи информации в регистр 9. Отсутствие парных комбинаций вида 112 на входах группы преобразователей 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•τmm/2) разрядов которого соединены со вторыми входами i-x элементов И 10 j-й группы, выходы которых соединены с входами установки в ноль (j+i•τm)-x и (j+i•τmm/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 от числа 72710 при 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), а с его выхода код 0002 (см. таблицу) поступает на первый информационный вход комбинационного сумматора 4 по модулю, с выхода которого код 0002 поступает на информационный вход второго 9 регистра. Импульс, поступающий с тактового входа устройства (ТИ) на информационный вход элемента 5 запрета, производит сдвиг единицы из нулевого разряда регистра 2 в первый и, поступая через второй элемент 6 задержки на вход записи регистра 9, производит запись кода 0002. Сигнал с выхода первого разряда регистра 2 поступает на второй вход первого блока 3 элементов И группы, открывая его. На вход первого преобразователя 11 кода двойственных пар периодов повторения остатков от числа в код остатка по модулю поступает значение 10011 (см. фиг.2), а с его выхода код 0102 (см. таблицу) поступает на первый информационный вход комбинационного сумматора 4 по модулю, на второй информационный вход которого с выхода регистра 9 поступает код 0102. Результат сложения по модулю пять, равный 0102, заносится в регистр 9. При этом сигнал с выхода последнего разряда регистра 2 поступает на управляющий вход элемента 5 запрета, прекращая поступление тактовых импульсов. Результат операции Amod5=a=0102. С выхода первого элемента 7 задержки сигнал поступает на второй вход блока 8 элементов И, открывая его. Остаток а=0102 поступает на выход устройства. Проверка: 727mod 5=2mod 5.

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

Похожие патенты RU2209460C2

название год авторы номер документа
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ЧИСЛА 1996
  • Ирхин В.П.
RU2110147C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ЧИСЛА 1999
  • Ирхин В.П.
  • Долгачев А.А.
  • Крюков Ю.Г.
RU2157589C1
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ 1998
  • Ирхин В.П.
  • Глазков Е.Б.
  • Лукьянов И.М.
  • Гульбин С.С.
RU2143723C1
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ 1998
  • Ирхин В.П.
  • Обухов А.Н.
  • Гульбин С.С.
RU2145112C1
УСТРОЙСТВО ДЛЯ УМНОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ 1998
  • Ирхин В.П.
  • Глазков Е.Б.
  • Лукьянов И.М.
  • Гульбин С.С.
RU2137181C1
УСТРОЙСТВО ДЛЯ ВЫЧИТАНИЯ ПО МОДУЛЮ 1997
  • Ирхин В.П.
RU2133495C1
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ N ЧИСЕЛ ПО МОДУЛЮ 1997
  • Ирхин В.П.
RU2131618C1
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ ЧИСЕЛ ПО МОДУЛЮ 1996
  • Ирхин В.П.
RU2110087C1
СУММАТОР-ВЫЧИТАТЕЛЬ СТАРШИМИ РАЗРЯДАМИ ВПЕРЕД НА НЕЙРОНАХ 2002
  • Шевелев С.С.
RU2205444C1
УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ 1999
  • Ирхин В.П.
  • Глазков Е.Б.
  • Лукьянов М.А.
  • Долгачев А.А.
  • Крюков Ю.Г.
RU2156998C1

Иллюстрации к изобретению RU 2 209 460 C2

Реферат патента 2003 года УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ЧИСЛА

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

Формула изобретения RU 2 209 460 C2

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

Документы, цитированные в отчете о поиске Патент 2003 года RU2209460C2

УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО МОДУЛЮ ОТ ЧИСЛА 1996
  • Ирхин В.П.
RU2110147C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА 1990
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2029434C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА 1991
  • Петренко В.И.
  • Чипига А.Ф.
RU2023346C1
УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ ОСТАТКА ПО ПРОИЗВОЛЬНОМУ МОДУЛЮ ОТ ЧИСЛА 1991
  • Петренко Вячеслав Иванович
  • Чипига Александр Федорович
RU2007033C1
JP 10032493 А2, 03.02.1998.

RU 2 209 460 C2

Авторы

Ирхин В.П.

Иванкин Г.Е.

Ермаков А.Е.

Чекалин С.С.

Гульбин С.С.

Даты

2003-07-27Публикация

2000-11-15Подача