11.2. ПРОЕКТИРОВАНИЕ КОМБИНАЦИОННЫХ СХЕМ В БУЛЕВОМ И МОНОФУНКЦИОНАЛЬНОМ БАЗИСАХ

При проектировании КС на логических элементах И, ИЛИ, НЕ и отсутствии ограничений на число входов элементов пользуются изложенными ранее методами минимизации булевых функций. При наличии ограничений наиболее простым методом является применение специальных ИМС, называемых расширителями и имеющихся в комплектах ИМС. Расширители позволяют увеличить, в случае необходимости, число входов логического элемента путем включения дополнительного (точно такого же) логического элемента на один из входов основного.

Рассмотрим переход от реализации булевой функции в булевом базисе, т. е. на логических элементах И, ИЛИ, НЕ к схемам в монофункциональном базисе, т. е. реализованных на логических элементах ИЛИ - НЕ либо И - НЕ, (Преобразование логических формул рассматривалось в гл. 9). Такие логические элементы широко используются в имеющихся на практике комплектах ИМС. Заметим, что если булева функция вбизисс реализована двухуровневой КС в соответствии с рис. 11.6; 11.7, то переход к реализации в базисе И - НЕ либо ИЛИ - НЕ может быть осуществлен заменой всех элементов КС (рис. 11.6) на логические элементы ИЛИ - НЕ, и элементов КС (рис.

11.7) на логические элементы ИЛИ - НЕ с сохранением как переменных, поданных на входы элементов, так и связей между ними. Преобразованные КС представлены на рис. 11.8, 11.9. В приведенных на рисунках схемах полагается, что на входы КС переменные поступают как с отрицанием, так и без отрицания, т. е. элемент НЕ на входах КС не учитывается.

Однако использовать в качестве внешних входов КС переменные не всегда удается. В этом случае КС, реализованная в булевом базисе, может быть представлена рис. 11.10; 11.11 и является трехуровневой. Соответствующие КС, реализованные в монофункциональном базисе, также будут трехуровневыми (рис. 11.12; 11.13).

Существует весьма простой способ перехода от реализации КС в базисе И - НЕ к реализации КС в базисе И - ИЛИ. Способ основан на применении правил де Моргана и позволяет с помощью несложного алгоритма сразу по реализации КС в базисе И - НЕ получить реализацию КС в базисе И - ИЛИ. Если в исходной КС отсутствуют элементы И-НЕ, выполняющие функцию инвертора, то преобразованная КС будет содержать ровно столько логических элементов И, ИЛИ, сколько их имеется в исходной КС. Если в исходной КС инверторы имеются, то в преобразованной КС число логических элементов (по сравнению с исходной КС) будет уменьшено ровно на число инверторов. Алгоритм

(кликните для просмотра скана)

перехода основывается на следующих простых эквивалентных преобразованиях, иллюстрируемых рис.

1. Присвоить выходу КС метку

2. Выбрать из КС два логических элемента И - НЕ, схема соединений которых соответствует рис. 11.14, а, а выход одного из элементов помечен меткой Произвести замену в соответствии с рис. без обозначения входов полученных элементов. Зачеркнуть метку Входу элемента ИЛИ, на котором произошло инвертирование переменной, присвоить метку , а каждому выходу логического элемента И присвоить метки

3. Если есть непросмотренные метки 7» то перейти к иначе — к

4. Если метка есть вход КС, то произвести инвертирование входной для преобразуемой КС переменной. Метку 7 зачеркнуть. Перейти к п. 3, иначе — к п. 5.

5. Если метка 7 есть выход элемента И - НЕ, входы которого являются входами КС, то произвести замену элемента И - НЕ в соответствии с рис. 11.15, Перейти к п. 3, иначе — к п. 6.

6. Если метка 7 есть выход элемента И - НЕ, играющего роль инвертора, то произвести замену в соответствии с рис. 11.16, вычеркнув элемент И - НЕ из КС. Перейти к п. 3, иначе — к п. 7.

7. Нели метка есть выход внутреннего для КС элемента И - НЕ, то выбрать из логических элемента И - НЕ, схема соединений которых соответствует рис. 11.17, д, а выход одного из элементов помечен меткой Проштести замену соответствии с рис. 11.17, б. Входам элементы ИЛИ, на которых произошло инвертирование переменных, присвоить метки Свободному входу элемента И присвоить метку Перейти к п. 3.

