Логическая оптимизация , часть логического синтеза в электронике , представляет собой процесс поиска эквивалентного представления указанной логической схемы при одном или нескольких указанных ограничениях. Обычно схема ограничена минимальной площадью кристалла, соответствующей заранее заданной задержке.
С появлением логического синтеза одной из самых больших проблем, с которыми столкнулась индустрия автоматизации проектирования электроники (EDA), было найти лучшее представление списка соединений для данного описания проекта. Хотя двухуровневая логическая оптимизация долгое время существовала в форме алгоритма Куайна-МакКласки , за которым позже последовал эвристический минимизатор логики Espresso , быстро увеличивающаяся плотность микросхем и широкое применение HDL для описания схем формализовали область логической оптимизации как он существует сегодня.
В то время как двухуровневое представление схем строго относится к уплощенному представлению схемы с точки зрения SOP ( суммы продуктов ), что более применимо к реализации проекта в PLA [ требуется пояснение ] - многоуровневый представление является более общий вид схемы в терминах произвольно соединенных СОП, POSS ( продукт-оф-сумм ), факторизованном виде алгоритмы оптимизации и т.д. Логика обычно работают либо на структурных (СОП, факторизованном виде) или функциональных ( БДДС , прибавляет ) представление схемы. [ требуется разъяснение ]
В то время как количество уровней здесь равно 3, общее количество терминов и литералов продукта уменьшается [ количественно ] из-за совместного использования термина B + C.
Точно так же мы различаем последовательные и комбинационные схемы , поведение которых может быть описано в терминах таблиц / диаграмм состояний конечного автомата или булевых функций и отношений соответственно. [ требуется разъяснение ]
В булевой алгебре , минимизация цепи является проблемой получения наималейшей логической схемы (булева формула) , которая представляет собой заданную булеву функцию или таблицу истинности . Для случая, когда логическая функция задается схемой (то есть мы хотим найти эквивалентную схему минимально возможного размера), проблема неограниченной минимизации схемы долгое время предполагалась как -полная , и результат был окончательно доказан в 2008 году. [1], но существуют эффективные эвристики, такие как карты Карно и алгоритм Куайна – Маккласки, которые облегчают этот процесс.
