Устройство реализации операции "кубическое исключающее или"

Изобретение относится к вычислительной технике. Техническим результатом изобретения является расширение функциональных возможностей и увеличение производительности вычислительной техники. Технический результат достигается за счет аппаратной реализации операции «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ» (XOR, ). Устройство содержит n однотипных вычислительных ячеек. Каждая i-я вычислительная ячейка имеет четыре входа, два выхода и содержит элементы НЕ, элементы И и элементы ИЛИ. За счет оригинального двоичного кодирования троичных значений координат кубов и оригинального соединения входов и выходов элементов вычислительных ячеек реализуется троичная таблица истинности операции «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ» и достигается заявленный технический результат. 2 ил., 2 табл.

 

Изобретение относится к вычислительной технике и может быть использовано при создании специализированной ЭВМ (специализированного сопроцессора для универсальной ЭВМ), реализующих операции кубического исчисления, используемые в алгоритме Рота синтеза дискретных устройств (алгоритм извлечения) [см. Миллер Р. Теория переключательных схем. - М.: Наука, 1970. Т. 1; Проектирование цифровых вычислительных машин. Под ред. С.А. Майорова. Учебн. пособ. для вузов. М.. Высшая школа, 1972; Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). - Л.: Энергия, Ленингр. отд., 1979. - 232 с.; Луцик Ю.А., Лукьянова И.В. Арифметические и логические основы вычислительной техники: Учеб. пособие -Минск: БГУИР, 2014. - 174 с.].

Известно устройство реализации кубической операции х-произведение [А.с. SU 1656522 А1, авторы. Альбеков А.Ш., Герасимов Е.Р., 1991]. Устройство содержит n вычислительных ячеек, каждая из которых содержит элементы И, ИЛИ-НЕ, ИЛИ, по четыре входа и по три выхода и один решающий узел, содержащий 3n входов, 3n выходов и элементы ИЛИ, ЗАПРЕТ, мажоритарный элемент и реализует таблицу истинности кубической операции х-произведение [Миллер Р. Теория переключательных схем. - М.: Наука, 1970. Т. 1; Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). -Л.: Энергия, Ленингр. отд., 1979. - 232 с.]. Недостатком данного устройства

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

Известно устройство для обработки логической информации, реализующее кубическую операцию склеивания n-мерных кубов [Патент RU 2027218 С1, авторы: Альбеков А.Ш., Герасимов Е.Р., Хализев В.Н., 1995]. Устройство является комбинационным, с жесткой логикой, содержит n вычислительных ячеек, каждая из которых содержит элементы И, ИЛИ-НЕ, ИЛИ, по четыре входа и по три выхода и один решающий блок, содержащий 3n входов, 3n выходов и элементы И, ИЛИ, НЕ, ИСКЛЮЧАЮЩЕЕ ИЛИ и реализует таблицу истинности кубической операции склеивания n-мерных кубов [Миллер Р. Теория переключательных схем. - М.: Наука, 1970. Т. 1; Баранов С.И. Синтез микропрограммных автоматов (граф-схемы и автоматы). - Л.: Энергия, Ленингр. отд., 1979. - 232 с.]. Причина, которая не позволяет достичь с помощью аналога того технического результата, который обеспечивается заявляемым изобретением, заключается в невозможности реализации кубической операции ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR, ) из-за жесткости закона его функционирования.

Наиболее близким (прототипом) к патентуемому изобретению является устройство реализации кубической операции И [Патент РФ 2772311 от 18.05.2022 г., автор: Альбеков А.Ш.]. Устройство является комбинационным, с жесткой логикой, содержит n вычислительных ячеек, каждая из которых содержит элементы И, ИЛИ, НЕ, по четыре входа, по два выхода и реализует таблицу истинности кубической операции И n-мерных кубов [studall.org/all3-26567.html]. Причина, которая не позволяет достичь с помощью аналога того технического результата, который обеспечивается заявляемым изобретением, заключается в невозможности реализации прототипом операции «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ» (XOR, ) из-за жесткости закона его функционирования.

Целью изобретения является расширение функциональных возможностей и производительности специализированной вычислительной техники при реализации ею алгоритмов синтеза дискретных устройств и тестов поиска неисправностей схем автоматики и вычислительной техники. Цель достигается за счет аппаратной реализации операции «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ».

Техническим результатом изобретения является возможность схемного выполнения заявляемым устройством операции «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ» над n - мерными кубами. N - мерный куб К[1:n] представляет собой вектор, содержащий n координат (компонент), каждая из которых принимает значение на троичном множестве {0, 1, X}.

