Otimização lógica - Logic optimization

A otimização lógica é um processo de encontrar uma representação equivalente do circuito lógico especificado sob uma ou mais restrições especificadas. Este processo faz parte de uma síntese lógica aplicada à eletrônica digital e ao projeto de circuitos integrados .

Geralmente, o circuito é restrito a uma área mínima do chip atendendo a um atraso de resposta predefinido. O objetivo da otimização lógica de um determinado circuito é obter o menor circuito lógico que avalie os mesmos valores do original. O circuito menor com a mesma função é mais barato, ocupa menos espaço, consome menos energia , tem latência mais curta e minimiza os riscos de cross-talk inesperado , risco de processamento de sinal atrasado e outros problemas presentes no nível de nanoescala de estruturas metálicas em um circuito integrado .

Em termos de álgebra booleana , a otimização de uma expressão booleana complexa é o processo de encontrar uma expressão mais simples, que, ao ser avaliada, acabaria por produzir os mesmos resultados que a original.

Motivação

O problema de ter um circuito complicado (ou seja, um com muitos elementos, como portas lógicas ) é que cada elemento ocupa espaço físico em sua implementação e custa tempo e dinheiro para ser produzido por si mesmo. A minimização de circuitos pode ser uma forma de otimização lógica usada para reduzir a área de lógica complexa em circuitos integrados .

Com o advento da síntese lógica , um dos maiores desafios enfrentados pela indústria de automação de projeto eletrônico (EDA) foi encontrar a representação de circuito mais simples da descrição de projeto dada. Embora a otimização lógica de dois níveis já existisse há muito tempo na forma do algoritmo Quine-McCluskey , mais tarde seguida pelo minimizador lógico heurístico Espresso , as densidades de chip em rápida melhoria e a ampla adoção de linguagens de descrição de hardware para descrição de circuitos formalizaram a otimização lógica domínio como existe hoje.

Métodos

Os métodos de simplificação de circuitos lógicos são igualmente aplicáveis ​​à minimização de expressões booleanas .

Classificação

Hoje, a otimização lógica é dividida em várias categorias:

Com base na representação do circuito

Otimização de lógica de dois níveis

Otimização lógica multinível

Com base nas características do circuito

Otimização de lógica sequencial

Otimização de lógica combinatória

Com base no tipo de execução

Métodos de otimização gráfica

Métodos de otimização tabular

Métodos de otimização algébrica

Métodos gráficos

Os métodos de minimização gráfica para lógica de dois níveis incluem:

