Электроника:Цифровая электроника/Карты Карно/Упрощение логики с помощью карт Карно

Содержание

Теория

Практика

Проверка знаний

Рецепты

Эксперименты

Резерв

Резерв

Резерв

Резерв

Перевод: Макаров В. (valemak)

Проверка/Оформление/Редактирование: Мякишев Е.А.

Упрощение логики с помощью карт Карно

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

В этом разделе мы рассмотрим несколько надуманных примеров, оставив большинство реальных приложений для главы «Комбинаторная логика». Под надуманным мы подразумеваем примеры, скорее иллюстрирующие сами техники упрощения, чем решающие реальные проблемы.

Этот подход позволит разработать инструменты, необходимые для перехода к более сложным приложениям, описанным в главе «Комбинаторная логика».

Карты Карно и последовательность кода Грея

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

Рис. 1. Шаблоны карт Карно для трёх переменных.

Обратите внимание на последовательность чисел в верхней части карты. Это не соответствует тому, в каком порядке идут двоичные числа (последовательность которых была бы 00, 01, 10, 11). Здесь мы видим 00, 01, 11 10, а это, кстати, последовательность в виде кода Грея. В такой последовательности меняется только один двоичный бит при переходе от предыдущего числа к следующему, в отличие от двоичной последовательности.

Это означает, что любые соседние ячейки отличаются только одним битом – а значит, только одной логической переменной. Это именно то, что нам нужно для организации выходных данных логической функции, чтобы мы могли обобщать смежные ячейки. И кстати, первый и последний столбец стали соседними, потому что заголовки этих двух столбцов отличаются только в одном бите, как и любая другая пара смежных столбцов карты.

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

Соседние ячейки различаются только на один бит, потому что последовательность в виде когда Грея изменяется только на один бит при переходе от одного числа к другому.

Как сгенерировать код Грея

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

Рис. 2. Как сгенерировать код Грея.

Обратите внимание, что последовательность кода Грея, расположенная вверху справа, изменяется только на один бит при спуске сверху-вниз или подъёме снизу-вверх по списку. Это свойство кода Грея часто используется для цифровой электроники в целом. В частности, это применяется и к картам Карно.

Примеры упрощения с картами Карно

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

Рис. 3. Упрощаем A'B'C' + A'B'C с помощью карты Карно до A'B'.

На рисунке 3 выше показано, что сначала заносятся единицы в K-карту для каждого из членов Суммы-Произведений, затем идентифицируется группа из двух единиц, затем записываем член Суммы-Произведений для единственной группы в качестве нашего упрощённого результата.

Рис. 4. Упрощаем A'B'C' + A'B'C + A'BC + A'BC' с помощью карты Карно до A'.

На рисунке 4 выше отображение четырёх членов Суммы-Произведений дают группу из четырёх единиц, соответствующей логическому значению A'.

Рис. 5. Упрощаем A'B'C' + A'BC + AB'C + ABC с помощью карты Карно до C.

На рисунке 5 выше четыре члена Суммы-Произведений дают группу из четырёх смежных единиц, соответствующей одной переменной C.

Рис. 6. Упрощаем A'B'C' + A'B'C + A'BC' + ABC + ABC' с помощью карты Карно до A' + B.

На рисунке 6 выше после проставления шести членов Суммы-Произведений определяем верхнюю группу из четырёх единиц (в строке для A', синий цвет), затем следует взять две нижние ячейки с единицами (в строке для A) и объединить с единицами над ними, сформировав как группу из четырёх единиц (красный цвет). Обратите внимание, что две единицы входят в обе группы – это целиком допустимый приём, дающий более простой результат.

Поскольку обнаружено две группы, в результате получим Сумму-Произведений A' + B с двумя членами.

Рис. 7. Упрощаем A'BC + ABC с помощью карты Карно до BC.

На рисунке 7 выше два приведённых выше члена Суммы-Произведений образуют одну группу из двух единиц и упрощаются до BC.

Рис. 8. Упрощаем A'BC + A'BC' + ABC + ABC' с помощью карты Карно до B.

На рисунке 8 выше отображение четырёх слагаемых Суммы-Произведений даёт одну группу из четырёх единиц, которая является просто B.

Рис. 9. Упрощаем A'B'C' + AB'C' + A'BC' + ABC' с помощью карты Карно до C'.

На рисунке 9 выше отображение четырёх членов Суммы-Произведений даёт группу из четырёх единиц. Если карту Карно как бы свернуть в цилиндр (правая часть рисунка 9), тогда будет очевидно, что ячейки с единицами являются смежными. Обычно подобные группы отмечаются так как показано в левой части рисунка 9.

Для этой группы из переменных A, B, C только одна является общей: C'. C' – это всего четыре ячейки с 0 по этой переменной. Конечный результат – C'.

Рис. 10. Упрощаем A'B'C' + A'B'C + A'BC + A'BC' + AB'C' + ABC' с помощью карты Карно до A' + C'.

На рисунке 10 выше неупрощённое выражение генерирует шесть ячеек с единицами, которые можно разделить на две группы по четыре смежных ячейки (пара ячеек входит в обе группы). Заметьте, что одна группа находится на первом и последнем столбце, которые тоже являются смежными. Эти две группы дают два члена в нашем упрощённом результате A' + C'.

Упрощение булевых уравнений с помощью карт Карно

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

Рис. 11. Неупрощённая вентильная схема, спроектированная для установки сжигания токсичных отходов из прошлой главы.

Булево уравнение для выхода имеет четыре члена Суммы-Произведений. Отображаем на карте Карно четыре единицы, соответствующие этим членам. Формируя группы ячеек, мы получаем три группы по две единицы. В упрощённом результате будет три члена, по одному для каждой группы смежных единиц. В той главе приведена итоговая логическая схема, вот она:

Рис. 12. Упрощённая вентильная схема, спроектированная для установки сжигания токсичных отходов из прошлой главы.

Чтобы показать, насколько быстрее упрощать с помощью карт Карно, воспроизведём упрощение методами булевой алгебры для установки сжигания токсичных отходов:

Рис. 13. Вот так мы в прошлой главе упрощали логическое выражение для вентильной схемы.

А теперь продублируем решение с помощью карты Карно, чтобы сравнить с аналитическим методом. Этот наглядно показывает, почему карты Карно широко используются для упрощения логики.

Рис. 14. Упрощение с помощью карты Карно.

Метод с картами Карно определённо выглядит на порядок проще, чем утомительные математические выкладки с помощью тождеств и правил булевой алгебры.