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

 

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

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

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

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

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

Недостаток прототипа - низкое быстродействие формирования остатка, ввиду того, что эта операция проводится путем последовательного t поразрядного сдвига обрабатываемого числа в младшие разряды входного регистра. Другим недостатком прототипа является невозможность формирования остатка по произвольному модулю, а только для строго определенных модулей, так, что Рассмотрим подробнее этот вопрос, отобразив последовательность чередования остатков для модулей m=3, 5 и 7 в (2,3,4) 2⁰=1, 2¹=2, 2²=1,... 2⁰=1, 2¹=2, 2²=4, 2³=3, 2⁴=1,... 2⁰=1, 2¹=2, 2²=4, 2³=1,... Рассматривая функционирование прототипа при m=5, согласно последовательности (3) можно отметить, что уже на первом цикле работы в регистр 18 поступает число большее, чем модуль (при произвольном исходном числе A). В дальнейшем это несоответствие нарастает, при m=11 сумма поразрядных модульных остатков внутри периода повторения превышает величину модуля в пять раз. Возможно при определенной величине m либо числе A устройство будет правильно функционировать, однако сомнение в этом вызывает описание работы накапливающего сумматора 3 по модулю. В частности, комбинационный сумматор 18 проводит сложение двух двоичных чисел, число разрядов которых равно длине периода, однако, как следует из (3), например, веса двоичных разрядов числа A не соответствуют весам модульных остатков, поэтому сложение будет производиться неправильно. Это положение относится и к вычислителю 20. Вызывает интерес построение и функционирование в этом случае элемента 19 сравнения. Если же предположить, что комбинационный сумматор 18 является специализированным (этого не следует из описания прототипа) и производит поразрядную обработку числа (с перекодировкой значений разрядных модульных остатков в двоичный код), то это обстоятельство приведет к дальнейшему уменьшению быстродействия формирования остатка и, что самое главное, обуславливает жесткую схемотехническую привязку его к модулю.

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

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

Технический результат достигается тем, что в устройство для формирования остатка по модулю от числа, содержащее два элемента задержки, элемент запрета, с первого по третий регистры, блок элементов И, причем информационный вход кода числа соединен с информационным входом первого регистра, вход начала вычислений устройства соединен с входами записи первого и третьего регистров, отличающееся тем, что в него введены группа преобразователей кодов, группа блоков элементов И, комбинационный сумматор по модулю, причем информационный вход нулевого разряда третьего регистра соединен с входом записи первого регистра, l-е выходы разрядов которого (l = t·i+j≅k; ; где k - число двоичных разрядов первого регистра; t - число двоичных разрядов в группе) соединены с j-ми входами i-х преобразователей кодов группы, выходы которых соединены с первыми входами соответствующих блоков элементов И группы, вторые входы которых соединены с соответствующими разрядными выходами третьего регистра, а выходы - с информационным входом первой группы комбинационного сумматора по модулю, тактовый вход устройства соединен с информационным входом элемента запрета, выход которого соединен с входом второго элемента задержки и входом сдвига третьего регистра, [k/t]-й выход которого соединен с входом первого элемента задержки и управляющим входом элемента запрета, выходы первого и второго элементов задержки соединены соответственно со вторым входом блока элементов И и входом записи второго регистра, информационный вход которого соединен с выходом комбинационного сумматора по модулю, а выход - с информационным входом второй группы комбинационного сумматора по модулю и первым входом блока элементов И, выход которого является выходом устройства.

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

Представим число A в d-ичной системе счисления A=a₀d⁰+a₁d¹+..+a_k-1d^k-1, где Тогда число Amodm можно записать в виде
где k - число двоичных разрядов регистра i,t - число двоичных разрядов в группе, m - модуль устройства, α_ti+j - числа (0 или 1) двоичного представления числа и в двоично- α -ичной системе счисления, α - основание системы счисления.

Выражение, заключенное в скобках (5), реализуется с помощью группы преобразователей 3 кодов, при этом время выполнения операции формирования остатка по модулю от числа составляет [k/t], что при t > 1 существенно меньше аналогичного времени прототипа. В частности, устройство нормально функционирует в том случае, когда d является степенью числа два (двоично-четверичная, двоично-восьмеричная системы и т.д.). Отметим, что при 2^t-1=l(modm) преобразователи 3 кодов идентичны, а если m≥α, то преобразователи 3 кодов не нужны.

Комбинационный сумматор 5 по модулю представляет собой устройство сложения двоичных чисел по модулю (табличного типа). Первый 8 элемент задержки производит задержку сигнала на время, равное времени суммирования в комбинационном сумматоре 5 по модулю плюс время записи информации в регистр 10. Второй 7 элемент задержки производит задержку сигнала на время, равное времени суммирования чисел в комбинационном сумматоре 5 по модулю.

Число двоичных разрядов второго 10 регистра [log₂d], а третьего 2 регистра -[k/t].

Следует отметить, что при (m,d)≠1 устройство существенно упрощается.

