Устройство для сложения и вычитания чисел по модулю

 

Изобретение относится к автоматике и вычислительной технике и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Сущность изобретения состоит в проведении операции модульного сложения (вычитания) по частным модулям m₁ и m₂ (m₁·m₂ ≥ m , где m - модуль операции) с последующим преобразованием в результате операции по модулю. Устройство содержит дешифратор 2, два блока 3, 14 элементов И, две группы элементов ИЛИ 27, 28, пять элементов И 6, 7, 22, 24, 25, два элемента 11, 23 запрета, два преобразователя 18, 19 кода, два счетчика 13, 20, два элемента ИЛИ-НЕ 12, 21, коммутатор 29, шифратор 15, два кольцевых регистра 5, 26 сдвига. 3 табл., 1 ил.

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

Известно устройство для сложения и вычитания чисел в системе остаточных классов, содержащее входные регистры, выходной регистр, дешифратор, сумматор по модулю P, приемный регистр, схему сравнения, суммирующий счетчик, генератор импульсов, кольцевой регистр, умножитель частоты, элементы И и ИЛИ, группы элементов И и ИЛИ [1].

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

Известно устройство, содержащее входные регистры, дешифраторы, сумматоры по модулю P, выходной регистр, схему сравнения, суммирующий счетчик, приемный регистр, кольцевой регистр, генератор импульсов, умножитель частоты, группы элементов И, элементы И и ИЛИ [2].

Недостаток устройства - низкое быстродействие модульных операций.

Наиболее близким по технической сущности к изобретению является устройство для сложения и вычитания чисел по модулю, содержащее дешифратор, два блока элементов И, элемент запрета, шифратор, счетчик, элемент ИЛИ-НЕ, два элемента И, кольцевой регистр сдвига [3].

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

Цель изобретения - повышение быстродействия.

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

Сущность изобретения состоит в проведении операции модульного сложения (вычитания) по частным модулям m₁ и m₂ (m₁ m₂ ≥ m) с последующим преобразованием в результат операции по модулю m. Ввиду того, что m₁ (m₂) < m, достигается существенное повышение быстродействия. Одновременно можно отметить, что m₁ + m₂ < m, следовательно, уменьшается суммарное количество двоичных разрядов в двух кольцевых сдвигающих регистрах, необходимых для одновременного проведения операции модульного сложения (вычитания) по модулям m₁ и m₂. Также уменьшается разрядность счетчиков, необходимых для построения устройства. Для преобразования в окончательный результат необходим коммутатор размерностью m₁ ˙m₂. Рассмотрим подробнее построение устройства при m₁ = 3, m₂ = 5, m = 15. Табл. 1 отображает работу коммутатора.

Первый и второй преобразователи кода преобразуют входной операнд B в число B₁ и B₂ соответственно по модулю m₁ и m₂, как отражено на табл. 2 и 3.

Первый и второй кольцевые регистры сдвига состоят соответственно из трех и пяти двоичных разрядов (3 + 5 = 8 < 15), а максимальная длительность модульных операций составляет 5 тактов вместо 15 в прототипе. Первая группа элементов ИЛИ состоит из трех элементов, причем нулевой элемент ИЛИ объединяет 0, 3, 6, 9 и 12-й выходы дешифратора, первый - 1, 4, 7, 10 и 13-й; второй - 2, 5, 8, 11 и 14-й. Вторая группа элементов ИЛИ состоит из пяти элементов, причем нулевой элемент ИЛИ объединяет 0, 5 и 10-й выходы дешифратора, первый - 1, 6 и 11-й, второй - 2, 7 и 12-й, третий - 3, 8 и 13-й, четвертый - 4, 9 и 14-й.

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

Заявляемое техническое решение соответствует критерию "новизна", так как введенные новые признаки (первая и вторая группы элементов ИЛИ, с третьего по пятый элементы И, второй кольцевой регистр сдвига, коммутатор, первый и второй преобразователи кода, второй элемент запрета, второй счетчик и их связи) в совокупности с техническими свойствами вносимых изменений (уменьшение максимального количества сдвигов кольцевых регистров сдвига) являются существенными, т. е. новая совокупность признаков способствует достижению цели - повышению быстродействия.

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

