УСТРОЙСТВО ДЛЯ СЛОЖЕНИЯ И ВЫЧИТАНИЯ ЧИСЕЛ ПО МОДУЛЮ Российский патент 2000 года по МПК G06F7/49 G06F7/72 

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

Известно устройство (аналог) (Авт. св. СССР N 1636844, МКИ G 06 F 7/72, Б. И. N 11, 1991 г.), содержащее дешифраторы, блоки элементов И и ИЛИ, элементы запрета, кольцевой регистр сдвига, схему сравнения, элементы И и ИЛИ, шифраторы. Недостаток устройства - низкое быстродействие выполнения модульных операций.

Известно также устройство (аналог) (Авт. св. СССР N 1683011, МКИ G 06 F 7/72, Б. И. N 37, 1991 г.), содержащее кольцевой регистр сдвига, вычитатель по модулю, блоки элементов И, блок элементов ИЛИ, регистр, схему сравнения, счетчик, элементы запрета, шифратор, преобразователь единичного кода в унитарный код, преобразователь двоичного кода в единичный код. Недостаток устройства - низкое быстродействие выполнения модульных операций.

Наиболее близким по технической сущности (прототипом к предлагаемому изобретению) является устройство (Авт.св. СССР N 1820380, МКИ G 06 F 7/72, Б. И. N 21, 1993 г.), содержащее дешифратор, группу элементов ИЛИ, кольцевой регистр сдвига, шифратор, элементы И и ИЛИ, блок элементов И, преобразователи кода, счетчик, элементы ИЛИ-НЕ, элемент запрета, сумматор по модулю два, элементы НЕ. Длительность модульной операции пропорциональна модулю устройства, что обуславливает его основной недостаток.

Недостаток прототипа - низкое быстродействие, которое определяется в худшем случае (m-1)/2, т. е. пропорционально модулю устройства.

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

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

