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

 

Изобретение относится к вычислительной технике, а именно к устройствам для решения логических уравнений . Цель изобретения - повышение точности устройства за счет получения решения минимальной мощности. Устройство содержит счетчик 3, п групп элементов по m элементов И в каждой , где п - число переменных уравнения; m - разрядность коэффициентов уравнений, операционный блок 5, блок 6 сравнения, триггер 7, элементы НЕ 8 и 9, элемент И 13 и блок 14 памяти. В основе работы устройства лежит формирование лексикографически упорядоченных значений параметров и оценки решения на каждом шаге. 3 ил., 1 табл.

СООЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИН (51)4 G 06 F 15 20

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

М А BTOPCHOMY СВИДЕТЕЛЬСТВУ

1л

11

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4157) 44/24-24 (22) 05.12.86 (46) 23.07.88. Бкл. У 27 (71) Харьковский авиационный институт им. Н.Е.Жуковского (72) В.А.Дергачев (53) 681.325(088.8) (56) Авторское свидетельство СССР

В 746531, кл. G 06 F 15/20, 1977, Авторское свидетельсТво СССР

Р 1262519, кл. G 06 F 15/20, 1985. (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ ЛОГИЧЕСКИХ УРАВНЕНИЙ (57) Изобретение относится к вычислительной технике, а именно к устройÄÄSUÄÄ 1411768 А1 ствам для решения логических уравнений. Цель изобретения - повышение точности устройства за счет получения решения минимальной мощности. Устройство содержит счетчик 3, и групп элементов 4 -4 по m элементов И в каж1 дой, где п — число переменных уравнения; m — разрядность коэффициентов уравнения, операционный блок 5, блок

6 сравнения, триггер 7, элементы НЕ

8 и 9, элемент И 13 и блок 14 памяти.

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

1411768

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

На фиг.l представлена схема устройства; на фиг.2 — схема операцион1 ного блока на фиг.3 — схема блока

9 сраннения, (Устройство содержит нходы 1,— I коэффициентов уравнения устройства, ! вход 1>,Д правой части уравнения уст- 15 ройстна, выходы 2 результата устройства, счетчик 3, группы 4„- 4„с первой по и-ю элементов И, операционный блок 5, блок 6 сравнения, триггер 7, первый 8 и второй 9 элементы НЕ, выходы 1О признака отсутствия решения .уравнения устройства, выход 11 признака наличия решения уравнения устройства, тактовый вход l2 устройства, элемент И 13, блок !4 памяти. Опера- 25 ционный блок 5 содержит сумматоры

15> 15 по модулю 2, выходы 16 операционного блока. Блок 6 сравнения содержит элементы РАВНОЗНАЧНОСТЬ 17,—

17, элемент И 18. 30

Устройство, работает следующим образом.

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

35 г х.А;=В при х шип э= э — 1 э э=f э 1 где А — 1 е ID pBзрядное pBQHBHoe слово; и — количество двоичных слов и, соответственно, количество, переменных; ..; ° (O, I %

 — двоичное слово, соответствующее правой части уравнения.

Решение уравнения заключается и определении множества х= x, õ,) минимальной мощности, удовлетворяющего этому jjc JIoBHM î

59

В зависимости от двоичного кода, поступающего с выхода счетчика 3, с выхода блока 14 памяти выдаются сигналы "1" в соответствующих позициях, при этом номера позиций "1", формируемые для каждого состояния счетчика 3, являются лексикографически упорядоченными. В таблице приведен пример формирования сочетания для n=3.

Значения сигЗначения формирователя сочетаний на налон выходах входах

001

001

0lI

101

10I

Из таблицы видно, что вначале формируются сочетания по одному элементу, затем по два, по три и т.д.

На входы 1, — 1„ подаются соответственно двоичные слона А,...,А, на э вход 1„, подается двоичное слово В, (j-й разряд всех двоичных слов, имеющий вес 2 3 ", подается на j-й вход, j=I m). В исходном состоянии триггер 7 находится в состоянии "1", двоичный счетчик 3 н состоянии О...О.

На.выходе блока 14 памяти двоичный код 0...01. На (и+1)-м выходе двоичного счетчика — сигнал "0", на выходе элемента HE 9 "1", поэтому после подачи тактовых импульсов через элемент И 13 импульсы поступают иа счетный вход двоичного счетчика 3, меняя его состояние. Значение 1 го выходного разряда блока 14 памяти соответствует значению х . Если х =1, то открывается i-я группа элементов И 4, и на .вход операционного блока 5 поступает двоичное слоно А;, если х =О, то А„=О. Операционный блок 5 нычисляет выражение

С =¹ х.А.

1=э э путем поразрядного сложения по модулю 2 соответствующих разрядов, поступающих на его входы двоичных чисел.

Блок 6 сравнения производит поразрядное сравнение чисел С и В. При

1411768

В=С на выходе блока 6 сравнения формируетсяя сигнал " 1", сб расывающий триггер 7 в нулевое состояние, При этом закрывается элемент И 13, и импульсы не пиоходят на счетный вход двоичного счетчика 3 и не меняют его состояния, В процессе решения могут быть два случая.

Решение уравнения существует. При этом на выходе 11 появляется признак наличия решения, и значение разрядов на выходах 2 результата соответствует значениям х.

Решения нет. В этом случае после перебора всех 2 вариантов двоичный счетчик 3 íà (n+I.)-м выходе формирует сигнал "1", при этом на выходе 10 появляется признак отсутствия решения, через элемент НЕ 9 на вход элемента И 13 поступает сигнал "0" закрывающий поступление импульсов на счетный вход счетчика 3.

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

1.-й группы, выход которого подключен к j ìó информационному входу i-й группы операционного блока, j-й вы5 ход которого подключен к -му входу первой группы блока сравнения, j-й вход второй группы блока сравнения подключен к j -му входу значения .пра- . вой части уравнения устройства, тактовый вход устройства подключен к первому входу элемента И, выход которого подключен к счетному входу счетчика, первый информационный выход которого подключен к выходу признака отсутствия решения устройства и к входу первого элемента НЕ, выход которого подключен к второму входу элемента И, выход блока сравнения подключен к счетному входу триггера, выход которого подключен к выходу признака наличия решения устройства и к входу второго элемента НЕ, выход которого подключен к третьему входу

25 элемента И, о т л и ч а ю щ е е с я тем, что, с целью повышения точности эа счет получения решения минимальной мощности, оно содержит блок памяти, причем с второго по (п+1)-й информационные выходы счетчика подключены соответственно к адресным входам с первого по п-й блока памяти, вход чтения которого подключен к тактовому входу устройства, i-й выход блока памяти подключен к i-му выходу результата решения устройства и к вторым входам m элементов i-й группы.

141176с

Составитель В. Смирнов

Техр ед N. Дидык Корректор С.ЧерниРедактор Н.Бобкова

Тираж 704 Подписное

ВНИИПИ Государственного комитета СССР по делам изобретений и открытий

113035, Москва, Ж-35, Раушская наб., д. 4/5

Заказ 3663/45

Производственно-полиграфическое предприятие, r. Ужгород, ул. Проектная, 4