Операция «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ» осуществляется над двумя n-разрядными кубами К₁[1:n] и К₂[1:n] в соответствии с троичной таблицей истинности табл. 1 [см. studfile.net/preview/7014248/page:5; studall.org/all3-26567.html; dl.nure.ua/pluginfile.php/534/mod_resource/content/2 /content/example1.html].

Результатом выполнения операции является n-разрядный куб К₃[1:n], координаты которого также определены на троичном множестве {0, 1, X}.

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

С целью схемного представления троичных значений координат кубов предлагается двухпозиционное представление b[i] и x[i] (табл. 2) координат кубов К_j[1:n], j=1, 2, 3, где b[i] - позиция, кодирующая бинарные значения 0 и 1 из табл. 1; x[i] - позиция, кодирующая значение X из табл. 1.

Поскольку значения координат куба-результата К₃[1:n] независимы друг от друга и полностью определяются таблицей истинности (табл. 1), устройство содержит n независимых вычислительных ячеек, каждая из которых реализует табл. 1 с учетом принятой двоичной кодировки (табл. 2) значений координат, и не содержит решающего узла (блока), имеющегося в аналогах. Извлечение из таблиц 1 и 2 аналитических формул логических функций, реализуемых ячейками устройства, дает следующую систему уравнений, записанных в ДНФ на языке микроопераций (регистровых передач):

где b_k - кодовые значения бинарных (0, 1) координат кубов К_1,2,3[1:n]; - кодовые значения Х-координат кубов К_1,2,3[1:n]; i (i=1,2,…n) - номер кубической координаты; знак «точка» (•) означает «ЛОГИЧЕСКОЕ И»; знак V означает «ЛОГИЧЕСКОЕ ИЛИ».

На фиг. 1 представлена структурная схема устройства реализации операции «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ», на фиг. 2 - функциональная схема вычислительной ячейки 1 устройства. Каждая вычислительная ячейка устройства 2,…,3, как и ячейка 1, реализует систему логических функций (1) и идентична ячейке 1.

Устройство (фиг. 1) содержит n вычислительных ячеек 1, 2, 3; 2×n входов, соответствующих координатам куба К₁[1:n]; 2×n входов, соответствующих координатам куба К₂[1:n]; и 2×n выходов, соответствующих координатам куба-результата К₃[1:n].

Вычислительная ячейка 1 устройства (фиг. 2), имеет четыре входа, два выхода и содержит инверторы НЕ 4, 5, 6, 7, двухвходовые элементы И 8, 9, трехвходовые элементы И 10, 11, 15, четырехвходовой элемент И 12, двухвходовой элемент ИЛИ 13 и трехвходовой элемент ИЛИ 14.

Причем, первый вход ячейки соединен с входом элемента НЕ 4 и первым входом элемента И 8. Второй вход ячейки соединен с входом инвертора 5, вторым входом элемента И 10 и третьим входом элемента И 12. Третий вход ячейки соединен с входом инвертора 6 и вторым входом элемента И 9. Четвертый вход ячейки соединен с входом инвертора 7, третьим входом элемента И 11 и четвертым входом элемента И 12.

Выход инвертора 4 соединен с первым входом элемента И 9, первым входом элемента И 10 и первым входом элемента И 12. Выход инвертора 5 соединен со вторым входом элемента И 15 и вторым входом элемента И 11. Выход инвертора 6 соединен со вторым входом элемента И 8, первым входом элемента И 11 и вторым входом элемента И 12. Выход инвертора 7 соединен с третьим входом элемента И 15 и третьим входом элемента И 10.

Выход элемента И 8 соединен с первым входом элемента ИЛИ 13, а выход элемента И 9 соединен со вторым входом элемента ИЛИ 13, выход которого соединен с первым входом элемента И 15, выход которого является первым выходом вычислительной ячейки 1.

Выход элемента И 10 соединен с первым входом элемента ИЛИ 14, выход элемента И 11 соединен со вторым входом элемента ИЛИ 14, а выход элемента И 12 соединен с третьим входом элемента ИЛИ 14, выход которого является вторым выходом вычислительной ячейки 1.