Технический результат достигается тем, что в устройство для сложения и вычитания чисел по модулю, содержащее дешифратор, первую группу элементов ИЛИ, с первого по третий блоки элементов И, первый счетчик, первый элемент ИЛИ-НЕ, первый элемент запрета, с первого по четвертый элементы И, первый и второй элементы НЕ, первый кольцевой регистр сдвига, элемент ИЛИ, шифратор, блок элементов ИЛИ и три преобразователя, причем первый информационный вход устройства соединен со входом дешифратора, 1-ые выходы которого (1 = (t•k+d) < m; m - модуль операции; k - внутренний модуль устройства) соединены с t-ми входами d-ых элементов ИЛИ первой группы, выходы которых соединены с первыми входами соответствующих элементов И первого блока, вторые входы которых соединены с входом начальной установки устройства и с входом разрешения записи первого кольцевого регистра сдвига, входы d-ых разрядов которого соединены с соответствующими выходами первого блока элементов И, первый вход второго элемента И соединен со входом первого элемента НЕ, выход которого соединен с первым входом первого элемента И, второй вход которого соединен с вторым входом второго элемента И, с выходом первого элемента запрета и с вычитающим входом первого счетчика, выходы разрядов которого соединены с соответствующими входами первого элемента ИЛИ-НЕ, выход которого соединен с управляющим входом первого элемента запрета, выходы второго и первого элементов И соединены соответственно с входами задания сдвига вправо и сдвига влево содержимого первого кольцевого регистра сдвига, введены вторая группа элементов ИЛИ, с четвертого по шестой блоки элементов И, дифференцирующая цепочка, с пятого по седьмой элементы И, второй и третий кольцевой регистры сдвига, со второго по четвертый элементы запрета, один из преобразователей выполнен в виде преобразователя кода числа в код [X/k), другой является преобразователем кода числа X в код Xmodk и третий - преобразователем кода числа в дополнительный код по модулю, второй счетчик, второй элемент ИЛИ-НЕ, причем 1-е выходы дешифратора соединены с d-ми входами t-ых элементов ИЛИ второй группы, выходы которых соединены с первыми входами соответствующих элементов И пятого блока, вторые входы которых соединены с входом начальной установки устройства и с входом разрешения записи второго кольцевого регистра сдвига, входы разрядов которого соединены с выходами соответствующих элементов И пятого блока, а выходы разрядов - с первыми входами соответствующих элементов И шестого блока, n-ые выходы которого соединены с (k•n•mod m)-ми входами разрядов третьего кольцевого регистра сдвига, выходы разрядов которого соединены с первыми входами соответствующих элементов И четвертого блока, выходы которого соединены со входами шифратора, выход которого является выходом устройства, второй информационный вход устройства соединен с первыми входами второго и третьего блоков элементов И, выходы которого соединены со входами преобразователя кода числа в дополнительный код по модулю, выход которого соединен с первым входом блока элементов ИЛИ, второй вход которого соединен с выходом второго блока элементов И, входы задания вычитания и сложения устройства соединены со вторыми входами соответственно второго и третьего блоков элементов И, выход блока элементов ИЛИ соединен с преобразователем кода числа X в код Xmodk и преобразователем кода числа X в код [X/k), выходы которых соединены с установочными входами соответственно первого и второго счетчиков, выходы разрядов последнего из которых соединены с соответствующими входами второго элемента ИЛИ-НЕ, выход которого соединен с управляющим входом второго элемента запрета, выход которого соединен с вычитающим входом второго счетчика и входом разрешения сдвига второго кольцевого регистра сдвига, выходы первого и второго элементов ИЛИ-НЕ соединены соответственно с первым и вторым входами шестого элемента И, выход которого соединен с первыми входами пятого и седьмого элементов И, второй вход которого соединен с выходом третьего элемента запрета и информационными входами первого и второго элементов запрета, а выход - с информационным входом четвертого элемента запрета, управляющий вход которого соединен с выходом нулевого разряда первого кольцевого регистра сдвига, со вторыми входами разрядов четвертого блока элементов И и управляющим входом третьего элемента запрета, информационный вход которого соединен с тактовым входом устройства, выход пятого элемента И соединен с входом первого элемента НЕ, p-ые выходы первого кольцевого регистра сдвига соединены с соответствующими входами элемента ИЛИ, выход которого соединен со вторым входом пятого элемента И, первым входом четвертого элемента И и входом второго элемента НЕ, выход которого соединен с первым входом третьего элемента И, выход четвертого элемента запрета соединен с первым входом второго элемента И и вторыми входами третьего и четвертого элементов И, выходы которых соединены соответственно со входами сдвига вправо и влево содержимого третьего кольцевого регистра сдвига, входы разрешения записи разрядов которого и вторые входы разрядов шестого блока элементов И соединены с выходом дифференцирующей цепочки, вход которой соединен с выходом второго элемента ИЛИ-НЕ.

Сущность изобретения состоит в уменьшении каждого операнда в k раз, и после нахождения результата производится его увеличение в k раз с последующей коррекцией в зависимости от соотношения Amodk и Bmodk (A, B - операнды), ввиду чего происходит уменьшение количества тактов, необходимых для реализации модульной операции. Обозначим A' = [A/k], B' = [B/k], Δ_A = Amodk, Δ_B = Bmodk. Тогда для любого внутреннего модуля k устройства можно записывать в общем виде
(A-B)modm = [k(A′-B′)+(Δ_A-Δ_B)]modm (1)
Операция модульного сложения реализуется при помощи следующего соотношения:
(A+B)modm=[A-(m-B)]modm.

Для модуля m = 11 и внутреннего модуля k = 3 имеем следующие основные параметры устройства:
- первая 3 группа элементов ИЛИ состоит из трех элементов (нулевой объединяет 0, 3, 6 и 9 выходы дешифратора 2; первый - 1, 4, 7 и 10 выходы дешифратора 2; второй - 2, 5 и 8 выходы дешифратора 2);
- вторая 13 группа элементов ИЛИ состоит из четырех элементов (нулевой объединяет 0, 1 и 2 выходы дешифратора 2; первый - 3, 4 и 5 выходы дешифратора 2; второй - 6, 7 и 8 выходы дешифратора 2; третий - 9 и 10 выходы дешифратора 2);
первый 6 кольцевой регистр сдвига, в котором проводится операция (Δ_A-Δ_B)mod11, состоит из 5 разрядов с номерами соответственно 0, 1, 2, 9 и 10;
- второй 15 кольцевой регистр сдвига, в котором проводится операция (A' - B') mod 11, состоит из 7 разрядов с номерами соответственно 0, 1, 2, 3, 8, 9 и 10;
- третий 17 кольцевой регистр сдвига, в котором получается окончательный результат операции (A - B)mod 11 состоит из 11 разрядов, соединение которых с разрядами второго 15 кольцевого регистра сдвига показано условно

