Устройство решения систем логических уравнений Российский патент 2018 года по МПК G06F17/12 

Описание патента на изобретение RU2654137C1

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

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

Недостатком данного устройства является низкое быстродействие.

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

Недостатком данного устройства является также низкое быстродействие.

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

Поставленная цель достигается тем, что в устройство решения систем логических уравнений, включающее генератор тактовых импульсов, вычитающий счетчик, выходы которого подключены к информационным входам выходного регистра, 2n блоков двухвходовых логических элементов И, устройство сравнения, выход которого подключен к входу подачи сигнала записи выходного регистра, вход подачи значений коэффициентов уравнений, являющийся входом устройства, d выходов выдачи результатов вычисления системы логических уравнений, являющихся выходами устройства; введены блоки памяти 1-й группы блоков памяти, первые входы каждого из которых подключены к входу подачи значений коэффициентов уравнений, являющемуся входом устройства; устройство распределения тактовых импульсов, первый вход которого подключен к входу подачи сигнала начала работы устройства, являющемуся входом устройства, второй вход подключен к выходу генератора тактовых импульсов, а первый выход подключен к входам синхронизации каждого из m блоков памяти 1-й группы блоков памяти, второй выход подключен к входам синхронизации каждого из 2n m-входовых многоразрядных сумматоров, третий выход подключен к входам каждого из 2n блоков памяти 2-й группы блоков памяти, четвертый выход подключен к входу подачи тактовых импульсов вычитающего счетчика, при этом выходы m блоков памяти 1-й группы блоков памяти подключены к входам 2n m-входовых многоразрядных сумматоров, где i-й выход j-го блока памяти 1-й группы блоков памяти подключен к j-му входу j-го m-входового многоразрядного сумматора (i=1, 2, …, 2n, j=1, 2, …, m), выходы 2n m-входовых многоразрядных сумматоров подключены к входам 2n блоков памяти 2-й группы блоков памяти, где выход i-го m-входового многоразрядного сумматора подключен к входу i-го блока памяти 2-й группы блоков памяти (i=1, 2, …, 2n), выходы 2n блоков памяти 2-й группы блоков памяти подключены ко вторым входам 2n блоков двухвходовых логических элементов И, где выход i-го блока памяти 2-й группы блоков памяти подключен к 2-му входу i-го блока двухвходовых логических элементов И (i=1, 2, …, 2n); конъюнктор, входы которого подключены к выходам вычитающего счетчика, а выходы подключены к 1-м входам 2n блоков двухвходовых логических элементов И, где i-й выход конъюнктора подключен к 1-му входу i-го блока двухвходовых логических элементов И (i=1, 2, …, 2n); вход начального заполнения вычитающего счетчика, являющийся входом устройства, подключен к 2-му входу вычитающего счетчика; n-входовый логический элемент ИЛИ-НЕ, входы которого подключены к соответствующим выходам вычитающего счетчика, при этом выход n-входового логического элемента ИЛИ-НЕ подключен к входу подачи сигнала окончания работы устройства распределения тактовых импульсов и входу подачи сигнала выдачи результата выходного регистра; 2n-входовый многоразрядный сумматор, входы которого подключены к выходам 2n блоков двухвходовых логических элементов И, а выход подключен к второму входу устройства сравнения, при этом первый вход устройства сравнения подключен к входу подачи значения количества логических уравнений, являющемуся входом устройства.

Сущность устройства поясняется фиг. 1, на которой представлена структурная схема предлагаемого устройства, включающая: генератор тактовых импульсов 1, устройство распределения тактовых импульсов 2, блоки памяти 1-й группы блоков памяти 3.1-3.m, m-входовые многоразрядные сумматоры 4.1-4.2n, блоки памяти 2-й группы блоков памяти 5.1-5.2n, вычитающий счетчик 6, конъюнктор 7, блоки двухвходовых логических элементов И 8.1-8.2n, n-входовый логический элемент ИЛИ-НЕ 9, 2n-входовый многоразрядный сумматор 10, устройство сравнения 11, выходной регистр 12, вход подачи значений коэффициентов уравнений 13, вход подачи сигнала начала работы устройства 14, вход начального заполнения вычитающего счетчика 15, вход подачи значения количества логических уравнений 16, выходы выдачи результатов вычисления системы логических уравнений 17.1-17.d.