8. Если есть непросмотренные метки то перейти к п. 9, иначе — к п. 13.

9. Если метка есть вход КС, то оставить входную для преобразуемой КС переменную без изменения. Перейти к п. 3, иначе — к п. 10.

10. Если метка есть выход элемента И-НЕ, все входы которого есть входы КС, то произвести замену элемента И - НЕ в соответствии с рис. 11.18. Входы полученного элемента ИЛИ пометить меткой Перейти к п. 3, иначе — к п. 11.

11. Если метка есть выход элемента И - НЕ, играющего роль инвертора, то произвести замену в соответствии с рис. 11.19, вычеркнув элемент И - НЕ из КС. Перейти к п. 3, иначе — к п. 12.

12. Если метка есть выход внутреннего для КС элемента И - НЕ, то перейти к п. 2, иначе — к п. 3.

13. Конец.

Пример. Задана КС, реализованная в базисе И - НЕ (ряс. 11.20). Применение алгоритма приводит к КС в базисе И - ИЛИ (рис. 11.21).

Преобразование сложных аналитических выражений из булева базиса в базис ИЛИ - НЕ либо И - НЕ может быть сделано с помощью метода, основанного на последовательном применении теорем де Моргана.

Рис. 11.20

Рис. 11.21

Метод позволяет осуществлять переход от произвольной по форме булевой функции, реализованной на элементах И, ИЛИ, НЕ, к форме, реализуемой на элементах И - НЕ либо и в частности — от минимальной ее КНФ (минимальной к минимальным (с точностью до одной буквы) кратчайшим формулам в базисе ИЛИ - НЕ либо в базисе И - НЕ.

Опишем переход к реализации в базисе ИЛИ - НЕ. При изложении метода будем опираться на следующие очевидные соотношения:

Пусть задана некоторая формула в базисе И, ИЛИ, НЕ. Обозначим искомую формулу в базисе ИЛИ - НЕ, эквивалентную через символ Тогда работа метода может быть описана с помощью следующих правил:

2. Если где — формулы в базисе И, ИЛИ, НЕ и где — произвольная формула в базисе либо где произвольная формула в базисе либо где то где — некоторая формула в базисе ИЛИ - НЕ, эквивалентная

3. Если где А — формула в базисе И, ИЛИ, НЕ и если:

где В — формула в базисе И, ИЛИ, НЕ то

4. Если где либо либо т. е. общем случае формула

может быть представлена выражением

то формула эквивалентная формуле имеет вид

где — формула в базисе И, ИЛИ, НЕ, a — некоторая эквивалентная ей формула в базисе ИЛИ - НЕ.

5. Формулы вида в выражении для определяются по правилам 1, 2,3,4 соответственно из формул вида входящих в выражение для

Пример. Пусть Найти выражение для эквивалентное с помощью описанного метода. Запишем . где Используя правило 2, получим

Выражение для представим в виде где Применив правило 4, получим Представим В в виде где Применив правило 4, получим Используя правило 2 к выражению для С, получим Таким образом,

Выражение для представим виде , Тогда, применив правило

4, получим Используя правило 3, получим

Следовательно, .

Представив В как где лгахя, и используя правило 2, получим Следовательно, . Используя соотношение получим Применив к правило 4, получим Следовательно, Окончательно получим

Переход к реализации КС в базисе И - НЕ основан на аналогичных правилах.

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

Пусть — исходная формула в базисе И, ИЛИ, НЕ, а формула — эквивалентная формула в базисе И - НЕ. Тогда работа метода может быть представлена с помощью следующих правил:

Если в базисе И, ИЛИ, НЕ, то где — формула в базисе И - НЕ, эквивалентная формуле

3. Если где А — формула в базисе И, ИЛИ, НЕ и если:

а) А — В, где В — формула в базисе то

4. Пусть . Очевидно, что может быть либо , либо либо где . В общем случае

Тогда формула может быть представлена в виде

или

Упростив выражение, получим

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

1) получение СДНФ булевой функции;

2) получение минимальной ДНФ булевой функции на основе ее СДНФ с помощью любого известного метода минимизации булевых функций;

3) перевод минимальной ДНФ в монофункциональный базис применением теорем де Моргана в любой последовательности.

Последнее справедливо, в силу того, что применение теорем де Моргана не изменяет числа букв в выражении.