Эти связи реализуют операцию умножения на k величины (A' - B') из формулы (1), а k = 3;
- элемент ИЛИ 39 объединяет выходы разрядов 9 и 10 первого 6 кольцевого регистра сдвига.

Дифференцирующая 43 цепочка производит преобразование постоянного сигнала в одиночный импульс, на месте которой может быть использован ждущий мультивибратор. Преобразователи 28 и 29 выполнены на программируемых логических матрицах (ПЛМ), в которых используются не все логические элементы матрицы постоянных запоминающих устройств (ПЗУ), что при выполнении специализированных функций уменьшает потребляемую мощность и время распространения сигналов.

Выходы нулевого, первого и второго элементов первой 3 группы элементов ИЛИ соединены через первый 4 блок элементов И с выходами соответствующих разрядов первого 6 кольцевого регистра сдвига, а выходы нулевого, первого, второго и третьего элементов второй 13 группы элементов ИЛИ - через пятый 14 блок элементов И с выходами соответствующих разрядов второго 15 кольцевого регистра сдвига.

Определим оптимальную по быстродействию величину внутреннего модуля устройства (К). Нижнюю границу быстродействия устройства выразим через количество тактов N, необходимых для проведения одной модульной операции:


при этом

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

На чертеже представлена структурная схема устройства, где 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 - преобразователь кода числа X в код Xmodk, 29 - преобразователь кода числа X в код [X/k], 30 - второй счетчик, 31 - второй элемент ИЛИ-НЕ, 32 - второй элемент запрета, 33 - шестой элемент И, 34 - пятый элемент И, 35 - седьмой элемент И, 36 - третий элемент запрета, 37 - четвертый элемент запрета, 38 - тактовый вход устройства, 39 - элемент ИЛИ, 40 - четвертый элемент И, 41 - второй элемент НЕ, 42 - третий элемент И, 43 - дифференцирующая цепочка. Первый 1 информационный вход устройства соединен со входом дешифратора 2, 1-ые выходы которого (1 = (t-k + d) < m; m - модуль операции; k - внутренний модуль устройства) соединены с t-ми входами d-ых элементов ИЛИ первой 3 группы, выходы которых соединены с первыми входами соответствующих элементов первого 4 блока элементов И, вторые входы элементов которого соединены с входом 5 начальной установки устройства и с входом разрешения записи первого 6 кольцевого регистра сдвига, входы d-ых разрядов которого соединены с выходами соответствующих элементов первого 4 блока элементов И, первый вход второго 7 элемента И соединен со входом первого 8 элемента НЕ, выход которого соединен с первым входом первого 9 элемента И, второй вход которого соединен со вторым входом второго 7 элемента И, с выходом первого 10 элемента запрета и с вычитающим входом первого 11 счетчика, выходы разрядов которого соединены с соответствующими входами первого 12 элемента ИЛИ-НЕ, выход которого соединен с управляющим входом первого 10 элемента запрета, выходы второго 7 и первого 9 элементов И соединены соответственно с входами задания сдвига вправо и сдвига влево содержимого первого 6 кольцевого регистра сдвига, причем 1-е выходы дешифратора 2 соединены с d-ми входами t-ых элементов ИЛИ второй 13 группы, выходы которых соединены с первыми входами соответствующих элементов пятого 14 блока элементов И, вторые входы разрядов которого соединены с входом 5 начальной установки устройства и с входом разрешения записи второго 15 кольцевого регистра сдвига, входы разрядов которого соединены с выходами соответствующих элементов пятого 14 блока элементов И, а выходы разрядов - с первыми входами соответствующих элементов шестого 16 блока элементов И, n-ые выходы разрядов соединены с (knmodm)-ми входами разрядов третьего 17 кольцевого регистра сдвига, выходы разрядов которого соединены с первыми входами соответствующих элементов четвертого 18 блока элементов И, выход которого соединен со входом шифратора 19, выход которого является выходом 20 устройства, второй 21 информационный вход устройства соединен с первыми входами второго 22 и третьего 23 блоков элементов И, выход которого соединен со входом преобразователя кода 24 числа в дополнительный код по модулю, выход которого соединен с первым входом блока 25 элементов ИЛИ, второй вход которого соединен с выходом второго 22 блока элементов И, входы задания вычитания 26 и сложения 27 устройства соединены с вторыми входами соответственно второго 22 и третьего 23 блоков элементов И, выход блока 25 элементов ИЛИ соединен с преобразователем кода 28 числа X в код Xmodk и преобразователем кода числа в код [X/k}, выходы которых соединены с установочными входами соответственно первого 11 и второго 30 счетчиков, выходы разрядов которого соединены с соответствующими входами второго 31 элемента ИЛИ-НЕ, выход которого соединен с управляющим входом второго 32 элемента запрета, выход которого соединен с вычитающим входом второго 30 счетчика и входом разрешения сдвига второго 15 кольцевого регистра сдвига, вход разрешения записи которого соединен со входом начальной установки устройства, выходы первого 12 и второго 31 элементов ИЛИ-НЕ соединены соответственно с первым и вторым входами шестого 33 элемента И, выход которого соединен с первыми входами пятого 34 и седьмого 35 элементов И, второй вход которого соединен с выходом третьего 36 элемента запрета и информационными входами первого 10 и второго 32 элементов запрета, а выход - с информационным входом четвертого 37 элемента запрета, управляющий вход которого соединен с выходом нулевого разряда первого 6 кольцевого регистра сдвига, со вторыми входами элементов четвертого 18 блока элементов И и управляющим входом третьего 36 элемента запрета, информационный вход которого соединен с тактовым входом 38 устройства, выход пятого 34 элемента И соединен со вторым входом второго 7 элемента И и входом первого 8 элемента НЕ, p-ые выходы первого 6 кольцевого регистра сдвига соединены с соответствующими входами элемента ИЛИ 39, выход которого соединен со вторым входом пятого 34 элемента И, первым входом четвертого 40 элемента И и входом второго 41 элемента НЕ, выход которого соединен с первым входом третьего 42 элемента И, выход четвертого 37 элемента запрета соединен с первым входом второго 7 элемента И и вторыми входами третьего 42 и четвертого 40 элементов И, выходы которых соединены соответственно со входами сдвига вправо и влево содержимого третьего 17 кольцевого регистра сдвига, входы разрешения записи разрядов которого и вторые входы элементов шестого 16 блока элементов И соединены с выходом дифференцирующей 43 цепочки, вход которой соединен с выходом второго 31 элемента ИЛИ-НЕ.

