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

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

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

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

Мотивация

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

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

Методы

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

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

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

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

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

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

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

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

Комбинационная логическая оптимизация

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

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

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

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

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

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

• Диаграмма Эйлера (также известная как круг Эйлера ) (1768) Леонарда П. Эйлера (1707–1783)
• Диаграмма Венна (1880 г.) Джона Венна (1834–1923 гг.)
• Диаграмма Маркуанда (1881) Аллана Маркуанда (1853–1924)
• Гарвардская минимизирующая диаграмма (также известная как Гарвардская диаграмма ) (1951) Ховарда Х. Эйкена (1900–1973) и Марты Л. Уайтхаус
• Диаграмма разложения (1952) Роберта Л. Эшенхерста (1929–2009) и Теодора Сингера (1916–1991)
• График Вейча (1952 г.) Эдварда В. Вейча (1924–2013 гг.)
• Карта Карно (1953) Мориса Карно (1924–)
• Контактные кости , контактные сетки (1955), а триадная карта по Антонинам Свободе (1907-1980)
• Графический метод (1957) Вадима Николаевича Рогинского [ Вадим Николаевич Рогинский ] (1913–1983)
• Диаграмма Гендлера (также известная как круговой граф Гендлера , Händler'scher Kreisgraph , Kreisgraph nach Händler , Händler-Kreisgraph , Händler-Diagramm , Minimisierungsgraph , M ⁿ graph ) (1958) Вольфганга Хендлера (1920–1998)
• Карта Махони, также известная как М-карта или номера обозначений (1963) Мэтью В. Махони
• Метод графов (1965) Герберта Ф. Кортума  [ de ] (1907–1979)
• Уменьшенная карта Карно (RKM)
• Метод гиперкуба (1982) Стаматиоса В. Карталопулоса
• Карта Минтерм-кольца (MRM) или алгоритм Минтерм-кольца (1990) Томаса Р. МакКаллы
• V-диаграмма (2001) Джонатана Вестфала (1951–)
• Paraboomig (2003) Шриш Верма и Киран Д. Пермар
• Граф мажоритарного инвертора (MIG) (2014) Луки Амару, Пьера-Эммануэля Гайярдона и Джованни Де Микели
• Заговор Пандита (2017) Ведхаса Пандита и Бьорна В. Шуллера (1975–)
• График истинности (2020) Эйсы Альхарби

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

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

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

Методы минимизации логической функции включают:

• Метод Блейка - Порецкого
• Метод Нельсона
• Алгоритм Куайна – Маккласки
• Метод алгебраических преобразований
• Метод Петрика
• Метод Рота
• Куделька метод
• Метод Уэллса
• Бинарный метод Шейнмана
• метод минимизации функций в базисах ДА-НЕТ и ИЛИ-НЕ (базис Шеффера и Пирса)
• метод неопределенных коэффициентов
• метод гиперкуба
• метод функциональной декомпозиции

Минимизатор эвристической логики эспрессо

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

В то время как двухуровневое представление схем строго относится к уплощенному представлению схемы с точки зрения СОП ( суммы произведений ), что более применимо к реализации проекта в PLA, многоуровневое представление является более подходящим вариантом. общий вид схемы в терминах произвольно связанных SOP, POS ( произведение сумм ), факторизованной формы и т.д. Алгоритмы логической оптимизации обычно работают либо в структурном (SOP, факторизованная форма), либо в функциональном ( двоичные диаграммы решений , ADD ) представлении схемы.

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

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

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

Вышеупомянутое двухуровневое представление занимает шесть элементов продукта и 24 транзистора в CMOS Rep.

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

Р = В + С .

F ₁ = AP + AD .

F ₂ = А'П + А'Е .

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

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

Пример

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

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

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

Правильность результата можно проверить с помощью таблицы истинности .

Смотрите также

• Диаграмма двоичного решения (BDD)
• Состояние безразлично
• Главный импликант
• Сложность схемы - об оценке сложности схемы
• Состав функций
• Разложение функций
• Недогрузка ворот
• Гарвардская минимизирующая диаграмма (Викиверситет) (Викиучебники)

использованная литература

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

• Хва, "Шерман" Сюэн Рен (июнь 1974 г.). «Метод генерации простых импликантов булевого выражения» . Транзакции IEEE на компьютерах . IEEE . С-23 (6): 637–641. DOI : 10.1109 / TC.1974.224003 . eISSN  1557-9956 . ISSN  0018-9340 . S2CID  10646917 . CD- ISSN  2326-3814 . 1F09 . Проверено 12 мая 2020 ; Хва, "Шерман" Сюэн Рен (апрель 1973 г.). Метод генерации простых импликантов булевого выражения . Бассер, факультет компьютерных наук, Сиднейский университет . Технический отчет 82.
• Линд, Ларри Фредерик; Нельсон, Джон Кристофер Канлифф (1977). Анализ и проектирование последовательных цифровых систем . Macmillan Press . ISBN 0-33319266-4. [49] (146 стр.)
• Гош, Дебидас (июнь 1977 г.) [1977-01-21]. «Метод генерации простых множителей логического выражения в конъюнктивной нормальной форме с возможностью включения комбинации« Неважно » (PDF) . Журнал технологий . Отделение математики Бенгальского инженерного колледжа, Ховрах, Индия. XXII (1). Архивации (PDF) с оригинала на 2020-05-12 . Проверено 12 мая 2020 .
• Де Микели, Джованни (1994). Синтез и оптимизация цифровых схем . Макгроу-Хилл . ISBN 0-07-016333-2. (NB. Главы 7–9 охватывают комбинаторную двухуровневую, комбинаторную многоуровневую и, соответственно, последовательную оптимизацию схем.)
• Hachtel, Gary D .; Соменци, Фабио (2006) [1996]. Алгоритмы логического синтеза и проверки . Springer Science & Business Media . ISBN 978-0-387-31005-3.
• Кохави, Цви; Джа, Нирадж К. (2009). «4–6». Теория переключений и конечных автоматов (3-е изд.). Издательство Кембриджского университета . ISBN 978-0-521-85748-2.
• Кнут, Дональд Эрвин (2010). «7.1.2: Логическая оценка». Искусство программирования . 4А . Эддисон-Уэсли . С. 96–133. ISBN 978-0-201-03804-0.
• Рутенбар, Роб А. Многоуровневая минимизация, Часть I: Модели и методы (PDF) (слайды лекций). Университет Карнеги-Меллона (CMU). Лекция 7. Архивировано (PDF) из оригинала 15.01.2018 . Проверено 15 января 2018 ; Рутенбар, Роб А. Многоуровневая минимизация, Часть II: Извлечение куба / коядра (PDF) (слайды лекций). Университет Карнеги-Меллона (CMU). Лекция 8. Архивировано (PDF) из оригинала 15.01.2018 . Проверено 15 января 2018 .
• Томашевский, Себастьян П .; Челик, Ильгаз У .; Антониу, Джордж Э. (декабрь 2003 г.) [2003-03-05, 2002-04-09]. «Минимизация логических функций на основе WWW» (PDF) . Международный журнал прикладной математики и информатики . 13 (4): 577–584. Архивировано (PDF) из оригинала на 2020-05-10 . Проверено 10 мая 2020 . [50] [51] (7 страниц)
• Вильгельми, Александр; Куделька, Виктор; Деуссен, Питер; Бёлинг, Карл Хайнц ; Хендлер, Вольфганг ; Неандер, Иоахим (январь 1963 г.) [1961-10-18]. Дёрр, Йоханнес; Пешль, Эрнст Фердинанд ; Унгер, Хайнц (ред.). 2. Colloquium über Schaltkreis- und Schaltwerk-Theorie - Vortragsauszüge vom 18. bis 20. Октябрь 1961 г. в Саарбрюккене . Internationale Schriftenreihe zur Numerischen Mathematik [Международная серия вычислительной математики] (ISNM) (на немецком языке). 4 (2013-12-20 перепечатка 1-го изд.). Institut für Angewandte Mathematik, Universität Saarbrücken , Rheinisch-Westfälisches Institut für Instrumentelle Mathematik: Springer Basel AG / Birkhäuser Verlag Basel . DOI : 10.1007 / 978-3-0348-4156-6 . ISBN 978-3-0348-4081-1. Проверено 15 апреля 2020 . (152 страницы)
• Брайтон, Роберт Кинг ; Руделл, Ричард Л .; Санжиованни-Винчентелли, Альберто Луиджи ; Ван, Альберт Р. (декабрь 1987 г.). «MIS: многоуровневая система оптимизации логики» . IEEE Transactions по автоматизированному проектированию интегральных схем и систем . 6 (6): 1062–1081. DOI : 10,1109 / TCAD.1987.1270347 . (MIS) (20 страниц)
• Де Геус, Аарт Дж .; Коэн, Уильям У. (июль – август 1985 г.). «Система на основе правил для оптимизации комбинационной логики» . IEEE Design & Test of Computers . 2 (4): 22–32. DOI : 10.1109 / MDT.1985.294719 . eISSN  1558-1918 . ISSN  0740-7475 . S2CID  46651690 . Архивировано 19 февраля 2021 года . Проверено 19 февраля 20 .(11 страниц) [52] (СОКРАТ)
• Хатри, Сунил П .; Гулати, Кануприя, ред. (2011). Передовые методы логического синтеза, оптимизации и приложений (1-е изд.). Нью-Йорк / Дордрехт / Гейдельберг / Лондон: Springer Science + Business Media, LLC . ISBN 978-1-4419-7517-1. (xxii + 423 + 1 стр.)
• Джесси, Джобст Э. (февраль 1972 г.). Написано в Саннивейл, Калифорния, США. «Более эффективное использование карт Карно» . Компьютерный дизайн . Vol. 11 нет. 2. Конкорд, Массачусетс, США: Computer Design Publishing Corporation. С. 80–82. ISSN  0010-4566 . OCLC  828863003 . CODEN  CMPDA . (3 страницы)
• Ройш, Бернд (сентябрь 1975 г.). «Генерация основных импликантов из подфункций и объединяющий подход к проблеме покрытия» . Транзакции IEEE на компьютерах . IEEE . С-24 (9): 924–930. DOI : 10.1109 / TC.1975.224338 . eISSN  1557-9956 . ISSN  0018-9340 . S2CID  32090834 . CD- ISSN  2326-3814 . Проверено 19 февраля 20 . (7 страниц)
• Динли, Р.Л. (апрель 1969 г.). «В редакцию» . Письма в редакцию. Компьютерный дизайн . Vol. 8 нет. 4. Конкорд, Массачусетс, США: Computer Design Publishing Corporation. п. 16. ISSN  0010-4566 . OCLC  828863003 . CODEN  CMPDA . п. 16: […] Я хотел бы предложить метод упрощения логического выражения типа maxterm с помощью диаграммы Вейча . Насколько мне известно, я являюсь создателем этого метода, получив его в 1960 году, когда посещал курс «Основы работы с цифровыми компьютерами» в Redstone Arsenal . Большинство текстов упрощают выражение типа maxterm ( произведение сумм ), нанося отдельные термины на отдельные диаграммы Вейча, а затем накладывая диаграммы, чтобы обнаружить пересечения, или «аннулированную» функцию. […] Предлагаемый здесь метод позволяет изобразить все термины на одной диаграмме с легко различимой взаимосвязью "и". […] Каждому элементу суммы выражения присваивается символ. Этот символ наносится на Veitch для каждого из факторов or'd термина. Функция «и» возникает всякий раз, когда любой квадрат или комбинация 2 ⁿ смежных квадратов содержат все присвоенные символы. Проиллюстрирую это на простом примере. […] (A + BC) ^[1] (A + C) ^[2] = A + BC […] С уважением, Р.Л. Динли, Sperry Rand Corp.(1 страница) (NB. Упоминается в письме Шульца выше.)
• Perkowski, Marek A .; Григель, Станислав (1995-11-20). «6. Исторический обзор исследований разложения». Обзор литературы по разложению функций (PDF) . Версия IV. Группа функционального разложения, Департамент электротехники, Портлендский университет, Портленд, Орегон, США. CiteSeerX  10.1.1.64.1129 . Архивировано (PDF) из оригинала 28 марта 2021 года . Проверено 28 марта 2021 . (188 стр.)
• Станкович, Радомир С .; Сасао, Цутому; Астола, Яакко Т. (август 2001 г.). «Публикации за первые двадцать лет теории переключений и логического проектирования» (PDF) . Серии Международного центра обработки сигналов Тампере (TICSP). Технологический университет Тампере / TTKK, Монистамо, Финляндия. ISSN  1456-2774 . S2CID  62319288 . №14. Архивировано (PDF) из оригинала на 2017-08-09 . Проверено 28 марта 2021 . (4 + 60 страниц)