Минимизация логических функций

Минимизация логических функций Логическая схема устройства, реализующая заданный алгоритм обработки сигналов, может быть непосредственно синтезирована по выражению логической функции, представленному в виде СДНФ или СКНФ. Однако, полученная таким образом схема, как правило, не является оптимальной с точки зрения практической реализации. Поэтому исходное выражение логической функции предварительно минимизируют. Это позволяет минимизировать стоимость реализации логической функции. Используемые критерии минимизации логических функций не являются однозначными. Часто используют критерий минимизации логических функций, заключающийся в уменьшении количества элементарных логических элементов при использовании только однородных элементов, например, только элементов «ИНЕ» («ИЛИ-НЕ»). Метод минимизации с использованием карт Карно1 основывается на табличном представлении логических функций. Он широко используется для «ручной» (т.е. неавтоматизированной, без применения ЭВМ) минимизации логических функций с числом переменных, не превышающих шести. Картой Карно называется таблица, число клеток которой для функции n переменных равно 2 n , причём каждому минтерму соответствует своя клетка (рисунок 25). Таким образом, карты Карно можно рассматривать как плоскую развертку n-мерного булева куба. Из рисунков 25 (а, б, в) видно, что минтерм занимает минимальную площадь и представляется одной клеткой на картах Карно. Макстерм занимает максимальную площадь и охватывает все клетки, кроме одной x 0 + x1 . Если требуется представить на карте Карно логическую функцию, заданную в виде СНДФ, в соответствующие клетки заносятся единицы. Остальные клетки остаются незаполненными или заполняются нулями. Логическая функция на карте Карно представляется совокупностью клеток, заполненных единицами, а инверсия функции − совокупностью пустых или заполненных нулями клеток. При минимизации логических функций используются либо единичные, либо нулевые значения клеток. В обоих случаях получаются равносильные выражения, которые, однако, могут отличаться числом членов и выполненных логических операций. Карты Вейча (Карнό) были предложены Эдвардом Вейчем в 1952 г., а затем усовершенствованы Морисом Карно в 1953 г., и предназначались для упрощения разработки цифровых электронных схем. 1 Рисунок 25 − Карты Карно для двух (а), трёх (б) и четырёх (в) переменных Таким образом, алгоритм минимизации с использованием карт Карно сводится к следующему: 1. На карте Карно выделяют прямоугольные области (контуры), объединяющие выбранные значения функции («1» или «0»). Причём каждая область должна содержать 2 k клеток, где k может принимать значения 0, 1, 2, 4, т.е. прямоугольную область образуют 1, 2, 4, 8, 16 клеток. Выделенные области могут пересекаться, т.е. одна клетка может входить в несколько областей. 2. Каждая из выделенных областей является самостоятельным произведением переменных, значения которых в рамках выделенной области остаются постоянными. Каждое произведение содержит n-k переменных и носит название импликанты, где n − число аргументов исходной логической функции. 3. Из полученного множества выделенных областей выбирают минимальное число максимально больших областей, включающих все клетки с выбранным значением логической функции. Сумма полученных произведений образует минимальную ДНФ. При объединении клеток с нулевыми значениями получается логическая функция, инверсная заданной. Пример минимизации логической функции Предположим, имеется следующая таблица истинности логической функции F трёх переменных X, Y и Z (таблица 13). Таблица 13 Таблица истинности логической функции F(X,Y,Z) Значения аргументов X Y Z 1 1 1 1 1 1 1 1 1 1 1 1 Значения функции F(X,Y,Z) 1 1 1 1 Из табличного представления логической функции F(X,Y,Z) получим выражение СДНФ, имеющее следующий вид: F ( X ,Y , Z ) = ( X ⋅ Y ⋅ Z ) + ( X ⋅ Y ⋅ Z ) + ( X ⋅ Y ⋅ Z ) + ( X ⋅ Y ⋅ Z ) . Полученное выражение СДНФ можно упростить (минимизировать), используя законы булевой алгебры. В данном примере функция будет иметь вид: F ( X , Y , Z ) = X ⋅ Y ⋅ ( Z + Z ) + X ⋅ Z ⋅ (Y + Y ) = X ⋅ Y + X ⋅ Z . При упрощении сначала используем распределительный закон, вынося за скобки логические произведения X ⋅ Y и X ⋅ Z , затем − закон дополнительности Z + Z = 1 и Y + Y = 1 . Минимизированная ДНФ (МДНФ) функции F(X,Y,Z), полученная с использованием законов булевой алгебры, записывается как F ( X ,Y , Z ) = X ⋅ Y + X ⋅ Z . Теперь выполним минимизацию выражения СДНФ методом карт Карно. Как отмечалось выше, карта Карно − это представление таблицы истинности логической функции в виде прямоугольной таблицы с соответствующим числом клеток ( 2 n , где n − количество логических переменных функции), каждая из которых отвечает определённой конъюнкции (произведению переменных). Значения переменных следуют так, чтобы в соседних клетках отличалась только одна из них, т.е. вместо чередования 00, 01, 10, 11 используется код Грея: 00, 01, 11, 10. В клетки карты Карно заносятся значения функции F(X,Y,Z) в соответствии с таблицей истинности (см. выше таблицу 13). Далее на карте выделяются один или несколько прямоугольных контуров (прямоугольников), включающих возможно большее число клеток, содержащих n логическую 1. При этом контуры могут содержать 2 клеток, т.е. 1, 2, 4, 8 и т.д. Одна и та же клетка может входить в несколько контуров. В данном случае можно выделить два контура (отмечены серым цветом), которые можно условно назвать «вертикальным» и «горизонтальным» (рисунок 26). XY Z X ⋅Y X ⋅Y X ⋅Y X ⋅Y 0 0 0 1 1 1 1 0 Z 1 Z 1 1 1 1 Рисунок 26 − Карта Карно для примера логической функции F(X,Y,Z) Для вертикального контура можно записать X ⋅ Y ⋅ Z + X ⋅ Y ⋅ Z = X ⋅ Y (Z + Z ) = X ⋅ Y . Для горизонтального контура можно записать X ⋅ Y ⋅ Z + X ⋅ Y ⋅ Z = X ⋅ Z (Y + Y ) = X ⋅ Z . МДНФ функции F(X,Y,Z), полученная с использованием карты Карно, записывается как F ( X ,Y , Z ) = X ⋅ Y + X ⋅ Z . Таким образом, МДНФ, полученные с помощью алгебраического упрощения и с использованием карты Карно, совпадают, что позволяет сделать вывод о равнозначности этих методов.