Минимизатор эвристической логики эспрессо - Espresso heuristic logic minimizer

В Минимизатор логики эспрессо это компьютерная программа, использующая эвристический и конкретные алгоритмы для эффективного сокращения сложность цифровых логический вентиль схемы.[1] Эспрессо был разработан в IBM к Роберт К. Брайтон.[2] Ричард Л. Руделл позже опубликовал вариант Espresso-MV в 1986 году под названием «Минимизация многозначной логики для синтеза PLA».[3] Эспрессо вдохновил на создание множества производных.

Вступление

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

Проектирование цифровых логических схем

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

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

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

  Сегменты цифрового кода A B C D E F G 0 0000 1 1 1 1 1 1 0 -A- 1 0001 0 1 1 0 0 0 0 | | 2 0010 1 1 0 1 1 0 1 F B 3 0011 1 1 1 1 0 0 1 | | 4 0100 0 1 1 0 0 1 1 -G- 5 0101 1 0 1 1 0 1 1 | | 6 0110 1 0 1 1 1 1 1 E C 7 0111 1 1 1 0 0 0 0 | | 8 1000 1 1 1 1 1 1 1 -D- 9 1001 1 1 1 1 0 1 1

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

Затем минимизированный результат может быть разделен на более мелкие части процедурой факторизации и в конечном итоге отображается на доступные базовые логические ячейки целевой технологии. Эту операцию обычно называют логическая оптимизация.[4]

Классические методы минимизации

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

Первым популярным альтернативным методом стал табличный метод, разработанный Уиллард Куайн и Эдвард МакКласки. Начиная с таблица истинности для набора логических функций, объединив минтермы для которых функции активны (крышка ON) или для которых значение функции не имеет значения ( Безразлично -крышка или DC-крышка) комплект основные импликанты состоит. Наконец, следует систематическая процедура, чтобы найти наименьший набор простых импликант, с которыми могут быть реализованы выходные функции.[6][7]

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

Алгоритм эспрессо

Другой подход к этой проблеме используется в алгоритме эспрессо, разработанном Брайтоном и др. на Калифорнийский университет в Беркли.[8][2] Вместо того, чтобы расширять логическую функцию до minterms, программа манипулирует «кубиками», итеративно представляя термины продукта в ON-, DC- и OFF- покрытиях. Хотя результат минимизации не гарантируется глобальный минимум, на практике это очень близко аппроксимируется, в то время как решение всегда свободно от избыточность. По сравнению с другими методами этот метод существенно более эффективен, сокращая использование памяти и время вычислений на несколько порядков. Его название отражает способ мгновенного приготовления чашки свежего кофе. Вряд ли есть какие-либо ограничения на количество переменных, выходных функций и членов комбинационного функционального блока. В общем, например, легко справляются с десятками переменных с десятками выходных функций.

Вход для эспрессо - это функциональная таблица желаемых функций; результатом является свернутая таблица, описывающая либо ВКЛ, либо ВЫКЛ функции, в зависимости от выбранных опций. По умолчанию термины продукта будут в максимально возможной степени использоваться несколькими функциями вывода, но программе можно дать указание обрабатывать каждую из функций вывода отдельно. Это позволяет эффективно реализовывать двухуровневые логические массивы, такие как PLA (Программируемый логический массив) или PAL (Программируемая логика массива).

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

Программного обеспечения

Эспрессо

Оригинал Эспрессо программа доступна как C исходный код из Калифорнийский университет в Беркли интернет сайт. Последним выпуском была версия 2.3 1988 года.[9] В Эспрессо-аб и Eqntott (уравнение в таблицу истинности), обновленная версия Espresso для современных POSIX систем, доступен в Debian Дистрибутив Linux (.deb), а также исходный код C. Последним выпуском была версия 9.0 от 2008 года.[10]

Логическая пятница