Конъюнктор 6 обеспечивает вычисление всех возможных конъюнкций для n переменных и представлен в [3].

В статическом виде элементы предлагаемого устройства взаимосвязаны следующим образом (фиг. 1): вход подачи значений коэффициентов уравнений 13, являющийся входом устройства, подключен к первым входам каждого из блоков памяти 1-й группы блоков памяти 3.1-3.m, первый вход устройства распределения тактовых импульсов 2 подключен к входу подачи сигнала начала работы устройства 14, являющемуся входом устройства, второй вход подключен к выходу генератора тактовых импульсов 1, а первый выход подключен к входам синхронизации каждого из m блоков памяти 1-й группы блоков памяти 3.1-3.m, второй выход подключен к входам синхронизации каждого из 2n m-входовых многоразрядных сумматоров 4.1-4.2n, третий выход подключен к входам каждого из 2n блоков памяти 2-й группы блоков памяти 5.1-5.2n, четвертый выход подключен к входу подачи тактовых импульсов вычитающего счетчика 6, при этом выходы m блоков памяти 1-й группы блоков памяти 3.1-3.m подключены к входам 2n m-входовых многоразрядных сумматоров 4.1-4.2n, где i-й выход j-го блока памяти 1-й группы блоков памяти 3.j подключен к j-му входу i-го m-входового многоразрядного сумматора 4.i (i=1, 2, …2n, j=1, 2, m), выходы 2n m-входовых многоразрядных сумматоров 4.1-4.2n подключены к входам 2n блоков памяти 2-й группы блоков памяти 5.1-5.2n, где выход i-го m-входового многоразрядного сумматора 4.i подключен к входу i-го блока памяти 2-й группы блоков памяти 5.i (i=1, 2, …, 2n), выходы 2n блоков памяти 2-й группы блоков памяти 5.1-5.2n подключены ко вторым входам 2n блоков двухвходовых логических элементов И 8.1-8.2n, где выход i-го блока памяти 2-й группы блоков памяти 5.i подключен к 2-му входу i-го блока двухвходовых логических элементов И 8.i (i=1, 2, …, 2n); входы конъюнктора 7 подключены к выходам вычитающего счетчика 6, а выходы конъюнктора 7 подключены к 1-м входам 2n блоков двухвходовых логических элементов И 8.1-8.2n, где i-й выход конъюнктора 7 подключен к 1-му входу i-го блока двухвходовых логических элементов И 8.i (i=1, 2, …, 2n); вход начального заполнения вычитающего счетчика 15, являющийся входом устройства, подключен к 2-му входу вычитающего счетчика 6; входы n-входового логического элемент ИЛИ-НЕ 9 подключены к соответствующим выходам вычитающего счетчика 6, при этом выход n-входового логического элемента ИЛИ-НЕ 9 подключен к входу подачи сигнала окончания работы устройства распределения тактовых импульсов 2 и входу подачи сигнала выдачи результата выходного регистра 12; входы 2n-входового многоразрядного сумматора 10 подключены к выходам 2n блоков двухвходовых логических элементов И 8.1-8.2n, а выход подключен к второму входу устройства сравнения 11, при этом первый вход устройства сравнения 11 подключен к входу подачи значения количества логических уравнений 16, являющемуся входом устройства; выходы вычитающего счетчика 6 подключены к информационным входам выходного регистра 12, вход подачи сигнала записи выходного регистра 12 подключен к выходу устройства сравнения 11, а выходы выходного регистра 12 подключены к d выходам выдачи результатов вычисления системы логических уравнений 17.1-17.d, являющимся выходами устройства.

Особенность устройства состоит в вычислении логических уравнений, заблаговременно представленных в арифметической форме, путем равносильных преобразований следующего вида:

1. а^b⇔a⋅b,

2. a∨b⇔а+b-а⋅b,

3. а⊕b⇔a+b-2⋅a⋅b,

4. ¬a⇔1-a.

Устройство предназначено для решения систем логических уравнений в арифметической форме, вида:

где левая часть уравнения системы (1) имеет вид:

где - коэффициенты логического уравнения, , j=1, 2, …, m, i=1, 2, …, 2n, iq∈{0, 1}, , q=1, 2, …, n,

При этом значения степеней логических переменных iq определяют лексикографический порядок наборов логических переменных и находятся в следующей зависимости (i1i2…in)2=i-1.

