Устройство для минимизации логических функций Советский патент 1980 года по МПК G06F17/10 

1

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

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

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

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

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

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

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

Обязательной буквой в рабочем наборе (оч, . . . , , 1,, , . . ., СИ), на котором булевая функция f (Х,--., 20 ) 1, называется буква Х-, , : если набор Р С,-, Х.;,,О, 0(,,..), соседний с набором ч по переменной K-j, . является нерабочим набором, т. е. на нем функция ( ) равна О.

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

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

Указанная цель достигается тем, что первые входы элементов индикации i -ой строки матрицы. ( 1 4 2) через размыкающие контакты -го переключателя соединены с положительной клеммой истошика питания, а через замыкающие контакты - с отрицательной клеммой источника питания, вторые входы -ык элементов индикации матрицы первого столбца (1, 3, 5, .... 2 - 1) соединены со вторыми входами.к -ых элементов индикации матрицы нулевого стапбца { к 2, 4, 6, .. . . , 2), вторые входы , -ых элементов индикации матрицы j -го столбца (Е - 1, 2, .

jj-vl

2J , 1, 2

22J -2-1

+ 2,

С-™ - , (j -2, 3, . . . , п) соединены со вторыми входами к-ых элементов индикации матрицы j -го столбца. На чертеже представлена схема устройства , где 1-64 элементы матрицы индикации, 65-89 переключатели. Подчеркнутая цифра над каждым эле ментом индикации означает значение переменной набора, соответствующей этокгу элементу. Положение переключателя 65, при котором к элементам индикации этого набора подключается клемма + источника питания, соответствует тому, что заданная булевая функция на этом наборе принимает значение, равное 1, а положение переключателя О, при котором к элементам индикации набора подключае ся клемма - соответствует тому, что заданная булевая функция на этом наборе принимает значение, равное О. Работа устройства иллюстрируется на примере .выделения обязательных букв в наборах функции, заданной таблицей истинности.

Продолжение таблщы Переключатели 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-ЗО, 34-50, 38-54, 42-58, . Поэтому работают элементы индикации 1О, 14, 26, 30, 34, 38, 50, 54. В столбце переменной Х элементы индикации соединены следующими парами: 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, 4О, 44, 48, 52, 56, 6О, 64. Таким образом, как в наборах, на которых функция равна 1, так и в наборах, на которых функция равна О, одновременно выделяются обязательные аереманные, обведенные в таблице истинности кружками. При задании булевой функции в виде дизъюнктивной нормальной формы (ДНФ) необходимо в 1 устанавливать те переключатели, наборы которых покрываются членами ДНФ.

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

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

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

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

5 и повышения быстродействия первые входы элементов (шдикации i -ой строки Матрицы ( 1 Л 2 ) через размыкающие контакты i -го переключателя соединены с положительной клеммой источ-

0 ннка питания, а через замыкающие контакты - с отрицательной клеммой источника, питания, вторые входы 6 -ых элементов 1шдикации матрицы первого столбца (Р -1., 3, 5, . . . , ) соединены со вторыми входами К -ых элементов индикации матрицы первого столбца (, 4, 6, . . . , 2), вторые входы Е -ых элементов индикации матрицы j -го столбца (В S- 1, 2, . . .. , 2,,

0 2- +1, 2 +2, . . . , 2J - 2J , (j- 2, 3, ,. . . ,n) соединены со вторыми входами K-Jbix элементов матрицы индикации J столбца.

5Источники информации,

принятые во внимание при экспертизе

1. Авторское свидетельство СССР № 177692, кл. G- Об F- 15/34, 1966,

0 2V Авторское свидетельство СССР № 428387, кл. G 06 F 15/34, 1974,. (прототип).