Jump to content

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

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

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

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

Мотивация

[ редактировать ]

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

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

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

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

[ редактировать ]

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

На основе представления схемы
Двухуровневая логическая оптимизация
Многоуровневая логическая оптимизация
На основе характеристик схемы
Последовательная логическая оптимизация
Оптимизация комбинационной логики
По типу исполнения
Методы графической оптимизации
Табличные методы оптимизации
Алгебраические методы оптимизации

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

[ редактировать ]

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

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

[ редактировать ]

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

В случае, когда булева функция задается схемой (то есть мы хотим найти эквивалентную схему минимально возможного размера), проблема минимизации неограниченной схемы давно предполагалась как -полный по временной сложности , результат окончательно доказан в 2008 году, [4] но существуют эффективные эвристики, такие как карты Карно и алгоритм Куайна-Маккласки , которые облегчают этот процесс.

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

[ редактировать ]

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

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

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

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

П = В + С.
F 1 = АП + АД .
F 2 = А'П + А'Е .

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

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

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

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

Хотя существует множество способов минимизировать схему, это пример минимизации (или упрощения) булевой функции. Булева функция, выполняемая схемой, напрямую связана с алгебраическим выражением, из которого реализуется функция. [7] Рассмотрим схему, используемую для представления . Очевидно, что в этом высказывании употребляются два отрицания, два союза и дизъюнкция. Это означает, что для построения схемы потребуются два инвертора , два вентиля И и вентиль ИЛИ .

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

А Б Б ) ( А Б) А Б
Ф Ф Ф Ф Т Ф Т Ф Ф Ф Ф Ф
Ф Т Ф Ф Ф Т Т Т Т Ф Т Т
Т Ф Т Т Т Т Ф Ф Ф Т Т Ф
Т Т Т Ф Ф Ф Ф Ф Т Т Ф Т

См. также

[ редактировать ]

Примечания

[ редактировать ]
  1. ^ Размер списка соединений можно использовать для измерения простоты.
  1. ^ Максфилд, Клайв «Макс» (1 января 2008 г.). «Глава 5: «Традиционные» процессы проектирования» . В Максфилде, Клайв «Макс» (ред.). ПЛИС . Мгновенный доступ. Берлингтон: Newnes / Elsevier Inc., стр. 75–106. дои : 10.1016/B978-0-7506-8974-8.00005-3 . ISBN  978-0-7506-8974-8 . Проверено 4 октября 2021 г.
  2. ^ Баласанян, Сейран; Агагулян, Мане; Вуттке, Хайнц-Дитрих; Хенке, Карстен (16 мая 2018 г.). «Цифровая электроника» (PDF) . Бакалавр встраиваемых систем – годовая группа. Темпус. Желание. Архивировано (PDF) из оригинала 04 октября 2021 г. Проверено 4 октября 2021 г. (101 страница)
  3. ^ Теобальд, М.; Новик, С.М. (ноябрь 1998 г.). «Быстрые эвристические и точные алгоритмы двухуровневой безопасной логической минимизации» . Транзакции IEEE по автоматизированному проектированию интегральных схем и систем . 17 (11): 1130–1147. дои : 10.1109/43.736186 .
  4. ^ Бухфюрер Давид; Уманс, Кристофер (январь 2011 г.). «Сложность минимизации булевой формулы» (PDF) . Журнал компьютерных и системных наук (JCSS) . 77 (1). Факультет компьютерных наук Калифорнийского технологического института , Пасадена, Калифорния, США: Elsevier Inc .: 142–153. дои : 10.1016/j.jcss.2010.06.011 . Это расширенная версия доклада конференции: Бухфюрер Давид; Уманс, Кристофер (2008). «Сложность минимизации булевой формулы». Труды по автоматам, языкам и программированию (PDF) . Конспекты лекций по информатике (LNCS). Том. 5125. Берлин/Гейдельберг, Германия: Springer-Verlag . стр. 24–35. дои : 10.1007/978-3-540-70575-8_3 . ISBN  978-3-540-70574-1 . Архивировано (PDF) из оригинала 14 января 2018 г. Проверено 14 января 2018 г. {{cite book}}: |work= игнорируется ( помогите )
  5. ^ Хаасвейк, Уинстон. «Точный синтез на основе SAT: кодировки, семейства топологий и параллелизм» (PDF) . ЭПФЛ . Проверено 7 декабря 2022 г.
  6. ^ Хаасвейк, Уинстон. «Точный синтез на основе SAT для многоуровневых логических сетей» (PDF) . ЭПФЛ . Проверено 7 декабря 2022 г.
  7. ^ Мано, М. Моррис; Кайм, Чарльз Р. (2014). Основы логики и компьютерного дизайна (4-е новое международное изд.). Пирсон Эдьюкейшн Лимитед . п. 54. ИСБН  978-1-292-02468-4 .

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

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e7f30a27bd148d9e7494db1d60cba026__1714642320
URL1:https://arc.ask3.ru/arc/aa/e7/26/e7f30a27bd148d9e7494db1d60cba026.html
Заголовок, (Title) документа по адресу, URL1:
Logic optimization - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)