Метод минимизации Блейка-Порецкого.

Минимизация ПФ в булевом базисе.

Лекция 2. Этапы синтеза

Раздел 2. Синтез цифровых автоматов без памяти

 

Будем рассматривать синтез КС, реализующих одну ПФ. Процесс синтеза КС на элементах заданного базиса разбивается на следующие этапы:

1) Аналитическая запись ПФ в булевом базисе (запись в виде СДНФ или в СКНФ).

2) Минимизация ПФ в булевом базисе.

3) Представление полученного после минимизации выражения в заданном базисе (переход к заданному базису).

4) Построение КС, реализующей полученное выражение, с учетом коэффициентов объединения, разветвления и требуемого быстродействия.

 

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

В процессе минимизации СДНФ получается последовательно в начале сокращенная ДНФ, далее тупиковая и минимальная.

Существуют различные методы минимизации ПФ, из которых чаще всего используются методы Квайна, Мак-Класки, Блейка-Порецкого, диаграмм Вейча и карт Карно. В принципе все эти методы являются равновидностями метода Квайна.

 

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

Лемма:

Если в ДНФ для данной функции f(x1,…,xn) входят две конъюнкции вида Ахi и B, то имеет место следующее равенство:

 

f=fvAB.

Доказательство леммы:

Запишем функцию f в следующем виде:

 

.

 

Из доказанной леммы вытекает метод построения сокращенной ДНФ. Этот метод заключается в том, что исходную функцию необходимо пополнить новыми членами вида АВ согласно лемме. После этого надо провести поглощения и вновь повторить пополнение ДНФ. Этот процесс необходимо производить до тех пор, пока будут возникать новые конъюнкции вида АВ. По окончании преобразований получаем сокращенную ДНФ. Процесс пополнения ДНФ осуществляется согласно лемме по формуле, которая называется операцией обобщенного склеивания:

 

Axi v B= Axi v Bv AB.

 

В основе метода Квайна так же лежит операция склеивания, но другая, которая называется операцией неполного склеивания.

Операция неполного склеивания является частным случаем операцией обобщенного склеивания при А=В.

 

Axi v A= A v Axi v A.

 

Рассмотрим примеры:

1. Найти сокращенную ДНФ для функции трех аргументов:

 

.

При использовании метода Блейка-Порецкого применяется операция поглощения, которую можно представить в виде х v xy=x.

2. Пусть дана функция трех аргументов:

3.

.