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

 

Изобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Технический результат изобретения заключается в уменьшении количества оборудования. Он достигается за счет введения третьей и четвертой групп элементов ИЛИ, второго коммутатора, первого и второго элементов И, кольцевого регистра сдвига, элемента НЕ, элемента ИЛИ, счетчика, элемента ИЛИ-НЕ, элемента запрета и блока элементов И. Сущность изобретения состоит в уменьшении каждого операнда в k раз. После нахождения результата производится увеличение его в k раз с соответствующей коррекцией результата. В зависимости от соотношения A_modk и B_modk (A, B - операнды) происходит уменьшение числа логических элементов, необходимых для реализации устройства. 1 ил., 2 табл.

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

Известно устройство (аналог) (авт. св. СССР N 959067, МКИ G 06 P 7/49, Б.И. N 54, 1982 г.), содержащее два дешифратора, три группы элементов ИЛИ, 9 элементов ИЛИ, 4 группы ключей, 8 элементов И, сумматор по модулю 2, выходной регистр и два коммутатора. Недостаток устройства - большое количество оборудования.

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

Наиболее близким по технической сущности (прототипом к предлагаемому изобретению) является устройство (авт. св. N 1689949. МКИ G 06 F 7/72, Б.И. N 41, 1981 г.), содержащее входные регистры и дешифраторы, элементы И и ИЛИ, группы элементов И и ИЛИ, коммутатор, шифратор, элемент ИЛИ - НЕ. Общее количество логических элементов И коммутатора составляет (m + 1)²/4, где m- модуль устройства, что обуславливает основной недостаток его.

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

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

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

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

Сущность изобретения состоит в уменьшении каждого операнда в k раз и после нахождения результата производится увеличение его в k раз с соответствующей коррекцией результата в зависимости от соотношения Amodk и Bmodk (A и B - операнды), ввиду чего происходит уменьшение числа логических элементов, необходимых для реализации устройства.

Обозначим через Aʹ= [A/k], Bʹ= [B/k], Δ_A= = Amodk, Δ_B= Bmodk.

Тогда, например, при k = 3 и m - модуле операции вычитания имеем следующие соотношения: Δ_A= 0, Δ_B= 0 (A-B) modm = 3(A' - B') modm, Δ_A= 0, Δ_B= 1 (A-B) modm = [3(A' - B') - 1] modm, Δ_A= 0, Δ_B= 2 (A-B) modm = [3(A' - B') - 2] modm, Δ_A= 1, Δ_B= 0 (A-B) modm = [3(A' - B') + 1] modm, Δ_A= 1, Δ_B= 1
(A-B) modm = 3(A' - B') modm,
Δ_A= 1, Δ_B= 2
(A-B) modm = [3(A' - B') -1] modm,
Δ_A= 2, Δ_B= 0
(A-B) modm = [3(A' - B') + 2] modm,
Δ_A= 2, Δ_B= 1
(A-B) modm = [3(A' - B') + 1] modm,
Δ_A= 2, Δ_B= 2
(A-B) modm = 3(A' - B') modm,
Для построения устройства при m = 11 (k = 3) необходимо с учетом симметрии реализовать две таблицы: табл. 1 и 2.

В таблице 2 знаком показано направление коррекции промежуточного результата операции. При любом внутреннем модуле k устройство можно записать в общем виде
(A-B)modm = [k(Aʹ-Bʹ)+(Δ_A-Δ_B)]modm (1)
Если обозначить через N общее количество логических элементов, требуемых для построения двух таблиц, тогда имеем

Следовательно, оптимальное значение внутреннего модуля В этом случае общее число логических элементов N минимально.

т. е. при подобном варианте реализации устройства количество логических элементов нарастает пропорционально модулю устройства.

