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

Изобретение относится к вычислительной технике, а именно к устройствам для решения логических уравнений, и может быть использовано для аппаратной реализации криптографических примитивов. Технический результат заключается в повышении быстродействия устройства решения систем логических уравнений. Технический результат достигается за счет устройства решения систем логических уравнений, которое включает: генератор тактовых импульсов 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 ил.

 

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

Известно устройство для решения систем логических уравнений [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 г

Устройство решения систем логических уравнений, содержащее генератор тактовых импульсов, вычитающий счетчик, выходы которого подключены к информационным входам выходного регистра, 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 блоков двухвходовых логических элементов И, а выход подключен к второму входу устройства сравнения, при этом первый вход устройства сравнения подключен к входу подачи значения количества логических уравнений, являющемуся входом устройства.



 

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

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

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

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

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

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

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

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

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

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

Группа изобретений относится к панорамному телевизионному наблюдению, которое выполняется телевизионной системой при помощи телевизионной камеры кругового обзора в области, близкой к полусфере, т.е.

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

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

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

Изобретение относится к электронным устройствам, сохраняющим историю о деятельности человека. Технический результат заключается в создании удобного электронного устройства.

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

Сменный объектив, присоединенный к корпусу камеры, который содержит: оптическую систему, которая включает в себя линзу регулировки фокуса; блок привода, который приводит в движение линзу регулировки фокуса в направлении оптической оси оптической системы; приемопередающий блок, который передает в корпус камеры первый коэффициент и по меньшей мере один из второго коэффициента и третьего коэффициента, определяющих величину перемещения плоскости изображения.

Изобретение относится к устройству захвата изображения. Устройство захвата изображения содержит: пиксельную область, имеющую множество пикселей, которые размещены двухмерным образом, причем каждый из множества пикселей служит в качестве пикселя захвата изображения и пикселя обнаружения фокуса, каждый из множества пикселей выполнен с возможностью выдавать сигнал для обнаружения фокуса на основе обнаружения разности фаз; множество асимметричных микролинз, причем каждая из множества асимметричных микролинз размещена согласно множеству блоков фотоэлектрического преобразования соответствующих пикселей.

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

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

Изобретение относится к области технологии терминалов и касается способа и устройства для настройки параметров фотографирования. Способ включает в себя получение параметров фотосъемки для настройки подчиненного устройства в соответствии с текущим установленным режимом фотосъемки.

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

Изобретение относится к вычислительной технике, а именно к устройствам для решения логических уравнений, и может быть использовано для аппаратной реализации криптографических примитивов. Технический результат заключается в повышении быстродействия устройства решения систем логических уравнений. Технический результат достигается за счет устройства решения систем логических уравнений, которое включает: генератор тактовых импульсов 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 ил.

Наверх