Войти
Минимизатор логики эспрессо - это компьютерная программа, использующая эвристический и специальные алгоритмы для эффективного уменьшения сложности цифровые логические схемы. Эспрессо был разработан в IBM Робертом К. Брайтоном. Ричард Л. Руделл позже опубликовал вариант Espresso-MV в 1986 году под названием «Минимизация многозначной логики для синтеза PLA». Эспрессо вдохновил на создание множества производных.
Электронные устройства состоят из множества блоков цифровых схем, комбинация которых выполняет требуемую задачу. Эффективная реализация логических функций в виде схем логических вентилей (таких, что используется не больше логических вентилей, чем необходимо), необходима для минимизации производственных затрат и / или максимизации производительность устройства.
Все цифровые системы состоят из двух элементарных функций: элементов памяти для хранения информации и комбинационных схем, которые преобразуют это Информация. Конечные автоматы, как и счетчики, представляют собой комбинацию элементов памяти и схем комбинационной логики. Поскольку элементы памяти представляют собой стандартные логические схемы, они выбираются из ограниченного набора альтернативных схем; поэтому проектирование цифровых функций сводится к разработке схем комбинационных вентилей и их соединению.
В целом создание логических схем из абстракции высокого уровня называется логическим синтезом, который может выполняться вручную, но обычно применяется какой-либо формальный метод с помощью компьютера. В этой статье кратко излагаются методы проектирования комбинационных логических схем.
Отправной точкой для проектирования цифровой логической схемы является ее желаемая функциональность, полученная в результате анализа системы в целом, частью которой должна стать логическая схема. Описание может быть сформулировано в некоторой алгоритмической форме или с помощью логических уравнений, но также может быть кратко изложено в виде таблицы. В приведенном ниже примере показана часть такой таблицы для драйвера 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
Процесс реализации начинается с этапа минимизации логики, который будет описан ниже, чтобы упростить таблицу функций за счет объединение отдельных терминов в более крупные, содержащие меньшее количество переменных.
Затем минимизированный результат может быть разделен на более мелкие части с помощью процедуры факторизации и в конечном итоге отображается на доступные базовые логические ячейки целевой технологии. Эту операцию обычно называют логической оптимизацией.
Минимизация булевых функций вручную с использованием классических карт Карно является трудоемким, утомительный и подверженный ошибкам процесс. Он не подходит для более чем шести входных переменных и практичен только для четырех переменных, в то время как совместное использование терминов продукта для нескольких выходных функций еще сложнее. Более того, этот метод не поддается автоматизации в виде компьютерной программы. Однако, поскольку современные логические функции обычно не ограничиваются таким небольшим количеством переменных, а стоимость, а также риск совершения ошибок недопустимы для ручного выполнения логических функций, использование компьютеров стало незаменимым.
Первым популярным альтернативным методом стал табличный метод, разработанный Уиллардом Куайном и Эдвардом МакКласки. Начиная с таблицы истинности для набора логических функций, комбинируя minterms, для которых функции активны (ON-cover) или для которых значение функции не имеет значения ( Don't-Care -cover или DC-cover) состоит набор простых импликант. Наконец, следует систематическая процедура, чтобы найти наименьший набор простых импликант, с которыми могут быть реализованы выходные функции.
Хотя этот алгоритм Куайна – Маккласки очень хорошо подходит для реализации в компьютерная программа, результат все еще далек от эффективного с точки зрения времени обработки и использования памяти. Добавление переменной к функции примерно удвоит их обе, потому что длина таблицы истинности увеличивается экспоненциально с увеличением количества переменных. Аналогичная проблема возникает при увеличении количества выходных функций комбинационного функционального блока. В результате метод Куайна – Маккласки применим только для функций с ограниченным числом входных переменных и выходных функций.
Другой подход к этой проблеме используется в алгоритме эспрессо, разработанном Брайтоном и др. в Калифорнийском университете, Беркли. Вместо того, чтобы расширять логическую функцию до minterms, программа манипулирует «кубиками», итеративно представляя термины продукта в ON-, DC- и OFF- покрытиях. Хотя не гарантируется, что результат минимизации будет глобальным минимумом, на практике это очень близко аппроксимируется, в то время как решение всегда свободно от избыточности. По сравнению с другими методами этот метод существенно более эффективен, сокращая использование памяти и время вычислений на несколько порядков. Его название отражает способ мгновенного приготовления чашки свежего кофе. Вряд ли есть какие-либо ограничения на количество переменных, выходных функций и членов комбинационного функционального блока. В общем, например, легко справляются с десятками переменных с десятками выходных функций.
Вход для эспрессо - это функциональная таблица с желаемой функциональностью; результатом является свернутая таблица, описывающая либо ВКЛ, либо ВЫКЛ функции, в зависимости от выбранных опций. По умолчанию, термины продукта будут использоваться в максимально возможной степени для нескольких функций вывода, но программе можно дать указание обрабатывать каждую из функций вывода отдельно. Это позволяет эффективно реализовывать двухуровневые логические массивы, такие как PLA (программируемый логический массив) или PAL (программируемая логическая матрица).
Алгоритм Espresso оказался настолько успешным, что был включен в качестве стандартного шага минимизации логической функции практически в любой современный инструмент логического синтеза. Для реализации функции в многоуровневой логике результат минимизации оптимизируется путем факторизации и отображается на доступные базовые логические ячейки в целевой технологии, независимо от того, касается ли это программируемой пользователем вентильной матрицы (FPGA) или специализированная интегральная схема (ASIC).
Исходная программа Espresso доступна в виде исходного кода C на веб-сайте Калифорнийского университета в Беркли. Последним выпуском была версия 2.3 от 1988 года. Программа Espresso-ab and eqntott (уравнение в таблицу истинности), обновленная версия Espresso для современных систем POSIX, доступна в Debian Формат файла (.deb) дистрибутива Linux, а также исходный код C. Последним выпуском была версия 9.0 от 2008 года.
Logic Friday - это бесплатная программа для Windows, которая предоставляет графический интерфейс для Espresso, а также для misII, еще один модуль в пакете Berkeley Octtools. С помощью Logic Friday пользователи могут ввести логическую функцию в виде таблицы истинности, уравнения или диаграммы ворот, минимизировать функцию, а затем просмотреть результаты в обоих других двух представлениях. Последним выпуском была версия 1.1.4 от 2012 года.
Minilog - это бесплатная программа для Windows, которая обеспечивает минимизацию логики с использованием этого алгоритма Espresso. Он может генерировать двухуровневую реализацию логического элемента для комбинационного функционального блока с 40 входами и выходами или синхронный конечный автомат с 256 состояниями. Это часть пакета образовательного дизайна Publicad.
Espresso-IISOJS - это JavaScript-реализация Espresso-II для функций с одним выходом. Он использует единичное распространение как дополнительный метод оптимизации для различных алгоритмов в Espresso-II, основанных на единой рекурсивной парадигме. Еще одно дополнение позволяет контролировать, когда могут возникать литералы, что может быть использовано для эффективного минимизации функций логики Клини.
