Карлогская Булевская Алгебраическая Упрощенная Методика
В этой статье дается представление о методе булевой алгебраической упрощения Karnaugh (K-map) с помощью нескольких примеров. В нем также содержится краткая заметка о преимуществах и недостатках K-карт.
Введение
Цифровая электроника имеет дело с дискретно-цифровыми сигналами. В общем, любая электронная система, основанная на цифровой логике, использует двоичную нотацию (нули и единицы) для представления состояний переменных, участвующих в ней. Таким образом, булево алгебраическое упрощение является неотъемлемой частью проектирования и анализа цифровой электронной системы.
Хотя для достижения цели можно использовать булевы алгебраические законы и теоремы ДеМоргана, процесс становится утомительным и подверженным ошибкам по мере увеличения числа переменных. Это требует использования подходящей, относительно простой методики упрощения, такой как карта Карно (K-карта), введенная Морисом Карно в 1953 году.
Типичная К-карта
Метод K-map решения логических выражений называется графическим методом упрощения булевых выражений. K-карты также называются двумерными таблицами истинности, поскольку каждое K-отображение представляет собой не что иное, как другой формат представления значений, присутствующих в одномерной таблице истинности.
K-карты в основном касаются техники вставки значений выходной переменной в ячейки в прямоугольнике или квадратной сетке в соответствии с определенным шаблоном. Количество ячеек в K-карте определяется количеством входных переменных и математически выражается как два поднятых до мощности числа входных переменных, т. Е. 2 n, где число входных переменных равно n.
Таким образом, для упрощения логического выражения с двумя входами нам требуется K-карта с ячейками 4 (= 2 2). Логическое выражение с четырьмя входами приведет к 16 (= 2 4) ячейкам-К-карте и так далее.
Серый код
Кроме того, каждая ячейка в К-карте имеет определенное значение места, которое получается с использованием метода кодирования, известного как код Грея.
Особенностью этого кода является тот факт, что смежные значения кода отличаются только одним битом. То есть, если заданное кодовое слово равно 01, то предыдущие и следующие кодовые слова могут быть 11 или 00 в любом порядке, но не могут быть 10 в любом случае.
В K-картах в строках и столбцах таблицы используется Grey code-labeling, которые в свою очередь представляют значения соответствующих входных переменных. Это означает, что каждая ячейка К-карты может быть решена с использованием уникального Gray Code-Word.
Эти концепции дополнительно подчеркиваются типичной 16-клеточной K-картой, показанной на рисунке 1, которая может быть использована для упрощения логического выражения, состоящего из 4-переменных (A, B, C и D, упомянутых в верхнем левом углу).
Рисунок 1: Типичная, но пустая карта Карно с 16 ячейками
Здесь строки и столбцы K-карты помечены с использованием 2-битного кода Grey, показанного на рисунке, который назначает определенный адрес для каждой из его ячеек.
Например, клетка серого цвета отображаемой K-карты может быть решена с использованием кодового слова «0101», которое эквивалентно 5 в десятичной форме (показано как зеленый номер на рисунке) и соответствует комбинации входных переменных A̅BC̅D или A + B̅ + C + D̅, в зависимости от того, выражается ли соотношение вход-выход в форме SOP (сумма продуктов) или POS (произведение сумм) соответственно.
Аналогично, AB̅CD или A̅ + B + C̅ + D̅ относится к кодовому слову Gray «1011», что эквивалентно 11 десятичным (опять же, показано зеленым на рисунке), что, в свою очередь, означает, что мы обращаемся к розово- цветной ячейки К-карты на рисунке.
Техника упрощения K-Map
С этой общей идеей K-карт перейдем теперь к процедуре, используемой при проектировании оптимальной (с точки зрения числа логических систем, используемой для реализации логической) цифровой системы. Мы начнем с заданной задачи.
Пример 1:
Создайте цифровую систему, выход которой определяется как логически низкий, если 4-битное двоичное двоичное число кратно 3; в противном случае выход будет логически высоким. Выход определяется тогда и только тогда, когда входное двоичное число больше 2.
Шаг 1: таблица истины / каноническое выражение, ведущее к минимальным или максимальным условиям
Первым шагом в разработке любой цифровой системы является четкое представление о переменных, участвующих в процессе, а также их значениях состояния. Далее, в зависимости от оператора проблемы, мы должны прийти к количеству выходных переменных и их значениям для каждой комбинации входных литералов, которые могут быть удобно представлены в виде таблицы истинности.
В данном примере:
Число входных переменных = 4, которые мы будем называть A, B, C и D.
Количество выходных переменных = 1, которые мы будем называть Y
где
Y = Не заботьтесь, если входной номер меньше 3 (оранжевые записи в таблице истинности)
Y = 0, если входное число является целым кратным 3 (зеленые записи в таблице истинности)
Y = 1, если входное число не является целым кратным 3 (синие записи в таблице истинности)
Таблица 1
Обратите внимание, что в дополнение к входным и выходным столбцам таблица истинности также имеет столбец, который дает десятичный эквивалент входной двоичной комбинации, что позволяет нам легко добраться до расширения minterm или maxterm для данной проблемы. Таким образом, для данного примера, Расширение Minterm будет Σ m (4, 5, 7, 8, 10, 11, 13, 14) + Σ d (0, 1, 2)
Расширение Макстерма будет Π M (3, 6, 9, 12, 15) · Π D (0, 1, 2)
Однако иногда логическое выражение, которое должно быть упрощено, может быть непосредственно дано в виде SOP или POS-форм. В этом случае требование таблицы истинности можно упускать из виду при условии, что мы выражаем данное выражение в его канонической форме, из которой могут быть получены соответствующие minterms или maxterms.
Шаг 2. Выбор и заполнение K-карты
Начиная с шага 1, мы знаем количество входных переменных, участвующих в логическом выражении, из которых будет определен размер требуемой K-карты. Кроме того, мы также знаем количество таких K-карт, которые необходимы для проектирования желаемой системы, поскольку число выходных переменных также будет известно определенно. Это означает, что для рассмотренного примера нам требуется одиночная (из-за одной выходной переменной) K-карта с 16 ячейками (так как есть четыре входные переменные).
Затем мы должны заполнить ячейки K-карты по одному для каждого minterm, ноль для каждого maxterm и Xfor Do not Care. Процедура должна повторяться для каждой выходной переменной. Следовательно, для этого примера мы получаем K-карту, как показано на рисунке 2.
Рисунок 2: Полностью заполненная 4-переменная K-карта
Шаг 3: сформируйте группы
Упрощение К-карты также можно назвать методом «упрощения по группировке», поскольку оно основано исключительно на формировании кластеров. То есть основная цель всего процесса состоит в том, чтобы собрать вместе столько же (для решения SOP) или нулей (для решения POS) под одной крышей для каждой из выходных переменных в указанной проблеме. Однако при этом мы должны строго соблюдать определенные правила и положения:
- Процесс должен быть инициирован путем группировки битов, которые находятся в смежных ячейках, так что сформированная группа содержит максимальное количество выбранных битов. Это означает, что для n- переменного K-отображения с 2 n ячейками сначала попытайтесь сгруппировать для 2 n ячеек, затем для 2 n- 1 клеток, затем для 2 n -2 клеток и так далее, пока не появится «группа» только 2 0 ячейки, т. е. изолированные биты (если они есть). Обратите внимание, что количество ячеек в группе должно быть равно целочисленной мощности до 2, т. Е. 1, 2, 4, 8..,,
- Процедура должна применяться для всех соседних ячеек K-карты, даже если они не смежны - верхняя строка считается смежной с нижней строкой, а самый правый столбец считается смежным с крайним левым столбцом, как будто K-карта обертывается сверху вниз и справа налево. Например, группа 1 решения SOP формы в таблице 1.
- Немного, появляющееся в одной группе, может быть повторено в другой группе при условии, что это приведет к увеличению итогового размера группы. Например, клетка 5 повторяется как в группе 3, так и 4 в растворе формы SOP в таблице 1, так как это приводит к образованию группы с двумя клетками вместо группы с одной клеткой.
- Не заботьтесь об условиях, которые следует учитывать для деятельности группировки, если и только если они помогают в получении большей группы. В противном случае их следует пренебрегать. Здесь считается, что члены Do not Care в ячейках 0 и 1 создают группу 2 формы решения SOP, так как это приводит к группе с четырьмя ячейками вместо двух.
| Решение SOP Form | Решение POS-формы | ||||
| Число групп, имеющих 16 ячеек | 0 | 0 | |||
| Число групп, имеющих 8 ячеек | 0 | 0 | |||
| Число групп, имеющих 4 ячейки (синие оболочки на рисунке 3) | 2 | Группа 1 (ячейки 0, 2, 8, 10) | 1 | Группа 1 (ячейки 0, 1, 2, 3) | |
| Группа 2 (ячейки 0, 1, 4, 5) | |||||
| Количество групп, имеющих 2 ячейки (оранжевые шкафы на рисунке 3) | 4 | Группа 3 (ячейки 5, 7) | Группа 4 (ячейки 5, 13) | 2 | Группа 2 (ячейки 1, 9) |
| Группа 5 (ячейки 10, 11) | Группа 6 (ячейки 10, 14) | Группа 3 (ячейки 2, 6) | |||
| Количество групп, имеющих 1 ячейку (зеленые оболочки на рисунке 3) | 0 | 2 | Группа 4 (ячейка 12) | ||
| Группа 5 (ячейка 15) | |||||
Таблица 1
Следовательно, в рассматриваемом примере K-карта, показывающая группы, может быть получена, как показано на фиг. 3, информация которой приведена в таблице 1.
Рисунок 3: K-карты, сгруппированные для (a) SOP-решения и (b) POS-решение
Шаг 4: Упрощенная логическая экспрессия
Для каждой из полученных групп мы должны получить соответствующее логическое выражение в терминах входных переменных. Это можно сделать, выражая биты, которые являются общими среди кодовых слов Грея, которые представляют ячейки, содержащиеся в рассматриваемой группе. Другой способ описать процесс получения упрощенного логического выражения для группы - это исключить переменную (ы), для которой соответствующие биты появляются внутри группы как 0, так и 1.
Наконец, все эти групповые логические выражения должны быть соответствующим образом объединены, чтобы сформировать упрощенное булево уравнение для выходной переменной. Та же процедура должна повторяться для каждой выходной переменной данной проблемы.
Например, в рассматриваемом примере логический термин для группы 2 решения формы SOP получается как A̅C̅. Это связано с тем, что эта группа имеет 0 как общий бит слова кода Сердца как вдоль его строк, так и своих столбцов, выделенных на рисунке 4 (а). Это дает нам литералы A̅ и C̅.
Аналогично, в случае группы 1 решения POS-формы мы можем получить логическое выражение как A + B. Это связано с тем, что группа имеет общие кодовые слова Grey как 0, 0 по всей своей строке (кодовые слова не являются обычными вдоль своих столбцов), которые соответствуют входным переменным A и B.
Рисунок 4: Метод упрощения K-карты для (a) решения SOP и (b) POS-решение
Следуя этому же процессу, мы можем получить логические термины, соответствующие каждой из групп, чтобы окончательно сформировать логическое выражение для конкретного вывода, как показано в таблице 2.
| Решение SOP Form | Решение POS-формы | ||
| группы | Логическое выражение | группы | Логическое выражение |
| Группа 1 | Bd | Группа 1 | А + В |
| Группа 2 | переменный ток | Группа 2 | B + C + D |
| Группа 3 | ABD | Группа 3 | А + C + D |
| Группа 4 | BCD | Группа 4 | A + B + C + D |
| Группа 5 | азбука | Группа 5 | A + B + C + D |
| Группа 6 | ДСА | ||
| Таким образом, Y = B̅D̅ + A̅C̅ + A̅BD + BC̅D + AB̅C + ACD̅ | Таким образом, Y = (A + B) (B + C + D̅) (A + C̅ + D) (A̅ + B̅ + C + D) (A̅ + B̅ + C̅ + D̅) | ||
Таблица 2
Шаг 5: Разработка системы
Получив упрощенное логическое выражение, мы можем определить тип и количество ворот, необходимых для реализации ожидаемой логики для каждого выходного бита, что в дальнейшем приводит к полной разработке желаемой системы.
Таким образом, цифровая система, соответствующая SOP и POS-формам решения для данного примера, может быть сконструирована с использованием основных ворот типа NOT, AND и OR, как показано на рис. 5 (a) и 5 (b).
Рисунок 5: Цифровая система, соответствующая (a) форме решения SOP и (b) POS-форме решения
Теперь, когда мы проанализировали каждый шаг для примера 1, давайте практикуем, применив их к еще двум примерам.
Пример 2:
Создайте полный сумматор, получив упрощенные выражения для суммирования и переноса выходов в форме POS.
Шаг 1:
Количество входных переменных = 3
Количество выходных переменных = 2
| входные | Десятичный эквивалент | Выходы | |||
| В | C i | S | C o | ||
| 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 0 |
| 0 | 1 | 0 | 2 | 1 | 0 |
| 0 | 1 | 1 | 3 | 0 | 1 |
| 1 | 0 | 0 | 4 | 1 | 0 |
| 1 | 0 | 1 | 5 | 0 | 1 |
| 1 | 1 | 0 | 6 | 0 | 1 |
| 1 | 1 | 1 | 7 | 1 | 1 |
Таблица 3
Разложение Макстерма для S = П M (0, 3, 5, 6)
Разложение Макстерма для Co = Π M (0, 1, 2, 4)
Этапы 2 и 3:
Количество необходимых K-карт = 2
Каждая К-карта должна содержать 8 ячеек.
Таким образом, мы получаем:
Рисунок 6: упрощение K-карты для полного сумматора (a) суммарный вывод и (b) перенос вывода
| Сумма, S | Выполнить вывод, C o | ||||||
| Группы с 8 ячейками | ноль | ноль | |||||
| Группы с 4 ячейками | ноль | ноль | |||||
| Группы с 2 ячейками | ноль | 3 | Группа 1 (ячейки 0, 1) | Группа 2 (ячейки 0, 2) | |||
| Группа 3 (ячейки 0, 4) | |||||||
| Группы с 1 ячейкой | 4 | Группа 1 (ячейка 0) | Группа 2 (ячейка 3) | ноль | |||
| Группа 3 (ячейка 5) | Группа 4 (ячейка 6) | ||||||
Таблица 4
Шаг 4:
| группы | Сумма, S | Выполнить вывод, C o |
| Группа 1 | A + B + C i | A + B |
| Группа 2 | A + B̅ + C̅ i | A + C i |
| Группа 3 | A̅ + B + C̅ i | B + C i |
| Группа 4 | A̅ + B̅ + C i | |
| S = (A + B + C i) (A + B̅ + C̅ i) (A + + B + C̅ i) (A + + B + C i) | C o = (A + B) (A + C i) (B + C i) |
Таблица 5
Шаг 5:
Цифровая система, предназначенная для реализации полного сумматора по суммарным и переносящим выходам (в форме POS), показана на рисунке 7:
Рисунок 7: Цепь полного сумматора
Пример 3:
Упростите булево выражение f (A, B, C, D, E) = Σ m (0, 3, 4, 7, 8, 12, 14, 16, 19, 20, 23, 24, 26, 28)
Шаг 1:
Количество входных переменных = 5
Количество выходных переменных = 1
Минтермовое расширение выхода задается как f (A, B, C, D, E) = Σ m (0, 3, 4, 7, 8, 12, 14, 16, 19, 20, 23, 24, 26, 28)
Этапы 2, 3 и 4:
Количество необходимых K-карт = 1
Каждая К-карта должна содержать 32 ячейки.
Таким образом, мы получаем:
Рисунок 8: Групповая 32-элементная K-карта
| Количество групп с 32 ячейками | ноль | |||
| Количество групп с 16 ячейками | ноль | |||
| Количество групп с 8 ячейками (оранжевые шкафы на рисунке 8) | 1 | Группа 1 (ячейки 0, 4, 8, 12, 16, 20, 24, 28) | Делавэр | |
| Количество групп с 4 ячейками (синие шкафы на рисунке 8) | 1 | Группа 2 (ячейки 3, 7, 19, 23) | BDE | |
| Количество групп с 2 ячейками | ноль | |||
| Количество групп с 1 ячейкой (зеленые оболочки на рисунке 8) | 2 | Группа 3 (ячейка 14) | ABCDE | |
| Группа 4 (ячейка 26) | ABCDE | |||
| Таким образом, f (A, B, C, D, E) = D̅E̅ + B̅DE + A̅BCDE̅ + ABC̅DE̅ | ||||
Таблица 6
Шаг 5:
Цифровая система, соответствующая заданной функции, получается, как показано на рисунке 9:
Рисунок 9: K-карта с 5 переменными для функции, показанной в примере 3
Преимущества K-Maps
- Методика упрощения К-карты проще и менее подвержена ошибкам по сравнению с методом решения логических выражений с использованием булевых законов.
- Это предотвращает необходимость запоминания каждой булевой алгебраической теоремы.
- Он включает в себя меньше шагов, чем метод алгебраической минимизации, чтобы получить упрощенное выражение.
- Метод упрощения K-карты всегда приводит к минимальному выражению, если выполняется правильно.
Недостатки K-карт
- По мере увеличения числа переменных в логическом выражении процесс упрощения К-карты усложняется.
- Минимальное логическое выражение, полученное с помощью процедуры упрощения K-карты, может быть или не быть уникальным в зависимости от выбора, сделанного при формировании групп. Например, для выходной переменной Y, показанной K-картой на рисунке 10, мы можем получить два разных, но точных логических выражения. Изменение полученного раствора наблюдается в третьем члене, которое может быть либо B̅C̅, либо AC̅ (выделено на рисунке 10). Эта разница зависит от того, выбираете ли вы группу клеток (0, 4) или (4, 6), чтобы сформировать группу с двумя клетками, чтобы покрыть ту, что была найдена в ячейке К-карты с номером 4.
Рисунок 10: K-карта с уникальным решением
Вывод
Проанализировав структуру K-карт, мы можем прийти к выводу, что процесс упрощения K-карты является эффективным методом сокращения при рассмотрении логических выражений, содержащих около трех-шести входных переменных.