На чертеже представлена структурная схема устройства, где 1 - первый информационный вход устройства, 2 - дешифратор, 3 - второй блок элементов И, 4 - вход начальной установки устройства, 5 - первый кольцевой регистр сдвига, 6 - первый элемент И, 7 - второй элемент И, 8 - вход задания сложения устройства, 9 - вход задания вычитания устройства, 10 - вход запуска устройства, 11 - первый элемент запрета, 12 - первый элемент ИЛИ-НЕ, 13 - первый счетчик, 14 - первый блок элементов И, 15 - шифратор, 16 - выход устройства, 17 - второй информационный вход устройства, 18 - первый преобразователь кода, 19 - второй преобразователь кода, 20 - второй счетчик, 21 - второй элемент ИЛИ-НЕ, 22 - пятый элемент И, 23 - второй элемент запрета, 24 - третий элемент И, 25 - четвертый элемент И, 26 - второй кольцевой регистр сдвига, 27 - первая группа элементов ИЛИ, 28 - вторая группа элементов ИЛИ, 29 - коммутатор.

Первый информационный вход 1 устройства соединен с входом дешифратора 2, выход которого соединен с первым входом второго блока 3 элементов И. Второй вход последнего соединен с входом 4 начальной установки устройства и с входом разрешения записи первого кольцевого регистра 5 сдвига, входы задания сдвига вправо и влево которого соединены с выходами соответственно первого 6 и второго 7 элементов И. Вторые входы элементов И 6 и 7 соединены соответственно с входами задания сложения 8 и вычитания 9 устройства, вход 10 запуска которого соединен с информационным входом первого элемента 11 запрета. Управляющий вход элемента 11 запрета соединен с выходом первого элемента ИЛИ-НЕ 12, а выход - с вычитающим входом первого счетчика 13, выходы разрядов которого соединены с соответствующими входами первого элемента ИЛИ-НЕ 12. Первые входы первого 6 и второго 7 элементов И соединены с выходом первого элемента 11 запрета, выход первого блока 14 элементов И соединен с входом шифратора 15, выход 16 которого является выходом устройства. Второй информационный вход 17 устройства соединен с входами первого 18 и второго 19 преобразователей кода, выходы которых соединены с установочными входами соответственно первого 13 и второго 20 счетчиков. Выходы разрядов счетчика 20 соединены с соответствующими входами второго элемента ИЛИ-НЕ 21, выход которого соединен с первым входом пятого элемента И 22 и с управляющим входом второго элемента 23 запрета. Информационный вход элемента 23 запрета соединен с информационным входом первого элемента 11 запрета, а выход - с вычитающим входом второго счетчика 20 и с первыми входами третьего 24 и четвертого 25 элементов И, вторые входы которых соединены с вторыми входами соответственно первого 6 и второго 7 элементов И, а выходы - с входами соответственно задания сдвига в право второго 26 кольцевого регистра сдвига, вход разрешения записи которого соединен с входом разрешения записи первого кольцевого регистра 5 сдвига. Выход первого элемента ИЛИ-НЕ 12 соединен с вторым входом пятого элемента И 22, выход которого соединен с первым входом первого блока 14 элементов И. Выходы второго блока 3 элементов И соединены с соответствующими входами элементов ИЛИ первой 27 и второй 28 групп, выходы которых соединены с входами соответствующих разрядов соответственно первого 5 и второго 26 кольцевых регистров сдвига. Выходы разрядов последних соединены соответственно с группами информационных и управляющих входов коммутатора 29, выходы которого соединены с вторыми входами соответствующих разрядов первого блока 14 элементов И.

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

