_1X_2X_3X_4 \vee \overline
_1\vee X_2\vee X_3\vee X_4) (\overline
Таким образом, главной задачей при минимизации СДНФ и СКНФ является поиск термов, пригодных к склейке с последующим поглощением, что для больших форм может оказаться достаточно сложной задачей. Карты Карно предоставляют наглядный способ отыскания таких термов.
Как известно, булевы функции N переменных, представленные в виде СДНФ или СКНФ, могут иметь в своем составе 2 N различных термов. Все эти члены составляют некоторую структуру, топологически эквивалентную N–мерному кубу, причем любые два терма, соединенные ребром, пригодны для склейки и поглощения.
На рисунке изображена простая таблица истинности для функции из двух переменных, соответствующий этой таблице 2-мерный куб (квадрат), а также 2-мерный куб с обозначением членов СДНФ и эквивалентная таблица для группировки термов:
В случае функции трех переменных приходится иметь дело с трехмерным кубом. Это сложнее и менее наглядно, но технически возможно. На рисунке в качестве примера показана таблица истинности для булевой функции трех переменных и соответствующий ей куб.
Как видно из рисунка, для трехмерного случая возможны более сложные конфигурации термов. Например, четыре терма, принадлежащие одной грани куба, объединяются в один терм с поглощением двух переменных:
В общем случае можно сказать, что 2 K термов, принадлежащие одной K–мерной грани гиперкуба, склеиваются в один терм, при этом поглощаются K переменных.
Как из Карт Карно Получить Минимизированную Функцию
Здесь должны быть представлены все возможные сочетания и соответствующие им состояния выхода (или выходов). В том случае, когда состояние входа не оказывает влияния на выход, ставится X (любое значение).
Шаг 2. Составим карту Карно. Она представляет собой нечто очень близкое к таблице истинности, но содержит переменные, которые расположены по двум осям. Переменные должны быть расположены таким образом, чтобы при переходе от каждого квадрата к соседнему менялось бы состояние только одного входа (рис.
8.27).
Шаг 3. Отметим на карте группы, содержащие 1 (можно также использовать и группы, содержащие 0). Три овала на рис. 8.27 определяют логические выражения АВ, АС и ВС.
схемная реализация ее показана на рис. 8.28. Этот результат кажется очевидным, когда он уже получен. Можно было бы составить выражение для нулей и вместо этого получить
Это выражение может оказаться полезным для случая, когда в каких-либо точках схемы имеются дополнения А, В и С.
Некоторые комментарии к картам Карно.
▪ Ищите группы, содержащие 2, 4, 8 и т. д. квадратов. Они имеют простые логические выражения.
3. Состыкуйте края карты Карно. Например, карта на рис. 8.29 описывается выражением С.
▪ Блок «единиц», содержащий один или два «нуля», лучше всего описывается с помощью группировки, показанной на рис. 8.30. Этому блоку соответствует логическое выражение .
▪ Места, содержащие X (любое значение), представляют собой «карт-бланш». Записывайте в них «нули» или «единицы» так, чтобы можно было получить простейшую логику.
Упражнение 8.13. Нарисуйте карту Карно для логики, которая позволит определить, является ли -разрядное двоичное число «главным», считая при этом, что главными не являются числа 0, 1 и 2. Дайте схемную реализацию на -входовых вентилях.
Упражнение . Найдите логическое выражение, с помощью которого можно было бы умножить два -разрядных двоичных числа и получить -разрядный результат. Рекомендации: для каждого выходного бита пользуйтесь отдельными картами Карно.
Метод минимизирующих карт Карно
Карты Карно – это графическое представление таблиц истинности логических функций. Они содержат по 2 n ячеек, где n—число логических переменных. Например, карта Карно для функции трех переменных содержит ячеек, для четырех переменных— ячеек.
Карта размечается системой координат, соответствующих значениям входных переменных. Обратим особое внимание на то, что координаты столбцов (а также и строк, если n >3), следуют не в естественном порядке возрастания двоичных кодов, а так: 00 01 11 10. Это делается для того, чтобы соседние наборы (в том числе и столбцов 1 и 4) отличались лишь одной цифрой в каком либо разряде.
Процесс минимизации заключается в формировании правильных прямоугольников, содержащих по 2 к ячеек, где к—целое число. В прямоугольники объединяются соседние ячейки, которые соответствуют соседним элементарным произведениям (т. е. отличаются только в одном разряде).
Несмотря на то, что карты Карно изображаются на плоскости, соседство квадратов устанавливается на поверхности тора. Верхняя и нижняя границы карты как бы склеиваются, образуя поверхность цилиндра. При склеивании боковых границ получается поверхность тора.
Пример: Минимизировать функцию трех переменных, заданную таблицей истинности (таблица 6).
| X1 X2 X3 | Y | X1 X2 X3 | Y |
| 0 0 0 0 0 1 0 1 0 0 1 1 | 1 0 0 1 0 1 1 1 0 1 1 1 |
Таким образом, карта Карно позволяет поместить рядом, то есть в соседних ячейках, соседние элементарные произведения, отличающиеся только одним сомножителем.
2 Ячейки карты Карно, соответствующие наборам переменных, обращающих функцию в «1», заполняются единицами, остальные – нулями.
3 Выбирается наилучшее покрытие карты прямоугольниками. Наилучшим считается покрытие, образованное минимальным числом прямоугольников, а если таких вариантов несколько, то выбирается тот, который дает максимальную площадь прямоугольников.
Пример: Минимизировать функцию четырех переменных, представленную картой Карно: (Рисунок 9)
Микропроцессоры и микроконтроллеры
Закон склеивания по карте Карно реализуется в том, что на карте прорисовываются прямоугольные контуры, содержащие единицы в строго соседних ячейках.
Логическая функция в минимизированной форме записывается на основе уравнений этих контуров путем исключением тех аргументов, которые изменяются в пределах контура (т. е. входят в соседние клетки в прямом и инверсном виде).
Правила формирования контуров: количество клеток, входящих в контур — 2, 4, 8, 16;
количество контуров должно быть минимальным, а их площадь максимальна;
соседними считаются и те клетки, которые находятся на противоположных краях таблицы.
Минимизированная функция получается как сумма конъюнкций, описывающих эти контуры.
Минимизация функции из рассматриваемого примера на основе карты Кар-но показана на рис. 2.3.
Рисунок 2.4 — Варианты заполнения карты Карно для функции из примера
Рисунок 2.3 — Пример минимизации логической функции трех аргументов
Размещение аргументов относительно карты Карно может быть любым, но следует соблюдать правило о соседних клетках (см. рис. 2.4).
При использовании любых материалов с сайта обратная ссылка на сайт обязательна.
Минимизация булевых функций
Используя законы булевой алгебры, можно получить для одной и той же логической функции множество эквивалентных представлений. Чем проще аналитическое выражение функции, тем экономичнее и проще ее практическая реализация на интегральных микросхемах. Сложность булевой функции определяется ее рангом, т. е. количеством переменных в ее конъюнктивных или дизъюнктивных членах.
Представление булевой функции в Сов ДНФ в большинстве случаев не является минимальным.
Используя операции поглощения и склеивания, его можно существенно упростить. Часто используется неполное склеивание, при котором оба члена, участвовавших в склеивании (или один из них), могут повторно склеиваться с другими оставшимися членами Сов ДНФ.
В процессе минимизации важно отыскать смежные конституенты, которые отличаются только одним аргументом (в одну конституенту аргумент входит с инверсией, а в другую – без нее).
Две смежные конституенты, склеиваясь, образуют импликанту рангом на единицу ниже, чем исходные конституенты.
Используя, например, неполное склеивание последней коституенты в Сов ДНФ функции F 1 последовательно с остальными, приходим к следующему выражению:
Процесс многоступенчатого склеивания приводит к импликантам, которые не склеиваются с другими. Такие импликанты называют простыми. Форма записи булевой функции в ДНФ, состоящая только из простых импликант, называется сокращенной дизъюнктивной нормальной формой (Сокр ДНФ).
В некоторых случаях в Сокр ДНФ могут содержаться лишние импликанты, которые могут быть исключены без изменения значения функции.
Одним из методов отыскания лишних импликант является метод испытания членов: чтобы испытать некоторый член функции, следует исключить его из Сокр ДНФ и подставить в оставшееся выражение такие значения аргументов, которые обращают исключенный член в единицу. Если при такой подстановке оставшееся выражение окажется тождественно равным единице, то испытуемый член является лишним.
Испытаем член AC. AC = 1, если A = 1 и C = 1. Подставим в оставшееся выражение A = 1 и C = 1, получим
При B = 0 F(A, B, C) = 1·1 Ъ 0·0 = 1, но при F(A, B, C) = 0·1 Ъ 0·0 = 0. Следовательно, член AC не лишний.
Последнее выражение равно 1 как при A = 1, так и при A = 0. Поэтому член – лишний.
Испытание члена по этой же методике показывает, что он не является лишним, в итоге тупиковая форма исходной функции имеет вид:
Для минимизации функций относительно небольшого числа переменной (не более шести) наиболее простым и наглядным является графический метод, использующий карты Карно.
Карта Карно – это прямоугольник, разбитый на квадраты, число которых равно числу наборов рассматриваемой функции, т. е. 2 n . Клетки размечаются так, чтобы наборы, для которых возможны смежные конституенты, оказались бы в соседних клетках.
При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. Например, для функции двух переменных А и В (рис. 5) карта Карно имеет вид
Единицы, представленные в клетках, обозначают конституенты единицы рассматриваемой функции. Отыскание минимальной ее формы сводится к определению варианта, при котором все конституенты единицы накрываются (охватываются контурами покрытия) наименьшим числом наиболее коротких импликант. Объединение клеток на карте эквивалентно выполнению операции склеивания.
Всегда нужно стремиться к минимальному количеству контуров и максимальной площади каждого из них, руководствуясь следующими правилами:
площадь контура покрытия должна быть S k = 2 m-i клеток, где – целое число, m – число переменных. Если, например, m = 3, то S k = 1, 2, 4, или 8 клеток;
число сокращаемых переменных N перем. = log 2 S k, т. е. при S k = 1 не сокращается ни одна переменная, при S k = 2 сокращается одна переменная и т. д.
В примере на рис. 5 пара единиц верхней строки охватывается импликантой Ā (т. е. обе клетки ) имеют общий аргумент Ā). Пара единиц правого столбца накрывается импликантой B, как общей для обеих клеток. Следовательно, минимальная ДНФ функции F(A, B) = Ā Ъ B.
Если имеется несколько вариантов объединения конституент контурами, то можно получить несколько различных эквивалентных минимальных ДНФ функции, одна из которых выбирается для реализации в цифровом устройстве.
Карту Карно удобно использовать и для минимизации функций, заданных в алгебраической форме, например,
Карта Карно, состоящая из 2 3 = 8 клеток, может быть размечена, как показано на рис. 6.
При охвате единиц контурами склеивания карту Карно можно сворачивать в цилиндр, как вдоль горизон-тальной, так и вертикальной оси. В результате все четыре единицы, расположенные в углах Карты, охватываются контуром с общей импликан-той . Такой минимизации соответствует выражение
Недоопределенность функции означает, что запрещенные наборы никогда не появятся в процессе работы устройства. Значит, такую функцию можно произвольно доопределить, установив ее значения на запрещенных наборах, и это не отразится на работе устройства, но обчит его реализацию.
Пусть необходимо минимизировать булеву функцию, заданную картой Карно (рис. 7).
Если группировать единицы в контурах только по исходному заданию (рис. 7, а), то минимальная форма функции будет иметь вид:
После доопределения функции (рис. 7, б), ее минимальная ДНФ (заметим, что это будет уже другая полностью определенная функция j ) оказывается предельно простой
Функция j, значения которой совпадают со значениями заданной функции F на тех наборах, где F определена, называется эквивалентной.
Таким образом, задача минимизации недоопределенной функции сводится к отысканию такой эквивалентной функции, которая имеет простейшую форму.
Поэтому устранение опасных состязаний достигается возвращением импликант, которые оказались лишними при переходе от сокращенной к тупиковой ДНФ.
