6. Бинарный фал. Синтез логических схем.

ФАЛ двух аргументов (бинарные): Всего таких функций . Другое название этих функций - двоичные бинарные (двухоперандные, двухразрядные) шифраторы с унарным (одноразрядным) выходом.

Основные этапы проектирования (синтеза) схем: 1)Представление функций, выполняемой схемой, в виде таблицы истинности или СКНФ (СДНФ). 2)Минимизация логической функции. 3)Перевод функции в базис, в котором будет строиться схема. 4)Построение схемы в выбранном базисе.

Составление ф-ций СКНФ и СДНФ сожжет быть представлено в виде таблицы истинности, в виде формулы. Таблица истинности – совокупность всех возможных комбинаций на входе цифрового устройства. СДНФ – в каждой конъюнкте представлены все литералы по одному роду. СКНФ – в каждой дизъюнкте представлены все литералы по одному роду. Литерал – формула или её логич отрицание.

14. Синтез фал в одноэлементном базисе. Работа с кнф

Часто устройства строят в одноэлементном базисе. Такими базисами служат: стрелка Пирса и штрих Шеффера.

Рассмотрим способы перевода МДНФ (МКНФ) в данные базисы.

1.Перевод в базис стрелка Пирса. . Применяя принцип суперпозиции и правило де Моргана, получим, . Синтез логических функций в базисе Пирса удобно производить, имея запись функции в КНФ.

Чтобы от КНФ перейти к базису Пирса и инверсии необходимо:

А)заменить операции дизъюнкции и конъюнкции операциями Пирса;

Б)заключить в скобки все те группы букв, которые соответствуют конъюнктивным членам.

Пример. .

2.Перевод в базис штрих Шеффера. . Применяя принцип суперпозиции и правило де Моргана, получим, . Синтез логических функций в базисе Пирса удобно производить, имея запись функции в ДНФ.

Чтобы от ДНФ перейти к базису Шеффера и инверсии необходимо:

А)заменить операции дизъюнкции и конъюнкции операциями Шеффера;

Б)группы букв, которые соответствуют дизъюнктивным членам, заключить в скобки.

Пример. .

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

Все, что было сказано относительно минимизации функции, представленной в СДНФ или ДНФ справедливо для функции, заданной в СКНФ или КНФ. В этом случае необходимо отыскивать правильные конфигурации, образованные нулями. В основном методы получения МКНФ аналогичны методам получения МДНФ и поэтому сформулируем лишь правила получения МКНФ:

1.Представить ФАЛ в СКНФ. Если она задана таблицей, то произвести запись функции по нулям, как это было сформулировано ранее. Если дана СДНФ, то из нее легко получить СКНФ:

2.При задании функции в произвольной конъюнктивной форме, применяя формулы развертывания получить СКНФ:

3.Выполнить все операции неполного склеивания:

и поглощения: и получить сокращенную КНФ.

4.Применить любой из методов минимизации.

При выполнении метода проб необходимо каждый конъюнктивный член приравнять нулю. Найти значения аргументов, которые обращают его в нуль, удалить его из выражения функции и найти значение функции при найденных значениях аргументов. Если функция обратится в нуль, то конъюнктивный член является лишним. По возможности отбросить одновременно несколько членов, поступить, как и при минимизации функции ДНФ. При использовании карт Карно ищутся правильные конфигурации, образованные нулями. При применении метода импликантных матриц поступают, как и в случае ДНФ, только колонкам присваивают имена конституент 0 функции, записанной в СКНФ, а горизонтальным рядам – простых импликант. Далее ищут оптимальное покрытие.