Отметим, что при m = 11, и в данном случае первая 3 группа элементов ИЛИ состоит из четырех элементов (первый объединяет 0, 1 и 2 выходы дешифратора 2; второй - 3, 4, 5; третий - 6, 7, 8; четвертый - 9, 10). Третья 10 группа элементов ИЛИ состоит из трех элементов (первый объединяет 0, 3, 6 и 9 выходы дешифратора 2; второй - 1, 4, 7, 10; третий - 2, 5, 8). Диагональ таблицы 2 содержит нулевые элементы, а элементы, которые находятся в клетках ниже ее, имеют положительный знак коррекции результата операции. Выходы первого 4 коммутатора соединены с двоичными разрядами кольцевого 20 регистра, номера которых указаны в табл.1. В исходном состоянии все m разрядов кольцевого 20 регистра сдвига содержат нули. Выходы второго 9 коммутатора объединены согласно наличию единицы в соответствующем двоичном разряде величины коррекции промежуточного результата операции согласно табл. 2. Элемент ИЛИ 11 объединяет выходы второго 9 коммутатора с положительным знаком коррекции промежуточного результата операции. В исходном состоянии счетчик 12, содержащий двоичное значение коррекции результата (промежуточного), имеет нули во всех ]k[ разрядах.

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

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

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

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

Рассмотрим работу устройства, которая производится в соответствии с формулой (1). Операнды A и B поступают в двоичном коде по соответствующим входам 1 и 5 на дешифраторы 2 и 6. Первая 5 и вторая 7 группы элементов ИЛИ осуществляют соответственно преобразованию A ---> A' и B ---> B'.

Третья 10 и четвертая 8 группы элементов ИЛИ осуществляют соответственно преобразованию A → Δ_A и B → Δ_B. Следовательно, на A'-й информационный и B'-й управляющий входы первого 4 коммутатора поступают сигналы. Выходной сигнал с коммутатора 4 производится запись единицы в [k(A' - B')]modm двоичном разряде кольцевого регистра 20 сдвига. На Δ_A-й информационный и Δ_B-й управляющий входы второго 8 коммутатора поступают сигналы. Выходной сигнал с коммутатора 9 производит запись величины в счетчик 12. Сигнал с выхода элемента ИЛИ 11 свидетельствует о положительном направлении коррекции промежуточного результата операции модульного вычитания. Если счетчик 12 содержит нулевую величину коррекции, то на выходе элемента ИЛИ-НЕ будет сигнал, который поступит на управляющий вход элемента 14 запрета, запрещая прохождение импульсов с тактового 17 входа устройства. Этот же сигнал поступает на вторые входы блока элементов И и результат операции с выходов КСР 20 в унитарном коде преобразуется в двоичную форму шифратором 21 и поступает на выход 16 устройства.

Пусть счетчик 12 содержит отличную от нуля величину коррекции и сигнал будет на выходе элемента ИЛИ 11, тогда с тактового входа на вычитающий вход счетчика 12 и вход сдвига вправо содержимого КСР 20 поступают импульсы, которые производят сдвиг вправо промежуточного результата операции в унитарном коде и уменьшают содержимое счетчика 12 до нуля. Дальнейшее протекание процесса получения результата операции описано выше. Если сигнала на выходе элемента ИЛИ 11 не будет, а содержимое счетчика 12 не равно нулю, то завершение процесса преобразования промежуточного результата операции в окончательный отличается только направлением сдвига содержимого КСР 20.

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

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

Операнд A = 4 в двоичном коде поступает на вход 1. Сигнал поступает с четвертого выхода дешифратора 2 через второй элемент первой 5 группы элементов ИЛИ на первый информационный вход коммутатора 4. Операнд B = 10 в двоичном коде поступает на вход 5. Сигнал поступает с десятого выхода дешифратора 6 через четвертый элемент второй 7 группы элементов ИЛИ на третий управляющий вход коммутатора 4. Согласно табл. 1 в пятом разряде КСР 20 будет произведена запись единицы. На первом информационном и первом управляющем входах второго 9 коммутатора будут сигналы. На выходе элемента ИЛИ 11 сигнала не будет. Содержимое счетчика 12 будет равно нулю. Сигнал с выхода элемента ИЛИ-НЕ поступает на второй вход блока 15 элементов И и результат операции с выхода шифратора 21 в двоичном виде 0101 поступает на выход 16 устройства
(4-10) mod 11 = 5 mod 11.

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

Прохождение операнда A=4 описано в примере 1. Сигнал с восьмого выхода дешифратора 6 через третий элемент второй 7 группы элементов ИЛИ на второй управляющий вход коммутатора 4. Согласно табл. 1 в восьмом разряде КСР 20 будет произведена запись единицы. На втором управляющем входе коммутатора 9 будет сигнал. Содержимое счетчика 12 будет равно единице. На выходе элемента ИЛИ 11 сигнала не будет. Состояние КСР 20 следующее: 0-0-0-0-0-0-0-0-1-0-0.

С тактового входа 17 устройства поступает один импульс, который переводит в ноль содержимое счетчика 12 и продвигает влево на один разряд содержимое КСР 20. Сигнал с выхода элемента ИЛИ-НЕ 13 открывает блок 15 элементов И и содержимое КСР 20: 0-0-0-0-0-0-0-1-0-0-0
с выхода шифратора 21 в виде 0111 поступает на выход 16. Это и будет результат модульной операции
(4-8) mod 11 = 7 mod 11.

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

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

РИСУНКИ

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