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

Изобретение относится к вычислительной технике. Технический результат заключается в повышении быстродействия и надежности функционирования устройства для формирования остатка по произвольному модулю от числа. Технический результат достигается за счёт того, что устройство для формирования остатка по произвольному модулю от числа содержит регистры (1) и (2), сумматоры (3) и (4), элементы И (5) и (6), элемент ИЛИ (7), регистр (8), генератор тактовых импульсов (ГТИ) (9), элемент И (10), счетчик (11), схему сравнения (12), регистр (13), элементы задержки (14), (15), (16), выходы (17) и (18), вход (19) устройства. 1 ил.

 

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

Известно устройство для сложения чисел по модулю, содержащее первый регистр (1), второй регистр (2), третий регистр (8), первый сумматор (3), генератор тактовых импульсов (ГТИ) (9), первый элемент И (10), первый вход которого подсоединен к входу (19) устройства, выход ГТИ (9) подсоединен к второму входу первого элемента И (10), выход первого регистра (1) подсоединен к первому входу первого сумматора (3) [1].

Недостатком данного устройства являются низкое быстродействие и малая надежность.

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

Это решение достигается тем, что в устройство для сложения чисел по модулю, содержащее первый регистр (1), второй регистр (2), третий регистр (8), первый сумматор (3), генератор тактовых импульсов (ГТИ) (9), первый элемент И (10), первый вход которого подсоединен к входу (19) устройства, выход ГТИ (9) подсоединен к второму входу первого элемента И (10), выход первого регистра (1) подсоединен к первому входу первого сумматора (3), введены второй сумматор (3), вторая группа элементов И (5), третья группа элементов И (6), группа элементов ИЛИ (7), третий регистр (8), счетчик (11), схема сравнения (12), четвертый регистр (13), первый элемент задержки (14), второй элемент задержки (15), третий элемент задержки (16), выход второго регистра (2).

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

Это решение достигается тем, что в устройство для сложения чисел по модулю, содержащее первый регистр (1), второй регистр (2), третий регистр (8), первый сумматор (3), генератор тактовых импульсов (ГТИ) (9), первый элемент И (10), первый вход которого подсоединен к входу (19) устройства, выход ГТИ (9) подсоединен к второму входу первого элемента И (10), выход первого регистра (1) подсоединен к первому входу первого сумматора (3), введены второй сумматор (3), вторая группа элементов И (5), третья группа элементов И (6), группа элементов ИЛИ (7), третий регистр (8), счетчик (11), схема сравнения (12), четвертый регистр (13), первый элемент задержки (14), второй элемент задержки (15), третий элемент задержки (16), выход второго регистра (2) подсоединен к первому входу второго сумматора (4), выход первого сумматора (3) подсоединен к первому входу второй группы элементов И (5) и к второму входу второго сумматора (4), первый выход которого подсоединен к второму входу второго элемента И (5), а второй выход - к первому входу третьей группы элемента И (6), второй вход которой подсоединен к второму выходу второго сумматора (4), а выход подсоединен к первому входу группы элементов ИЛИ (7), второй вход которой подсоединен к выходу группы вторых элементов И (5), а выход - к первому входу третьего регистра (8), первый выход которого является первым выходом устройства (18), второй выход - к второму входу первого сумматора (3), выход первого элемента И (10) подсоединен к входу счетчика (11), к входу второго элемента задержки (15), к входу третьего элемента задержки (16) и к второму входу третьего регистра (8), выход второго элемента задержки (15) подсоединен к третьему входу первого сумматора (3), к входу первого элемента задержки (14), выход которого подсоединен к третьему входу второго сумматора (4), выход счетчика (11) подсоединен к первому входу схемы сравнения (12), второй вход которой подсоединен к выходу третьего регистра (13), а выход - является вторым выходом устройства (18) и подсоединен к третьему инверсному входу первого элемента И (10), выход третьего элемента задержки (16), подсоединен к входу первого регистра (1).

Сущность изобретения заключается в реализации известного из теории чисел способа вычисления остатка R от числа А по модулю Р. Для целого положительного числа А, от которого необходимо вычислить остаток, справедлива зависимость:

где Р - целое положительное число, называемое модулем;

Q - целое положительное число, являющееся неполным частным от деления А на Р;

R - целое положительное число, являющееся остатком от деления А на Р.

Причем

где a_i (i=0,…(n-1)) - коэффициенты, принимающие значение 0 или 1 в зависимости от значения числа А;

