Minimização de circuitos

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Broom icon.svg
As referências deste artigo necessitam de formatação (desde abril de 2013).
Por favor, utilize fontes apropriadas contendo referência ao título, autor, data e fonte de publicação do trabalho para que o artigo permaneça verificável no futuro.

Na álgebra booleana, minimização de circuitos é o problema de se obter o menor circuito lógico, que representa uma função booleana ou uma tabela verdade dada. Acredita-se que o problema de minimização de circuitos é intratável,[1] mas existem heurísticas efetivas como o Mapa de Karnaugh e o algoritmo Quine-McCluskey que facilitam o processo.

Objetivo[editar | editar código-fonte]

O problema de ter um circuito eletrônico complicado (isto é, um com muitos elementos, como as portas lógicas) é que cada elemento ocupa um determinado espaço físico em sua implementação, o que custa tempo e dinheiro para produzi-lo. A minimização de circuitos pode ser uma forma de otimização lógica, usada para reduzir o tamanho da complexidade lógica dos circuitos integrados.

Exemplo[editar | editar código-fonte]

Existem muitas formas de minimizar um circuito, este é um exemplo que minimiza (ou simplifica) uma função booleana. Note que a função booleana realizada pelo circuito está diretamente relacionada com a expressão algébrica da qual a função é implementada.[2] Considere o circuito usado para representar (A \wedge \bar{B}) \vee (\bar{A} \wedge B). É evidente que duas negações, duas conjunções, e uma dinjunção são utilizadas nessa proposição. Isto significa que para construir o circuito, precisaria-se de duas portas NOT, duas portas AND, e uma porta OR.

Nós podemos simplificar (minimizar) o circuito, aplicando identificadores lógicos ou utilizando a intuição. Uma vez que o exemplo mostra que A é verdadeiro quando B é falso, ou o contrário, podemos concluir que isto simplesmente significa A \neq B. Em termos de portas lógicas, a desigualdade simplesmente significa uma porta XOR (OU exclusivo). Portanto, (A \wedge \bar{B}) \vee (\bar{A} \wedge B) \iff A \neq B. Então os dois circuitos mostrados abaixo são equivalentes:

Circuit-minimization.svg

Você pode observar também a veracidade do resultado usando uma tabela verdade.

Ver também[editar | editar código-fonte]

Referências

  1. Kabanets, Valentine; Cai, Jin-Yi (2000), "Circuit minimization problem", Proc. 32nd Symposium on Theory of Computing, Portland, Oregon, USA, pp. 73–79, doi:10.1145/335305.335314, Predefinição:ECCC .
  2. M. Mano, C. Kime. "Logic and Computer Design Fundamentals" (Fourth Edition). Pg 54

Leitura adicional[editar | editar código-fonte]

  • De Micheli, Giovanni. Synthesis and Optimization of Digital Circuits. McGraw-Hill, 1994, Part III, Logic-Level Syntesis and Optimization
  • Zvi Kohavi, Niraj K. Jha. Switching and Finite Automata Theory. 3rd ed. Cambridge University Press. 2009. ISBN 978-0-521-85748-2, chapters 4–6
  • Knuth, Donald E.. The Art of Computer Programming. [S.l.]: Addison-Wesley, 2010. 96–133 pp. vol. 4A. ISBN 0-201-03804-8