Логическая пятница это бесплатный Windows программа, которая предоставляет графический интерфейс для Espresso, а также для misII, другого модуля в пакете Berkeley Octtools. С помощью Logic Friday пользователи могут ввести логическую функцию в виде таблицы истинности, уравнения или диаграммы ворот, минимизировать функцию, а затем просмотреть результаты в обоих других двух представлениях. Последним выпуском была версия 1.1.4 от 2012 года.[11]

Минилог

Минилог - это бесплатная программа для Windows, которая обеспечивает минимизацию логики, используя алгоритм эспрессо. Он может создать двухуровневую реализацию логического элемента для комбинационного функционального блока с 40 входами и выходами или синхронный конечный автомат с 256 состояниями. Это часть Publicad образовательный дизайн-пакет.

Эспрессо-IISOJS

Эспрессо-IISOJS представляет собой реализацию Espresso-II на JavaScript для функций с одним выходом. В нем работают единичное распространение как дополнительный метод оптимизации для различных алгоритмов в Espresso-II, основанных на единой рекурсивной парадигме. Еще одно дополнение позволяет контролировать, когда могут возникать литералы, которые можно использовать для эффективного минимизации Клини логика функции.[12]

Рекомендации

  1. ^ Хейс, Джон Патрик (1993). Цифровой логический дизайн. Эддисон Уэсли. ISBN  0-201-15461-7.
  2. ^ а б "Роберт К. Брайтон; заслуженный профессор, профессор аспирантуры". Калифорнийский университет в Беркли. 2018-09-23. В архиве из оригинала на 2018-09-23. Получено 2018-09-23.
  3. ^ Руделл, Ричард Л. (1986-06-05). Минимизация многозначной логики для синтеза PLA (PDF). Меморандум № UCB / ERL M86-65. Беркли.
  4. ^ Де Микели, Джованни (1994). Синтез и оптимизация цифровых схем. McGraw-Hill Science Engineering. ISBN  0-07-016333-2.
  5. ^ Левин, Дуглас (1985). Проектирование логических систем. Ван Ностранд (ВЕЛИКОБРИТАНИЯ). ISBN  0-442-30606-7.
  6. ^ Кац, Рэнди Ховард; Борриелло, Гаэтано (1994). Современный логический дизайн. Издательство "Бенджамин / Каммингс". ISBN  0-8053-2703-7.
  7. ^ Лала, Параг К. (1996). Практическое проектирование и тестирование цифровой логики. Prentice Hall. ISBN  0-02-367171-8.
  8. ^ Брайтон, Роберт Кинг; Hachtel, Gary D .; Макмаллен, Кертис Трейси; Санжиованни-Винчентелли, Альберто Луиджи (1984). Алгоритмы логической минимизации для синтеза СБИС (9-е издание 2000 г., 1-е изд.). Kluwer Academic Publishers. ISBN  0-89838-164-9.
  9. ^ «Исходный код Espresso C (1988)». Калифорнийский университет в Беркли. 2018-09-21. В архиве из оригинала от 21.09.2018. Получено 2018-09-21.
  10. ^ "Исходный код и программа Espresso-eb / eqntott C (2008 г.)". Код Google. 2018-09-21. В архиве из оригинала от 21.09.2018. Получено 2018-09-21.
  11. ^ «Программа« Логическая пятница »(2012)». Sontrak. 2018-09-21. Архивировано из оригинал в 2013-10-22. Получено 2018-09-21.
  12. ^ «Эспрессо-ИИСОЙС».

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

  • Руделл, Ричард Л. (апрель 1989 г.). Логический синтез для проектирования СБИС (Кандидатская диссертация). Лаборатория исследований электроники, Инженерный колледж, Калифорнийский университет, Беркли, США. (Эспрессо-ТОЧНЫЙ)
  • Эшерманн, Бернхард (май 1993 г.). Funktionaler Entwurf digitaler Schaltungen - Methoden und CAD-Techniken [Функциональное проектирование цифровых схем - Методы и методы САПР]. Springer-Lehrbuch (на немецком языке). Springer-Verlag. С. 136–137, 140–141. ISBN  9-783540-56788-2. ISBN  3-540-56788-7.