p_i (i=0,…(n-1)) - коэффициенты, принимающие значение 0 или 1 в зависимости от значения модуля Р;

q_i (i=0,…(n-2)) - коэффициенты, принимающие значение 0 или 1 в зависимости от значения неполного частного Q;

r_i (i=0,…(n-2)) - коэффициенты, принимающие значение 0 или 1 в зависимости от значения остатка R;

n - количество разрядов в представлении чисел.

Задача состоит в том, чтобы по известным значениям А и Р отыскать остаток R. Остаток R является в терминах теории чисел вычетом числа А по модулю Р, поэтому говорят, что А сравнимо с R по модулю Р:

Значение остатка R может быть вычислено следующим образом:

Выражение (7) может быть представлено в следующем виде:

Из теории чисел известно, что операция приведения по модулю инвариантна к сложению и умножению, т.е. величина остатка не зависит от того, вычислен ли он от суммы (произведения) или от каждого слагаемого (сомножителя), а затем соответствующие частичные остатки просуммированы (перемножены) и от результата вычислен остаток по модулю.

Поэтому выражение (8) может быть представлено в виде

В таком виде существенно облегчается задача нахождения остатка R от числа А.

При проведении вычислений по модулю Р значение выражения (а_n-1-2+a_n-2) сравнивается с модулем Р. Если значение (a_n-1⋅2+a_n-2)≥Р, то из числа (a_n-1⋅2+a_n-2) вычитается значение модуля Р, то есть t₁=(a_n-1⋅2+a_n-2)-P. Если (a_n-1⋅2+a_n-2)<Р, то число (a_n-i⋅2+a_n-2) остается без изменений t₁=(a_n-1⋅2+a_n-2). Полученное в результате значение t₁ умножается на 2, складывается с а_n-3 и сравнивается со значением Р. Если значение (t₁⋅2+a_n-3)≥Р, то из (t₁⋅2+a_n-3) вычитается значение модуля Р, то есть t₂=(t₁⋅2+a_n-3)-Р. Если (t₁⋅2+a_n-3)<Р, то число (t₁⋅2+a_n-3) остается без изменений, t₂=(t₁⋅2+a_n-3). Полученное в результате значение t₂ умножается на 2, складывается с а_n-4 и сравнивается со значением Р и т.д. На последнем (n-1)-м шаге число (t_n-2⋅2+a₀) сравнивается с модулем Р. Если значение (t_n-2⋅2+а₀)≥Р, то из (t_n-2⋅2+a₀) вычитается значение числа Р, то есть t_n-1=(t_n-2⋅2+а₀)-Р. Если (t_n-2⋅2+a₀)<Р, то число (t_n-2⋅2+a₀) остается без изменений t_n-1=(t_n-2⋅2+a₀). Полученное в результате значение R=t_n-1 является остатком от деления числа А на число Р.

Операция умножения на два при вычислении выражения (t_i⋅2+a_n-2-i) во всех случаях осуществляется сдвигом всех разрядов множимого на один разряд в сторону старших разрядов. Суммирование осуществляется путем подачи коэффициента а_i на самый младший разряд сумматора. Ввиду того, что коэффициенты а_i могут принимать значение «0» или «1», а самый младший разряд сумматора после n сдвигов всегда будет равен «0», то переноса в следующий разряд при таком решении возникать не будет.

На фиг. 1 представлена схема устройства для формирования остатка по произвольному модулю от числа.

Устройство для формирования остатка по произвольному модулю Р от числа А, содержит: регистры (1) и (2), сумматоры (3) и (4), элементы И (5) и И (6), элемент ИЛИ (7), регистр (8), генератор тактовых импульсов (ГТИ) (9), элемент И (10), счетчик (11), схема сравнения (12), регистр (13), элемент задержки (14), элемент задержки (15), элемент задержки (16), выходы (17) и (18), вход (19) устройства.

Формирование остатка от n-разрядного числа А по модулю Р осуществляется за n тактов, где n - разрядность входных чисел.

В исходном состоянии на регистре (1) находится число А, на регистре (2) находится число Р, на регистре (13) находится число n, на счетчике (11) находится 0, поэтому с выхода схемы сравнения (12) на инверсный вход элемента И (10) поступает нулевой сигнал.

Для начала работы устройства и на протяжении всего цикла формирования остатка на вход (19) устройства подается сигнал логической «1». При этом тактовые импульсы с выхода ГТИ (9) поступают через элемент И (10) на вход счетчика (11), на входы элементов задержки (15) и (16), а также на вход сдвига на один разряд содержимого регистра (8) в сторону старших разрядов.

