Optimizare logică - Logic optimization

Optimizarea logică este un proces de găsire a unei reprezentări echivalente a circuitului logic specificat sub una sau mai multe constrângeri specificate. Acest proces face parte dintr-o sinteză logică aplicată în sistemele electronice digitale și în proiectarea circuitelor integrate .

În general, circuitul este limitat la o suprafață minimă a cipului care îndeplinește o întârziere de răspuns predefinită. Scopul optimizării logice a unui circuit dat este de a obține cel mai mic circuit logic care evaluează la aceleași valori ca și cel original. Circuitul mai mic cu aceeași funcție este mai ieftin, ocupă mai puțin spațiu, consumă mai puțină energie , are o latență mai scurtă și minimizează riscurile de conversații încrucișate neașteptate , pericolul procesării întârziate a semnalului și alte probleme prezente la nivelul nano-scării structurilor metalice. pe un circuit integrat .

În ceea ce privește algebra booleană , optimizarea unei expresii booleene complexe este un proces de a găsi una mai simplă, care la evaluare ar produce în cele din urmă aceleași rezultate ca și cea originală.

Motivație

Problema cu a avea un circuit complicat (adică unul cu multe elemente, cum ar fi porțile logice ) este că fiecare element ocupă spațiu fizic în implementarea sa și costă timp și bani pentru a produce în sine. Minimizarea circuitului poate fi o formă de optimizare logică utilizată pentru a reduce aria logicii complexe din circuitele integrate .

Odată cu apariția sintezei logice , una dintre cele mai mari provocări cu care s-a confruntat industria de automatizare a designului electronic (EDA) a fost de a găsi cea mai simplă reprezentare a circuitului pentru descrierea de proiectare dată. În timp ce optimizarea logică pe două niveluri a existat mult timp sub forma algoritmului Quine-McCluskey , urmat ulterior de minimizatorul logic euristic Espresso , densitatea cipurilor care se îmbunătățește rapid și adoptarea pe scară largă a limbajelor de descriere hardware pentru descrierea circuitelor, a oficializat optimizarea logică domeniu așa cum există astăzi.

Metode

Metodele de simplificare a circuitelor logice sunt aplicabile în mod egal minimizării expresiei booleene .

Clasificare

Astăzi, optimizarea logică este împărțită în diverse categorii:

Bazat pe reprezentarea circuitului

Optimizare logică pe două niveluri

Optimizare logică pe mai multe niveluri

Pe baza caracteristicilor circuitului

Optimizare logică secvențială

Optimizare logică combinațională

Pe baza tipului de execuție

Metode de optimizare grafică

Metode de optimizare tabulară

Metode de optimizare algebrică

Metode grafice

Metodele de minimizare grafică pentru logica pe două niveluri includ:

• Diagrama Euler (aka cercul eulerian ) (1768) de Leonhard P. Euler (1707–1783)
• Diagrama Venn (1880) de John Venn (1834–1923)
• Diagrama Marquand (1881) de Allan Marquand (1853-1924)
• Diagrama minimizatoare Harvard (aka Harvard chart ) (1951) de Howard H. Aiken (1900–1973) și Martha L. Whitehouse
• Diagrama descompunerii (1952) de Robert L. Ashenhurst (1929–2009) și Theodore Singer (1916–1991)
• Diagrama Veitch (1952) de Edward W. Veitch (1924–2013)
• Harta Karnaugh (1953) de Maurice Karnaugh (1924–)
• Oase de contact , grile de contact (1955) și harta triadică de Antonín Svoboda (1907–1980)
• Metoda grafică (1957) de Vadim Nikolaevich Roginskij [ Вадим Николаевич Рогинский ] (1913–1983)
• Diagrama Händler (alias graficul cercului Händler , Händler'scher Kreisgraph , Kreisgraph nach Händler , Händler-Kreisgraph , Händler-Diagramm , Minimisierungsgraph , M ⁿ graph ) (1958) de Wolfgang Händler (1920-1998)
• Harta Mahoney, alias M-map sau numere de desemnare (1963) de Matthew V. Mahoney
• Metoda grafică (1965) de Herbert F. Kortum  [ de ] (1907–1979)
• Harta Karnaugh redusă (RKM)
• Metoda Hypercube (1982) de Stamatios V. Kartalopoulos
• Harta Minterm-ring (MRM) sau algoritmul Minterm-ring (1990) de Thomas R. McCalla
• Diagrama V (2001) de Jonathan Westphal (1951–)
• Paraboomig (2003) de Shrish Verma și Kiran D. Permar
• Graficul invertorului majoritar (MIG) (2014) de Luca Amarú, Pierre-Emmanuel Gaillardon și Giovanni De Micheli
• Complot Pandit (2017) de Vedhas Pandit și Björn W. Schuller (1975–)
• Graficul adevărului (2020) de Eisa Alharbi

Minimizarea expresiei booleene

Aceleași metode de minimizare a expresiei booleene (simplificare) enumerate mai jos pot fi aplicate optimizării circuitului.

Pentru cazul în care funcția booleană este specificată de un circuit (adică vrem să găsim un circuit echivalent cu dimensiunea minimă posibilă), problema de minimizare a circuitului nelimitat a fost mult timp conjecturată ca fiind completă , rezultat demonstrat în cele din urmă în 2008, dar există euristici eficiente precum hărțile Karnaugh și algoritmul Quine – McCluskey care facilitează procesul. ${\ displaystyle \ Sigma _ {2} ^ {P}}$

Metodele de minimizare a funcției booleene includ:

• Blake - Metoda Poretsky
• Metoda Nelson
• Algoritm Quine – McCluskey
• Metoda transformărilor algebrice
• Metoda lui Petrick
• Metoda Roth
• Metoda Kudielka
• Metoda Wells
• Metoda binară a lui Scheinman
• o metodă de minimizare a funcțiilor în bazele DA-NU și SAU-NU (baza Schaeffer și Pierce)
• metoda coeficienților nedeterminați
• metoda hipercubului
• metoda funcțională de descompunere

Minimizare logică euristică espresso

Reprezentări pe două niveluri versus reprezentări pe mai multe niveluri

În timp ce o reprezentare a circuitelor pe două niveluri a circuitelor se referă strict la viziunea aplatizată a circuitului în termeni de SOP ( suma produselor ) - care este mai aplicabilă unei implementări PLA a designului - o reprezentare pe mai multe niveluri este mai vedere generică a circuitului în termeni de SOP-uri conectate în mod arbitrar, POS-uri ( produs-de-sume ), formă factorizată etc. Algoritmii de optimizare logică funcționează, în general, fie pe reprezentarea structurală (SOP-uri, formă factorizată), fie funcțională ( diagrame de decizie binare , ADD-uri ) a circuitului.

Dacă avem două funcții F ₁ și F ₂ :

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

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

Reprezentarea de 2 niveluri de mai sus necesită șase termeni de produs și 24 de tranzistoare în CMOS Rep.

O reprezentare echivalentă funcțională în mai multe niveluri poate fi:

P = B + C .

F ₁ = AP + AD .

F ₂ = A'P + A'E .

În timp ce numărul de niveluri de aici este 3, numărul total de termeni și literați ai produselor se reduce datorită partajării termenului B + C.

În mod similar, facem distincția între circuite secvențiale și combinaționale , al căror comportament poate fi descris în termeni de tabele / diagrame ale stării mașinilor în stare finită sau, respectiv, prin funcții și relații booleene.

Exemplu

Exemplu de circuit original și simplificat

Deși există multe modalități de a minimiza un circuit, acesta este un exemplu care minimizează (sau simplifică) o funcție booleană. Funcția booleană efectuată de circuit este direct legată de expresia algebrică din care este implementată funcția. Luați în considerare circuitul folosit pentru a reprezenta . Este evident că două negații, două conjuncții și o disjuncție sunt folosite în această afirmație. Aceasta înseamnă că pentru a construi circuitul ar fi nevoie de două invertoare , două porți ȘI și o poartă SAU . ${\ displaystyle (A \ wedge {\ bar {B}}) \ vee ({\ bar {A}} \ wedge B)}$

Circuitul poate fi simplificat (minimizat) prin aplicarea legilor algebrei booleene sau folosirea intuiției. Deoarece exemplul afirmă că este adevărat când este fals și invers, se poate concluziona că acest lucru înseamnă pur și simplu . În ceea ce privește porțile logice, inegalitatea înseamnă pur și simplu o poartă XOR (exclusivă sau). Prin urmare ,. Atunci cele două circuite prezentate mai jos sunt echivalente: ${\ displaystyle A}$${\ displaystyle B}$${\ displaystyle A \ neq B}$${\ displaystyle (A \ wedge {\ bar {B}}) \ vee ({\ bar {A}} \ wedge B) \ if A \ neq B}$

Corectitudinea rezultatului poate fi verificată folosind un tabel de adevăr .

Vezi si

• Diagrama binară de decizie (BDD)
• Nu-ți pasă starea
• Primul implicant
• Complexitatea circuitului - pe estimarea complexității circuitului
• Compoziția funcției
• Descompunerea funcției
• Subutilizarea porții
• Diagrama de minimizare Harvard (Wikiversity) (Wikibooks)

Referințe

Lecturi suplimentare

• Hwa, „Sherman” Hsuen Ren (iunie 1974). „O metodă de generare a primilor implicați ai unei expresii booleene” . Tranzacții IEEE pe computere . 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 . Adus 12-05-2020 ; Hwa, „Sherman” Hsuen Ren (aprilie 1973). O metodă de generare a primilor implicați ai unei expresii booleene . Departamentul de informatică Basser, Universitatea din Sydney . Raport tehnic 82.
• Lind, Larry Frederick; Nelson, John Christopher Cunliffe (1977). Analiza și proiectarea sistemelor digitale secvențiale . Macmillan Press . ISBN 0-33319266-4. [49] (146 pagini)
• Ghosh, Debidas (iunie 1977) [21-01 1977]. „O metodă de generare a factorilor primi ai unei expresii booleene într-o formă normală conjunctivă cu posibilitatea includerii combinației„ Nu-ți pasă ” (PDF) . Journal of Technology . Departamentul de matematică, Bengal Engineering College, Howrah, India. XXII (1). Arhivat (PDF) din original pe 12.05.2020 . Adus 12-05-2020 .
• De Micheli, Giovanni (1994). Sinteza și optimizarea circuitelor digitale . McGraw-Hill . ISBN 0-07-016333-2. (NB. Capitolele 7-9 acoperă combinatorial pe două niveluri, combinatorial pe mai multe niveluri și, respectiv, optimizarea circuitului secvențial.)
• Hachtel, Gary D .; Somenzi, Fabio (2006) [1996]. Algoritmi de sinteză și verificare logică . Springer Science & Business Media . ISBN 978-0-387-31005-3.
• Kohavi, Zvi; Jha, Niraj K. (2009). „4-6”. Comutarea și teoria automatelor finite (ediția a 3-a). Cambridge University Press . ISBN 978-0-521-85748-2.
• Knuth, Donald Ervin (2010). "7.1.2: Evaluare booleană". Arta programării pe calculator . 4A . Addison-Wesley . pp. 96–133. ISBN 978-0-201-03804-0.
• Rutenbar, Rob A. Minimizarea pe mai multe niveluri, Partea I: Modele și metode (PDF) (diapozitive de prelegere). Universitatea Carnegie Mellon (CMU). Prelegerea 7. Arhivat (PDF) din original la 15.01.2018 . Adus 15.01.2018 ; Rutenbar, Rob A. Minimizarea pe mai multe niveluri, Partea a II-a: Extract de cub / cokernel (PDF) (diapozitive de prelegere). Universitatea Carnegie Mellon (CMU). Cursul 8. Arhivat (PDF) din original la 15.01.2018 . Adus 15.01.2018 .
• Tomaszewski, Sebastian P .; Celik, Ilgaz U .; Antoniou, George E. (decembrie 2003) [2003-03-05, 2002-04-09]. „Minimizarea funcției booleene bazate pe WWW” (PDF) . Jurnalul internațional de matematică aplicată și informatică . 13 (4): 577-584. Arhivat (PDF) din original în data de 05.05.2020 . Adus la 10.05.2020 . [50] [51] (7 pagini)
• Wilhelmy, Alexandru; Kudielka, Viktor; Deussen, Peter; Böhling, Karl Heinz ; Händler, Wolfgang ; Neander, Joachim (ianuarie 1963) [1961-10-18]. Dörr, Johannes; Peschl, Ernst Ferdinand ; Unger, Heinz (eds.). 2. Colocviu über Schaltkreis- und Schaltwerk-Theorie - Vortragsauszüge vom 18. bis 20. Oktober 1961 în Saarbrücken . Internationale Schriftenreihe zur Numerischen Mathematik [International Series of Numerical Mathematics] (ISNM) (în germană). 4 (reeditare 2013-12-20 ed. I). 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. Adus 15-04-2020 . (152 pagini)
• Brayton, Robert King ; Rudell, Richard L .; Sangiovanni-Vincentelli, Alberto Luigi ; Wang, Albert R. (decembrie 1987). „MIS: un sistem de optimizare a logicii pe mai multe niveluri” . Tranzacții IEEE privind proiectarea asistată de computer a circuitelor și sistemelor integrate . 6 (6): 1062-1081. doi : 10.1109 / TCAD.1987.1270347 . (MIS) (20 de pagini)
• De Geus, Aart J .; Cohen, William W. (iulie-august 1985). „Un sistem bazat pe reguli pentru optimizarea logicii combinaționale” . Proiectarea și testarea computerelor IEEE . 2 (4): 22-32. doi : 10.1109 / MDT.1985.294719 . eISSN  1558-1918 . ISSN  0740-7475 . S2CID  46651690 . Arhivat din original la 19.02.2021 . Adus 2021-02-19 .(11 pagini) [52] (SOCRATE)
• Khatri, Sunil P .; Gulati, Kanupriya, eds. (2011). Tehnici avansate în sinteza logică, optimizări și aplicații (1 ed.). New York / Dordrecht / Heidelberg / Londra: Springer Science + Business Media, LLC . ISBN 978-1-4419-7517-1. (xxii + 423 + 1 pagini)
• Jesse, Jobst E. (februarie 1972). Scris la Sunnyvale, California, SUA. „O utilizare mai eficientă a hărților Karnaugh” . Proiectare computer . Vol. 11 nr. 2. Concord, Massachusetts, SUA: Computer Design Publishing Corporation. pp. 80-82. ISSN  0010-4566 . OCLC  828863003 . CODEN  CMPDA . (3 pagini)
• Reusch, Bernd (septembrie 1975). „Generarea primilor implicați din subfuncții și o abordare unificatoare a problemei de acoperire” . Tranzacții IEEE pe computere . IEEE . C-24 (9): 924-930. doi : 10.1109 / TC.1975.224338 . eISSN  1557-9956 . ISSN  0018-9340 . S2CID  32090834 . CD- ISSN  2326-3814 . Adus 2021-02-19 . (7 pagini)
• Dineley, RL (aprilie 1969). „Către editor” . Scrisori către editor. Proiectare computer . Vol. 8 nr. 4. Concord, Massachusetts, SUA: Computer Design Publishing Corporation. p. 16. ISSN  0010-4566 . OCLC  828863003 . CODEN  CMPDA . p. 16: […] Aș dori să ofer o metodă pentru simplificarea expresiei booleene de tip maxterm prin utilizarea diagramei Veitch . Din câte știu eu, sunt inițiatorul metodei, după ce am derivat-o în 1960 în timp ce participam la cursul Digital Computer Fundamentals de la Redstone Arsenal . Majoritatea textelor simplifică expresia de tip maxterm ( produsul sumelor ) prin trasarea termenilor individuali pe diagrame Veitch separate și apoi suprapunerea diagramelor pentru a descoperi funcția intersectată sau „anded”. […] Metoda oferită aici permite reprezentarea grafică a tuturor termenilor pe o diagramă cu relația „anded” ușor de discernut. […] Fiecărui termen sum al expresiei i se atribuie un simbol. Acest simbol este reprezentat pe Veitch pentru fiecare dintre factorii or'd ai termenului. Funcția „și” apare ori de câte ori orice pătrat sau combinație de 2 ⁿ pătrate adiacente conțin toate simbolurile atribuite. Un exemplu simplu va ilustra. […] (A + BC) ^[1] (A + C) ^[2] = A + BC […] Cu adevărat, RL Dineley, Sperry Rand Corp.(1 pagină) (NB. Menționat în scrisoarea lui Schultz de mai sus.)
• Perkowski, Marek A .; Grygiel, Stanislaw (1995-11-20). "6. Privire de ansamblu istorică a cercetării privind descompunerea". Un sondaj de literatură privind descompunerea funcției (PDF) . Versiunea IV. Grupul de descompunere funcțională, Departamentul de inginerie electrică, Universitatea Portland, Portland, Oregon, SUA. CiteSeerX  10.1.1.64.1129 . Arhivat (PDF) din originalul din 2021-03-28 . Adus 28.03.2021 . (188 pagini)
• Stanković, Radomir S .; Sasao, Tsutomu; Astola, Jaakko T. (august 2001). „Publicații în primii douăzeci de ani de teorie de comutare și proiectare logică” (PDF) . Seria Centrul Internațional de Procesare a Semnalului (TICSP) din Tampere. Universitatea de Tehnologie Tampere / TTKK, Monistamo, Finlanda. ISSN  1456-2774 . S2CID  62319288 . # 14. Arhivat (PDF) din originalul din 09.08.2017 . Adus 28.03.2021 . (4 + 60 de pagini)