Повышение оперативности работы устройства определяется приведением системы логических уравнений (1) к одному логическому уравнению в арифметической форме путем их сложения:

в результате чего получается уравнение вида:

где .

Решением системы логических уравнений (1) является множество наборов значений логических переменных х1, х2, …, хn, при которых все уравнения Р11, х2, …, хn), Р21, х2, …, хn), Рm1, х2, …, хn) системы (1) принимают значение 1 и соответственно уравнение (4) принимает значение m.

Устройство функционирует следующим образом: перед началом работы устройства на вход подачи значений коэффициентов уравнений 13 подаются значения коэффициентов соответствующих логических уравнений Р11, х2, …, хn), Р21, х2, …, хn), …, Рm1, х2, …, хn) системы (1); на вход начального заполнения вычитающего счетчика 15 подается значение 2n (где n - количество логических переменных), которое записывается в ячейки памяти вычитающего счетчика 6; на вход подачи значения количества логических уравнений 16 подается значение m, которое поступает на первый вход устройства сравнения 11. Далее, на вход подачи сигнала начала работы устройства 14 подается высокий сигнал, соответствующий началу работы устройства и поступающий на вход устройства распределения тактовых импульсов (УРТИ) 2; далее, УРТИ 2 выполняет распределение тактовых импульсов, подаваемых на его вход подачи тактовых импульсов с генератора тактовых импульсов 1 в следующем порядке: с первого выхода УРТИ 2 тактовый импульс поступает на входы подачи сигнала записи каждого блока памяти 1-й группы блоков памяти 3.1-3.m и приводит их в состояние записи коэффициентов уравнений Р11, х2, …, хn), Р21, х2, …, хn), Рm1, х2, …, хn) (в j-й блок памяти 3.j выполняется запись коэффициентов j-го уравнения); далее, со второго выхода УРТИ 2 тактовый импульс поступает на синхровходы m-входовых многоразрядных сумматоров 4.1-4.2n, выполняющих сложение коэффициентов уравнений (i-й m-входовый многоразрядный сумматор 4.i выполняет сложение i-х коэффициентов каждого уравнения , i=1, 2, …, 2n); далее с третьего выхода УРТИ 2 тактовый импульс поступает на входы подачи сигнала записи каждого блока памяти 2-й группы блоков памяти 5.1-5.2n и приводит их в состояние записи коэффициентов уравнения (4), подаваемых на их входы с соответствующих выходов m-входовых многоразрядных сумматоров 4.1-4.2n (запись bi выполняется в i-й m-входовый многоразрядный сумматор 4.i); далее с четвертого выхода УРТИ 2 подается 2n тактовых импульсов на вход подачи тактовых импульсов вычитающего счетчика 6, при этом каждое значение состояния ячеек памяти вычитающего счетчика 6 (соответствующее наборам значений переменных х1, х2, …, хn, убывающим в лексикографическом порядке с набора 111…11 до 000..00) подается на конъюнктор 7, на n-входовый логический элемент ИЛИ-НЕ 9 и на информационные входы выходного регистра 12, с конъюнктор 7 каждый раз вычисляет значения всех возможных конъюнкций уравнения (4), которые передаются на блоки двухвходовых логических элементов И 8.1-8.2n, обеспечивающих поразрядное логическое умножение коэффициентов bi на значения соответствующих конъюнкций , {i1i2…Jn)2=i-1, 2n-входовый многоразрядный сумматор 10 выполняет вычисление значения уравнения для заданного набора переменных путем сложения результатов вычисления, поступающих с выходов блоков двухвходовых логических элементов И 8.1-8.2n, устройство сравнения 11 выполняет сравнение результата вычисления уравнения (4) для заданного набора переменных со значением, подаваемым со входа подачи значения количества логических уравнений 16, при этом если результат вычисления совпадает, то с выхода устройства сравнения 11 подается сигнал на вход подачи сигнала записи выходного регистра 12, в результате чего выполняется запись значений заданного набора переменных в выходной регистр, в обратном случае запись не выполняется; при достижении вычитающим счетчиком значения 000…00 на выходе n-входового логического элемента ИЛИ-НЕ 9 формируется высокий сигнал, который подается на вход подачи сигнала выдачи значений выходного регистра 12, который выполняет подачу значений на выходы выдачи результатов вычисления системы логических уравнений 17.1-17.d и на третий вход УРТИ 2 и соответствует окончанию подачи тактовых импульсов.

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