Устройство работает следующим образом. На первые и вторые входы вычислительных ячеек 1,2,…,3 подается код куба К₁[1:n], на третьи и четвертые входы - код куба К₂[1:n]. На выходах вычислительных ячеек вырабатывается код куба К₃[1:n]=К₁[1:n] К₂[1:n], являющийся результатом операции «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ». Поскольку ячейки устройства являются комбинационными автоматами, то их работа полностью определена таблицей истинности (табл. 1) с учетом принятого двоичного кодирования (табл. 2) координат кубов (0, 1, X).

Повышение производительности вычислительного процесса с применением операции «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ», реализуемой заявляемым устройством, из-за жесткости законов функционирования аналогов, доказуемо в сравнении с универсальным программируемым вычислительным устройством последовательной архитектуры, при программной реализации им операции «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ». По сравнению с универсальным вычислительным устройством неймановской архитектуры (универсальным процессором) повышение производительности достигается тем, что заявляемое устройство реализует операцию, при условии выставления кодов кубов K₁[1:n] и K₂[1:n] на его входах, за четыре машинных такта в синхронном режиме работы и за один такт - в асинхронном, в то время, как универсальное устройство, с этой же целью, должно выполнить программный код поразрядной обработки кубов, состоящий из циклической последовательности операторов языка высокого уровня. Поскольку операция «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ» определена на 9-ти входных наборах (см. табл. 1), то циклический блок обработки таблицы 1 (напр., на С++) содержит 9 операторов if(), покрывающих все наборы таблицы:

Очевидно, что один оператор if() требует для своей реализации не менее 4-х машинных тактов, а обработка одного разряда кубов К₁[1:n], К₂[1:n] и К₃[1:n] требует, в среднем, выполнения 9/2=4,5 операторов if(). Следовательно, обработка всех разрядов кубов К₁[1:n], К₂[1:n] и К₃[1:n] потребует не менее 4×4,5×n машинных тактов, где n - разрядность обрабатываемых кубов. То есть, выигрыш В по времени реализации операции «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ» заявляемым устройством составит порядка 18×n/4 раз, где n - длина (размерность) обрабатываемых кубов. Так, для n=32, выигрыш составит В≥144 раз, а для n=64, выигрыш составит В>288 раз.

Устройство реализации операции «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ», содержащее n вычислительных ячеек, где n - размерность куба, причем каждая из n вычислительных ячеек содержит четыре элемента НЕ, два двухвходовых элемента И, три трехвходовых элемента И, один четырехвходовый элемент И, один двухвходовый элемент ИЛИ и один трехвходовый элемент ИЛИ, отличающееся тем, что с целью расширения функциональных возможностей за счет реализации операции «КУБИЧЕСКОЕ ИСКЛЮЧАЮЩЕЕ ИЛИ» над n - мерными кубами и с целью повышения производительности вычислений, каждая i-я вычислительная ячейка содержит четыре входа и два выхода, при этом первый вход i-й вычислительной ячейки соединен с входом первого элемента НЕ и первым входом первого двухвходового элемента И;

второй вход i-й вычислительной ячейки соединен с входом второго элемента НЕ, вторым входом первого трехвходового элемента И и третьим входом четырехвходового элемента И;

третий вход i-й вычислительной ячейки соединен с входом третьего элемента НЕ и вторым входом второго двухвходового элемента И;

четвертый вход i-й вычислительной ячейки соединен с входом четвертого элемента НЕ, третьим входом второго трехвходового элемента И и четвертым входом четырехвходового элемента И;

выход первого элемента НЕ соединен с первым входом второго двухвходового элемента И, первым входом первого трехвходового элемента И и первым входом четырехвходового элемента И;

выход второго элемента НЕ соединен со вторым входом третьего трехвходового элемента И и вторым входом второго трехвходового элемента И;

выход третьего элемента НЕ соединен со вторым входом первого двухвходового элемента И, первым входом второго трехвходового элемента И и вторым входом четырехвходового элемента И;

выход четвертого элемента НЕ соединен с третьим входом третьего трехвходового элемента И и третьим входом первого трехвходового элемента И;

выход первого двухвходового элемента И соединен с первым входом двухвходового элемента ИЛИ; выход второго двухвходового элемента И соединен со вторым входом двухвходового элемента ИЛИ, выход которого соединен с первым входом третьего трехвходового элемента И, выход которого является первым выходом i-й вычислительной ячейки;

выход первого трехвходового элемента И соединен с первым входом трехвходового элемента ИЛИ; выход второго трехвходового элемента И соединен со вторым входом трехвходового элемента ИЛИ; выход четырехвходового элемента И соединен с третьим входом трехвходового элемента ИЛИ, выход которого является вторым выходом i-й вычислительной ячейки.