4.11. Минимизация логических функций с использованием карт Карно (диаграмм Вейча)
Карты Карно представляют собой прямоугольную таблицу, состоящую из 2n полей (клеток), каждое из которых соответствует одному из 2n одночленов, порожденных n переменными, по числу всего множества конституент единицы или конституент нуля. Наборы значений аргументов логической функции ставятся в соответствие полям карты Карно таким образом, чтобы при переходе от одного поля к любому другому смежному с ним происходило изменение значения только одной переменной. Выполнение этого условия обеспечивает расположение в соседних полях карты «склеивающихся» между собой конституент единицы или нуля ( напомним, что операции склеивания соответствует преобразование x y Ú x`y = x (y Ú`y ) = x × 1 = x). Крайние строки и крайние столбцы карты Карно считаются смежными. Разметка, т.е. соответствие полей карт Карно значениям переменных для случая двух
(A, B), трех (A, B, C), четырех (A, B, C, D) и пяти (A, B, C, D, E) аргументов приведена на рис. 4.2.
При использовании диаграмм Вейча минимизируемую логическую функцию предварительно следует привести к дизъюнктивной нормальной форме, т.е. выразить в виде логической суммы простых конъюнкций, или к конъюнктивной нормальной форме. (Напомним: простой конъюнкцией считается логическое произведение переменных, взятых с отрицаниями или без них, в котором каждая переменная встречается не более одного раза. Простая конъюнкция, в которую входят все переменные называется минтермом.).
После того, как исходная функция представлена в ДНФ или КНФ и произведены очевидные упрощения, производится заполнение таблицы.
Для изображения на карте Карно заданной логической функции, представленной в СДНФ, в поля карты, соответствующие конституентам единицы заданной функции, проставляются символы «1», а в остальные поля – символы «0». Если заданная функция представлена в СКНФ, то в поля карты Карно, соответствующие конституентам нуля заданной функции, проставляются символы «0», а в остальные поля – символы «1».
В заполненной таблице производят выделение прямоугольных контуров, охватывающих все поля с единицами (если функция задана в ДНФ) и записывают минимизированную функцию в виде суммы логических произведений, описывающих эти контуры. Для получения минимальной конъюнктивной формы следует объединить нули логической функции.
При проведении контуров придерживаются следующих правил:
1) контур должен быть прямоугольным;
2) внутри контура должны быть только поля, заполненные единицами;
3) количество полей внутри контура должно быть целой степенью числа 2, т.е. может быть равно 1, 2, 4, 8, 16 и т.д.;
4) одни и те же поля, заполненные единицами, могут входить в несколько контуров;
5) при проведении контуров самая нижняя и самая верхняя строки таблицы считаются смежными, то же самое для самого левого и самого правого столбцов;
6) количество контуров должно быть как можно меньше, а количество полей с единицами в контуре должно быть как можно больше;
7) если контур охватывает столбцы или строки, содержащие как саму переменную хi так и ее отрицание `xi, это означает, что минимизируемая функция не зависит от значений этой переменной и в логическое выражение (простую конъюнкцию), описывающую этот контур, она не войдет.
При построении цифровых устройств иногда применяются логические цепи, закон функционирования которых определен не полностью. В таких цепях по условиям работы некоторые комбинации входных переменных не используются. Такие комбинации входных переменных называют запрещенными. Для запрещенных комбинаций входных переменных значения функции не определены, т.е. могут принимать любые значения – единицу или нуль. Поэтому при синтезе логических цепей с не полностью заданным законом функционирования можно произвольно задать значения логической функции (0 или 1), т.к. нормальная работа синтезируемой цепи при этом не нарушится. Обычно логической функции на запрещенных комбинациях придают такие значения, при которых можно синтезировать наиболее простую по числу логических элементов цепь.
Пример 4.6.
Необходимо синтезировать схему управления элемента «B» семисегментного индикатора, предназначенного для отображения десятичных цифр, представленных в двоичном коде 8-4-2-1.
Для решения этой задачи необходимо синтезировать логическую функцию, зависящую от четырех двоичных переменных x1, x2, x3, x4 , соответствующих четырем двоичным разрядам, и принимающую значение «1», если заданный элемент используется при индикации какой либо цифры (например светится) и «0», если элемент не используется.
Составим таблицу истинности для описываемой логической функции.
Таблица 4.9
|
Цифра |
Значения входных переменных |
Значение функции fB |
|||
|
x4 |
x3 |
x2 |
x1 |
||
|
0 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
1 |
1 |
|
2 |
0 |
0 |
1 |
0 |
1 |
|
3 |
0 |
0 |
1 |
1 |
1 |
|
4 |
0 |
1 |
0 |
0 |
1 |
|
5 |
0 |
1 |
0 |
1 |
0 |
|
6 |
0 |
1 |
1 |
0 |
0 |
|
7 |
0 |
1 |
1 |
1 |
1 |
|
8 |
1 |
0 |
0 |
0 |
1 |
|
9 |
1 |
0 |
0 |
1 |
1 |
По таблице истинности получаем совершенную дизъюнктивную нормальную форму для функции fB в виде
fB = `x1`x2`x3`x4 Ú x1`x2`x3`x4 Ú`x1 x2`x3`x4 Ú x1 x2`x3`x4 Ú`x1`x2 x3`x4 Ú x1 x2 x3`x4 Ú`x1`x2`x3 x4 Ú x1`x2`x3 x4.
Далее либо в соответствии с полученной СДНФ, либо непосредственно по таблице истинности заполняем карту Карно. Так как для изображения десяти цифр не нужны все 16 комбинаций, которые могут образовать 4 двоичных переменных (24 = 16), в полях карты Карно, соответствующих неиспользованным (запрещенным) комбинациям, временно поставим знак «Х». Объединив поля, содержащие единицы в соответствии с приведенными выше правилами, получаем четыре контура. Используя выделенные контуры, строим минимизированное выражение для функции fB .
fB =`x3`x4 Ú`x2`x3 Ú `x1`x2`x4 Ú x1 x2`x4.
Если использовать все или часть запрещенных комбинаций, проставив в соответствующие поля значение «1» с целью получения меньшего числа контуров, можно получить другой вариант карты Карно и, соответственно, минимизированной логической функции.
fB = `x3 Ú`x1`x2 Ú x1 x2.