Предложенное устройство может быть реализовано с использованием современной элементной базы программируемых логических интегральных схем фирм Altera, Xilinx.

Литература

1. Авторское свидетельство СССР №744644 от 30.06.1980 г.

2. SU 1411768, 23.07.88 г.

3. RU 2373564, 20.11.2009 г

Похожие патенты RU2654137C1

название год авторы номер документа
Логический вычислитель в системе остаточных классов 2016
  • Вишневский Артем Константинович
  • Мельник Валентин Анатольевич
  • Подсвиров Виталий Алексеевич
RU2637488C1
СПОСОБ КОРРЕКЦИИ ПОГРЕШНОСТЕЙ АНАЛОГО-ЦИФРОВОГО ПРЕОБРАЗОВАНИЯ И УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ 2007
  • Бондарь Мария Сергеевна
RU2326494C1
УСТРОЙСТВО ПОИСКА ИНФОРМАЦИИ 2014
  • Аверьянов Евгений Геннадьевич
  • Авраменко Владимир Семенович
  • Боголепов Григорий Сергеевич
  • Копчак Ян Миланович
  • Маликов Альберт Валерьянович
  • Паращук Игорь Борисович
RU2553093C1
СПОСОБ АДАПТИВНОЙ АДРЕСНОЙ СИГНАЛИЗАЦИИ И УСТРОЙСТВО ДЛЯ ЕГО ОСУЩЕСТВЛЕНИЯ 2000
  • В.Е.
RU2209468C2
УСТРОЙСТВО ПОИСКА ИНФОРМАЦИИ 2005
  • Бочков Максим Вадимович
  • Журавель Евгений Павлович
  • Копчак Ян Миланович
  • Паращук Игорь Борисович
  • Саенко Игорь Борисович
RU2296365C1
УСТРОЙСТВО ПОИСКА ИНФОРМАЦИИ 2006
  • Авраменко Владимир Семенович
  • Бухарин Владимир Владимирович
  • Бушуев Сергей Николаевич
  • Гурьев Сергей Николаевич
  • Копчак Ян Миланович
  • Паращук Игорь Борисович
RU2313128C1
ВЫЧИСЛИТЕЛЬНОЕ УСТРОЙСТВО 1998
  • Гребенев С.В.
  • Дроздов И.А.
  • Кузнецов В.Е.
  • Лихачев А.М.
  • Рунеев А.Ю.
  • Федяй С.И.
RU2132083C1
МНОГОРАЗРЯДНЫЙ УПРАВЛЯЕМЫЙ ДЕЛИТЕЛЬ ЧАСТОТЫ 1996
  • Островский В.А.
RU2119248C1
ЦИФРОВОЙ ЧАСТОТОМЕР 1996
  • Вердиев Т.М.
RU2097774C1
Арифметико-логическое устройство для умножения чисел по модулю 2017
  • Петренко Вячеслав Иванович
  • Свистунов Николай Юрьевич
  • Стручков Игорь Владиславович
RU2653263C1

Иллюстрации к изобретению RU 2 654 137 C1

Реферат патента 2018 года Устройство решения систем логических уравнений

Изобретение относится к вычислительной технике, а именно к устройствам для решения логических уравнений, и может быть использовано для аппаратной реализации криптографических примитивов. Технический результат заключается в повышении быстродействия устройства решения систем логических уравнений. Технический результат достигается за счет устройства решения систем логических уравнений, которое включает: генератор тактовых импульсов 1, устройство распределения тактовых импульсов 2, блоки памяти 1-й группы блоков памяти 3.1-3.m, m-входовые многоразрядные сумматоры 4.1-4.2n, блоки памяти 2-й группы блоков памяти 5.1-5.2n, вычитающий счетчик 6, конъюнктор 7, блоки двухвходовых логических элементов И 8.1-8.2n, n-входовый логический элемент ИЛИ-НЕ 9, 2n-входовый многоразрядный сумматор 10, устройство сравнения 11, выходной регистр 12, вход подачи значений коэффициентов уравнений 13, вход подачи сигнала начала работы устройства 14, вход начального заполнения вычитающего счетчика 15, вход подачи значения количества логических уравнений 16, выходы выдачи результатов вычисления системы логических уравнений 17.1-17.d. 1 ил.