Элемент задержки (15) задерживает сигнал на время надежного срабатывания сдвигающего регистра (8). Единичный сигнал с выхода элемента задержки (15) поступает на управляющий вход сумматора (3), на котором происходит сложение сдвинутого содержимого регистра (8) и старшего разряда регистра (1). Результат с выхода сумматора (3) поступает на вход группы элементов И (5) и на первый вход сумматора (4), на второй вход которого поступает код с выхода регистра (2).

Элемент задержки (14) задерживает сигнал на время надежного срабатывания сумматора (3). На сумматоре (4) происходит вычитание из содержимого сумматора (3) значения с выхода регистра (2).

Если содержимое сумматора (3) меньше содержимого регистра (2), то в знаковом разряде сумматора (4) будет единичный сигнал, по которому результат с выхода сумматора (3) через группу элементов И (5) и элементов ИЛИ (7) поступает на регистр (8). Если содержимое сумматора (3) не меньше содержимого регистра (2), то в знаковом разряде сумматора (4) будет нулевой сигнал, по которому результат с выхода сумматора (3) через группу элементов И (6) и элементов ИЛИ (7) поступает на регистр (8).

Элемент задержки (16) задерживает сигнал на время надежного срабатывания сумматора (3) и сумматора (4). Единичный сигнал с выхода элемента задержки (16) поступает на управляющий вход регистра (1), на котором происходит сдвиг содержимого регистра (1) на один разряд в сторону старшего разряда.

Аналогичная работа устройства происходит с приходом очередных тактовых импульсов до появления на счетчике (11) числа п, после чего на выходе схемы сравнения (12) появляется сигнал логической единицы, который подается как сигнал окончания работы устройства на выход (17) устройства и на инверсный вход элемента И (10), тем самым прекращается работа устройства.

Результат формирования остатка от n-разрядного числа А по модулю Р подается с выхода регистра (8) на выход (18) устройства. Цикл формирования остатка завершен.

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

Пусть n=4, А=14 (А₂=1110), Р=5 (Р₂=0101). Формирование остатка выполняется за (4) такт. В старшем разряде числа А стоит единица.

На первом такте первый импульс с выхода ГТИ (9) поступает через элемент И (10) на вход счетчика (11), на входы элементов задержки (15) и (16), а также на вход сдвига на один разряд содержимого регистра (8) в сторону старших разрядов. На выходе регистра (8) будет опять код 0000. На выходе сумматора (3) после задержки сигнала элементом (15) будет код 0000+1=0001. На выходе сумматора (4) после задержки сигнала элементом (14) будет код 0001-0101=-0100 (знак числа отрицательный), поэтому код с выхода сумматора (3) через группу элементов И (5) и ИЛИ (7) поступит на регистр (8), где зафиксируется код 0001. Далее по сигналу с выхода элемента задержки (16) произойдет сдвиг кода на регистре (1), где теперь буде код 1100.

На втором такте второй импульс с выхода ГТИ (9) поступает через элемент И (10) на вход счетчика (11), на входы элементов задержки (15) и (16), а также на вход сдвига на один разряд содержимого регистра (8) в сторону старших разрядов. На выходе регистра (8) будет теперь код 0010. На выходе сумматора (3) после задержки сигнала элементом (15) будет код 0010+1=0011. На выходе сумматора (4) после задержки сигнала элементом (14) будет код 0011-0101=-0010 (знак числа отрицательный). Код с выхода сумматора (3) через группу элементов И (5) и ИЛИ (7) поступит на регистр (8), где зафиксируется код 0011.

Далее по сигналу с выхода элемента задержки (16) произойдет сдвиг кода на регистре (1), где теперь буде код 1000.

На третьем такте третий импульс с выхода ГТИ (9) поступает через элемент И (10) на вход счетчика (11), на входы элементов задержки (15) и (16), а также на вход сдвига на один разряд содержимого регистра (8) в сторону старших разрядов. На выходе регистра (8) будет теперь код 0110. На выходе сумматора (3) после задержки сигнала элементом (15) будет код 0110+1=0111. На выходе сумматора (4) после задержки сигнала элементом (14) будет код 0111-0101=+0010 (знак числа положительный). Код с выхода сумматора (4) через группу элементов И (6) и ИЛИ (7) поступит на регистр (8), где зафиксируется код 0010. Далее по сигналу с выхода элемента задержки (16) произойдет сдвиг кода на регистре (1), где теперь буде код 0000.

