устройство для вычитания по модулю
| Классы МПК: | G06F7/49 для вычислений, выполняемых над числами с основанием, отличным от 2, 8, 16 или 10, например с троичным отрицательным или мнимым основаниями, комплексными основаниями G06F7/72 с помощью арифметического остатка |
| Автор(ы): | Ирхин В.П. |
| Патентообладатель(и): | Воронежский государственный университет |
| Приоритеты: |
подача заявки:
1997-12-04 публикация патента:
20.07.1999 |
Изобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительных машинах и устройствах, функционирующих в системе остаточных классов. Технический результат изобретения заключается в уменьшении количества оборудования. Он достигается за счет введения третьей и четвертой групп элементов ИЛИ, второго коммутатора, первого и второго элементов И, кольцевого регистра сдвига, элемента НЕ, элемента ИЛИ, счетчика, элемента ИЛИ-НЕ, элемента запрета и блока элементов И. Сущность изобретения состоит в уменьшении каждого операнда в k раз. После нахождения результата производится увеличение его в k раз с соответствующей коррекцией результата. В зависимости от соотношения Amodk и Bmodk (A, B - операнды) происходит уменьшение числа логических элементов, необходимых для реализации устройства. 1 ил., 2 табл.
Рисунок 1, Рисунок 2
Формула изобретения
Устройство для вычитания по модулю, содержащее первый и второй дешифраторы, три группы элементов ИЛИ, первый коммутатор, два элемента И, элемент НЕ, элемент ИЛИ-НЕ, шифратор, причем входы разрядов уменьшаемого устройства соединены с входами соответствующих разрядов первого дешифратора, l-е выходы которого
m - модуль операции, k - внутренний модуль устройства) соединены с d-ми входами t-х элементов ИЛИ первой группы, выходы которых соединены с соответствующими информационными входами первого коммутатора, входы разрядов вычитаемого устройства соединены с входами соответствующих разрядов второго дешифратора, l-е выходы которого соединены с d-ми входами t-х элементов ИЛИ второй группы, выходы которых соединены с соответствующими управляющими входами первого коммутатора, второй вход первого элемента И соединен с входом элемента НЕ, выход которого соединен с входом второго элемента И, отличающееся тем, что оно содержит второй коммутатор, четвертую группу элементов ИЛИ, кольцевой регистр сдвига, счетчик, элемент ИЛИ, элемент запрета, блок элементов И, причем l-е выходы второго дешифратора соединены с t-ми входами d-х элементов ИЛИ четвертой группы, выходы которых соединены с соответствующими информационными входами второго коммутатора, l-е выходы первого дешифратора соединены с t-ми входами d-х элементов ИЛИ третьей группы, выходы которых соединены с соответствующими управляющими входами второго коммутатора, выходы которого соединены с соответствующими входами элемента ИЛИ и с входами установки разрядов счетчика, выходы которого соединены с соответствующими входами элемента ИЛИ-НЕ, выход которого соединен с управляющим входом элемента запрета и вторыми входами элементов И блока, выход которого является выходом устройства, тактовый вход устройства соединен с информационным входом элемента запрета, выход которого соединен с вычитающим входом счетчика и с первыми входами первого и второго элементов И, выходы которых соединены соответственно с входами сдвига вправо и влево содержимого кольцевого регистра сдвига, входы установки разрядов которого соединены с соответствующими выходами первого коммутатора, а выходы - с соответствующими входами шифратора, выходы которого соединены с соответствующими первыми входами элементов И блока, выход элемента ИЛИ соединен с вторым входом первого элемента И.
Описание изобретения к патенту
Изобретение относится к области автоматики и вычислительной техники и может быть использовано в вычислительный машинах и устройствах, функционирующих в системе остаточных классов. Известно устройство (аналог) (авт. св. СССР 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)2/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.
Класс G06F7/49 для вычислений, выполняемых над числами с основанием, отличным от 2, 8, 16 или 10, например с троичным отрицательным или мнимым основаниями, комплексными основаниями
+1) "дополнительный код" с применением арифметических аксиом троичной системы счисления f(+1,0,-1) (варианты русской логики) - патент 2429523
Класс G06F7/72 с помощью арифметического остатка