Формула изобретения RU 2 654 137 C1

Устройство решения систем логических уравнений, содержащее генератор тактовых импульсов, вычитающий счетчик, выходы которого подключены к информационным входам выходного регистра, 2n блоков двухвходовых логических элементов И, устройство сравнения, выход которого подключен к входу подачи сигнала записи выходного регистра, вход подачи значений коэффициентов уравнений, являющийся входом устройства, d выходов выдачи результатов вычисления системы логических уравнений, являющихся выходами устройства, и отличающееся тем, что введены блоки памяти 1-й группы блоков памяти, первые входы каждого из которых подключены к входу подачи значений коэффициентов уравнений, являющемуся входом устройства; устройство распределения тактовых импульсов, первый вход которого подключен к входу подачи сигнала начала работы устройства, являющемуся входом устройства, второй вход подключен к выходу генератора тактовых импульсов, а первый выход подключен к входам синхронизации каждого из m блоков памяти 1-й группы блоков памяти, второй выход подключен к входам синхронизации каждого из 2n m-входовых многоразрядных сумматоров, третий выход подключен к входам каждого из 2n блоков памяти 2-й группы блоков памяти, четвертый выход подключен к входу подачи тактовых импульсов вычитающего счетчика, при этом выходы m блоков памяти 1-й группы блоков памяти подключены к входам 2n m-входовых многоразрядных сумматоров, где i-й выход j-го блока памяти 1-й группы блоков памяти подключен к j-му входу i-го m-входового многоразрядного сумматора (i=1, 2, …, 2n, j=1, 2, …, m), выходы 2n m-входовых многоразрядных сумматоров подключены к входам 2n блоков памяти 2-й группы блоков памяти, где выход i-го m-входового многоразрядного сумматора подключен к входу i-го блока памяти 2-й группы блоков памяти (i=1, 2, …, 2n), выходы 2n блоков памяти 2-й группы блоков памяти подключены ко вторым входам 2n блоков двухвходовых логических элементов И, где выход i-го блока памяти 2-й группы блоков памяти подключен к 2-му входу i-го блока двухвходовых логических элементов И (i=1, 2, …, 2n); конъюнктор, входы которого подключены к выходам вычитающего счетчика, а выходы подключены к 1-м входам 2n блоков двухвходовых логических элементов И, где i-й выход конъюнктора подключен к 1-му входу i-го блока двухвходовых логических элементов И (i=1, 2, …, 2n); вход начального заполнения вычитающего счетчика, являющийся входом устройства, подключен к 2-му входу вычитающего счетчика; n-входовый логический элемент ИЛИ-НЕ, входы которого подключены к соответствующим выходам вычитающего счетчика, при этом выход n-входового логического элемента ИЛИ-НЕ подключен к входу подачи сигнала окончания работы устройства распределения тактовых импульсов и входу подачи сигнала выдачи результата выходного регистра; 2n-входовый многоразрядный сумматор, входы которого подключены к выходам 2n блоков двухвходовых логических элементов И, а выход подключен к второму входу устройства сравнения, при этом первый вход устройства сравнения подключен к входу подачи значения количества логических уравнений, являющемуся входом устройства.

Документы, цитированные в отчете о поиске Патент 2018 года RU2654137C1

Устройство для решения логических уравнений 1986
  • Дергачев Владимир Андреевич
SU1411768A1
УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ 1990
  • Якуш В.П.
  • Косьянчук В.В.
  • Лиходед Н.А.
  • Соболевский П.И.
RU2037197C1
УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ 1994
  • Якуш Виктор Павлович
  • Драницин Олег Николаевич
  • Лиходед Николай Александрович
  • Соболевский Павел Иосифович
  • Тиунчик Александр Александрович
RU2116667C1
УСТРОЙСТВО ДЛЯ РЕШЕНИЯ СИСТЕМ ЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ УРАВНЕНИЙ 1993
  • Якуш Виктор Павлович
  • Смирнов Виталий Александрович
RU2049350C1
Способ и приспособление для нагревания хлебопекарных камер 1923
  • Иссерлис И.Л.
SU2003A1

RU 2 654 137 C1

Авторы

Вишневский Артем Константинович

Батяй Андрей Николаевич

Даты

2018-05-16Публикация

2017-03-10Подача