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

 

Союз Советскик

Социалистических

Ресттублмк

ОП ИСАНИЕ

ИЗОБРЕТЕН ИЯ

Х АВТОРСКОМУ СВИДЕТЕЛЬСТВУ ().750492 (61) Дополнительное к авт. свид-ву— (22) Заявлено 03.01.77 (21) 2439958/18-24

{5! )М. Кл. с присоединением заявки М—

G 06 F 15/31

Гаоударстаеииый комитет

СССР (23) ПриоритетОпубликовано 23.07.80 Бюллетень ¹ 27 по делам иаобретеиий и открытий

{5Зу ДК 681.142 (72) (088.8) Дата опубликования описания 28.07.80 (72) Автор.. изобретения

О. И. Сидоренко (71) Заявитель. (54) УСТРОЙСТВО ДЛЯ МИНИМИЗА1(ИИ

ЛОГИЧЕСКИХ ФУНКЦИЙ

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

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

Недостаток устройства — большой объем оборудования.

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

2 и дешифратору, а третий через регистр - к логическому блоку (2).

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

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

Обязательной буквой в рабочем наборе of=(oh. 6, Ф„), на котором булевая функция 1 ()(„, Хт ), равна 1, называется буква Хт если набор ру (М,1,..., о(,,g о(, 1 ) соседний с набором к по переменной g,, является нерабочим набором, т. е. на нем функция f, (>g > т Хт1 ) равна О.

750492 ф

Продолжение таблицы

0101

011 О

0.111

1 000

1 001

1 01 0

1011

1 100

1 1 01

1 1 1 0

1 1 1 1

О

14

0000 0

0001 1

001 0 0

001 1 0

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

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

Указанная цель достигается тем, что первые входы элементов индикации i -ой строки матрицы. (1 < 1 < 2 ) через размыкающие контакты 1 -га переключателя соединены с положительной клеммой истопника питания, а через замыкающие контакты - с отрицательной клеммой источника питания, вторые входы 0 -ых 15 элементов индикации матрицы первого столбца (9-=1, 3, 5, ..., 2 - 1) соединены со вторыми входами К -ых элементов индикации матрицы нулевого столбца (к-" 2, 4, 6,..., 2 ), вто- 20 рые входы 1 -ых элементов индикации матрицы j -го столбца (g -" 1, 2, . °

2, ) + 1, 2 + 2... (J =2, 3,..., A) соединены со вторыми вхоцами к-ых элементов индикации 25 матрицы ) -го столбца.

1!а чертеже представлена схегга устройства для п14, где 1-64 элемеггты матрицы ггггдикации, 65-89 ггереклгочатели. 30

Подчеркнутая цифра над каждым эле ментом индикации означает значение переменной набора, соответствующей этому элементу. Положение переключателя 65, при котором к элементам индикащш это- З5 го набора подключается клемма + источника питания, соответствует тому, что заданная булевая функция на этом наборе принимает значение, равное 1, а положение переключателя "0", при котором 40 к элементам индикации набора подключается клемма "-" соответствует тому, что заданная булевая функция на этом наборе принимает значение, равное О.

Работа устройства иллюстрируется на 45 примере .выделения обязательных букв в наборах функции, заданной таблицей истинности.

Переключатели 65 - 80, соответствующие единичным наборам заданной булевой функции, устанавливаются в положение "1", при этом клемма "+" источника питания оказывается подключенной к элементам индикации имеющим десятичные номера 1, 5, 6, 7, 9, 11, 12, 15, а клемма "-" источника - к элементам индикации с номерами О, 2, 3, 4, 8, 10, 13 и 14.

Так как элементы индикации в столбце переменной Х соединены следующими парами (см. чертеж); 1-33, 5-37, 9-41, 13-45; 17-49, 21-53, 25-57, 29-61, то работают элементы индикации соединенные парами 2-18, 6-22, 10-26, 14-30, 34-50, 38-54, 42-58, 4662. Поэтому работают элементы ичдикации 10, 14, 26, 30, 34, 38, 50, 54.

В столбце переменной X элементы индикации соединены следующими парами:

3-11, 7 15, 19-27, 23 31, 35-43, 51-59, 55-63, поэтому работают следующие элементы индикации 7, 15, 19, 27, 51, 55, 59, 63.

В столбце переменной Х элементы индикации соединены парами 4-8, 12-16, 20-24, 28-32, 36-40, 44-48, 52-56, 60-64, поэтому работают элементы индикации 4, 8, 20, 24, 36, 40, 44, 48, 5.2, 56, 60, 64.

Таким образом, как в наборах, на которых функция равна 1, так и в наборах, на которых функция равна О, одновре»

5 7504 менно выделяются обязательные переменные, обведенные в таблице истинности кружками. При задании булевой функции в виде дизьюнктивной нормальной формы (ДНФ) необходимо в 1 устанавливать те переключатели, наборы которых покрываются членами ДНФ.

В случае, если число переменных заданной функции меньше числа переменных, на которое рассчитано устройство, 10

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

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

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

Формула изобретения ЗО

Устройство для минимизации логических функций, содержащее 2 переключа92 6 телей (n -число переменных) и матрицу элементов индикации из 2 строк и

A -столбцов, о т л и ч а ю щ е е с я тем, что, с целью упрощения устройства и повышения быстродействия первые входы элементов индикации i -ой строки матрицы (1 4 S 2 ) через размыкающие контакты -го переключателя соединены с положительной клеммой источника питания, а через замыкающие контакты - с отрицательной клеммой источl ника питания, вторые входы 5 -ых элементов индикации матрицы первого столбца (9 =1., 3, 5,..., 2" - 1) соедине» ны со вторыми входами К -ых элементов индикации матрицы первого столбца (К 2, 4, 6,..., 2 ), вторые входы

Р -ых элементов индикации матрицы

J -го столбца (8 = 1, 2,...,, 2

2)+" +1, 2 +" +2...,, 2 — 2 (,) - 2, 3, ...,, a) соединены со вторыми входами к-ых элементов матрицы индикации д -го столбца.

Источники информации, принятые во внимание при экспертизе

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

М 177692, кл. G- 06 F- 15/34, 1966.

2. Авторское свидетельство СССР

N 442288338877, кл, G 06 Р 15/34, 1974. (прототип) .

750492 м ц

I !

S

1 !

1 !

«ю I!

1

Я у ю

ЦНИИПИ Заказ 4468/19 Тираж 751 Подписное

I s

f а !

l", 1es

1

И

37

+

Ю л

I sr

) IA

Фнпиал ППП Патент, г. Ужгород, уа. Проектная, 4