Оптимизация логики

Чтобы узнать о других значениях, см. Минимизация .

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

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

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

Мотивация

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

С появлением логического синтеза одной из самых больших проблем, с которыми столкнулась индустрия автоматизации электронного проектирования (EDA), стал поиск наиболее простого схемного представления данного описания проекта. Хотя двухуровневая логическая оптимизация уже давно существовала в форме алгоритма Куайна-МакКласки , за которым позже последовал эвристический логический минимизатор Эспрессо , быстрое улучшение плотности микросхем и широкое распространение языков описания аппаратных средств для описания схем формализовали логическую оптимизацию. домен в том виде, в котором он существует сегодня, включая Logic Friday (графический интерфейс), Minilog и ESPRESSO-IISOJS (многозначная логика).

Методы

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

Классификация

Сегодня оптимизация логики делится на различные категории:

На основе представления схемы

Двухуровневая логическая оптимизация

Многоуровневая логическая оптимизация

На основе характеристик схемы

Последовательная логическая оптимизация

Оптимизация комбинационной логики

По типу исполнения

Методы графической оптимизации

Табличные методы оптимизации

Алгебраические методы оптимизации

Графические методы

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

• Диаграмма Эйлера (также известная как эйлеров круг ) (1768 г.), автор Леонард П. Эйлер (1707–1783)
• Диаграмма Венна (1880 г.) Джона Венна (1834–1923)
• Карта Карно (1953) Мориса Карно

Минимизация логического выражения

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

В случае, когда булева функция задается схемой (то есть мы хотим найти эквивалентную схему минимально возможного размера), проблема минимизации неограниченной схемы давно предполагалась как $\Sigma _{2}^{P}$-полный по временной сложности , результат окончательно доказан в 2008 году, но существуют эффективные эвристики, такие как карты Карно и алгоритм Куайна-Маккласки , которые облегчают этот процесс.

К методам минимизации логических функций относятся:

• Алгоритм Куайна – Маккласки
• метод Петрика

Оптимальные многоуровневые методы

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

Эвристические методы

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

Двухуровневые и многоуровневые представления

В то время как двухуровневое представление схем строго относится к плоскому представлению схемы с точки зрения SOP ( суммы продуктов ), что более применимо к PLA . реализации проекта — многоуровневое представление — это более общий вид схемы с точки зрения произвольно связанных SOP, POS ( произведение сумм ), факторизованной формы и т. д. Алгоритмы логической оптимизации обычно работают либо в структурной форме (SOP, факторизованная форма), либо в структурной форме (SOP, факторизованная форма) или функциональное представление ( двоичные диаграммы решений , алгебраические диаграммы решений ) схемы. В форме суммы произведений (SOP) элементы AND образуют наименьшую единицу и соединяются с помощью OR, тогда как в форме произведения сумм (POS) все наоборот. Форма POS требует скобок для группировки терминов OR под логическими элементами AND, поскольку OR имеет более низкий приоритет, чем AND. Как формы SOP, так и POS прекрасно трансформируются в схемную логику.

Если у нас есть две функции F ₁ и F ₂ :

$F_{1}=AB+AC+AD,\,$

$F_{2}=A'B+A'C+A'E.\,$

Приведенное выше двухуровневое представление использует шесть терминов продукта и 24 транзистора в КМОП-реп.

Функционально эквивалентным многоуровневым представлением может быть:

П = В + С. ​

F ₁ = АП + АД .

F ₂ = А'П + А'Е .

Хотя количество уровней здесь равно 3, общее количество терминов и литералов продукта уменьшается. из-за совместного использования термина B + C.

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

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

Пример

Оригинальный и упрощенный пример схемы

Хотя существует множество способов минимизировать схему, это пример минимизации (или упрощения) булевой функции. Булева функция, выполняемая схемой, напрямую связана с алгебраическим выражением, из которого реализуется функция. Рассмотрим схему, используемую для представления $(A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)$. Очевидно, что в этом высказывании употребляются два отрицания, два союза и дизъюнкция. Это означает, что для построения схемы потребуются два инвертора , два вентиля И и вентиль ИЛИ .

Схему можно упростить (минимизировать), применив законы булевой алгебры или воспользовавшись интуицией. Поскольку в примере указано, что $A$ верно, когда $B$ ложно и наоборот, можно заключить, что это просто означает $A\neq B$. С точки зрения логических вентилей неравенство просто означает вентиль исключающее ИЛИ (исключающее или). Поэтому, $(A\wedge {\bar {B}})\vee ({\bar {A}}\wedge B)\iff A\neq B$. Тогда две схемы, показанные ниже, эквивалентны, что можно проверить с помощью таблицы истинности :

А	Б		(А	∧	Б )	∨	( А	∧	Б)		А	≠	Б
Ф	Ф		Ф	Ф	Т	Ф	Т	Ф	Ф		Ф	Ф	Ф
Ф	Т		Ф	Ф	Ф	Т	Т	Т	Т		Ф	Т	Т
Т	Ф		Т	Т	Т	Т	Ф	Ф	Ф		Т	Т	Ф
Т	Т		Т	Ф	Ф	Ф	Ф	Ф	Т		Т	Ф	Т

См. также

• Бинарная диаграмма решений (BDD)
• Плевать на состояние
• Премьер с участием
• Сложность схемы — об оценке сложности схемы.
• Функциональная композиция
• Функциональная декомпозиция
• Недоиспользование ворот
• Логическая избыточность
• Гарвардская минимизирующая диаграмма (Викиверситет) (Викибуки)

Дальнейшее чтение

• Линд, Ларри Фредерик; Нельсон, Джон Кристофер Канлифф (1977). Анализ и проектирование последовательных цифровых систем . Макмиллан Пресс . ISBN  0-33319266-4 . (146 страниц)
• Де Микели, Джованни (1994). Синтез и оптимизация цифровых схем . МакГроу-Хилл . ISBN  0-07-016333-2 . (Примечание: главы 7–9 посвящены комбинаторной двухуровневой, комбинаторной многоуровневой и соответственно последовательной оптимизации схем.)
• Хачтел, Гэри Д.; Соменци, Фабио (2006) [1996]. Алгоритмы логического синтеза и проверки . Springer Science & Business Media . ISBN  978-0-387-31005-3 .
• Кохави, Цви; Джа, Нирадж К. (2009). «4–6». Теория коммутации и конечных автоматов (3-е изд.). Издательство Кембриджского университета . ISBN  978-0-521-85748-2 .
• Рутенбар, Роб А. Многоуровневая минимизация, Часть I: Модели и методы (PDF) (слайды лекций). Университет Карнеги-Меллон (CMU). Лекция 7. Архивировано (PDF) из оригинала 15 января 2018 г. Проверено 15 января 2018 г .; Рутенбар, Роб А. Многоуровневая минимизация, Часть II: Извлечение куба/коядра (PDF) (слайды лекции). Университет Карнеги-Меллон (CMU). Лекция 8. Архивировано (PDF) из оригинала 15 января 2018 г. Проверено 15 января 2018 г.