Minimizador lógico heurístico Espresso - Espresso heuristic logic minimizer
O minimizador lógico ESPRESSO é um programa de computador que usa algoritmos heurísticos e específicos para reduzir com eficiência a complexidade dos circuitos de portas lógicas digitais . O ESPRESSO-I foi originalmente desenvolvido na IBM por Robert K. Brayton et. al. em 1982. e melhorado como ESPRESSO-II em 1984. Richard L. Rudell publicou mais tarde a variante ESPRESSO-MV em 1986 e ESPRESSO-EXACT em 1987. O Espresso inspirou muitos derivados.
Introdução
Os dispositivos eletrônicos são compostos por vários blocos de circuitos digitais, cuja combinação executa a tarefa necessária. A implementação eficiente de funções lógicas na forma de circuitos de porta lógica (de modo que não sejam usadas mais portas lógicas do que o necessário) é necessária para minimizar os custos de produção e / ou maximizar o desempenho de um dispositivo.
Projetando circuitos lógicos digitais
Todos os sistemas digitais são compostos por duas funções elementares: elementos de memória para armazenar informações e circuitos combinacionais que transformam essas informações. As máquinas de estado , como os contadores, são uma combinação de elementos de memória e circuitos lógicos combinacionais. Como os elementos de memória são circuitos lógicos padrão, eles são selecionados de um conjunto limitado de circuitos alternativos; portanto, o projeto de funções digitais se resume a projetar os circuitos de portas combinacionais e interconectá-los.
Em geral, a instanciação de circuitos lógicos de abstração de alto nível é referida como síntese lógica , que pode ser realizada manualmente, mas geralmente algum método formal por computador é aplicado. Neste artigo, os métodos de projeto para circuitos lógicos combinacionais são resumidos brevemente.
O ponto de partida para o projeto de um circuito lógico digital é a sua funcionalidade desejada, tendo derivado da análise do sistema como um todo, o circuito lógico deve fazer parte. A descrição pode ser declarada em alguma forma algorítmica ou por equações lógicas, mas também pode ser resumida na forma de uma tabela. O exemplo abaixo mostra uma parte de tal tabela para um driver de display de 7 segmentos que traduz o código binário para os valores de um dígito decimal em sinais que fazem com que os respectivos segmentos do display se iluminem.
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
O processo de implementação começa com uma fase de minimização lógica , a ser descrita a seguir, a fim de simplificar a tabela de funções combinando os termos separados em termos maiores contendo menos variáveis.
Em seguida, o resultado minimizado pode ser dividido em partes menores por um procedimento de fatoração e, eventualmente, mapeado nas células lógicas básicas disponíveis da tecnologia alvo. Essa operação é comumente conhecida como otimização lógica .
Métodos clássicos de minimização
Minimizar funções booleanas manualmente usando os mapas clássicos de Karnaugh é um processo trabalhoso, tedioso e sujeito a erros. Não é adequado para mais de seis variáveis de entrada e prático apenas para até quatro variáveis, enquanto o compartilhamento de termos de produto para várias funções de saída é ainda mais difícil de realizar. Além disso, esse método não se presta a ser automatizado na forma de um programa de computador. No entanto, como as funções lógicas modernas geralmente não são restritas a um número tão pequeno de variáveis, embora o custo e o risco de erros sejam proibitivos para a implementação manual de funções lógicas, o uso de computadores tornou-se indispensável.
O primeiro método alternativo a se tornar popular foi o método tabular desenvolvido por Willard Quine e Edward McCluskey . Começando com a tabela de verdade para um conjunto de funções lógicas, combinando os mintermos para os quais as funções estão ativas (a capa ON) ou para os quais o valor da função é irrelevante (a capa Don't-Care ou DC-cover) um conjunto de implicantes primários é composto. Finalmente, um procedimento sistemático é seguido para encontrar o menor conjunto de implicantes primos com os quais as funções de saída podem ser realizadas.
Embora este algoritmo Quine-McCluskey seja muito adequado para ser implementado em um programa de computador, o resultado ainda está longe de ser eficiente em termos de tempo de processamento e uso de memória. Adicionar uma variável à função dobrará aproximadamente os dois, porque o comprimento da tabela verdade aumenta exponencialmente com o número de variáveis. Um problema semelhante ocorre ao aumentar o número de funções de saída de um bloco de função combinacional. Como resultado, o método Quine – McCluskey é prático apenas para funções com um número limitado de variáveis de entrada e funções de saída.
Algoritmo ESPRESSO
Uma abordagem diferente para este problema é seguida no algoritmo ESPRESSO, desenvolvido por Brayton et al. na Universidade da Califórnia, Berkeley . É um algoritmo eficiente em termos de recursos e desempenho que visa resolver o problema de minimização de lógica de dois níveis sem risco heurístico .
Em vez de expandir uma função lógica em mintermos, o programa manipula "cubos", representando os termos do produto nas coberturas ON-, DC- e OFF- iterativamente. Embora o resultado da minimização não seja garantido como sendo o mínimo global , na prática isso é muito próximo, enquanto a solução está sempre livre de redundância . Comparado com os outros métodos, este é essencialmente mais eficiente, reduzindo o uso de memória e o tempo de computação em várias ordens de magnitude. Seu nome reflete a maneira de fazer instantaneamente uma xícara de café fresco. Quase não há restrição ao número de variáveis, funções de saída e termos de produto de um bloco de função combinacional. Em geral, por exemplo, dezenas de variáveis com dezenas de funções de saída são prontamente tratadas.
A entrada para ESPRESSO é uma tabela de funções da funcionalidade desejada; o resultado é uma tabela minimizada, descrevendo a capa ON ou a capa OFF da função, dependendo das opções selecionadas. Por padrão, os termos do produto serão compartilhados tanto quanto possível pelas várias funções de saída, mas o programa pode ser instruído a lidar com cada uma das funções de saída separadamente. Isso permite uma implementação eficiente em matrizes lógicas de dois níveis, como PLA (Matriz Lógica Programável) ou PAL (Lógica de Matriz Programável).
O algoritmo ESPRESSO provou ser tão bem-sucedido que foi incorporado como uma etapa de minimização de função lógica padrão em virtualmente qualquer ferramenta de síntese lógica contemporânea . Para implementar uma função na lógica de vários níveis, o resultado da minimização é otimizado pela fatoração e mapeado nas células lógicas básicas disponíveis na tecnologia alvo, quer se trate de uma matriz de portas programáveis em campo (FPGA) ou de um circuito integrado específico de aplicação ( ASIC).
Programas
ESPRESSO
O programa ESPRESSO original está disponível como código-fonte C no site da Universidade da Califórnia, Berkeley . O último lançamento foi a versão 2.3 de 1988. O programa ESPRESSO-AB e EQNTOTT (equação para tabela verdade), uma versão atualizada do ESPRESSO para sistemas POSIX modernos, está disponível no formato de arquivo da distribuição Debian Linux (.deb), bem como no código-fonte C código. A última versão foi a versão 9.0 datada de 2008.
Sexta-feira lógica
O Logic Friday é um programa gratuito do Windows que fornece uma interface gráfica para o Espresso, bem como para o misII, outro módulo do pacote Berkeley Octtools. Com o Logic Friday, os usuários podem inserir uma função lógica como uma tabela verdade, equação ou diagrama de porta, minimizar a função e, em seguida, visualizar os resultados em ambas as outras duas representações. A última versão foi a versão 1.1.4 de 2012.
Minilog
Minilog é um programa gratuito do Windows que fornece minimização lógica, explorando este algoritmo Espresso. Ele é capaz de gerar uma implementação de porta de dois níveis para um bloco de função combinacional com até 40 entradas e saídas ou uma máquina de estado síncrono com até 256 estados. Faz parte do pacote de design educacional Publicad .
ESPRESSO-IISOJS
ESPRESSO-IISOJS é uma implementação JavaScript do ESPRESSO-II para funções de saída única. Ele emprega a propagação de unidades como uma técnica de otimização adicional para os vários algoritmos no ESPRESSO-II que são baseados no paradigma recursivo único. Outra adição é permitir o controle sobre quando os literais podem ser aumentados, o que pode ser explorado para minimizar efetivamente as funções lógicas de Kleene .
Referências
Leitura adicional
- Eschermann, Bernhard (maio de 1993). Funktionaler Entwurf digitaler Schaltungen - Methoden und CAD-Techniken [ Projeto funcional de circuitos digitais - Métodos e técnicas CAD ]. Springer-Lehrbuch (em alemão). Springer-Verlag . pp. 136–137, 140–141. ISBN 9-783540-56788-2. ISBN 3-540-56788-7 .