Минимизатор эвристической логики эспрессо
— Логический минимизатор ESPRESSO это компьютерная программа, использующая эвристические и специальные алгоритмы для эффективного снижения сложности схем цифровых логических элементов . [1] ESPRESSO-I был первоначально разработан в IBM Робертом К. Брайтоном и др. в 1982 году. [2] [3] и улучшен как ESPRESSO-II в 1984 году. [4] [5] Ричард Л. Руделл позже опубликовал вариант ESPRESSO-MV в 1986 году. [6] и ESPRESSO-EXACT в 1987 году. [7] [8] [5] Эспрессо вдохновил на создание множества производных.
Введение [ править ]
Электронные устройства состоят из многочисленных блоков цифровых схем, совокупность которых выполняет требуемую задачу. Эффективная реализация логических функций в виде схем логических вентилей (таких, чтобы логических вентилей не использовалось больше, чем необходимо) необходима для минимизации производственных затрат и/или максимизации производительности устройства.
Проектирование цифровых логических схем [ править ]
Все цифровые системы состоят из двух элементарных функций: элементов памяти для хранения информации и комбинационных схем , преобразующих эту информацию. Конечные автоматы , как и счетчики, представляют собой комбинацию элементов памяти и комбинационных логических схем. Поскольку элементы памяти представляют собой стандартные логические схемы, они выбираются из ограниченного набора альтернативных схем; поэтому проектирование цифровых функций сводится к разработке схем комбинационных вентилей и их соединению между собой.
В общем, создание логических схем из абстракции высокого уровня называется логическим синтезом , который может быть выполнен вручную, но обычно применяется какой-либо формальный метод с помощью компьютера. В этой статье кратко изложены методы проектирования комбинационных логических схем.
Отправной точкой проектирования цифровой логической схемы является ее желаемая функциональность, полученная в результате анализа системы в целом, частью которой должна стать логическая схема. Описание может быть сформулировано в той или иной алгоритмической форме или с помощью логических уравнений, а также может быть сведено в виде таблицы. В приведенном ниже примере показана часть такой таблицы для драйвера 7-сегментного дисплея , который преобразует двоичный код значений десятичных цифр в сигналы, которые вызывают загорание соответствующих сегментов дисплея.
Digit Code Segments
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
Процесс реализации начинается с этапа логической минимизации , который будет описан ниже, чтобы упростить таблицу функций путем объединения отдельных членов в более крупные, содержащие меньше переменных.
Затем минимизированный результат можно разделить на более мелкие части с помощью процедуры факторизации и в конечном итоге сопоставить с доступными базовыми логическими ячейками целевой технологии. Эту операцию обычно называют логической оптимизацией . [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 .
ЭСПРЕССО-IISOJS [ править ]
ESPRESSO-IISOJS — это реализация ESPRESSO-II на JavaScript для функций с одним выходом. Он использует распространение единиц в качестве дополнительного метода оптимизации для различных алгоритмов ESPRESSO-II, основанных на единой рекурсивной парадигме. Еще одним дополнением является возможность контролировать, когда можно создавать литералы, что можно использовать для эффективной минимизации логических функций Клини . [18]
Ссылки [ править ]
- ^ Хейс, Джон Патрик (1993). Проектирование цифровой логики . Эддисон Уэсли . ISBN 0-201-15461-7 .
- ^ Брайтон, Роберт Кинг; Хачтел, Гэри Д.; Хемачандра, Лейн А.; Ньютон, А. Ричард; Санджованни-Винсентелли, Альберто Луиджи М. (1982). «Сравнение стратегий минимизации логики с использованием ESPRESSO: программного пакета APL для моделирования разделенной логики». Труды Международного симпозиума IEEE по схемам и системам, 1982 г. Нью-Йорк, Нью-Йорк, США: IEEE : 42–48.
- ↑ Перейти обратно: Перейти обратно: а б «Роберт К. Брайтон; почетный профессор, профессор аспирантуры» . Калифорнийский университет в Беркли . 23 сентября 2018 г. Архивировано из оригинала 23 сентября 2018 г. Проверено 23 сентября 2018 г.
- ↑ Перейти обратно: Перейти обратно: а б Брайтон, Роберт Кинг; Хачтел, Гэри Д.; Макмаллен, Кертис Трейси ; Санджованни-Винсентелли, Альберто Луиджи М. (1984). Алгоритмы логической минимизации для синтеза СБИС (9-е издание 2000 г., 1-е изд.). Бостон, Массачусетс, США: Kluwer Academic Publishers . ISBN 0-89838-164-9 .
- ↑ Перейти обратно: Перейти обратно: а б Болтон, Мартин (1990). «4.3.3 ЭСПРЕССО-II». Написано в Бристольском университете, Бристоль, Великобритания. В Даглессе Эрик Л. (ред.). Проектирование цифровых систем с программируемой логикой . Серия электронных системотехники (1-е изд.). Уокингем, Великобритания: Addison-Wesley Publishers Ltd., стр. 112, 115–116. ISBN 0-201-14545-6 . LCCN 90000007 . ISBN 978-0-201-14545-8 арк:/13960/t2f83p38r . Проверено 17 апреля 2021 г.
- ^ Руделл, Ричард Л. (5 июня 1986 г.). «Минимизация многозначной логики для синтеза PLA» (PDF) . Меморандум № UCB/ERL M86-65 . Беркли, США.
- ^ Руделл, Ричард Л.; Санджованни-Винсентелли, Альберто Луиджи М. (сентябрь 1987 г.). «Минимизация многозначной логики для оптимизации PLA». Транзакции IEEE в области автоматизированного проектирования . 6 (5): 727–750. дои : 10.1109/TCAD.1987.1270318 . S2CID 13525177 .
- ^ Руделл, Ричард Л. (апрель 1989 г.). Логический синтез для проектирования СБИС (кандидатская диссертация). Беркли: Калифорнийский университет . (ЭСПРЕССО-ТОЧНО)
- ^ Де Микели, Джованни (1994). Синтез и оптимизация цифровых схем . МакГроу-Хилл, Научная инженерия . ISBN 0-07-016333-2 .
- ^ Левин, Дуглас (1985). Проектирование логических систем . Ван Ностранд (Великобритания). ISBN 0-442-30606-7 .
- ^ Кац, Рэнди Ховард ; Борриелло, Гаэтано (1994). Современный логический дизайн . Издательская компания Бенджамина/Каммингса . ISBN 0-8053-2703-7 .
- ^ Лала, Параг К. (1996). Практическое проектирование и тестирование цифровой логики . Прентис Холл . ISBN 0-02-367171-8 .
- ^ Теобальд, Майкл; Новик, Стивен М. (1998). Быстрые эвристические и точные алгоритмы для двухуровневой безопасной логической минимизации . Колумбийский университет (отчет). дои : 10.7916/D8N58V58 . Проверено 4 октября 2021 г.
- ^ «Исходный код Espresso C (1988)» . Калифорнийский университет в Беркли . 21 сентября 2018 г. Архивировано из оригинала 21 сентября 2018 г. Проверено 21 сентября 2018 г.
- ^ «Исходный код и программа Espresso-eb/eqntott C (2008)» . Гугл-код . 21 сентября 2018 г. Архивировано из оригинала 21 сентября 2018 г. Проверено 21 сентября 2018 г.
- ^ «Минимизатор эвристической логики эспрессо C++20, исходный код для Windows» . Гитхаб .
- ^ «Программа «Логическая пятница (2012)» . сонрак . 21 сентября 2018 г. Архивировано из оригинала 22 октября 2013 г. Проверено 21 сентября 2018 г.
- ^ «Эспрессо-IISOJS» . Гитхаб .
Дальнейшее чтение [ править ]
- Эшерманн, Бернхард (май 1993 г.). схем. Методы и Функциональное проектирование цифровых технологии САПР. Учебник Springer (на немецком языке). Издательство Спрингер . стр. 136–137, 140–141. ISBN 9-783540-56788-2 . ISBN 3-540-56788-7 .