УП часть 2 ТА

функцию F(a,b,c) . В частности, если начать испытание импликант с последней импликанты в (1.3), то полученная

1.3 Визуальные методы минимизации логических функций

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

Импликантная матрица – это таблица, столбцы которой содержат элементарные конъюнкции (минтермы) СДНФ логической функции, а строки – найденные по методу Квайна импликанты.

Проиллюстрируем данный метод на примере рассматриваемой нами ранее логической функции F (a,b,c) , СДНФ которой определяется соотношением (1.1):

F СДНФ (a,b,c) = abc + abc + abc + abc + abc + abc

Составим для этой функции импликантную матрицу (табл.1.3), в которой Ki - элементарные конъюнкции из (1.1), а U j - импликанты из выражения (1.3).

Таблица 1.3

В импликантной матрице ставим “ Χ ” на пересечении тех строк и столбцов матрицы, в которых импликанта может поглотить конъюнкцию. Для получения тупиковой ДНФ необходимо выбрать

минимальное число таких импликант U j , которые в совокупности поглотили бы все элементарные конъюнкции Ki . В результате этих

1.4.1 Метод минимизации полностью определенных логических функций с помощью карт Карно

Метод минимизации логических функций с помощью карт Карно заключается в следующем: на карту Карно наносятся единичные и нулевые значения логических функций. Для получения ДНФ логической функции рассматриваются единичные значения функции, а для получения КНФ – нулевые [элем теор авт].

Пусть с помощью карты Карно задана логическая функция

f (x1,..., xn ) , необходимо найти ее тупиковую ДНФ. Тогда задача минимизации решается следующим образом: среди единичных

значений логической функции f (x1,..., xn ) , предварительно нанесенных на карту Карно, отыскиваются прямоугольники и/или

квадраты с числом клеток 2k , где k=(n-1),…,0. Выделяемые прямоугольники и/или квадраты могут пересекаться между собой.

Задача минимизации состоит в том, чтобы все единичные значения логической функции покрыть минимальным количеством прямоугольников и/или квадратов максимальной площади, величина

которых должна быть кратна 2k .

Тупиковой дизъюнктивной нормальной формой логической функции f (x1,..., xn ) называется такая ДНФ, реализующая

f (x1,...,xn ) , в которой ни одна из импликант не является лишней,

то есть ни одна из импликант не может быть удалена из формулы. Импликанты – это элементарные конъюнкции ранга меньше

максимального, которые не могут быть склеены (т.е. объединены) между собой.

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

Если необходимо найти тупиковую КНФ логической функции f (x1,..., xn ) , то задача минимизации решается следующим образом: среди нулевых значений логической функции f (x1,..., xn ) , предварительно нанесенных на карту Карно, отыскиваются прямоугольники и/или квадраты с числом клеток

2k , где k=(n-1),…,0. Выделяемые прямоугольники и/или квадраты могут пересекаться между собой.

Задача минимизации состоит в том, чтобы все нулевые значения логической функции покрыть минимальным количеством прямоугольников и/или квадратов максимальной площади, величина

которых должна быть кратна 2k .

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

При применении метода минимизации логических функций с помощью карт Карно необходимо помнить о том, что карты Карно

обладают свойством цилиндричности, т.е. клетки, расположенные по краям карт Карно являются соседними в каждом столбце и каждой строке и могут объединяться в прямоугольники и/или квадраты.

Минимизируем с помощью данного метода логическую

функцию F (a,b,c) , СДНФ которой определяется соотношением

(1.1):

F СДНФ (a,b,c) = abc + abc + abc + abc + abc + abc

Построим для функции F (a,b,c) карту Карно (рис.1.1).

Рис. 1.1 Карта Карно функции F (a,b,c)

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

вычисляется как 2k , где k=(n-1),(n-2),…,0, а n – число аргументов, от которых зависит логическая функция. В нашем случае n=3, следовательно максимальный размер прямоугольника равен

23−1 = 22 =4. В карте Карно нет прямоугольника, состоящего из четырех единиц, стоящих рядом, поэтому объединять клетки карты можно только по две, например так, как показано на рис. 1.2.

Минтермы функции образуют в карте три группы. Одна группа состоит из двух минтермов abc и abc . Общей

импликантой у них является ab . В соответствии с теоремами алгебры логики имеем:

abc + abc = ab(c + c) = ab ,

то есть переменная c из этой группы может быть исключена [Яглом].

