Логический минимизатор ESPRESSO — это компьютерная программа, использующая эвристические и специальные алгоритмы для эффективного снижения сложности схем цифровых логических элементов . [1] ESPRESSO-I был первоначально разработан в IBM Робертом К. Брайтоном и др. в 1982 году. [2] [3] и улучшенный как ESPRESSO-II в 1984 году. [4] [5] Ричард Л. Руделл позже опубликовал вариант ESPRESSO-MV в 1986 году [6] и ESPRESSO-EXACT в 1987 году. [7] [8] [5] Эспрессо вдохновил на создание множества производных.
Электронные устройства состоят из многочисленных блоков цифровых схем, совокупность которых выполняет требуемую задачу. Эффективная реализация логических функций в виде схем логических вентилей (таких, чтобы логических вентилей не использовалось больше, чем необходимо) необходима для минимизации производственных затрат и/или максимизации производительности устройства.
Все цифровые системы состоят из двух элементарных функций: элементов памяти для хранения информации и комбинационных схем , преобразующих эту информацию. Конечные автоматы , как и счетчики, представляют собой комбинацию элементов памяти и комбинационных логических схем. Поскольку элементы памяти представляют собой стандартные логические схемы, они выбираются из ограниченного набора альтернативных схем; поэтому проектирование цифровых функций сводится к разработке схем комбинационных вентилей и их соединению между собой.
В общем, создание логических схем из абстракции высокого уровня называется логическим синтезом , который может быть выполнен вручную, но обычно применяется какой-либо формальный метод с помощью компьютера. В этой статье кратко изложены методы проектирования комбинационных логических схем.
Отправной точкой проектирования цифровой логической схемы является ее желаемая функциональность, полученная на основе анализа системы в целом, частью которой должна стать логическая схема. Описание может быть сформулировано в той или иной алгоритмической форме или с помощью логических уравнений, а также может быть сведено в виде таблицы. В приведенном ниже примере показана часть такой таблицы для драйвера 7-сегментного дисплея , который преобразует двоичный код значений десятичных цифр в сигналы, которые вызывают загорание соответствующих сегментов дисплея.
Сегменты цифрового кода ABCDEFG 0 0000 1 1 1 1 1 1 0 -А- 1 0001 0 1 1 0 0 0 0 | | 2 0010 1 1 0 1 1 0 1 ФБ 3 0011 1 1 1 1 0 0 1 | | 4 0100 0 1 1 0 0 1 1 -Г- 5 0101 1 0 1 1 0 1 1 | | 6 0110 1 0 1 1 1 1 1 ЕС 7 0111 1 1 1 0 0 0 0 | | 8 1000 1 1 1 1 1 1 1 -Д- 9 1001 1 1 1 1 0 1 1
Процесс реализации начинается с этапа логической минимизации , который будет описан ниже, чтобы упростить таблицу функций путем объединения отдельных членов в более крупные, содержащие меньше переменных.
Затем минимизированный результат можно разделить на более мелкие части с помощью процедуры факторизации и в конечном итоге сопоставить с доступными базовыми логическими ячейками целевой технологии. Эту операцию обычно называют логической оптимизацией . [9]
Минимизация логических функций вручную с использованием классических карт Карно — трудоемкий, утомительный и подверженный ошибкам процесс. Он не подходит для более чем шести входных переменных и практичен только для четырех переменных, в то время как совместное использование терминов продукта для нескольких выходных функций еще сложнее реализовать. [10] Более того, этот метод не поддается автоматизации в виде компьютерной программы. Однако, поскольку современные логические функции, как правило, не ограничиваются таким небольшим количеством переменных, а стоимость, а также риск совершения ошибок непомерно высоки для ручной реализации логических функций, использование компьютеров стало необходимым.
Первым альтернативным методом, ставшим популярным, стал табличный метод, разработанный Уиллардом Куайном и Эдвардом Маккласки . Начиная с таблицы истинности для набора логических функций путем объединения минтермов , для которых функции активны (покрытие ON) или для которых значение функции не имеет значения ( покрытие Don't-Care или DC-покрытие). составляется набор основных импликант . Наконец, применяется систематическая процедура для поиска наименьшего набора простых импликант, с помощью которых могут быть реализованы выходные функции. [11] [12]
Хотя этот алгоритм Куайна-Маккласки очень хорошо подходит для реализации в компьютерной программе, результат все еще далек от эффективности с точки зрения времени обработки и использования памяти. Добавление переменной в функцию примерно удвоит их обоих, поскольку длина таблицы истинности увеличивается экспоненциально с увеличением количества переменных. Аналогичная проблема возникает при увеличении количества выходных функций комбинационного функционального блока. В результате метод Куайна – МакКласки практичен только для функций с ограниченным количеством входных переменных и выходных функций.
Другой подход к этой проблеме используется в алгоритме ESPRESSO, разработанном Брайтоном и др. в Калифорнийском университете в Беркли . [4] [3] Это эффективный с точки зрения ресурсов и производительности алгоритм, направленный на решение эвристической безопасной двухуровневой логической задачи минимизации. [13]
Вместо того, чтобы расширять логическую функцию в минтермы, программа манипулирует «кубами», итеративно представляя термины продукта в покрытиях ON, DC и OFF. Хотя результат минимизации не гарантированно будет глобальным минимумом , на практике он очень близко аппроксимируется, при этом решение всегда свободно от избыточности . По сравнению с другими методами этот существенно более эффективен, сокращая использование памяти и время вычислений на несколько порядков. Его название отражает способ мгновенного приготовления чашки свежего кофе. Практически нет ограничений на количество переменных, выходных функций и продуктов комбинационного функционального блока. В общем, легко иметь дело, например, с десятками переменных и десятками выходных функций.
Входными данными для ЭСПРЕССО является таблица функций желаемой функциональности; В результате получается свернутая таблица, описывающая либо ВКЛ-, либо ВЫКЛ-покрытие функции, в зависимости от выбранных опций. По умолчанию условия продукта будут в максимально возможной степени совместно использоваться несколькими функциями вывода, но программе можно поручить обрабатывать каждую из функций вывода отдельно. Это позволяет эффективно реализовать двухуровневые логические массивы, такие как PLA (программируемая логическая матрица) или PAL (программируемая логическая матрица).
Алгоритм ESPRESSO оказался настолько успешным, что он был включен в качестве стандартного этапа минимизации логических функций практически в любой современный инструмент логического синтеза . Для реализации функции в многоуровневой логике результат минимизации оптимизируется путем факторизации и отображается на доступные базовые логические ячейки в целевой технологии, независимо от того, касается ли это программируемой вентильной матрицы (FPGA) или интегральной схемы для конкретного приложения ( АСИК).
Исходная программа ESPRESSO доступна в виде исходного кода C на веб-сайте Калифорнийского университета в Беркли . Последним выпуском была версия 2.3, датированная 1988 годом. [14] Программа ESPRESSO-AB и EQNTOTT (уравнение таблицы истинности), обновленная версия ESPRESSO для современных систем POSIX , также доступна в формате файлов дистрибутива Debian Linux (.deb). исходный код C. Последним выпуском была версия 9.0, датированная 2008 годом. [15] Версия, совместимая с Windows и C++20, была портирована на GitHub в 2020 году. [16]
Logic Friday — бесплатная программа для Windows , предоставляющая графический интерфейс для Espresso, а также для misII, другого модуля в пакете Berkeley Octtools. С помощью Logic Friday пользователи могут ввести логическую функцию в виде таблицы истинности, уравнения или вентильной диаграммы, минимизировать функцию, а затем просмотреть результаты в обоих других двух представлениях. Последним выпуском была версия 1.1.4 от 2012 года. [17]
Minilog — это бесплатная программа для Windows, которая обеспечивает логическую минимизацию, используя этот алгоритм Espresso. Он способен генерировать реализацию двухуровневого вентиля для комбинационного функционального блока с количеством входов и выходов до 40 или синхронного автомата с числом состояний до 256. Это часть пакета образовательного дизайна Publicad .
ESPRESSO-IISOJS — это реализация ESPRESSO-II на JavaScript для функций с одним выходом. Он использует распространение единиц в качестве дополнительного метода оптимизации для различных алгоритмов ESPRESSO-II, основанных на единой рекурсивной парадигме. Еще одним дополнением является возможность контролировать, когда можно создавать литералы, что можно использовать для эффективной минимизации логических функций Клини . [18]