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

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

Иллюстрации

Показать все

Реферат

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

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

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

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

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

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

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

Сущность устройства поясняется фиг. 1, на которой представлена структурная схема предлагаемого устройства, включающая: генератор тактовых импульсов 1, устройство распределения тактовых импульсов 2, блоки памяти 1-й группы блоков памяти 3.1-3.m, m-входовые многоразрядные сумматоры 4.1-4.2ⁿ, блоки памяти 2-й группы блоков памяти 5.1-5.2ⁿ, вычитающий счетчик 6, конъюнктор 7, блоки двухвходовых логических элементов И 8.1-8.2ⁿ, n-входовый логический элемент ИЛИ-НЕ 9, 2ⁿ-входовый многоразрядный сумматор 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, второй выход подключен к входам синхронизации каждого из 2ⁿ m-входовых многоразрядных сумматоров 4.1-4.2ⁿ, третий выход подключен к входам каждого из 2ⁿ блоков памяти 2-й группы блоков памяти 5.1-5.2ⁿ, четвертый выход подключен к входу подачи тактовых импульсов вычитающего счетчика 6, при этом выходы m блоков памяти 1-й группы блоков памяти 3.1-3.m подключены к входам 2ⁿ m-входовых многоразрядных сумматоров 4.1-4.2ⁿ, где i-й выход j-го блока памяти 1-й группы блоков памяти 3.j подключен к j-му входу i-го m-входового многоразрядного сумматора 4.i (i=1, 2, …2ⁿ, j=1, 2, m), выходы 2ⁿ m-входовых многоразрядных сумматоров 4.1-4.2ⁿ подключены к входам 2ⁿ блоков памяти 2-й группы блоков памяти 5.1-5.2ⁿ, где выход i-го m-входового многоразрядного сумматора 4.i подключен к входу i-го блока памяти 2-й группы блоков памяти 5.i (i=1, 2, …, 2ⁿ), выходы 2ⁿ блоков памяти 2-й группы блоков памяти 5.1-5.2ⁿ подключены ко вторым входам 2ⁿ блоков двухвходовых логических элементов И 8.1-8.2ⁿ, где выход i-го блока памяти 2-й группы блоков памяти 5.i подключен к 2-му входу i-го блока двухвходовых логических элементов И 8.i (i=1, 2, …, 2ⁿ); входы конъюнктора 7 подключены к выходам вычитающего счетчика 6, а выходы конъюнктора 7 подключены к 1-м входам 2ⁿ блоков двухвходовых логических элементов И 8.1-8.2n, где i-й выход конъюнктора 7 подключен к 1-му входу i-го блока двухвходовых логических элементов И 8.i (i=1, 2, …, 2ⁿ); вход начального заполнения вычитающего счетчика 15, являющийся входом устройства, подключен к 2-му входу вычитающего счетчика 6; входы n-входового логического элемент ИЛИ-НЕ 9 подключены к соответствующим выходам вычитающего счетчика 6, при этом выход n-входового логического элемента ИЛИ-НЕ 9 подключен к входу подачи сигнала окончания работы устройства распределения тактовых импульсов 2 и входу подачи сигнала выдачи результата выходного регистра 12; входы 2ⁿ-входового многоразрядного сумматора 10 подключены к выходам 2ⁿ блоков двухвходовых логических элементов И 8.1-8.2ⁿ, а выход подключен к второму входу устройства сравнения 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, …, 2ⁿ, i_q∈{0, 1}, , q=1, 2, …, n,

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

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

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

где .

Решением системы логических уравнений (1) является множество наборов значений логических переменных х₁, х₂, …, х_n, при которых все уравнения Р₁(х₁, х₂, …, х_n), Р₂(х₁, х₂, …, х_n), Р_m(х₁, х₂, …, х_n) системы (1) принимают значение 1 и соответственно уравнение (4) принимает значение m.

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

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

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

Литература

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

2. SU 1411768, 23.07.88 г.

3. RU 2373564, 20.11.2009 г

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