Работу устройства удобно рассматривать в двух режимах.

1. Режим определения результата операции модульного вычитания. 2. Режим определения результата операции модульного сложения. В первом режиме операнд A со входа 1 поступает на вход дешифратора 2, а с A-го выхода которого -на [A/k] -ый вход (A-[A/k)K)-го элемента ИЛИ первой 3 группы. С его выхода сигнал поступает на первый вход (Amodk)-го элемента первого 4 блока элементов И. С A-го выхода дешифратора 2 сигнал также поступает на (A-[A/k]K)-ый вход [A/k] -го элемента ИЛИ второй 13 группы, с выхода которого сигнал поступает на первый вход [A/k]-го элемента пятого 14 блока элементов И. По одиночному импульсу, поступающему со входа 5 начальной установки устройства в [A/'k]-ый разряд второго 15 кольцевого регистра сдвига и в (Amodk)-ый разряд первого 6 кольцевого регистра сдвига, производится запись единицы. Операнд B в двоичном коде через открытый второй 22 блок элементов И (сигнал на входе 26 задания вычитания присутствует) поступает на второй вход блока 25 элементов ИЛИ, с выхода которого B поступает на входы преобразователя 28 кода числа X в код Xmodk и преобразователя 29 кода числа X в код [X/k]. Величины Вmodk и [B/k] в двоичном коде поступают на установочные входы соответственно первого 11 и второго 30 счетчиков. Импульсы с тактового входа 38 устройства через третий 36 элемент запрета поступают на вычитающие входы второго 30 и первого 11 счетчиков через соответствующие второй 32 и первый 10 элементы запрета, с выходов которых они поступают также соответственно на вход разрешения сдвига второго 15 кольцевого регистра сдвига и второй вход первого 9 элемента И, с выхода которого импульсы поступают на вход задания сдвига влево первого 6 кольцевого регистра сдвига. Когда содержимое второго 30 счетчика станет равным нулю, то на выходе второго 31 элемента ИЛИ-НЕ будет сигнал, который поступит на управляющий вход второго 32 элемента запрета, прекращая поступление тактовых импульсов как на вычитающий вход второго 30 счетчика, так и на вход разрешения сдвига второго 15 кольцевого регистра сдвига. Одновременно этот сигнал поступит на вход дифференцирующей 43 цепочки, с выхода которой одиночный импульс, поступивший на вторые входы элементов шестого 16 блока элементов И и входы разрешения записи третьего 17 кольцевого регистра сдвига, произведет запись полученного результата (A' - B')modm (см. ф-лу (1)) из второго 15 кольцевого регистра сдвига в виде k: (A' - B')modm (см. ф-лу (1)) в третий 17 кольцевой регистр сдвига. Когда содержимое первого 11 счетчика станет равным нулю, то с выхода первого 12 элемента ИЛИ-НЕ сигнал поступит на управляющий вход первого 10 элемента запрета, прекращая поступление тактовых импульсов на вычитающий вход первого 11 счетчика и вход задания сдвига влево первого 6 кольцевого регистра сдвига. При этом образуется другая цепочка прохождения тактовых импульсов на входы задания сдвига первого 6 и третьего 17 кольцевых регистров сдвига. Тактовые импульсы с выхода третьего 36 элемента запрета поступают через второй вход седьмого 35 элемента И (сигнал на первом входе которого присутствует) и далее через четвертый 37 элемент запрета. При этом, если результат операции (Δ_A-Δ_B)modm, см. ф-лу(1)), реализуемый первым 6 кольцевым регистром сдвига, оказывается в p-ых разрядах его, то для повышения быстродействия устройства и уменьшения количества разрядов первого 6 кольцевого регистра сдвига при проведении коррекции (см. ф-лу (1)) производится изменение направления сдвига в первом 6 и третьем 17 кольцевых регистрах сдвига. При этом сигнал с выхода элемента ИЛИ 39 поступает на второй вход второго 7 элемента И и первый вход четвертого 40 элемента И, обеспечивая сдвиг вправо содержимого первого 6 кольцевого регистра сдвига и сдвиг влево содержимого третьего 17 кольцевого регистра сдвига. При отсутствии сигнала с выхода элемента ИЛИ 39 сдвиг содержимого кольцевых регистров 6 и 17 происходит в противоположных направлениях. Когда единица оказывается в нулевом разряде первого 6 кольцевого регистра сдвига, то соответствующий сигнал с его выхода поступает на управляющий вход четвертого 37 элемента запрета, прекращая поступление тактовых импульсов, и одновременно поступает на вторые входы элементов четвертого 18 блока элементов И.

Результат операции модульного вычитания с выходов разрядов третьего 17 кольцевого регистра сдвига поступает в унитарном коде на вход шифратора 19, с выхода которого в двоичном коде поступает на выход 20 устройства.

В режиме определения результата операции модульного сложения (сигнал на шине 27 присутствует) на выход блока 25 элементов ИЛИ поступает не операнд B, а число (m-B) в двоичном коде, т.е. все происходит аналогично первому режиму, но с операндами A и (m-B) (см. ф-лу (2)).

Рассмотрим примеры конкретного выполнения модульных операций при m = 11, K = 3.

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

Операнд A = 0111₂ поступает на вход дешифратора 2 и с седьмого выхода его на второй вход первого элемента ИЛИ первый 3 группы. С его выхода сигнал поступает на первый вход первого элемента первого 4 блока элементов И. С седьмого выхода дешифратора 2 сигнал также поступает на первый вход второго элемента ИЛИ второй 13 группы, с выхода которого сигнал поступает на первый вход второго элемента пятого 14 блока элементов И. По одиночному импульсу, поступающему со входа 5 начальной установки во второй разряд второго 15 кольцевого регистра сдвига и в первый разряд первого 6 кольцевого регистра сдвига производится запись единицы. Операнд B = 0100₂ через открытый второй 22 блок элементов И поступает на входы преобразователя 28 кода числа X в код Xmod3 и преобразователя 29 кода числа X в код [X/3]. Величины Bmod3=001₂ и [B/3] = 001₂ поступают на установочные входы соответственно первого 11 и второго 30 счетчиков. Исходное состояние первого 6 и второго 15 кольцевых регистров сдвига (КРС1, КРС2) следующее:

С тактового входа 38 устройства поступает импульс через третий 36 элемент запрета на вычитающие входы второго 30 и первого 11 счетчиков через соответствующие второй 32 и первый 10 элементы запрета, с выходов которых он поступает также соответственно на вход разрешения сдвига второго 15 кольцевого регистра сдвига и второй вход первого 9 элемента И, с выхода которого импульс поступает на вход задания сдвига влево первого 6 кольцевого регистра сдвига. Состояние первого 6 и второго 15 кольцевых регистров сдвига следующее:

Содержимое первого 11 и второго 30 счетчиков равно нулю. На выходе второго 31 элемента ИЛИ-НЕ будет сигнал, который поступит на управляющий вход второго 32 элемента запрета, прекращая поступление следующих импульсов как на вычитающий вход второго 30 счетчика, так как и на вход разрешения сдвига второго 15 кольцевого регистра сдвига. Этот сигнал поступит также на вход дифференцирующей 43 цепочки, с выхода которой одиночный импульс, поступивший на вторые входы элементов шестого 16 блока элементов И и входы разрешения записи третьего 17 кольцевого регистра сдвига, производит запись (2 - l)mod11 из второго 15 кольцевого регистра сдвига в виде (3•1)mod11 в третий 17 кольцевого регистра сдвига. Ввиду того, что содержимое первого 11 счетчика равно нулю и единица находится в нулевом разряде первого 6 кольцевого регистра сдвига, сигнал с его выхода поступает на управляющий вход четвертого 37 элемента запрета, запрещая поступление тактовых импульсов на входы сдвига вправо и влево содержимого третьего 17 кольцевого регистра сдвига. Одновременно этот сигнал поступает на вторые входы элементов четвертого 18 блока элементов И. Результат операции модульного вычитания с выходов разрядов третьего 17 кольцевого регистра сдвига поступает в унитарном коде на вход шифратора 19, с выхода которого результат операции (7 - 4)mod11 =0011₂ поступает на выход 20 устройства.

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

В этом случае прохождение операнда A = 0111₂ и запись A' и Δ_A в кольцевые регистры сдвига соответственно второй 15 и первый 6 в унитарном коде аналогично первому примеру. Следовательно, исходное состояние первого 6 и второго кольцевых регистров сдвига (КРС1, КРС2) следующее:

Операнд В = 0011₂ через открытый третий 27 блок элементов И поступает на вход преобразователя 24 кода числа в дополнительный код по модулю, с выхода которого число 1000₂ через блок 25 элементов ИЛИ поступает на входы преобразователя 28 кода числа X в код Xmod3 = 010₂ и преобразователя 29 кода числа X в код [X/3] = 010₂. Эти величины поступают на установочные входы соответственно первого 11 и второго 30 счетчиков. С тактового входа 38 устройства поступает импульс через третий 36 элемент запрета на вычитающие входы второго 30 и первого 11 счетчиков через соответствующие второй 32 и первый 10 элементы запрета, с выходов которых он поступает также соответственно на вход разрешения сдвига второго 15 кольцевого регистра сдвига и второй вход первого 9 элемента И, с выхода которого импульс поступает на вход задания сдвига влево первого 6 кольцевого регистра сдвига. Состояние первого 6 и второго 15 кольцевого регистра сдвига следующие:

После прохождения второго импульса состояние кольцевых регистров сдвига 6 и 15 будет следующее:

На выходе второго 31 элемента ИЛИ-НЕ будет сигнал, который поступит на управляющий вход второго 32 элемента запрета, прекращая поступление тактовых импульсов на вычитающий вход второго 30 счетчика, так и на вход разрешения сдвига второго 15 кольцевого регистра сдвига. Одновременно этот сигнал поступит на вход дифференцирующей 43 цепочки, с выхода которой одиночный импульс, поступивший на вторые входы элементов шестого 16 блока элементов И и входы разрешения записи третьего 17 кольцевого регистра сдвига, произведет запись полученного результата (2-2)mod11= 0mod11 из второго 15 кольцевого регистра сдвига в виде 3•0mod11=0mod11 в третий 17 кольцевой регистр сдвига. Так как на управляющем входе первого 10 элемента запрета есть сигнал, то тактовые импульсы с выхода третьего 36 элемента запрета поступают на второй вход седьмого 35 элемента И (сигнал на первом входе которого присутствует) и далее на информационный вход четвертого 37 элемента запрета. При этом с выхода элемента ИЛИ 39 поступает сигнал на второй вход второго 7 элемента И и первый вход четвертого 40 элемента И, обеспечивая сдвиг вправо содержимого первого 6 кольцевого регистра сдвига и сдвиг влево содержимого третьего 17 кольцевого регистра сдвига. После прохождения одного тактового импульса состояние первого 6 и третьего 17 кольцевых регистров сдвига будет следующее:

На управляющем входе четвертого 37 элемента запрета будет сигнал, который прекращает прохождение тактовых импульсов и открывает четвертый 18 блок элементов И. Результат операции модульного сложения (7+3)mod11=1010₂ с выхода шифратора 19 поступает на вход 20 устройства.

Изобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Техническим результатом является повышение быстродействия. Устройство содержит две группы элементов ИЛИ, три кольцевых регистра сдвига, шесть блоков элементов И, дифференцирующую цепочку, семь элементов И, четыре элемента запрета, шифратор, дешифратор, блок элементов ИЛИ, два элемента НЕ, два счетчика, два элемента ИЛИ-НЕ, элемент ИЛИ, преобразователь числа в код [Х/k], преобразователь кода числа Х в код Xmodk, преобразователь кода числа в дополнительный код по модулю. Сущность изобретения состоит в уменьшении каждого операнда К раз, и после нахождения результата производится увеличение его в k с последующей коррекцией в зависимости от отношения Amodk и Bmodk (А, В - операнды), ввиду чего происходит уменьшение количества тактов, необходимых для реализации модульной операции. 1 ил.

Устройство для сложения и вычитания чисел по модулю, содержащее дешифратор, первую группу элементов ИЛИ, с первого по третий блоки элементов И, первый счетчик, первый элемент ИЛИ-НЕ, первый элемент запрета, с первого по четвертый элементы И, первый и второй элементы НЕ, первый кольцевой регистр сдвига, элемент ИЛИ, шифратор, блок элементов ИЛИ и три преобразователя, причем, первый информационный вход устройства соединен со входом дешифратора, 1-е выходы которого (1=(t•k+d) < m; m - модуль операции; k - внутренний модуль устройства) соединены с t-ми входами d-х элементов ИЛИ первой группы, выходы которых соединены с первыми входами соответствующих элементов И первого блока, вторые входы которых соединены с входом начальной установки устройства и с входом разрешения записи первого кольцевого регистра сдвига, входы d-х разрядов которого соединены с соответствующими выходами первого блока элементов И, первый вход второго элемента И соединен со входом первого элемента НЕ, выход которого соединен с первым входом первого элемента И, второй вход которого соединен с вторым входом второго элемента И, с выходом первого элемента запрета и с вычитающим входом первого счетчика, выходы разрядов которого соединены с соответствующими входами первого элемента ИЛИ-НЕ, выход которого соединен с управляющим входом первого элемента запрета, выходы второго и первого элементов И соединены соответственно с входами задания сдвига вправо и сдвига влево содержимого первого кольцевого регистра сдвига, отличающийся тем, что в него введены вторая группа элементов ИЛИ, с четвертого по шестой блоки элементов И, дифференцирующая цепочка, с пятого по седьмой элементы И, второй и третий кольцевой регистры сдвига, со второго по четвертый элементы запрета, один из преобразователей выполнен в виде преобразователя кода числа в код [X/k] , другой - является преобразователем кода числа X в код Xmodk и третий - преобразователем кода числа в дополнительный код по модулю, второй счетчик, второй элемент ИЛИ-НЕ, причем 1-е выходы дешифратора соединены с d-ми входами t-х элементов ИЛИ второй группы, выходы которых соединены с первыми входами соответствующих элементов И пятого блока, вторые входы которых соединены с входом начальной установки устройства и с входом разрешения записи второго кольцевого регистра сдвига, входы разрядов которого соединены с выходами соответствующих элементов И пятого блока, а выходы разрядов - с первыми входами соответствующих элементов И шестого блока, n-е выходы которого соединены с (k • n • mod m)-ми входами разрядов третьего кольцевого регистра сдвига, выходы разрядов которого соединены с первыми входами соответствующих элементов И четвертого блока, выходы которого соединены со входами шифратора, выход которого является выходом устройства, второй информационный вход устройства соединен с первыми входами второго и третьего блоков элементов И, выходы которого соединены со входами преобразователя кода числа в дополнительный код по модулю, выход которого соединен с первым входом блока элементов ИЛИ, второй вход которого соединен с выходом второго блока элементов И, входы задания вычитания и сложения устройства соединены со вторыми входами соответственно второго и третьего блоков элементов И, выход блока элементов ИЛИ соединен с преобразователем кода числа Х в код Xmodk и преобразователем кода числа Х в код [X/k], выходы которых соединены с установочными входами соответственно первого и второго счетчиков, выходы разрядов последнего из которых соединены с соответствующими входами второго элемента ИЛИ-НЕ, выход которого соединен с управляющим входом второго элемента запрета, выход которого соединен с вычитающим входом второго счетчика и входом разрешения сдвига второго кольцевого регистра сдвига, выходы первого и второго элементов ИЛИ-НЕ соединены соответственно с первым и вторым входами шестого элемента И, выход которого соединен с первыми входами пятого и седьмого элементов И, второй вход которого соединен с выходом третьего элемента запрета и информационными входами первого и второго элементов запрета, а выход - с информационным входом четвертого элемента запрета, управляющий вход которого соединен с выходом нулевого разряда первого кольцевого регистра сдвига, со вторыми входами разрядов четвертого блока элементов И и управляющим входом третьего элемента запрета, информационный вход которого соединен с тактовым входом устройства, выход пятого элемента И соединен с входом первого элемента НЕ, p-е выходы первого кольцевого регистра сдвига соединены с соответствующими входами элемента ИЛИ, выход которого соединен со вторым входом пятого элемента И, первым входом четвертого элемента И и входом второго элемента НЕ, выход которого соединен с первым входом третьего элемента И, выход четвертого элемента запрета соединен с первым входом второго элемента И и вторыми входами третьего и четвертого элементов И, выходы которых соединены соответственно со входами сдвига вправо и влево содержимого третьего кольцевого регистра сдвига, входы разрешения записи разрядов которого и вторые входы разрядов шестого блока элементов И соединены с выходом дифференцирующей цепочки, вход которой соединен с выходом второго элемента ИЛИ-НЕ.