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

 

Изобретение относится к вычислительной технике и предназначено для использования в цифровых вычислительных устройствах, а также в устройствах для формирования конечных полей. Цель изобретения - повышение быстродействия формирования остатка, достигается введением третьего регистра 2, группы преобразователей 3 кода числа единиц в код остатка по модулю, группы блоков 4 элементов И, комбинационного сумматора 5 по модулю и блока 9 элементов И. Сущность изобретения: число А (начиная с младшего разряда) для определения модуля m разбивается на числа, длина которых равна периоду повторения остатков от чисел 2i (i = 0, n), наложению этих периодов и последовательному суммированию промежуточных модульных остатков периода по модулю. 2 ил., 4 табл.

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

Известное устройство (аналог) (авт. св. СССР 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 = a020 + a121 + ... + ak-12k-1.

Как следует из малой теории Ферма, всегда существует такой наименьший показатель степени m, , что Это положение свидетельствует о цикличности остатков по модулю m в разложении (5) числа A. Для определения периода повторения применим теорию индексов, откуда m=(m-1)/I2, где I2 - индекс числа 2 по модулю устройства m. Отметим, что если число 2 является первообразным корнем по модулю m, то I2 = 1 и m = m-1.

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

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

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

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

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

Данная разрядность входного регистра 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=72710 при k=10.

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


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

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


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

РИСУНКИ

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



 

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

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

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

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

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

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

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

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

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

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

Изобретение относится к вычислительной технике

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

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

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

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

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

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

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

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

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

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