Мастерство 5- и 6-переменных карт Карно для эффективного логического проектирования

По мере роста комбинаторной логики растет и размер карты Карно. Знание того, когда 5- или 6-переменная карта уместна — и как интерпретировать и группировать её ячейки — может резко сократить использование логики в FPGA и ASIC проектах.

Altera (ныне часть Intel) изучила тысячи клиентских проектов, чтобы понять типичные размеры фан-ин. Полученное распределение было почти плоским от двух до шести входов, с явным пиком на пяти. На практике большинство схем используют не более шести входов, и средний дизайн комфортно помещается в пять.

Собственные данные Altera, извлеченные из библиотеки клиентских проектов, подтверждают ценность гетерогенности. Изучая логические конусы, отображая их на LUT-базированные узлы и сортируя по числу входов, оптимальных для каждого узла, Altera обнаружила, что распределение фан-ин было почти плоским между двумя и шестью входами, с красивым пиком на пяти.

Ниже приведена классическая пятипеременная карта Карно.

Пятипеременная K-карта (отражающая карта)

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

Наложительная версия K-карты

Наложительная карта состоит из двух идентичных 4-ячеечных под-карт, отличающихся только старшим битом 3-битного адреса по верху. Нумерация отличается от отражающей карты: если игнорировать старший разряд, последовательность 00, 01, 11, 10 появляется в обеих под-картах. Восьмибитная последовательность не является кодом Грея, но двухбитный суффикс 01, 10 — является.

Применим пятипеременную карту к реальной задаче: спроектировать схему, принимающую 5-битный двоичный вход (A = MSB, B, C, D, E) и выдающую логическую единицу всякий раз, когда двоичное число простое.

Простые числа в 5-битном диапазоне: (1, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31). Отметьте 1 в каждой соответствующей ячейке, затем сгруппируйте единицы. Завершите записью упрощенного выражения.

В отражающей карте 4-ячеечная группа A'B'E охватывает две зеркальные пары, а 2-ячеечная группа AB'DE появляется как отраженная пара. При использовании наложительной карты ищите зеркальные образы через две половины.

Out = A'B'E + B'C'E + A'CDE + A'CD'E + ABCE + AB'DE + A'B'C'D

Ниже наложительная версия того же выражения.

Сравнивая две карты, некоторые ячейки сдвигаются из-за разницы адресации. Наложение одной половины на другую раскрывает перекрывающиеся группы, направляющие упрощение. Например, 4-ячеечная группа A'B'E покрывает паттерн ABCDE = 00xx1, то есть A, B, E зафиксированы как 0,0,1, а C и D варьируются.

Пример 6-переменной карты Карно следует. Ментально сложив четыре под-карты, можно выявить 4-ячеечную группу, реализующую Out = C'F'.

Для иллюстрации 6-переменной карты рассмотрим 3-битный компаратор величин, выдающий три выхода: равно, больше, меньше. Компаратор принимает два 3-битных входа A₂A₁A₀ и B₂B₁B₀. Для простоты решим только выход A > B.

6-переменная K-карта

Наложительная карта ниже помогает упростить логику для выхода A > B 3-битного компаратора. Двоичный адресный код по верху и слева не является полным 3-битным кодом Грея, но 2-битные коды каждой из четырех под-карт — Греевские.

Везде, где ABC превышает XYZ, наносится 1. Карта заполняется соответственно.

Группировка следует этим руководящим принципам:

• Одна группа из 16 ячеек
• Две группы из 8 ячеек
• Четыре группы из 4 ячеек

16-ячеечная группа AX' занимает правую нижнюю под-карту. Две 8-ячеечные группы образуются наложением идентичных 4-ячеечных паттернов из верхней и нижней под-карт. Четыре 4-ячеечные группы появляются на карте; каждая дает слагаемое-произведение. Финальная СП-редукция содержит семь термов.

Подсчет единиц дает 28 единиц. До редукции СП содержал бы 28 слагаемых-произведений по шесть входов каждый. K-карта сворачивает это до семи слагаемых-произведений по четыре или меньше входов — драматическое упрощение.

Схема соединений опущена, но вот список компонентов для 3-битного компаратора величин (A > B) на 4-TTL логике:

• 1 × 7410 тройной 3-входовый NAND (AX', ABY', BX'Y')
• 2 × 7420 двойной 4-входовый NAND (ABCZ', ACY'Z', BCX'Z', CX'Y'Z')
• 1 × 7430 8-входовый NAND (для финального 7-термового выхода)

Обзор

• Булева алгебра, карты Карно и САПР — основные инструменты упрощения логики.
• Минимально-стоимостное решение использует наименьшее число гейтов с наименьшим числом входов.
• Диаграммы Венна помогают визуализировать булевы выражения перед переводом в K-карты.
• Ячейки K-карты организованы в код Грея, раскрывая избыточность для упрощения.
• Сумма Произведений (СП) обычно реализуется как гейты И, питающие один гейт ИЛИ.
• СП можно реализовать NAND-NAND логикой, заменяя И и ИЛИ на NAND.
• Произведение Сумм (ПС) менее распространено, но может быть реализовано гейтами ИЛИ, питающими один гейт И, основанным на нулях карты (макстермах).