Табличный метод минимизации ФАЛ

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 02:30, 8 июня 2016.
TemplateDifinitionIcon.svg Определение «Определение - Табличный метод минимизации ФАЛ»
Табличный метод минимизации ФАЛ - метод минимизации булевых функций с использованием карт Карно или диаграмм Вейча (специального вида таблиц, отличающихся друг от друга расположением строк и столбцов).

Следует отметить, что риск сбоя представляет собой только возможность ложного срабатывания. Конкретная цепь может давать риск сбоя, а может и не давать, причем даже при наличии риска сбоя может отсутствовать ложное срабатывание. Его успешно применяют для решения задач минимизации функций алгебры логики от большого числа аргументов, потому что этот метод даёт возможность легко осуществить операцию склеивания при упрощении функции. Впервые Карты Карно были предложены Эдвардом В. Вейчем в 1952 году, а в 1953 году усовершенствованы Морисом Карно, физиком из крупного исследовательского центра «Bell Labs».

Описание

Булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своём составе 2N различных термов.Карта Карно - это определенная плоская развертка n-мерного булева куба. Каждая клетка этой таблицы является одной из вершин булева куба.

Булев куб.gif

Порядок работы

Карты Карно имеют порядок склеивания 00 01 11 10, диаграммы Вейча - 00 01 10 11. В остальном эти методы идентичны. Рассмотрим порядок процесса минимизации с помощью карт Карно:

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

Для заполнения таблицы удобно пользоваться эталонными картами Карно:

а) Эталонная карта Карно для функции от 4 переменных б) для функции от 5 переменных в) для функции от 6 переменных

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

Достоинства и недостатки

Достоиства:

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

Недостатки:

  • При большем числе переменных карты Карно становятся неэффективными
  • Метод не является алгоритмически систематическим, многое зависит от навыков разработчика