Минимизация - Преобразователи кода

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

Минимизация означает переход от СДНФ к ДНФ с минимумом слагаемых (избавиться от "совершенства"), при этом количество множителей в каждом слагаемом должно быть также минимальным, то есть максимально уменьшить количество переменных и операций в СДНФ.

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

    - карта Карно (Вейча) - Квайна - Квайна - Мак-Класки - Петрика

Отличие метода карт Карно от карт Вейча заключается в способе обозначения строк и столбцов карт. У карт Карно строки и столбцы обозначаются с помощью кода Грея. Однако, принципиальной разницы между ними нет.

Метод минимизационных карт Карно (или карт Вейча) хорошо работает при числе аргументов 3,4 и даже 5 и обеспечивает простоту получения результата. Этот метод основан на зрительном анализе таблиц (карт) и не может быть применен для обработки вычислительной техникой.

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

Рис 4.3.1. Карта Карно для 2-х и для 3-х переменных

Число клеток карты равно числу всех возможных комбинаций входных переменных, т. е. 2?, где N- чило входных переменных. Это также значит, что число клеток карты равно максимальному числу минтерм СНДФ.

Каждая клетка карты соответствует логическому произведению (прямого или инверсного значения) переменных, на пересечении которых она находится, что соответствует минтерме СНДФ. В карту Карно заносятся соответствующие значения минтерм.

Строки и столбцы карты обозначаются таким образом, чтобы любые соседние клетки по строкам или по столбцам отличались бы между собой значением только одной переменной. Такое обозначение соответствует последовательности чисел в коде Грея. Это сделано для того, чтобы было бы возможно применить закон склеивания.

Клетки, находящиеся на границах одной строки или столбца, так же считаются соседними.

Рис. 4.3.2. Карта Карно строится на основании таблицы истинности

A

B

C

F

0

0

0

А'b'c'

1

0

0

Ab'c'

0

1

0

A'bc'

0

0

1

A'b'c

1

1

0

Abc'

1

0

1

Ab'c

0

1

1

A'bc

1

1

1

Abc

Каждая клетка карты соответствует произведению переменных, на пересечении которых она находится.

Рис. 4.3.3. Принцип составления карты Карно

Для минимизации функций используется закон "склеивания":

Ab + ab' = a

Если переменная (аргумент) изменяет свое значение, а функция при этом остается неизменной, то эту переменную можно исключить из выражения.

Похожие статьи




Минимизация - Преобразователи кода

Предыдущая | Следующая