Тема 3. Минимизация логических функций

 

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

Существует два основных “ручных” метода минимизации логических функций:

1. Аналитический метод с использованием законов и правил алгебры логики.

2. Табличный метод, при котором функция представляется в виде карты Карно (диаграммы Вейча).

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

Два минтерма K_i (ν) и K_j (ν) (макстерма М_i (ν) и M_j (ν)) называются соседними, если они различаются только одним первичным термом (т.е., если один из минтермов содержит , а другой , все же остальные первичные термы одинаковые). Так, например, минтермы K ₂(ν) = и K ₆(ν) = = являются соседними, так как они различаются только одним первичным термом . Для минтерма K ₂(ν) соседними будут также минтермы K ₀(ν) = , K ₃(ν) = . Очевидно, что каждый минтерм (макстерм) n переменных K_i (ν) имеет по n соседних минтермов (макстермов) из общего числа 2 ⁿ. На основании свойств дизъюнкции и конъюнкции один и тот же минтерм (макстерм), входящий в СДНФ (СКНФ) может использоваться несколько раз для объединения с соседними минтермами (макстермами).

Пусть задана СКНФ функции трех переменных F (ν) = K ₀(ν) Ú K ₂(ν) Ú Ú K ₃(ν) Ú K ₆(ν) = . Здесь для минимизации минтерм K ₂(ν) = необходимо использовать три раза:

 

 

Уже из этого элементарного примера видно, что аналитический метод достаточно сложен в силу трудоемкости поиска соседних минтермов.

Табличный метод минимизации логической функции базируется на использовании диаграммы Вейча (карты Карно), которая является одним из способов табличного задания функции и состоит из клеток, каждая из которых соответствует определенной точке ν _i области определения функций, т. е. диаграммы Вейча для функции n переменных состоят из 2 ⁿ клеток, которые можно пронумеровать числами i = 0, 1,..., 2 ⁿ – 1. Чтобы с помощью диаграммы Вейча задать функцию F (ν), необходимо в каждую клетку с номером i занести значение функции F (ν _i) = а_i = 0 или 1, которое она принимает в точке i. Таким образом, одна строка таблицы истинности функции в диаграмме Вейча представляется одной ячейкой.

Для составления диаграммы Вейча (карты Карно) рисуется таблица, ее строки и столбцы нумеруются в двоичном коде и им присваиваются переменные. Вид диаграммы Вейча и карты Карно для функции четырех переменных представлен на рисунке 3.1. Здесь для наглядности координаты клеток указаны в трёх формах: в виде соответствующего минтерма; в виде двоичного числа, соответствующего порядковому номеру наборов аргументов; в десятичном эквиваленте номеров наборов аргументов.

 

	0 0 0 0	0 0 0 1	0 0 1 0	0 0 1 1
	0 1 0 0	0 1 0 1	0 1 1 0	0 1 1 1
	1 0 0 0	1 0 0 1	1 0 1 0	1 0 1 1
	1 1 0 0	1 1 0 1	1 1 1 0	1 1 1 1

а)

 

	0 0 0 0	0 0 0 1	0 0 1 1	0 0 1 0
	0 1 0 0	0 1 0 1	0 1 1 1	0 1 1 0
	1 1 0 0	1 1 0 1	1 1 1 1	1 1 1 0
	1 0 0 0	1 0 0 1	1 0 1 1	1 0 1 0

б)

Рисунок 3.1 – Вид диаграммы Вейча (а) и карты Карно для функции четырех аргументов

 

Следует отметить, что диаграмма Вейча отличается от карты Карно только в способе обозначения строк и столбцов. В диаграмме Вейча строки и столбцы пронумерованы в порядке нарастания двоичных чисел (00, 01, 10, 11), а в карте Карно – последовательностью чисел в коде Грея (00, 01, 11, 10), что делает все клетки карты Карно соседними. Это свойство определяет более широкое применение при минимизации функции именно карты Карно.

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

Для минимизации функции единицы в карте объединяются замкнутыми контурами в группы по правилам:

1. Число единиц в группе должно быть , где k = 0, 1, 2, 3…, следовательно, допустимое число клеток в контуре 1, 2, 4, 8,…

2. Внутри контура должны быть только клетки, заполненные единицами, одна и та же клетка может входить несколько контуров.

3. Крайние столбцы и строки карты Карно являются соседними и их клетки могут входить в общий контур.

4. Число контуров (групп) должно быть минимальным, охватывая все единичные клетки.

5. При записи минтермов в минимизированной функции исключаются переменные, имеющие взаимоинверсные значения (0 и 1 либо и ).

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

 

Таблица 3.1 – Таблица истинности логической функции

 

Карта Карно, соответствующая данной функции представлена на рисунке 3.2.

 

б)

Рисунок 3.2 – Карты Карно для функции

 

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

 

 

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