Минимизация ФАЛ методом карт Карно

Под минимизацией логической функции понимается преобразование ее логического выражения с целью получения наиболее простого представления ФАЛ. Логическому выражению с минимальным количеством букв всегда соответствует схема с минимальным количеством контактов. В инженерной практике для минимизации ФАЛ наиболее широко используются: метод последовательного упрощения, основанный на применении законов и тождеств АЛ; метод, основанный на применении карт Карно; метод Квайна-Мак-Класки.

При использовании метода карт Карно производится накрытие с помощью правильных конфигураций полей карты, содержащей нули и единицы. Правильными конфигурациями ранга i на карте Карно от n переменных, являются все прямоугольники (вертикальные, горизонтальные и квадратные), имеющие площадь (i=1,2,3,…,n) и только такие прямоугольники. Рангом накрытия называется сумма рангов, всех образующих накрытие правильных конфигураций. Накрытие функции является минимальным, если его ранг не превосходит ранга любого другого накрытия этой функции с помощью правильных конфигураций. Для выполнения данного условия, необходимо накрыть все нули или все единицы карты с помощью минимального числа правильных конфигураций максимальной площади. При выборе накрытия возможно объединение крайних полей, расположенных на противоположных краях карты. Конфигурации могут перекрываться, накладываться одна на другую.

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

 

Рис 2.1. Примеры минимизации ФАЛ методом карт Карно

Как видно из рис. 2.1, при объединении двух полей исключается одна переменная, при объединении четырех – две переменные, при объединении восьми – три переменные.

Карты Карно наиболее целесообразно использовать для минимизации ФАЛ от 2-х до 5 переменных. При минимизации ФАЛ пяти переменных приходится оперировать с двумя картами по 16 полей каждая. Одной из карт ставится в соответствие прямое, а другой инверсное значение пятой переменной. При минимизации ФАЛ шести переменных, рассматриваются четыре карты по 16 полей.

Порядок выполнения работы

2.3.1. Изучить по данному методическому указанию и рекомендуемой литературе метод минимизации ФАЛ, основанный на использовании карт Карно;

2.3.2. С использованием карт Карно произвести минимизацию 2-х функций трех и четырех переменных, выбираемых из табл. 2.4 в соответствии с вариантом;

2.3.3. Представить полученные при минимизации функции в базисах «И-НЕ», «ИЛИ-НЕ» и нарисовать логические структуры, реализующие данные функции во всех трех базисах;

2.3.4. Проверить соответствие полученных при выполнении пункта 2.3.3 и исходных ФАЛ.

Содержание отчета

Отчет должен содержать:

· Наименование и цель работы;

· Схемы реализации полученных в результате минимизации ФАЛ в различных функциональных базисах;

· Дополненные выводами и комментариями результаты выполнения заданий по пунктам 2.3.2 – 2.3.4.

Таблица 2.4

Варианты ФАЛ трех переменных

Аргументы

Варианты, определяющие ФАЛ

a

b

c

f 1

f 2

f 3

f 4

f 5

f 6

f 7

f 8

f 9

f 10

f 11

f 12

f 13

f 14

f 15

f 16

f 17

 

Таблица 2.5

Варианты ФАЛ четырех переменных

Аргументы

Варианты, определяющие ФАЛ

a

b

c

d

f 1

f 2

f 3

f 4

f 5

f 6

f 7

f 8

f 9

f 10

f 11

f 12

f 13

f 14

f 15

f 16

f 17

 

ЛАБОРАТОРНАЯ РАБОТА №3