Меню
Главная
Авторизация/Регистрация
 
Главная arrow Логика arrow Анализ и синтез комбинационных схем

Минимизация ФАЛ с помощью карт Карно

Так как одна и та же ФАЛ может быть записана с помощью различных формул, то возникает задача получения минимальной формы записи (с минимальным числом букв), которая потребует минимальных затрат аппаратуры при реализации.

Рассмотрим процесс минимизации ФАЛ с помощью карт Карно. Карта Карно может быть составлена для любого количества переменных, однако удобно работать при количестве переменных не более шести. Карта Карно (рис. 10) является другой формой представления таблицы истинности (табл. 5). Каждая клетка карты соответствует строке таблицы (двоичному набору). Часть клеток (половина), которым соответствует значение xi = 1, отмечается чертой. Соответственно в областях, не обозначенных чертой, переменная xi = 0.

Таблица 5

Таблица истинности

x1

x2

x3

x4

y

0

0

0

0

0

0

1

0

0

0

1

1

2

0

0

1

0

0

3

0

0

1

1

1

4

0

1

0

0

1

5

0

1

0

1

1

6

0

1

1

0

1

7

0

1

1

1

1

8

1

0

0

0

0

9

1

0

0

1

0

10

1

0

1

0

1

11

1

0

1

1

0

12

1

1

0

0

1

13

1

1

0

1

1

14

1

1

1

0

1

15

1

1

1

1

1

Для задания ФАЛ в карте Карно надо проставить 1 в тех клетках, которые соответствуют разрешенным наборам. В карте на рис. 10 задана ФАЛ из табл. 5.

Карта Карно

Рис. 10. Карта Карно

Минимизация ФАЛ по карте Карно заключается в объединении соседних клеток в прямоугольные контуры, причем соседними считаются и клетки, разделенные внешней границей карты.

Минимизация производится по следующим правилам.

Все единицы должны быть включены в прямоугольные контуры.

Во всех клетках контура должны стоять единицы.

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

Контуры могут накладываться друг на друга.

Контуры, все клетки которых уже вошли в другие контуры, являются лишними.

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

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

Конъюнкции контуров объединяются знаками дизъюнкции.

Ниже представлена ФАЛ, соответствующая карте Карно на рис. 10:

Минимизируем функцию, представленную своими разрешёнными наборами, с использованием карт Карно (рис. 11):

.

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

Минимизация по карте Карно

Рис. 11. Минимизация по карте Карно

В итоге мы получаем следующую функцию:

 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 
Предметы
Агропромышленность
Банковское дело
БЖД
Бухучет и аудит
География
Документоведение
Естествознание
Журналистика
Информатика
История
Культурология
Литература
Логика
Логистика
Маркетинг
Математика, химия, физика
Медицина
Менеджмент
Недвижимость
Педагогика
Политология
Право
Психология
Религиоведение
Социология
Статистика
Страховое дело
Техника
Товароведение
Туризм
Философия
Финансы
Экология
Экономика
Этика и эстетика
Прочее