Рассмотрим построение устройства при k = d = 10 и m = 7. В этом случае требуется три преобразователя 3 кодов с нулевого по второй, реализуемые согласно таблицам 1-3.

Преобразователи 3 кодов реализуются на программируемых логических матрицах согласно таблицам 1 - 3 при t = 4.

Возможность достижения положительного эффекта от использования данного изобретения состоит в повышении в t раз быстродействия при формировании остатка по модулю от числа. Быстродействие можно повысить также, применяя деление числа А на группы, кратные величине t при соответствующем увеличении оборудования. Дополнительным положительным эффектом является возможность определения остатка по модулю не только числа, записанного в двоично-d-ичной системе счисления, но и числа в двоичном виде.

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

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

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

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

Рассмотрим пример выполнения операции формирования остатка по модулю m=7 при d= 10, k=10, A=396. При d-10, t =[log₂d]= 4. Исходное число A в двоично-десятичной системе счисления представится в виде 1110010110.

В исходном состоянии все регистры обнулены. После подачи кода исходного числа в виде 0110100111 на вход первого 1 регистра, поступает импульс на вход начала вычислений, который, поступая на входы записи регистров 1 и 2, осуществляет запись кода числа в первый регистр 1 и единицы в нулевой разряд третьего регистра 2. Сигнал с выхода этого разряда поступает на второй вход нулевого блока 4 элементов И группы и открывает его. Нулевая группа 0110 двоичных разрядов числа A поступает на входы нулевого преобразователя 3 кодов группы, с выхода которого модульный остаток 110 (см. табл. 1) поступает на информационный вход первой группы комбинационного сумматора 5 по модулю. С тактового входа устройства на информационный вход элемента 6 запрета поступает импульс и далее через второй 7 элемент задержки поступает на вход записи второго 10 регистра, производя запись числа 110 в регистр 10. (Иначе говоря, производится сложение модульного остатка нулевой группы числа A с нулем). Второй тактовый импульс, поступая через элемент 6 запрета на вход сдвига третьего 2 регистра, продвигает единицу из нулевого в первый разряд. Сигнал с выхода первого разряда третьего 2 регистра поступает на второй вход первого блока 4 элементов И группы, обеспечивая поступление модульного 110 первой группы 1001 числа A (см. табл. 2) с выхода первого преобразователя 6 кодов группы на информационный вход первой группы комбинационного сумматора 5 по модулю, на информационный вход второй группы которого с выхода второго 10 регистра поступает модульный остаток нулевой группы числа, равный 110. Результат модульного сложения 101 по сигналу, поступающему с выхода элемента 7 задержки на вход записи второго 2 регистра, записывается в регистр 10. Третий тактовый импульс продвигает единицу из первого разряда регистра 2 в последний (второй) разряд, модульный остаток 110 второй группы 11 числа A с выхода второго преобразователя 5 кодов группы (см. табл. 3) поступает через соответствующий открытый блок 4 элементов группы на информационный вход первой группы комбинационного сумматора 5 по модулю, в которой происходит его сложение по модулю m=7 с величиной 101. Остаток A=100 записывается в регистр 10. Единичный сигнал с выхода второго разряда регистра 2 поступает на управляющий вход элемента 6 запрета, прекращая поступление импульсов с тактового входа устройства. Сигнал с выхода первого элемента 8 задержки поступает на второй вход блока 9 элементов И и обеспечивает прохождение результата операции а= 100 на выход устройства. Проверка: 396 (mod7)=4 (mod7)=100 (mod7).

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

Устройство для формирования остатка по модулю от числа, содержащее два элемента задержки, элемент запрета, с первого по третий регистры, блок элементов И, группу блоков элементов И, комбинационный сумматор по модулю, причем информационный вход кода числа соединен с информационным входом первого регистра, вход начала вычислений устройства - с входами записи первого и третьего регистров, информационный вход нулевого разряда которого соединен с входом записи первого регистра, вторые входы блоков элементов И группы соединены с соответствующими разрядными выходами третьего регистра, а выходы - с информационным входом первой группы комбинационного сумматора по модулю, тактовый вход устройства соединен с информационным входом элемента запрета, выход которого соединен с входом второго элемента задержки и входом сдвига третьего регистра, [k/t]-й выход которого (k - число двоичных разрядов первого регистра, t - число двоичных разрядов в группе) соединен с входом первого элемента задержки и управляющим входом элемента запрета, выходы первого и второго элементов задержки соединены соответственно с вторым входом блока элементов И и входом записи второго регистра, информационный вход которого соединен с выходом комбинационного сумматора по модулю, а выход - с информационным входом второй группы комбинационного сумматора по модулю и первым входом блока элементов И, выход которого является выходом устройства, отличающееся тем, что в него введена группа преобразователей кода группы двоичных разрядов числа в модульный
остаток, причем l-е выходы разрядов первого регистра (l = t · i + j ≅ k; соединены с j-ми входами i-х преобразователей кода группы двоичных разрядов числа в модульный остаток, выходы которых соединены с первыми входами соответствующих блоков элемента И группы.

РИСУНКИ

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