Синтез и анализ простейших схем

S(a,b,c,d) = bc' + ab'd' + bd

6.3 Минимизация логических функций с помощью графического представления n-мерного куба

 

   При количестве переменных не более 4-х  все возможные тупиковые и  саму минимальную формы можно  просто увидеть на пространственной диаграмме - n-мерном (в нашем примере - 3-х мерном) кубе - декартовом графике (рисунок 3), где на осях, соответствующих переменным, отображены точки их возможных состояний (0 или 1). Точки-состояния, в которых (согласно таблице истинности) функция принимает единичные значения, изобразим более крупными:

   Формула ребра вдоль оси-переменной не содержит этой переменной, т. к. значение функции на "склеенных" им вершинах не зависит от значения этой переменной, что соответствует операции выноса за скобки общего множителя. Например, ребро x·z соединяет точки x·y'·z и x·y·z:                  (x·y'·z) + (x·y·z) = x ·z ·(y' + y) = x ·z 

Рисунок 3 

   По  диаграмме задача минимизации сводится к объединению максимума вершин, на которых функция принимает  единичные значения, в минимум  ребер. В нашем случае - это два  ребра y'·z и x·y, "склеившие" четыре вершины.

   "Неудачный"  вариант минимизации соответствует выбору одного ребра x·z и "оставшихся" вершин x'·y'·z и x·y·z'.

   Очевидны  другие тупиковые ДНФ: два варианта смежных ребер плюс одна оставшаяся вершины и три ребра. Все варианты не минимальны. Чтобы получить указанные  варианты тупиковых форм аналитически, нужно воспользоваться известным тождеством

x + x = x

и записать "необходимую" конъюнкцию дважды. Например, по диаграмме очевидна ДНФ  из двух ребер и точки:

F(x,y,z) = x·y + x·z + x'·y'·z

Получим её аналитически, записав конъюнкцию x·y·z дважды:

F(x,y,z) = x'·y'·z + x·y'·z + x·y·z' + x·y·z + x·y·z =  
= x'·y'·z + x·y·(z' + z) + x·z ·(y' + y) = 
= x'·y'·z + x·y + x·z

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

   Пусть, например, дана СДНФ некоторой функции G(x,y,z):

G(x,y,z) = x·y'·z' + x·y·z + x'·y·z + x'·y·z' + x·y·z'

Здесь конъюнкции со 2-й по 5-ю как раз и образуют грань, формула которой – y (рисунок 4).

 Формула ребра,  склеившего вершины x·y'·z' и x·y·z', есть x·z'. Так что минимальная  ДНФ равна: 

G(x,y,z) = x·z' + y

Рисунок 4 

   Пространственная  диаграмма "выдерживает" представление  и 4-й переменной, отрицание которой  определяется на вершинах внутреннего куба, вставленного во внешний куб (рисунок 5). Значения других переменных определены на обоих кубах идентично:

   

Рисунок 5

6.4 Использование специальных методов

6.4.1 Карты Карно

  Рассмотрим  кратко метод карт Карно, как самый  удобный метод, позволяющий быстро решать задачи минимизации булевых функций от достаточно большого числа аргументов  
(6-12). При этом получается минимальная форма в базисе И, ИЛИ, НЕ. Существуют карты Карно на 2 , 3 , 4 , 5 и 6 переменных. Причем последние стали использоваться достаточно недавно. На рисунке 6 представлены карты Карно для 2, 3, 4, 5 и 6 аргументов.

6.4.2 Карты и прямоугольники Карно

  Метод Карно основан на законе склеивания. Склеиваются наборы, отличающиеся друг от друга значением одного разряда. Такие наборы называются соседними. Карно закодировал клетки своей карты так ,что в соседних клетках оказались соседние, а значит, склеивающиеся наборы. Соседними могут быть не только отдельные клетки, которые мы назовем элементарными квадратами Карно, но и целые группы соседних клеток (назовем их прямоугольниками Карно). Под прямоугольником Карно будем понимать некоторую, зачастую разрозненную фигуру покрытия, все соседние клетки которой закодированы соседними наборами. Например, на рисунке 7 в поле карты для 4-х переменных изображён прямоугольник Карно P, состоящий из четырёх элементарных квадратов Карно, описываемых наборами  
x₄^x₃^x₂^x₁^ , x₄^x₃^x₂ x₁^  , x₄ x₃^x₂^x₁^  , x₄ x₃^x₂ x₁^  . Если над логической суммой этих четырёх наборов произвести последовательно операции склеивания, то мы аналитически получим результат в виде импликанты (под импликантой будем понимать неполный набор) x₃^x₁^. Карта Карно позволяет получить этот результат графически значительно быстрее и проще. Для решения этой задачи используем алгоритм графической минимизации. Кстати говоря, сам Карно никакого алгоритма так и не предложил.

5.4.3 Алгоритм "НИИРТА" графической минимизации булевых функций

1. Заполнить карту  Карно нулями и единицами в  соответствии с таблицей истинности.
2. Покрыть все единичные наборы минимальным количеством прямоугольников Карно, каждый из которых имеет максимальную площадь.
3. Каждому прямоугольнику Карно соответствует одна импликанта, причём, если в границах прямоугольника Карно какая-либо переменная принимает значения как 0 , так и 1 , то она склеивается.

Примечание

   Если  в карте Карно нулей окажется меньше чем единиц, то удобнее прямоугольниками Карно покрыть все нулевые  наборы. В результате мы получим  инверсию минимизируемой функции.

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

Синтез комбинационных схем можно проиллюстрировать решением простой задачи.

5.4.4 Пример решения задачи

   Рассмотрим  следующую задачу.

  Необходимо синтезировать схему логического устройства для голосования в приемной комиссии, если приёмная комиссия в составе трех членов и одного председателя решает судьбу абитуриента большинством голосов. В случае равного распределения голосов большинство определяется той группой, в которой оказался председатель приемной комиссии.

6.4.4.1 Математическая модель цифрового устройства

   Пусть f - функция большинства голосов. f = 1, если большинство членов комиссии проголосовало за приём абитуриента, и f  =  0 в противном случае.

   Обозначим через x₄ голос председателя комиссии. x₄ = 1, если председатель комиссии проголосовал за приём абитуриента. x₃, x₂, x₁ - голоса членов приёмной комиссии.

   С учётом вышеуказанных допущений  условие задачи можно однозначно представить в виде таблицы истинности. Заполнение таблицы осуществляем с  учётом того, что функция f является полностью определённой, т.е. она определена на всех возможных наборах переменных x₁ - x₄. Для n входных переменных существует N = 2ⁿ наборов переменных. В нашем примере  
N = 2**4 = 16 наборов. Записывать эти наборы можно в любом порядке, но лучше в порядке возрастания двоичного кода.

x4   x3   x2   x1   f

0    0    0    0    0

0    0    0    1    0

0    0    1    0    0

0    0    1    1    0

0    1    0    0    0

0    1    0    1    0

0    1    1    0    0

0    1    1    1    1

1    0    0    0    0

1    0    0    1    1

1    0    1    0    1

1    0    1    1    1

1    1    0    0    1

1    1    0    1    1

1    1    1    0    1

1    1    1    1    1

Примечание 

   Здесь и  далее под набором будем понимать конъюнкцию всех входных переменных.

   Все наборы, на которых функция принимает  значение 1 , будем называть единичными, или рабочими. Наборы, на которых  функция принимает значение 0, будем  называть нулевыми, или запрещенными (кстати, существует множество научных  определений для набора: конституента,  терм, импликанта, минтерм и т.д., но они только вносят путаницу).

   Для того, чтобы по таблице истинности найти функцию f, достаточно выписать все единичные наборы и соединить  их знаком дизъюнкции.

   Таким образом,

   f = x₄^x₃x₂x₁ + x₄x₃^x₂^x₁ + x₄x₃^x₂x₁^ + x₄x₃^x₂x₁ + x₄x₃x₂^x₁^ + x₄x₃x₂^x₁ +

       + x₄x₃x₂x₁^ + x₄x₃x₂x₁

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

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

    Применим  карту Карно для решения этой задачи. Возможны два варианта решения.

f = x₄x₁ + x₄x₂ + x₄x₃ + x₃x₂x₁

f' = x₄^x₁^ + x₄^x₂^ + x₄^x₃^ + x₃^x₂^x₁^

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

f = x₄(x₁ + x₂ + x₃) + x₃x₂x₁

На рисунке 7  представлены карта Карно для  решения данной задачи и логические схемы цифрового устройства.

 
5.4.5 Основные правила

1. Начните с  булева выражения в дизъюнктивной  нормальной форме или с таблицы  истинности.
2. Начертите карту Карно с необходимым числом переменных и нанесите «единицы» в соответствующие ячейки.
3. Объедините смежные ячейки, содержащие единицы контурами (рисунок 8), охватывающими два, четыре или восемь ячеек (одну ячейку можно использовать несколько раз, не вводя контуров, в которых все ячейки с единицами уже вошли в другие контуры).
4. Проведите упрощения, включая члены, дополняющие друг друга внутри контура и опуская смежные переменные.
5. Объедините оставшиеся члены (по одному в каждом контуре) функцией ИЛИ ( + ).
6. Запишите полученное упрощенное булево выражение в дизъюнктивной нормальной форме,(дополнив его слагаемыми учитывающими единицы, не вошедшие ни в какие контуры).

 

  6 Практическое задание

1. Согласно  вашему варианту задания выбрать из таблицы 3 логическую функцию.
2. Выполнить процедуру минимизации логической функции любым методом.
3. Дать представление минимальной функции в двух базисах “И-НЕ” и “ИЛИ-НЕ”.
4. Синтезировать в пакете EWB схемы минимальной функции в двух базисах.
5. Провести диагностику двух схем в потенциальном режиме с использованием светодиодов как на входе так и на выходе (можно использовать так же светодиодную матрицу).
6. Провести диагностику только одной из схемы (на ваш выбор) в импульсном режиме с использованием генератора слов и анализатора импульсов.
7. Обязательно привести в отчете табличную функцию для удобства проверки синтезированных схем
8. Подготовить отчет для защиты.