Рис. 1.2 Карта Карно функции F (a,b,c)

Объединяя знаком дизъюнкции найденные из каждого прямоугольника импликанты, получаем тупиковую ДНФ функции

F (a,b,c) :

Объединить клетки карты Карно можно и другим образом (рис.1.3),

0 1 1 1 0

1 1 0 1 1

Рис. 1.3 Карта Карно функции F(a,b,c)

тогда получим еще одну тупиковую ДНФ, реализующую функцию

F (a,b,c) (1.9):

1.4.2. Метод минимизации частично определенных логических функций с помощью карт Карно

Пусть не полностью определенная логическая функция R(a,b,c,d) задана с помощью карты Карно (рис 1.4).

Рис. 1.4 Карта Карно логической функции R(a,b,c,d)

Для представления функции R(a,b,c,d) в виде минимальной ДНФ целесообразно следующее доопределение логической функции

(рис.1.5):

Рис. 1.5 Доопределенная карта Карно логической функции

R(a,b,c,d)

Доопределяем функцию единицами и нулями так, чтобы при составлении ДНФ было минимальное число импликант наименьшего ранга, т.е. покрываем все единичные значения функции минимальным числом прямоугольников максимального размера так, как показано на рис.1.6.

Рис. 1.6 Карта Карно логической функции R(a,b,c,d)

В результате минимизации получим минимальную ДНФ логической функции R(a,b, c,d):

RМДНФ (a,b,c,d) = a × c + b × d + b × c + abc + a ×b × d (1.10)

Сравнение эффективности минимизированных форм часто проводят по способу Шеннона. Этот способ базируется на введении такого понятия как цена схемы – Ц. Цену схемы можно рассчитать по следующей формуле:

i, j=1

где K ji - количество входов у j-ого элемента, i-количество

элементов.

Пусть логическая функция R(a,b,c,d) задана в виде СДНФ

(1.10 а):

Оценим минимальную ДНФ логической функции R(a,b, c,d) (1.10) по формуле (1.11). Элементов “И” в выражении присутствует 5 (два элемента “И” по 2 входа, три элемента “И” по 3 входа), элементов “ИЛИ”- 1 (один элемент на 5 входов), элементов “НЕ”- 4 (4 элемента по 1 входу), следовательно:

Ц=2*2+3*3+1*5+4*1=22 входа

Тем же способом оценим СДНФ логической функции

R(a,b,c,d) – выражение (1.10 а):

Элементов “И” - 11 (одиннадцать элементов по 4 входа), элементов “ИЛИ”- 1 (один элемент на 11 входов), элементов “НЕ”- 4 (4 элемента по 1 входу), следовательно:

Ц=11*4+1*11+4*1=59 входов

1.5 Машинно-ориентированные методы минимизации логических функций

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

1.Использование числового представления логических функций и реализация алгоритма минимизации на ЭВМ.

2.В этом методе практически отсутствуют ограничения на число логических переменных, от которых зависит минимизируемая функция.

Метод Квайна-Мак-Класки базируется на следующих основных этапах:

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

2.Построение таблицы покрытий матрицы Квайна.

3.Отыскание минимального покрытия логической

функции.

4.Получение минимальной формы логической функции. Более подробно этот материал изложен в [3], [4].

1.6 Групповая минимизация системы логических функций

Минимизация в широком смысле слова — такое преобразование логических выражений, которое упрощает их в смысле некоторого критерия. Целью минимизации одиночных логических функций является сокращение ранга и числа элементарных конъюнкций, входящих в исходную ДНФ логической функции. В результате минимизации по таким критериям могут быть получены кратчайшие и/или минимальные тупиковые дизъюнктивные нормальные формы, обеспечивающие минимальную структурную сложность при реализации логической функции в элементных базисах И, ИЛИ, НЕ; И-НЕ; ИЛИ-НЕ и прочее.

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

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

При реализации системы логических функций наиболее эффективен метод группой минимизации, который легко реализуется и состоит в следующем: в системе логических уравнений отыскиваются группы одинаковых элементарных конъюнкций. Для каждой группы одинаковых элементарных конъюнкций вводится фиктивная переменная с каким – либо индексом (например, Z1, … ZS). Далее все исходные логические уравнения переписываются в терминах фиктивных переменных. Затем на логической схеме реализуют элементарные конъюнкции, соответствующие каждой фиктивной переменной и их дизъюнкции в соответствии с уравнениями, содержащими фиктивные переменные.

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