На четвертом такте четвертый импульс с выхода ГТИ (9) поступает через элемент И (10) на вход счетчика (11), на входы элементов задержки (15) и (16), а также на вход сдвига на один разряд содержимого регистра (8) в сторону старших разрядов. На выходе регистра (8) будет теперь код 0100. На выходе сумматора (3) после задержки сигнала элементом (15) будет код 0100+0=0100. На выходе сумматора 4 после задержки сигнала элементом (14) будет код 0100-0101=-0001 (знак числа отрицательный). Код с выхода сумматора (3) через группу элементов И (5) и ИЛИ (7) поступит на регистр (8), где зафиксируется код 0100. Далее по сигналу с выхода элемента задержки (16) произойдет сдвиг кода на регистре (1), где теперь буде код 0000.

На счетчике (11) будет код числа (4), поэтому на выходе схемы сравнения (12) появляется сигнал логической единицы, который подается как сигнал окончания работы устройства на выход (17) устройства и на инверсный вход элемента И (10), тем самым прекращается работа устройства.

(15) и (16), а также на вход сдвига на один разряд содержимого регистра (8) в сторону старших разрядов. На выходе регистра (8) будет теперь код 0100. На выходе сумматора (3) после задержки сигнала элементом (15) будет код 0100+0=0100. На выходе сумматора 4 после задержки сигнала элементом (14) будет код 0100-0101=-0001 (знак числа отрицательный). Код с выхода сумматора (3) через группу элементов И (5) и ИЛИ (7) поступит на регистр (8), где зафиксируется код 0100. Далее по сигналу с выхода элемента задержки (16) произойдет сдвиг кода на регистре (1), где теперь буде код 0000.

На счетчике (11) будет код числа (4), поэтому на выходе схемы сравнения (12) появляется сигнал логической единицы, который подается как сигнал окончания работы устройства на выход (17) устройства и на инверсный вход элемента И (10), тем самым прекращается работа устройства.

Таким образом, результат операции формирования остатка по модулю равен 4. Операция выполнена корректно, поскольку 14 (mod 5)=4.

Техническим результатом данного изобретения является повышение быстродействия и сокращение объема оборудования и, как следствие, уменьшение энергопотребления.

Литература

1. SU №2696223, 2019.

Устройство для формирования остатка по произвольному модулю от числа, содержащее первый регистр (1), второй регистр (2), третий регистр (8), первый сумматор (3), генератор тактовых импульсов ГТИ (9), первый элемент И (10), первый вход которого подсоединен к входу (19) устройства, выход ГТИ (9) подсоединен к второму входу первого элемента И (10), выход первого регистра (1) подсоединен к первому входу первого сумматора (3), отличающееся тем, что в него введены второй сумматор (3), вторая группа элементов И (5), третья группа элементов И (6), группа элементов ИЛИ (7), третий регистр (8), счетчик (11), схема сравнения (12), четвертый регистр (13), первый элемент задержки (14), второй элемент задержки (15), третий элемент задержки (16), выход второго регистра (2) подсоединен к первому входу второго сумматора (4), выход первого сумматора (3) подсоединен к первому входу второй группы элементов И (5) и к второму входу второго сумматора (4), первый выход которого подсоединен к второму входу второго элемента И (5), а второй выход - к первому входу третьей группы элемента И (6), второй вход которой подсоединен к второму выходу второго сумматора (4), а выход подсоединен к первому входу группы элементов ИЛИ (7), второй вход которой подсоединен к выходу группы вторых элементов И (5), а выход - к первому входу третьего регистра (8), первый выход которого является первым выходом устройства (18), второй выход - к второму входу первого сумматора (3), выход первого элемента И (10) подсоединен к входу счетчика (11), к входу второго элемента задержки (15), к входу третьего элемента задержки (16) и к второму входу третьего регистра (8), выход второго элемента задержки (15) подсоединен к третьему входу первого сумматора (3), к входу первого элемента задержки (14), выход которого подсоединен к третьему входу второго сумматора (4), выход счетчика (11) подсоединен к первому входу схемы сравнения (12), второй вход которой подсоединен к выходу третьего регистра (13), а выход - является вторым выходом устройства (18) и подсоединен к третьему инверсному входу первого элемента И (10), выход третьего элемента задержки (16) подсоединен к входу первого регистра (1).