• Diagrama de Euler (também conhecido como círculo Euleriano ) (1768) por Leonhard P. Euler (1707-1783)
• Diagrama de Venn (1880) por John Venn (1834–1923)
• Diagrama de Marquand (1881) por Allan Marquand (1853–1924)
• Harvard minimizing chart (aka Harvard chart ) (1951) por Howard H. Aiken (1900–1973) e Martha L. Whitehouse
• Gráfico de decomposição (1952) de Robert L. Ashenhurst (1929–2009) e Theodore Singer (1916–1991)
• Veitch chart (1952) por Edward W. Veitch (1924–2013)
• Mapa de Karnaugh (1953) por Maurice Karnaugh (1924–)
• Ossos de contato , grades de contato (1955) e o mapa triádico de Antonín Svoboda (1907–1980)
• Método gráfico (1957) por Vadim Nikolaevich Roginskij [ Вадим Николаевич Рогинский ] (1913-1983)
• Diagrama de Händler (também conhecido como gráfico de círculo de Händler , Händler'scher Kreisgraph , Kreisgraph nach Händler , Händler-Kreisgraph , Händler-Diagramm , Minimisierungsgraph , gráfico M ⁿ ) (1958) por Wolfgang Händler (1920–1998)
• Mapa Mahoney, também conhecido como M-map ou números de designação (1963) de Matthew V. Mahoney
• Método de gráfico (1965) por Herbert F. Kortum  [ de ] (1907-1979)
• Mapa reduzido de Karnaugh (RKM)
• Método Hypercube (1982) por Stamatios V. Kartalopoulos
• Mapa do anel Minterm (MRM) ou algoritmo do anel Minterm (1990) por Thomas R. McCalla
• Diagrama V (2001) por Jonathan Westphal (1951–)
• Paraboomig (2003) de Shrish Verma e Kiran D. Permar
• Gráfico do inversor de maioria (MIG) (2014) de Luca Amarú, Pierre-Emmanuel Gaillardon e Giovanni De Micheli
• Enredo de Pandit (2017) por Vedhas Pandit e Björn W. Schuller (1975–)
• Gráfico da verdade (2020) por Eisa Alharbi

Minimização de expressão booleana

Os mesmos métodos de minimização (simplificação) de expressão booleana listados abaixo podem ser aplicados à otimização do circuito.

Para o caso em que a função booleana é especificada por um circuito (ou seja, queremos encontrar um circuito equivalente de tamanho mínimo possível), o problema de minimização de circuito ilimitado foi há muito conjecturado como completo , um resultado finalmente comprovado em 2008, mas existem heurísticas eficazes, como mapas de Karnaugh e o algoritmo Quine-McCluskey, que facilitam o processo. ${\ displaystyle \ Sigma _ {2} ^ {P}}$

Os métodos de minimização de função booleana incluem:

• Método de Blake - Poretsky
• Método Nelson
• Algoritmo Quine-McCluskey
• Método de transformações algébricas
• Método de Petrick
• Método Roth
• Método Kudielka
• Método Wells
• Método binário de Scheinman
• um método de minimizar funções em bases SIM-NÃO e OU NÃO (base Schaeffer e Pierce)
• método de coeficientes indeterminados
• método hipercubo
• método de decomposição funcional

Minimizador lógico heurístico Espresso

Representações de dois níveis versus representações de vários níveis

Enquanto uma representação de circuito de dois níveis de circuitos refere-se estritamente à visão achatada do circuito em termos de SOPs ( soma de produtos ) - que é mais aplicável a uma implementação de PLA do projeto - uma representação de vários níveis é mais visão genérica do circuito em termos de SOPs conectados arbitrariamente, POSs ( produto das somas ), forma fatorada etc. Os algoritmos de otimização lógica geralmente funcionam na representação estrutural (SOPs, forma fatorada) ou funcional ( diagramas de decisão binários , ADDs ) do circuito.

Se tivermos duas funções F ₁ e F ₂ :

${\ displaystyle F_ {1} = AB + AC + AD, \,}$

${\ displaystyle F_ {2} = A'B + A'C + A'E. \,}$

A representação de 2 níveis acima leva seis termos de produto e 24 transistores em CMOS Rep.

Uma representação funcionalmente equivalente em vários níveis pode ser:

P = B + C .

F ₁ = AP + AD .

F ₂ = A'P + A'E .

Embora o número de níveis aqui seja 3, o número total de termos e literais do produto reduz devido ao compartilhamento do termo B + C.

Da mesma forma, distinguimos entre circuitos sequenciais e combinacionais , cujo comportamento pode ser descrito em termos de tabelas / diagramas de estado de máquina de estado finito ou por funções e relações booleanas, respectivamente.

Exemplo

Circuito de exemplo original e simplificado

Embora existam muitas maneiras de minimizar um circuito, este é um exemplo que minimiza (ou simplifica) uma função booleana. A função booleana realizada pelo circuito está diretamente relacionada à expressão algébrica a partir da qual a função é implementada. Considere o circuito usado para representar . É evidente que duas negações, duas conjunções e uma disjunção são usadas nesta declaração. Isso significa que, para construir o circuito, seriam necessários dois inversores , duas portas AND e uma porta OR . ${\ displaystyle (A \ wedge {\ bar {B}}) \ vee ({\ bar {A}} \ wedge B)}$

O circuito pode ser simplificado (minimizado) aplicando-se as leis da álgebra booleana ou usando a intuição. Uma vez que o exemplo afirma que é verdadeiro quando é falso e vice-versa, pode-se concluir que isso significa simplesmente . Em termos de portas lógicas, a desigualdade significa simplesmente uma porta XOR (exclusiva ou). Portanto ,. Então, os dois circuitos mostrados abaixo são equivalentes: ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A \ neq B}$${\ displaystyle (A \ wedge {\ bar {B}}) \ vee ({\ bar {A}} \ wedge B) \ iff A \ neq B}$

A exatidão do resultado pode ser verificada usando uma tabela verdade .

Veja também

• Diagrama de decisão binária (BDD)
• Não se preocupe com a condição
• Implicante principal
• Complexidade do circuito - na estimativa da complexidade do circuito
• Composição de funções
• Decomposição de função
• Subutilização do portão
• Gráfico de minimização de Harvard (Wikiversidade) (Wikilivros)

Referências

Leitura adicional

• Hwa, "Sherman" Hsuen Ren (junho de 1974). "A Method of Generating Prime Implicants of a Boolean Expression" . Transações IEEE em computadores . IEEE . C-23 (6): 637–641. doi : 10.1109 / TC.1974.224003 . eISSN  1557-9956 . ISSN  0018-9340 . S2CID  10646917 . CD- ISSN  2326-3814 . 1F09 . Página visitada em 2020-05-12 ; Hwa, "Sherman" Hsuen Ren (abril de 1973). Um método de geração de implantes primários de uma expressão booleana . Departamento de Ciência da Computação Basser, Universidade de Sydney . Relatório Técnico 82.
• Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1977). Análise e Projeto de Sistemas Digitais Sequenciais . Macmillan Press . ISBN 0-33319266-4. [49] (146 páginas)
• Ghosh, Debidas (junho de 1977) [1977-01-21]. "Um método de geração de fatores primos de uma expressão booleana em uma forma normal conjuntiva com a possibilidade de inclusão de combinação Don't care" (PDF) . Journal of Technology . Departamento de Matemática, Faculdade de Engenharia de Bengala, Howrah, Índia. XXII (1). Arquivado (PDF) do original em 12/05/2020 . Página visitada em 2020-05-12 .
• De Micheli, Giovanni (1994). Síntese e Otimização de Circuitos Digitais . McGraw-Hill . ISBN 0-07-016333-2. (NB. Os capítulos 7–9 cobrem a otimização combinatória de dois níveis, combinatória multinível e, respectivamente, a otimização do circuito sequencial.)
• Hachtel, Gary D .; Somenzi, Fabio (2006) [1996]. Algoritmos de Síntese Lógica e Verificação . Springer Science & Business Media . ISBN 978-0-387-31005-3.
• Kohavi, Zvi; Jha, Niraj K. (2009). "4-6". Switching and Finite Automata Theory (3ª ed.). Cambridge University Press . ISBN 978-0-521-85748-2.
• Knuth, Donald Ervin (2010). "7.1.2: Avaliação Booleana". The Art of Computer Programming . 4A . Addison-Wesley . pp. 96–133. ISBN 978-0-201-03804-0.
• Rutenbar, Rob A. Minimização multinível, Parte I: Modelos e Métodos (PDF) (slides de aula). Carnegie Mellon University (CMU). Aula 7. Arquivado (PDF) do original em 15/01/2018 . Página visitada em 2018-01-15 ; Rutenbar, Rob A. Minimização de vários níveis, Parte II: Cube / Cokernel Extract (PDF) (slides de aula). Carnegie Mellon University (CMU). Aula 8. Arquivado (PDF) do original em 15/01/2018 . Recuperado em 15/01/2018 .
• Tomaszewski, Sebastian P .; Celik, Ilgaz U .; Antoniou, George E. (dezembro de 2003) [2003-03-05, 2002-04-09]. "Minimização de função booleana baseada em WWW" (PDF) . Revista Internacional de Matemática Aplicada e Ciência da Computação . 13 (4): 577–584. Arquivado (PDF) do original em 2020-05-10 . Página visitada em 2020-05-10 . [50] [51] (7 páginas)
• Wilhelmy, Alexander; Kudielka, Viktor; Deussen, Peter; Böhling, Karl Heinz ; Händler, Wolfgang ; Neander, Joachim (janeiro de 1963) [1961-10-18]. Dörr, Johannes; Peschl, Ernst Ferdinand ; Unger, Heinz (eds.). 2. Colloquium über Schaltkreis- und Schaltwerk-Theorie - Vortragsauszüge vom 18. bis 20. Outubro de 1961 em Saarbrücken . Internationale Schriftenreihe zur Numerischen Mathematik [Série Internacional de Matemática Numérica] (ISNM) (em alemão). 4 (reimpressão de 2013-12-20 da 1ª ed.). Institut für Angewandte Mathematik, Universität Saarbrücken , Rheinisch-Westfälisches Institut für Instrumentelle Mathematik: Springer Basel AG / Birkhäuser Verlag Basel . doi : 10.1007 / 978-3-0348-4156-6 . ISBN 978-3-0348-4081-1. Página visitada em 2020-04-15 . (152 páginas)
• Brayton, Robert King ; Rudell, Richard L .; Sangiovanni-Vincentelli, Alberto Luigi ; Wang, Albert R. (dezembro de 1987). "MIS: um sistema de otimização lógica de vários níveis" . Transações IEEE em Projeto Auxiliado por Computador de Circuitos Integrados e Sistemas . 6 (6): 1062–1081. doi : 10.1109 / TCAD.1987.1270347 . (MIS) (20 páginas)
• De Geus, Aart J .; Cohen, William W. (julho-agosto de 1985). "Um sistema baseado em regras para otimizar a lógica combinacional" . Projeto IEEE e Teste de Computadores . 2 (4): 22–32. doi : 10.1109 / MDT.1985.294719 . eISSN  1558-1918 . ISSN  0740-7475 . S2CID  46651690 . Arquivado do original em 19/02/2021 . Recuperado em 2021-02-19 .(11 páginas) [52] (SÓCRATES)
• Khatri, Sunil P .; Gulati, Kanupriya, eds. (2011). Técnicas Avançadas em Síntese Lógica, Otimizações e Aplicações (1 ed.). Nova York / Dordrecht / Heidelberg / Londres: Springer Science + Business Media, LLC . ISBN 978-1-4419-7517-1. (xxii + 423 + 1 páginas)
• Jesse, Jobst E. (fevereiro de 1972). Escrito em Sunnyvale, Califórnia, EUA. "Um uso mais eficiente dos mapas de Karnaugh" . Design de computador . Vol. 11 não. 2. Concord, Massachusetts, EUA: Computer Design Publishing Corporation. pp. 80–82. ISSN  0010-4566 . OCLC  828863003 . CODEN  CMPDA . (3 páginas)
• Reusch, Bernd (setembro de 1975). "Geração de implantes primários a partir de subfunções e uma abordagem unificadora para o problema de cobertura" . Transações IEEE em computadores . IEEE . C-24 (9): 924–930. doi : 10.1109 / TC.1975.224338 . eISSN  1557-9956 . ISSN  0018-9340 . S2CID  32090834 . CD- ISSN  2326-3814 . Recuperado em 2021-02-19 . (7 páginas)
• Dineley, RL (abril de 1969). "Para o Editor" . Cartas para o editor. Design de computador . Vol. 8 não. 4. Concord, Massachusetts, EUA: Computer Design Publishing Corporation. p. 16. ISSN  0010-4566 . OCLC  828863003 . CODEN  CMPDA . p. 16: [...] Eu gostaria de oferecer um método para a simplificação da expressão booleana do tipo maxterm pelo uso do diagrama de Veitch . Até onde sei, sou o criador do método, tendo-o derivado em 1960, enquanto participava do curso Fundamentos de Computação Digital no Redstone Arsenal . A maioria dos textos simplifica a expressão de tipo maxterm ( produto de somas ) traçando os termos individuais em diagramas Veitch separados e, em seguida, sobrepondo os diagramas para descobrir as interseções, ou função "anded". [...] O método oferecido aqui permite a plotagem de todos os termos em um diagrama com a relação "anded" facilmente discernível. […] Cada termo de soma da expressão é atribuído a um símbolo. Este símbolo é plotado no Veitch para cada um dos fatores OR do termo. A função "e" ocorre sempre que qualquer quadrado ou combinação de 2 ⁿ quadrados adjacentes contém todos os símbolos atribuídos. Um exemplo simples ilustrará. […] (A + BC) ^[1] (A + C) ^[2] = A + BC […] Atenciosamente, RL Dineley, Sperry Rand Corp.(1 página) (NB. Referido na carta de Schultz acima.)
• Perkowski, Marek A .; Grygiel, Stanislaw (1995-11-20). "6. Panorama Histórico da Pesquisa em Decomposição". A Survey of Literature on Function Decomposition (PDF) . Versão IV. Grupo de Decomposição Funcional, Departamento de Engenharia Elétrica, Universidade de Portland, Portland, Oregon, EUA. CiteSeerX  10.1.1.64.1129 . Arquivado (PDF) do original em 2021-03-28 . Recuperado em 2021-03-28 . (188 páginas)
• Stanković, Radomir S .; Sasao, Tsutomu; Astola, Jaakko T. (agosto de 2001). "Publicações nos primeiros vinte anos de teoria de comutação e design lógico" (PDF) . Tampere International Center for Signal Processing (TICSP) Series. Universidade de Tecnologia de Tampere / TTKK, Monistamo, Finlândia. ISSN  1456-2774 . S2CID  62319288 . # 14. Arquivado (PDF) do original em 09/08/2017 . Recuperado em 2021-03-28 . (4 + 60 páginas)