Исходное состояние регистров 5, 26 - нули во всех разрядах. Сигнал на выходе элементов ИЛИ-НЕ 12, 21 появляются в том случае, когда на всех выходах счетчиков 13, 20 нули. При проведении операции модульного сложения ((A + B) mod m, где A, B - операнды) операнд A поступает на вход дешифратора 2. Первая 27 и вторая 28 группы элементов ИЛИ производят нахождение соответственно остатков операнда A по модулям m₁ и m₂, т.е. в унитарном коде производит определение чисел A₁, A₂ (A = =(A₁, A₂). Одиночный импульс, поступающий с входа 4 на второй вход блока 3 элементов И, обеспечивает запись единицы в A₁ (A₁ = ) и в A₂(A₂ = ) разрядах кольцевых 5 и 26 регистров сдвига. Операнд B поступает в двоичном коде на входы преобразователей 18 и 19 кода, которые производят определение остатков числа B по модулям m₁ и m₂, т.е. B₁ и B₂. В счетчиках 13 и 20 устанавливается соответственно числа B₁ и B₂ в двоичном коде. По сигналу входа 10 запуска устройства через открытые элементы 11 и 23 запрета поступают импульсы на входы счетчиков 13 и 20, а также на входы сдвига вправо содержимого регистров 5 и 26 через открытые элементы И 6 и 24 соответственно (присутствует сигнал на входе 8). Производится продвижение единицы, записанной в регистры 5 и 26, на B₁ и B₂ двоичных разрядов вправо. Когда содержимое счетчика 13 (20) становится равным нулю, сигнал с выхода ИЛИ-НЕ 12(21) закрывает элемент 11 (23) запрета, запрещая прохождение импульсов на сдвиг двоичных разрядов регистра 5 (26). В том случае, если содержимое счетчиков 13 и 20 станет равно нулю, то с выхода элемента И 22 на первый вход блока 14 элементов И поступает сигнал. На кольцевых регистрах 5 и 26 имеют унитарные коды модульных операций (A₁ + B₁) mod m и (A₂ + B₂) mod m₂, которые поступают на информационные и управляющие группы входов коммутатора 29, на выходе которого образуется унитарный код модульной операции (A + B) mod m, поступающий через открытый блок 14 элементов И на вход шифратора 15, с выхода которого результат операции модульного сложения поступает на выход 16 устройства.

Работа устройства при выполнении операции модульного вычитания (A - B) mod m отличается от модульного сложения только тем, что присутствует сигнал на входе 9, поэтому производится сдвиг разрядов регистров 5 и 26 соответственно на A₁ и A₂ двоичных разрядов влево.

Рассмотрим примеры конкретного выполнения операций модульного сложения и вычитания для m = 15.

П р и м е р 1. Пусть необходимо определить результат операции модульного сложения для A = 4, B = 11 (A и B - операнды).

Первый операнд A = 0100 поступает на вход дешифратора 2 и после импульса с входа 4 через первый элемент первой группы 27 элементов ИЛИ и через четвертый элемент второй группы 28 элементов ИЛИ в первом разряде регистра 5 и в четвертом разряде регистра 26 записаны единицы (остальные разряды регистров 5 и 26 - нули). Второй операнд B = 1011 устанавливает в содержимом счетчике 13 B = 10 и в содержимом счетчика 20 B₂ = 001 (см. табл. 2, 3). Следовательно, содержимое регистра 5 и регистра 26 имеет вид С входа 10 через элемент 23 запрета поступает один импульс, который продвигает единицу в регистре 26 на один двоичный разряд вправо (сигнал на входе 8 присутствует) и уменьшает содержимое счетчика 20 до нуля. С выхода элемента ИЛИ-НЕ 21 поступает сигнал, который закрывает элемент 23 запрета. Одновременно этот импульс продвигает единицу в регистре 5 на один двоичный разряд вправо и уменьшает содержимое счетчика 13 до единицы. Содержимое регистра 5 и регистра 26 имеет вид Затем с входа 10 через элемент 11 запрета поступает один импульс, который продвигает единицу только в регистре 5 на один двоичный сигнал вправо. С выхода элемента ИЛИ-НЕ 12 поступает сигнал, который закрывает элемент 11 запрета. На первый вход блока 14 элементов И поступает сигнал с выхода пятого элемента И 22. Состояние регистра 5 и регистра 26 следующее: Следовательно, на нулевые и информационный и управляющие входы коммутатора 29 поступают сигналы. Результат операции равен нулю (см. табл. 1). Этот результат через открытый блок 14 элементов И и шифратор 15 поступает в виде (A + B) mod 15 = 0000 на выход 16 устройства. Проверка (4 + 11) mod 15 = 0 mod 15.

П р и м е р 2. Пусть необходимо определить результат операции модульного вычитания для A = 4, B = 11 (A и B - операнды).

В этом случае все процессы происходят аналогично примеру 1, за исключением того, что сдвиг содержимого регистра 5 и регистра 26 (единиц) в A₁-м и A₂-м двоичных разрядах производится влево. Содержимое регистра 5 и регистра 26 по завершении операции следующее: Результат операции равен 8 = 1000 (см. табл. 1). Этот результат поступает на выход 16 устройства. Проверка (4 - 11) mod 15 = 8 mod 15. Коммутатор 29 производит преобразование [A₁(B₁) * A₂(B₂)] _→ A(B)
Техническое преимущество изобретения в сравнении с прототипом состоит в том, что примерно в раз повышается быстродействие выполнения модульных операций сложения и вычитания. Дополнительным преимуществом является уменьшение количества оборудования ввиду уменьшения суммарного числа двоичных разрядов обоих регистрах, а также разрядности счетчиков. В частности при m = 15 быстродействие повышается в три раза (m₂ = 5).

Достоверность достижения цели подтверждается конкретными примерами выполнения модульных операций сложения и вычитания при m = 15.

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

УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ, содержащее дешифратор, первый и второй блоки элементов И, шифратор, первый кольцевой регистр сдвига, первый и второй элементы И, первый счетчик, первый элемент ИЛИ - НЕ и первый элемент запрета, причем первый информационный вход устройства соединен с входом дешифратора, выход которого соединен с первыми входами элементов И первого блока, вторые входы которых соединены с входом начальной установки устройства и входом разрешения записи первого кольцевого регистра сдвига, входы задания сдвига вправо и влево которого соединены с выходами соответственно первого и второго элементов И, первые входы которых соединены соответственно с входами задания сложения и вычитания устройства, вход запуска которого соединен с прямым входом первого элемента запрета, инверсный вход которого соединен с выходом первого элемента ИЛИ - НЕ, а выход первого элемента запрета соединен с вторыми входами первого и второго элементов И и с вычитающим входом первого счетчика, выходы разрядов которого соединены с соответствующими входами первого элемента ИЛИ - НЕ, выходы элементов И второго блока соединены с входом шифратора, выход которого является выходом устройства, отличающееся тем, что оно содержит первую и вторую группы элементов ИЛИ, с третьего по пятый элементы И, второй кольцевой регистр сдвига, коммутатор, первый и второй преобразователи кода, второй элемент запрета, второй счетчик, второй элемент ИЛИ - НЕ, причем второй информационный вход устройства соединен с входами первого и второго преобразователей кода, выходы которых соединены с установочными входами соответственно первого и второго счетчиков, выходы разрядов второго счетчика соединены с соответствующими входами второго элемента ИЛИ - НЕ, выход которого соединен с первым входом третьего элемента И и инверсным входом второго элемента запрета, прямой вход которого соединен с прямым входом первого элемента запрета, а выход второго элемента запрета соединен с вычитающим входом второго счетчика и с первыми входами четвертого и пятого элементов И, вторые входы которых соединены с вторыми входами соответственно первого и второго элементов И, а выходы четвертого и пятого элементов И соединены с входами соответственно задания сдвига вправо и влево второго кольцевого регистра сдвига, вход разрешения записи которого соединен с входами разрешения записи первого кольцевого регистра сдвига, выход первого элемента ИЛИ - НЕ соединен с вторым входом третьего элемента И, выход которого соединен с первым входом элементов И второго блока, выходы элементов И первого блока соединены с соответствующими входами элементов ИЛИ первой и второй групп, выходы которых соединены с входами соответствующих разрядов первого и второго кольцевых регистров сдвига соответственно, выходы разрядов которых соединены соответственно с информационными управляющими входами коммутатора, выходы которого соединены с вторыми входами соответствующих элементов И второго блока.

РИСУНКИ

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