Za´padoˇceska´ univerzita v Plzni Fakulta aplikovany´ch vˇed Katedra informatiky a vy´poˇcetn´ı techniky
Bakal´ aˇ rsk´ a pr´ ace Metody k´ odov´ an´ı stav˚ u synchronn´ıch automat˚ u
Plzeˇ n 2013
Monika Kov´aˇrov´a
Prohl´ aˇ sen´ı Prohlaˇsuji, ˇze jsem bakal´aˇrskou pr´aci vypracovala samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. V Plzni dne 6. kvˇetna 2013 Monika Kov´aˇrov´a
Podˇ ekov´ an´ı T´ımto bych chtˇela podˇekovat doc. Ing. Vlastimilu Vavˇriˇckovi, CSc. za materia´ly, kter´e mi poskytl pro moj´ı pr´aci a za ˇcas, kter´ y mi vˇenoval na konzultac´ıch.
Abstract Methods of coding states of synchronous machines This paper describes the various methods of coding states for synchronous finite state machines. These methods are divided into two basic groups, according to their computational complexity and given set of rules. These groups are basic and advanced algorithms. Advanced algorithms are further divided into heuristic and genetic algorithm group. The aim of this study is to compare several methods and identify those that best minimize the number of components needed for building the circuit. Further, this work deals with the DAG algorithm and examines the impact of used technological parameters on coding. The methods are applied to set of machines that have different number of inputs, outputs and next states.
Obsah ´ 1 Uvod 2 Teorie automat˚ u 2.1 Dˇelen´ı automat˚ u . . . . . . . . . . 2.1.1 Mooreho automat . . . . . . 2.1.2 Mealyho automat . . . . . . 2.1.3 Pravdivostn´ı tabulka . . . . 2.1.4 Minimalizace logick´e funkce 2.1.5 Hlavn´ı pravidla pro tvorbu a 2.2 Uk´azkov´ y pˇr´ıklad . . . . . . . . . .
1
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . u ´pravy logick´ ych v´ yraz˚ u . . . . . . . . . . . . . .
3 K´ odov´ an´ı stav˚ u logick´ ych automat˚ u 3.1 Poˇcet r˚ uzn´ ych k´odov´an´ı . . . . . . . . . . . . . . . ´ 3.2 Uˇcinnost metod k´odov´an´ı stav˚ u . . . . . . . . . . . 3.3 Z´akladn´ı metody k´odov´an´ı . . . . . . . . . . . . . . 3.3.1 Bin´arn´ı k´odov´an´ı . . . . . . . . . . . . . . . 3.3.2 Grayovo k´odov´an´ı . . . . . . . . . . . . . . . 3.3.3 One-hot k´odov´an´ı . . . . . . . . . . . . . . . 3.3.4 2-hot k´odov´an´ı . . . . . . . . . . . . . . . . 3.3.5 Zero-hot k´odov´an´ı . . . . . . . . . . . . . . . 3.3.6 Johnsonovo k´odov´an´ı . . . . . . . . . . . . . 3.3.7 K´odov´an´ı m-n . . . . . . . . . . . . . . . . . 3.3.8 N´ahodn´e k´odov´an´ı . . . . . . . . . . . . . . 3.3.9 Metoda postupn´eho proch´azen´ı . . . . . . . 3.4 Pokroˇcil´e metody k´odov´an´ı . . . . . . . . . . . . . . 3.5 Heuristick´e algoritmy . . . . . . . . . . . . . . . . . 3.5.1 DAG k´odov´an´ı . . . . . . . . . . . . . . . . 3.5.2 Output-Based encoding (V´ ystupn´ı k´odov´an´ı) 3.5.3 TOOL1 . . . . . . . . . . . . . . . . . . . . 3.5.4 TOOL2 . . . . . . . . . . . . . . . . . . . . 3.5.5 Mustang . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
. . . . . . .
2 3 4 5 6 6 7 7
. . . . . . . . . . . . . . . . . . .
11 11 12 13 13 13 14 14 15 15 16 16 17 17 18 19 23 24 25 26
3.5.6
Genetick´e algoritmy . . . . . . . . . . . . . . . . . . . 30
4 Implementace k´ odovac´ıho algoritmu DAG 4.1 Tˇr´ıda Stav . . . . . . . . . . . . . . . . . . 4.1.1 Metoda ToString . . . . . . . . . . 4.2 Tˇr´ıda StavovaTrida . . . . . . . . . . . . . 4.2.1 Metoda VypoctiMaticiVystupu . . 4.2.2 Metoda VypoctiMaticiNasledniku . 4.2.3 Metoda VypoctiMaticiPredchudcu 4.2.4 Metoda VypoctiMaticiPrechodu . . 4.2.5 Metoda VypoctiMaticiDAG . . . . 4.2.6 Metoda HammingovaVzdalenost . . 4.2.7 Metoda VypoctiPoleVah . . . . . . 4.2.8 Metoda TabulkaPrirazeni . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
. . . . . . . . . . .
31 31 31 32 32 32 32 33 33 33 33 34
5 Porovn´ an´ı metod k´ odov´ an´ı
35
6 Z´ avˇ er
42
´ 1 Uvod V dneˇsn´ım svˇetˇe jsme obklopeni vˇedou a technikou. Snad kaˇzd´ y jiˇz minim´alnˇe jednou pouˇzil automat na k´avu, praˇcku nebo myˇcku. Tyto stroje“ a mnoho ” dalˇs´ıch ˇrad´ıme mezi automaty. Vykon´avaj´ı danou sekvenci krok˚ u podle zvolen´eho programu. Aby byla moˇzn´a implementace, je potˇreba navrhnout strukturu a jednoznaˇcnˇe stanovit kaˇzd´ y krok chodu automatu, tzn. urˇcit stavy, vstupy a v´ ystupy. Tyto stavy je potˇreba k´odovat, aby bylo moˇzn´e obvod realizovat pomoc´ı elektronick´ ych souˇc´astek (AND, OR, NOT, klopn´e obvody, ...). Tato bakal´aˇrsk´a pr´ace se t´ yk´a obecn´ ych automat˚ u a popisuje metody pro k´odov´an´ı stav˚ u. Metody k´odov´an´ı stav˚ u se zab´ yvaj´ı probl´emem stavov´eho pˇriˇrazen´ı tj. pˇriˇrazen´ı bin´arn´ıho k´odu vnitˇrn´ım stav˚ um koneˇcn´eho automatu. K´odov´an´ı stav˚ u patˇr´ı mezi zn´am´e probl´emy, kter´e jsou zaˇrazeny do kategorie NP-´ upln´e. Neum´ıme naj´ıt nejlepˇs´ı“ algoritmus, proto se snaˇz´ıme dos´ahnout alespoˇ n ” dobr´eho“ k´odov´an´ı. Hled´ame metody, kter´e u ´ˇcinnˇe minimalizuj´ı poˇcet sou” ˇc´astek potˇrebn´ ych pro realizaci obvodu [2]. Pokud je nalezen alespoˇ n dobr´ y“ algoritmus, zmenˇs´ı se poˇcet klopn´ ych ” obvod˚ u potˇrebn´ ych pro dan´ y automat, redukuje se poˇcet hradel nutn´ ych pro implementaci, zmenˇs´ı se vyˇzadovan´ y v´ ykon a sn´ıˇz´ı se doba zpoˇzdˇen´ı obvodu [18]. Souˇca´st´ı t´eto pr´ace je i mˇeˇren´ı u ´ˇcinnosti metod pro k´odov´an´ı stav˚ u a obsaI huje v´ ysledky cen obvod˚ u dan´ ych automat˚ u pro metody bin´arn´ıho k´odov´an´ı, Grayovo k´odov´an´ı, DAG k´odov´an´ı a v´ ystupn´ıho k´odov´an´ı.
I
cena je v dalˇs´ım textu ch´ apana jako poˇcet vstup˚ u do el. souˇc´astek potˇrebn´ ych pro realizaci obvodu dan´eho automatu
1
2 Teorie automat˚ u Bakal´aˇrsk´a pr´ace je zamˇeˇrena na synchronn´ı koneˇcn´e automaty [4], tzn. zmˇena stav˚ u nast´av´a aˇz pˇri p˚ usoben´ı synchronizaˇcn´ıho (hodinov´eho) impulzu CLK. Koneˇcn´ y automat nad abecedou Σ rozum´ıme uspoˇra´danou pˇetici A = (Q, Σ, δ, q0 , F)[5], kde • Q je koneˇcn´a nepr´azdn´a mnoˇzina stav˚ u (stavov´ y prostor), • Σ je nepr´azdn´a koneˇcn´a mnoˇzina vstupn´ıch symbol˚ u (vstupn´ı abeceda), • δ je zobrazen´ı δ:Q × Σ −→ Q naz´ yv´ame pˇrechodov´a funkce, • q0 ∈ Q je poˇc´ateˇcn´ı stav (inici´aln´ı stav), • F −→ je c´ılov´a (fin´aln´ı) mnoˇzina koncov´ ych stav˚ u. Koneˇcn´ y automat je abstraktn´ım modelem sekvenˇcn´ıho obvodu. Stavy ch´apeme jako sign´aly, kter´e mohou nab´ yvat dvou hodnot (0 a 1), a kter´ ych je vˇzdy koneˇcn´ y poˇcet. Kaˇzdou z kombinac´ı oznaˇc´ıme kv˚ uli u ´sporn´emu z´apisu symbolem, napˇr. p´ısmenem. Obr´azek 2.1 ukazuje automat se vstupn´ımi sign´aly xi , v´ ystupn´ı sign´aly zi a vnitˇrn´ımi sign´aly Qi . Vstup je oznaˇcen jako I, v´ ystup jako O a stav jako S. Jednotliv´e konkr´etn´ı kombinace hodnot vstup˚ u oznaˇc´ıme jako I0 ,I1 , atd. Obdobnˇe budou oznaˇceny kombinace hodnot v´ ystup˚ u O0 ,O1 , atd., a stav˚ u S0 , S1 , atd. [14]
Obr´azek 2.1: Sign´aly a stavy v sekvenˇcn´ım obvodu Z´avislost n´asleduj´ıc´ıho stavu na souˇcasn´em stavu a vstupu vyjadˇruje pˇrechodov´a funkce: S t + 1 = f (S t , I t ), kde symbol S t + 1 znaˇc´ı n´asleduj´ıc´ı stav, S t znaˇc´ı souˇcasn´ y stav, I t znaˇc´ı souˇcasn´ y v´ ystup [14]. V´ ystup koneˇcn´eho automatu m˚ uˇze b´ yt generov´an nˇekolika zp˚ usoby. Kaˇzd´ y z nich je definov´an pˇr´ısluˇsnou v´ ystupn´ı funkc´ı. V obecn´em pˇr´ıpadˇe je v´ ystup 2
Teorie automat˚ u
Dˇelen´ı automat˚ u
funkc´ı vstupu a souˇcasn´eho stavu : Ot = g(S t , I t ) [14]. Zp˚ usob odvozen´ı v´ ystupu nem´a vliv na k´odov´an´ı stav˚ u. Koneˇcn´ y automat lze reprezentovat r˚ uzn´ ymi zp˚ usoby: grafem (pˇr´ıklad uveden na obr´azku 2.2), stavovou tabulkou (pˇr´ıklad uveden na obr´azku 2.3), soustavou rovnic.
Obr´azek 2.2: Graf
Obr´azek 2.3: Stavov´a tabulka
2.1
Dˇ elen´ı automat˚ u
Pevn´ y automat lze dˇelit z hlediska v´ ystupu do dvou skupin: Mooreho (pˇr´ıklad Mooreho automatu je zn´azornˇen na obr´azku 2.4) a Mealyho (pˇr´ıklad je 3
Teorie automat˚ u
Dˇelen´ı automat˚ u
uveden na obr´azku 2.5).
Obr´azek 2.4: Mooreho automat
Obr´azek 2.5: Mealyho automat
2.1.1
Mooreho automat
Mooreho automat si m˚ uˇzeme pˇredstavit jako zaˇr´ızen´ı s koneˇcn´ ym poˇctem stav˚ u, kter´e pracuj´ı na z´akladˇe vstupn´ıch symbol˚ u. Kaˇzd´ y stav m´a definovanou pr´avˇe jednu hodnotu na v´ ystupu. Automat d´ale mus´ı m´ıt definovan´ y v´ ychoz´ı stav, ve kter´em se nach´az´ı pˇred zad´an´ım prvn´ıho vstupn´ıho symbolu a pravidla pro pˇrechody mezi jednotliv´ ymi stavy. V´ ystup Mooreho automatu t t z´avis´ı pouze na vnitˇrn´ım stavu, tedy: O = g(S ). Zmˇena v´ ystupu nast´av´a pouze pˇri vstupu hodinov´eho sign´alu (CLK) [14]. Form´ aln´ı definice: Koneˇcn´ y automat typu Moore je uspoˇra´dan´a ˇsestice (X, Y, S, S0 , δ, ω), kde 4
Teorie automat˚ u
Dˇelen´ı automat˚ u
• X: |X|<∞ je koneˇcn´a vstupn´ı abeceda (mnoˇzina vstupn´ıch symbol˚ u), • Y: |Y|<∞ je koneˇcn´a v´ ystupn´ı abeceda (mnoˇzina v´ ystupn´ıch symbol˚ u), • S: |S|<∞ je koneˇcn´a mnoˇzina vnitˇrn´ıch stav˚ u, • S0 : S0 ∈S je v´ ychoz´ı vnitˇrn´ı stav, • δ:S×X−→S je pˇrechodov´a funkce, • ω:S−→Y je v´ ystupn´ı funkce.
2.1.2
Mealyho automat
Mealyho automat je koneˇcn´ y automat, jehoˇz v´ ystup je spojen s pˇrechody mezi stavy. V´ ystup je generov´an na z´akladˇe pˇr´ıchoz´ıho vstupu i moment´aln´ıho stavu, ve kter´em se automat nach´az´ı, tzn. Ot = g(S t , I t ). Stavov´ y diagram automatu m´a ke kaˇzd´emu pˇrechodu pˇriˇrazenou nejen vstupn´ı hodnotu, kterou je pˇrechod aktivov´an, ale i v´ ystupn´ı hodnotou, kter´a je pˇri aktivaci pˇrechodu vygenerov´ana. Zmˇena v´ ystupu m˚ uˇze nastat v libovoln´em ˇcase, bez ohledu na hodinov´ y sign´al CLK [14]. Form´ aln´ı definice: Mealyho stroj je uspoˇr´adan´a ˇsestice (Z, Q, Y, φ, ψ, q), kde: • Z = z1 , z2 , ..., zn je koneˇcn´a vstupn´ı abeceda, • Q = q1 , q2 , ..., qn je nepr´azdn´a koneˇcn´a mnoˇzina stav˚ u promˇenliv´ ych v ˇcase, • Y = y1 , y2 , ..., yn je koneˇcn´a v´ ystupn´ı abeceda, • φ = g(t+1) = φ[q(t), z(t)] je pˇrechodov´a funkce, • ψ = y(t) = ψ[q(t), z(t)] je v´ ystupn´ı funkce, kde z´aleˇz´ı na stavu, ve kter´em se automat nach´az´ı a z´aroveˇ n i na vstupn´ım sign´alu, • g je poˇc´ateˇcn´ı stav z mnoˇziny Q.
5
Teorie automat˚ u
2.1.3
Dˇelen´ı automat˚ u
Pravdivostn´ı tabulka
Logickou funkci lze zapisovat pravdivostn´ı tabulkou. Tabulka obsahuje pouze logick´e hodnoty 0, 1 nebo neurˇcit´e stavy (ˇcasto oznaˇcov´any symboly X“ ” nebo -“ ). Velikost tabulky je d´ana poˇctem vˇsech vstupn´ıch promˇenn´ ych ” a poˇctem v´ ystupn´ıch funkc´ı. To znamen´a, ˇze tabulka bude m´ıt tolik ˇr´adk˚ u, kolik je poˇcet vˇsech kombinac´ı stav˚ u v´ ystupn´ıch promˇenn´ ych, kter´e mohou nastat. Poˇcet tˇechto kombinac´ı se vypoˇc´ıt´a jako 2n , kde n je poˇcet vstupn´ıch promˇenn´ ych. Pˇr´ıklad pro funkci tˇr´ı promˇenn´ ych f (x, y, z) a jej´ı negaci f (x, y, z) je uveden v tabulce 2.1. Tabulka 2.1: Pravdivostn´ı tabulka
Zhuˇstˇen´ y z´apis pravdivostn´ ı tabulky 2.1 je (vyjmenujeme ty ˇra´dky, kde P P f = 1): f (x, y, z) = m(0, 1, 3, 4, 6) I , symbol naznaˇcuje, ˇze funkce f je vyj´adˇrena v souˇcinov´em (disjunktn´ım) tvaru. Libovolnou logickou funkci lze vyj´adˇrit jako souˇcet element´arn´ıch logick´ ych funkc´ı mi , kter´e se naz´ yvaj´ı mintermy. V´ ysledn´ y souˇcet minterm˚ u se naz´ yv´a u ´pln´a souˇctov´a norm´aln´ı ´ forma, zkr´acenˇe UDNF a z´ısk´ame ji, pokud vybereme jen ty mintermy, kter´e odpov´ıdaj´ı ˇra´dk˚ um s funkˇcn´ı hodnotou 1 [14].
2.1.4
Minimalizace logick´ e funkce
Zp˚ usob˚ u minimalizace logick´e funkce je nˇekolik a prov´ad´ı se s vyuˇzit´ım: Booleovy algebry, DeMorganov´ ych z´akon˚ u, Karnaughovy mapy a krychlov´eho komplexu. I
Pokud by tabulka obsahovala ych z´avorek do souP i neurˇcit´e stavy zap´ıˇs´ı se do hranat´ ˇcinov´eho tvaru, pˇr. f (x, y, z) = m(0, 1, 3, [4, 6])
6
Teorie automat˚ u
Uk´azkov´y pˇr´ıklad
Obdobnˇe jako v bˇeˇzn´e algebˇre i v Booleovˇ e algebˇ re plat´ı komutativn´ı, asociativn´ı a distributivn´ı z´akon. Pouˇz´ıv´an´ı z´avorek se neliˇs´ı od pouˇz´ıv´an´ı v bˇeˇzn´e algebˇre. DeMorganovy z´ akony jsou: (a + b) = a · b (a · b) = a + b Karnaughova mapa je jeden z moˇzn´ ych z´apis˚ u logick´e funkce. Tuto mapu pouˇzijeme pˇri minimalizaci nebo pˇri anal´ yze. Jej´ım principem je zobrazen´ı pravdivostn´ı tabulky do dvourozmˇern´e mapy, d´ıky kter´e je moˇzno vyhledat sluˇciteln´e termy (oblasti, kter´e jsou zcela nez´avisl´e na jedn´e ze vstupn´ıch promˇenn´ ych a ty pak zapisujeme jako minimalizovanou funkci) [14]. Uk´azka minimalizace pomoc´ı Karnaughovy mapy bude uvedena v textu (kapitola 2.2). Krychlov´ ym komplexem C(λ) funkce λ(x1 , x2 , ..., xm ) rozum´ıme mnoˇzinu vrchol˚ u (0-krychl´ı) m-mˇern´e jednotkov´e krychle, event. mnoˇzinu podkrychl´ı m-mˇern´e jednotkov´e krychle, na jejichˇz vrcholech nab´ yv´a funkce λ hodnotou 1 ˇci nen´ı definov´ana (0 ˇci nen´ı definov´ana nebo 0 ˇci 1) [5].
2.1.5
Hlavn´ı pravidla pro tvorbu a u ´ pravy logick´ ych v´ yraz˚ u
Logick´e v´ yrazy upravujeme podle dvou krit´eri´ı. Bud’ se jedn´a o zjednoduˇsen´ı ve smyslu sn´ıˇzen´ı poˇctu p´ısmen ve v´ ysledn´em v´ yrazu, nebo se jedn´a o u ´pravu do takov´eho tvaru, kter´ y vyhovuje ˇc´ıslicov´emu obvodu (souˇca´stce), kter´ y je jiˇz k dispozici [14]. V t´eto pr´aci budeme uvaˇzovat pouze prvn´ı pˇr´ıpad. Pˇredpokl´adejme tedy, ˇze m´ame k dispozici vˇsechny potˇrebn´e obvody.
2.2
Uk´ azkov´ y pˇ r´ıklad
Pˇr´ıklad v´ypoˇctu ceny logick´eho automatu, tedy poˇcet AND-OR vstup˚ u poˇzadovan´ ych v dvoustupˇ nov´em proveden´ı kaˇzd´eho vstupn´ıho pamˇet’ov´eho prvku vstupn´ı rovnice.
7
Teorie automat˚ u
Uk´azkov´y pˇr´ıklad
1. krok: Ze zak´odovan´e stavov´e tabulky 2.2 (ˇcervenˇe oznaˇcen´e sloupce) sestroj´ıme Karnaughovu mapu (obr´azek 2.6). Tabulka 2.2: Zak´odovan´a stavov´a tabulka pro Karnaughovu mapu
Obr´azek 2.6: Karnaugova mapa pro prvn´ı stavovou promˇennou a1 Logick´a funkce pro prvn´ı stavovou promˇennou: P f1 (d, c, b, a1 ) = m(2, 4, 6, 7[10, 11, 12, 13, 14, 15]) ´ UDNF pro prvn´ı stavovou promˇennou: f1 (d, c, b, a1 ) = ab + ac + bc 2. krok: Stejn´ y zp˚ usobem pokraˇcujeme i pro ostatn´ı sloupce n´asleduj´ıc´ıch stav˚ u (obr´azek 2.7 a 2.8) Logick´a funkce pro druhou stavovou promˇennou: P f2 (d, c, b, a2 ) = m(1, 3, 5[10, 11, 12, 13, 14, 15]) 8
Teorie automat˚ u
Uk´azkov´y pˇr´ıklad
Obr´azek 2.7: Karnaugova mapa pro druhou stavovou promˇennou a2 ´ UDNF pro druhou stavovou promˇennou: f2 (d, c, b, a2 ) = abd + acd
Obr´azek 2.8: Karnaugova mapa pro tˇret´ı stavovou promˇennou a3 Logick´a funkce pro tˇret´ı stavovou promˇennou: P f3 (d, c, b, a3 ) = m(0,3,5[10,11,12,13,14,15]) ´ UDNF pro tˇret´ı stavovou promˇennou: f(d,c,b,a) = abcd + abc + abc 3. krok: D´ale vytvoˇr´ıme mapu i pro v´ ystupy (obr´azky 2.9 a 2.10). P Logick´a funkce pro v´ ystup Z0 : f4 (d, c, b) = m(1,2[5,6,7]) ´ UDNF pro v´ ystup Z0 : f4 (d, c, b) = bc + bc Logick´a funkce pro v´ ystup Z1 : f5 (d, c, b) = 9
P
m(1,3[5,6,7])
Teorie automat˚ u
Uk´azkov´y pˇr´ıklad
´ UDNF pro v´ ystup Z1 : f5 (d, c, b) = b
Obr´azek 2.9: Karnaugova mapa pro prvn´ı v´ ystup
Obr´azek 2.10: Karnaugova mapa pro druh´ y v´ ystup 4. krok: Vypoˇc´ıt´ame celkovou cenu obvodu ze vˇsech uveden´ ych forem fi (tzn. poˇcet vstup˚ u do log. ˇclen˚ u AND a OR), viz tabulka 2.3 . Tabulka 2.3: Cena obvodu
10
3 K´odov´an´ı stav˚ u logick´ ych automat˚ u Probl´em k´odov´an´ı stav˚ u, s minim´aln´ımi n´aklady na cenu obvodu nen´ı zcela vyˇreˇsen. Metody, kter´e jsou prozat´ım navrˇzeny, maj´ı jeden nebo v´ıce z n´asleduj´ıc´ıch nedostatk˚ u [9]: • jsou velmi pracn´e, • vyˇzaduj´ı velk´e mnoˇzstv´ı ruˇcn´ıho ˇsit´ı“ metod pro kaˇzd´ y probl´em, tzn. ” nen´ı moˇzn´e implementovat na digit´aln´ım poˇc´ıtaˇci, • jsou pouˇziteln´e pouze pro mal´e obvody.
3.1
Poˇ cet r˚ uzn´ ych k´ odov´ an´ı
Necht’ je d´an koneˇcn´ y automat M, kter´ y m´a r stav˚ u. Pˇredpokl´ad´ame, ˇze pro zak´odov´an´ı stav˚ u pouˇzijeme s bit˚ u, kde s je nejmenˇs´ı cel´e ˇc´ıslo, vyhovuj´ıc´ı podm´ınce 2s ≥ r [19]. Kolik r˚ uzn´ ych pˇriˇrazen´ı stav˚ u m˚ uˇzeme dos´ahnout u tohoto automatu? Vzorec je pomˇernˇe jednoduch´ y, ale v´ ysledky jsou pˇrekvapiv´e [2]: A = C2r =
2s ! (2s − r)!
Pokud zvaˇzujeme ekvivalentn´ı pˇriˇrazen´ı stavu, pak poˇcet r˚ uzn´ ych k´odov´an´ı podle definice McCluksey je roven (pro obvody pouˇz´ıvaj´ıc´ı klopn´e obvody SR, JK a T) [19]: A1 =
(2s − 1)! (2s − r)!s!
S dalˇs´ı definic´ı pˇriˇsli Weiner-Smith a Harrison (pro obvody typu D) [19]: A2 =
(2s )! (2s − r)!s!
V n´asleduj´ıc´ı tabulce 3.1 je vidˇet, kolik r˚ uzn´ ych k´odov´an´ı stav˚ u m˚ uˇzeme dos´ahnout [19]. 11
´ cinnost metod k´odov´an´ı stav˚ Uˇ u
K´odov´an´ı stav˚ u logick´ych automat˚ u
Tabulka 3.1: Poˇcet r˚ uzn´ ych k´odov´an´ı
3.2
´ cinnost metod k´ Uˇ odov´ an´ı stav˚ u
Pro porovn´av´an´ı metod k´odov´an´ı stav˚ u je potˇreba urˇcit metriku, podle kter´e budeme porovn´avat jednotliv´e metody. Tˇri z´akladn´ı zp˚ usoby porovn´av´an´ı u ´ˇcinnosti metod jsou: • efektivita z hlediska v´ ypoˇcetn´ı sloˇzitosti (v´ ysledek v re´aln´em ˇcase, sloˇzitost algoritmu), • minim´aln´ı plocha (tzn. nejmenˇs´ı poˇcet souˇca´stek potˇrebn´ ych pro dan´ y automat), • nejmenˇs´ı cena (tzn. nejmenˇs´ı poˇcet vstupn´ıch ˇclen˚ u). V t´eto pr´aci bude vyuˇz´ıv´an pouze tˇret´ı zp˚ usob porovn´av´an´ı (nejmenˇs´ı cena). To znamen´a, ˇze bude poˇc´ıt´an poˇcet vstup˚ u do logick´eho ˇclenu AND a poˇcet vstup˚ u do logick´ ych ˇclenu OR. Souˇcet tˇechto vstupn´ıch ˇclen˚ u bude pro jednoduchost oznaˇcov´an jako cena obvodu“. ”
12
K´odov´an´ı stav˚ u logick´ych automat˚ u
3.3
Z´akladn´ı metody k´odov´an´ı
Z´ akladn´ı metody k´ odov´ an´ı
Tyto metody nerespektuj´ı strukturu automatu (tzn. neberou v u ´vahu n´asleduj´ıc´ı stavy, pˇredchoz´ı stavy ani pˇrechody stav˚ u), a proto m˚ uˇze b´ yt toto k´odov´an´ı velmi neefektivn´ı z hlediska ceny obvodu (viz kapitola 6 V´ ysledky k´ odov´ an´ı). Na druhou stranu nejsou algoritmicky n´aroˇcn´e.
3.3.1
Bin´ arn´ı k´ odov´ an´ı
Bin´arn´ı k´odov´an´ı pracuje na principu oˇc´ıslov´an´ı jednotliv´ ych stav˚ u tak, jak jsou na ˇc´ıseln´e ose. Kaˇzd´ y stav je reprezentov´an jedn´ım ˇc´ıslem v bin´arn´ı podobˇe (obr´azek 3.1). V´ yhodou tohoto k´odov´an´ı je kromˇe rychlosti i minim´aln´ı d´elka slova potˇrebn´a pro zak´odov´an´ı automatu. Poˇcet potˇrebn´ ych bit˚ u odpov´ıd´a dlog2 N e, kde N je poˇcet stav˚ u koneˇcn´eho automatu [12].
Obr´azek 3.1: Bin´arn´ı k´odov´an´ı
3.3.2
Grayovo k´ odov´ an´ı
Gray˚ uv k´od je specifick´ y t´ım, ˇze se dvˇe sousedn´ı slova (stavy) liˇs´ı pouze v jednom bitu (tj. jejich Hammingova vzd´alenost se rovn´a 1). Pouˇzit´ı tohoto k´odov´an´ı pro nˇekter´e obecn´e automaty m˚ uˇze znamenat, ˇze nebudeme m´ıt minim´aln´ı poˇcet pamˇet’ov´ ych prvk˚ u. Uk´azka Grayova k´odov´an´ı je na obr´azku 3.2 [14].
13
K´odov´an´ı stav˚ u logick´ych automat˚ u
Z´akladn´ı metody k´odov´an´ı
Obr´azek 3.2: Grayovo k´odov´an´ı
3.3.3
One-hot k´ odov´ an´ı
One-hot k´odov´an´ı pˇriˇrazuje kaˇzd´emu stavu pr´avˇe jednu logickou 1 v bin´arn´ım ˇretˇezci o d´elce odpov´ıdaj´ıc´ı poˇctu stav˚ u. V´ yhodou tohoto k´odov´an´ı je, ˇze Hammingova vzd´alenost se rovn´a 2 mezi libovoln´ ymi dvˇema stavy koneˇcn´eho automatu (obr´azek 3.3). D´ıky t´eto vlastnosti je tento k´od vhodn´ y pro rozs´ahl´e automaty s mnoha stavy (v praxi s v´ıce neˇz osmi). Nev´ yhodou je velk´ y poˇcet klopn´ ych obvod˚ u, potˇrebn´ ych pro realizaci obvodu (poˇcet KO se rovn´a poˇctu stav˚ u dan´eho automatu). Nˇekdy se pro zmenˇsen´ı celkov´e vzd´alenosti mezi stavy (tedy pˇrep´ınac´ı“ aktivitou, switching activity) pouˇz´ıv´a jako poˇc´ateˇcn´ı ” stav ˇretˇezec obsahuj´ıc´ı sam´e 0, coˇz umoˇzn ˇuje nejen zkr´atit ˇretˇez o jeden bit, ale tak´e sn´ıˇz´ı Hammingovu vzd´alenost na 1 mezi prvn´ım stavem a libovoln´ ym stavem [13] .
Obr´azek 3.3: One-hot k´odov´an´ı
3.3.4
2-hot k´ odov´ an´ı
2-hot k´odov´an´ı je specifick´a varianta m-n k´ odov´ an´ı. Je tedy moˇzn´e zak´odon vat 2 stav˚ u, v optim´aln´ım pˇr´ıpadˇe je moˇzn´e udrˇzet Hammingovu vzd´alenost 14
K´odov´an´ı stav˚ u logick´ych automat˚ u
Z´akladn´ı metody k´odov´an´ı
mezi vˇsemi pˇrechody na vzd´alenosti 2 (obr´azek 3.4) [10].
Obr´azek 3.4: 2-hot k´odov´an´ı
3.3.5
Zero-hot k´ odov´ an´ı
Jak jiˇz n´azev napov´ıd´a, nejedn´a se o nic jin´eho, neˇz opaˇcn´e k´odov´an´ı k onehot, tj. m´ısto logick´e 1 urˇcuje stav logick´a 0 mezi jedniˇckami (obr´azek 3.5). Stejnˇe jako u one-hot je moˇzn´e zmenˇsit d´elku slova pouˇzit´ım sam´ ych 1 jako startovn´ıho stavu [10].
Obr´azek 3.5: Zero-hot k´odov´an´ı
3.3.6
Johnsonovo k´ odov´ an´ı
Pro zak´odov´an´ı je potˇreba q = d N2 e bit˚ u, kde N je poˇcet stav˚ u automatu. Prvn´ı stav je zak´odov´an bin´arn´ı k´odem 0. U dalˇs´ıch stav˚ u se od konce slova postupnˇe mˇen´ı 0 na 1 do doby, neˇz slovo obsahuje sam´e jedniˇcky. U zb´ yvaj´ıc´ıch stav˚ u se obdobnˇe mˇen´ı jedniˇcky na nuly (obr´azek 3.6). N´asleduj´ıc´ı
15
K´odov´an´ı stav˚ u logick´ych automat˚ u
Z´akladn´ı metody k´odov´an´ı
stavy v tabulce za sebou se opˇet liˇs´ı jedn´ım bitem (tzn. ˇze jejich Hammingova vzd´alenost je rovn´a 1) [15]. Jedn´a se tedy o upravenou variantu Grayova k´odu.
Obr´azek 3.6: Johnsonovo k´odov´an´ı
3.3.7
K´ odov´ an´ı m-n
Toto k´odov´an´ı vyˇzaduje d´elku slova n a poˇcet logick´ ych 1, kter´e jsou ve slovˇe obsaˇzeny, je m. Jednotliv´e k´ody jsou permutacemi slova obsahuj´ıc´ıho n jedniˇcek a (m-n) nul. Parametry m a n mus´ı b´ yt zvoleny tak, aby jimi bylo moˇzn´e vˇsechny stavy pokr´ yt (obr´azek 3.7). Maxim´ aln´ı poˇcet stav˚ u, kter´e lze m zak´odovat, odpov´ ıd´a kombinaˇcn´ımu ˇc´ıslu n , proto m a n mus´ı b´ yt zvoleno m tak, aby n ≥ N [10].
Obr´azek 3.7: K´odov´an´ı m-n
3.3.8
N´ ahodn´ e k´ odov´ an´ı
Z n´azvu je zˇrejm´e, ˇze toto k´odov´an´ı se neˇr´ıd´ı ˇza´dn´ ymi pravidly (obr´azek 3.8). s D´elka stavu se ˇr´ıd´ı podle vztahu 2 ≥ r, kde s je poˇcet bit˚ u (d´elka stavu) a 16
K´odov´an´ı stav˚ u logick´ych automat˚ u
Pokroˇcil´e metody k´odov´an´ı
r je celkov´ y poˇcet stav˚ u koneˇcn´eho automatu [10].
Obr´azek 3.8: N´ahodn´e k´odov´an´ı
3.3.9
Metoda postupn´ eho proch´ azen´ı
Tato metoda postupnˇe vyzkouˇs´ı vˇsechny moˇzn´e kombinace bin´arn´ıch k´od˚ u (viz kapitola 5.1 Poˇ cet r˚ uzn´ ych k´ odov´ an´ı ). Pro kaˇzd´ y pˇr´ıpad vypoˇc´ıt´a cenovou n´aroˇcnost obvodu a zapamatuje si nejlepˇs´ı ˇreˇsen´ı, kter´ ym pot´e zak´oduje koneˇcn´ y stavov´ y automat. Vzhledem k ˇcasov´e sloˇzitosti je metoda urˇcena pouze pro automaty s mal´ ym poˇctem stav˚ u (do osmi stav˚ u) [15].
3.4
Pokroˇ cil´ e metody k´ odov´ an´ı
Nalezen´ı nejlepˇs´ıho stavov´eho pˇriˇrazen´ı synchronn´ıho obvodu je d˚ uleˇzit´e pˇri sniˇzov´an´ı ceny a sloˇzitosti obvodu v automatech. Tento probl´em SAP (State Assignment Problem, nalezen´ı souvislosti mezi stavy a k´odov´an´ım) patˇr´ı do ˇsirˇs´ı skupiny kombinatorick´ ych optimalizaˇcn´ıch probl´em˚ u a z´aroveˇ n patˇr´ı do skupiny NP-´ upln´ y [3]. Pro vˇsechny druhy k´odov´an´ı plat´ı obecn´ y postup pro pˇriˇrazen´ı bin´arn´ıch k´od˚ u stav˚ um (obr´azek 3.9) [11]: 1. ze stavov´e tabulky urˇc´ıme ekvivalentn´ı stavy a provedeme eliminaci redundantn´ıch stav˚ u, 2. k´odujeme vˇsechny stavy unik´atn´ım bin´arn´ım k´odem,
17
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
3. pouˇzijeme nevyuˇzit´e bin´arn´ı k´ody pro neurˇcit´e stavy (pouze v pˇr´ıpadˇe , ˇze ve f´azi zjednoduˇsov´an´ı funkce se uk´aˇz´ı jako uˇziteˇcn´e).
Obr´azek 3.9: Obecn´ y postup pro k´odov´an´ı stav˚ u Mezi pokroˇcil´e metody k´odov´an´ı ˇrad´ıme: • heuristick´e algoritmy (napˇr´ıklad MUSTANG, DAG), • genetick´e algoritmy (jsou srovnateln´e nebo lepˇs´ı neˇz heuristick´e algoritmy).
3.5
Heuristick´ e algoritmy
Heuristick´e algoritmy maj´ı dva hlavn´ı c´ıle. Nal´ezt algoritmus, kter´ y • nalezne v´ ysledek v re´aln´em ˇcase, • povede alespoˇ n k dobr´emu v´ ysledku. . Heuristick´ ych algoritm˚ u je cel´a ˇrada a vˇetˇsina metod jsou varianty tˇechto bod˚ u: 18
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
• urˇcen´ı sousedn´ıch stav˚ u (v´aˇzen´ ych p´ar˚ u), • generov´an´ı omezuj´ıc´ıch podm´ınek (stavy, kter´e jsou ve stejn´e krychli), • maximalizovat poˇcet spoleˇcn´ ych krychl´ı (v´aˇzen´ y souˇcet).
3.5.1
DAG k´ odov´ an´ı
DAG je zkratka z anglick´eho slova The Desired Adjacency Graph, neboli graf sousednosti[3]. DAG je neorientovan´ y, v´aˇzen´ y, plnˇe propojen´ y graf, kter´ y m´a jako uzly stavy z FSM. Pro n´ızk´e n´aklady na cenu obvodu je nutn´e, aby se minimalizovala vzd´alenost mezi stavy, kter´e jsou pevnˇe spojeny. Opˇet pro lepˇs´ı pochopen´ı je algoritmus vysvˇetlen na uk´azkov´em pˇr´ıkladu, kde obr´azek 3.10 m´am ukazuje pˇrechody mezi jednotliv´ ymi stavy a v´ ystupy, kter´e jsou pˇriˇrazeny kaˇzd´emu stavu:
Obr´azek 3.10: Pˇr´ıklad stavov´e tabulky Postup pro vytvoˇren´ı DAG k´odov´an´ı je n´asleduj´ıc´ı: 1.krok : Vytvoˇr´ıme si mnoˇzinu n´asledn´ık˚ u (z obr´azku 3.10). Pozn.: zapisujeme pouze mnoˇziny, kter´e maj´ı 2 nebo v´ıce n´asledn´ık˚ u. S(S0 ) = S1 , S2 S(S1 ) = S3 , S4 S(S2 ) = S3 , S4 Z t´eto mnoˇziny vytvoˇr´ıme doln´ı troj´ uheln´ıkovou matici n´asledn´ık˚ u. Zaˇc´ın´ame nulami, kter´e jsou pˇriˇrazeny vˇsem hran´am. Hranˇe (Sa , Sb ) pˇripoˇc´ıt´av´ame 1, jestliˇze Sa a Sb jsou prvky mnoˇziny n´asledn´ık˚ u. T´ımto vznikne Graf sousednosti (DAG) n´ asledn´ık˚ u (obr´azek 3.11). 19
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
2.krok: Vytvoˇr´ıme si mnoˇzinu pˇredch˚ udc˚ u (z p˚ uvodn´ıho obr´azku 3.10). P(S4 , I0 = 0) = S1 , S2 , S3 P(S3 , I1 = 1) = S1 , S2
Obr´azek 3.11: Graf sousednosti (DAG) n´asledn´ık˚ u Jako v pˇredchoz´ım kroku, opˇet vytvoˇr´ıme doln´ı troj´ uheln´ıkovou matici, tentokr´at matici pˇredch˚ udc˚ u. Zaˇc´ın´ame nulami, kter´e jsou pˇriˇrazeny vˇsem hran´am. Hranˇe (Sa , Sb ) pˇripoˇc´ıt´ame 1, jestliˇze Sa a Sb jsou prvkem mnoˇziny pˇredch˚ udc˚ u stavu. Vznikne Graf sousednosti (DAG) pˇ redch˚ udc˚ u (obr´azek 3.12).
Obr´azek 3.12: Graf sousednosti (DAG) pˇredch˚ udc˚ u 3.krok: Vytvoˇr´ıme si mnoˇzinu v´ystup˚ u. O(Z0 ) = (S0 , S3 , S4 ), (S1 , S2 ) O(Z1 ) = (S0 , S2 , S4 ), (S1 , S3 ) Pozn.: Stavy, kter´e maj´ı ve sloupci Z0 v´ystup 0, jsou v prvn´ı mnoˇzinˇe z´avorek. Stavy, jejichˇz v´ystup ve sloupci Z0 je 1, jsou v druh´e mnoˇzinˇe z´avorek. Stejn´ymi kroky postupujeme i pro v´ystup Z1 . Z t´eto mnoˇziny vytvoˇr´ıme doln´ı troj´ uheln´ıkovou matici v´ ystup˚ u. Zaˇc´ın´ame nulami, kter´e jsou pˇriˇrazeny vˇsem hran´am. Hranˇe (Sa , Sb ) pˇripoˇc´ıt´a20
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
v´ame 1, jestliˇze Sa a Sb jsou prvky mnoˇziny n´asledn´ık˚ u. T´ımto vznikne Graf sousednosti (DAG) v´ ystup˚ u (obr´azek 3.13).
Obr´azek 3.13: Graf sousednosti (DAG) v´ ystup˚ u 4.krok: Vytvoˇr´ıme si posledn´ı matici: matici pˇrechod˚ u. Zaˇc´ın´ame nulami, kter´e jsou pˇriˇrazeny vˇsem hran´am. Hranˇe (Sa , Sb ) pˇripoˇc´ıt´av´ame 1, jestliˇze existuje hrana vedouc´ı z Sa do Sb (obr´azek 3.14).
Obr´azek 3.14: Graf sousednosti (DAG) pˇrechod˚ u 5.krok: V tomto kroku spoj´ıme vˇsechny matice z pˇredchoz´ıch krok˚ u. Ovˇsem kaˇzd´a matice m´a jinou v´ahu, kterou urˇcil Amaral v roce 1990 [2]. DAG = 3*n´asledn´ık + 4*pˇredch˚ udce + 2*v´ ystupn´ı + 1*pˇrechody Tyto v´ahy v jist´e m´ıˇre ovlivˇ nuj´ı v´ ysledn´e k´odov´an´ı. Proto tyto konstanty byly zmˇenˇeny a porovn´any (viz kapitola Z´avˇer). Algoritmus byl tedy rozˇs´ıˇren na: • DAG1 = 1*n´asledn´ık + 1*pˇredch˚ udce + 1*v´ ystupn´ı + 1*pˇrechody • DAG2 = 2*n´asledn´ık + 1*pˇredch˚ udce + 3*v´ ystupn´ı + 4*pˇrechody • DAG3 = 4*n´asledn´ık + 3*pˇredch˚ udce + 1*v´ ystupn´ı + 2*pˇrechody • DAG4 = 2*n´asledn´ık + 2*pˇredch˚ udce + 1*v´ ystupn´ı + 1*pˇrechody 21
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
Po vyn´asoben´ı (p˚ uvodn´ımi konstantami) a seˇcten´ı matic n´am vznikne koneˇ cn´ a matice grafu sousednosti DAG (obr´azek 3.15).
Obr´azek 3.15: Koneˇcn´a matice grafu sousednosti DAG 6.krok: Z koneˇcn´e matice DAG (obr´azek 3.15) vypoˇc´ıt´ame v´ahu stavu Sa seˇcten´ım hodnot pˇriˇrazen´ ym hran´am (Sa , S? ). Z´ıskan´ y v´ahov´ y vektor vyjadˇruje, kter´emu stavu m´a b´ yt d´ana v procesu k´odov´an´ı pˇrednost. Tento krok zopakujeme pro vˇsechny stavy. 7.krok: Pokud jiˇz m´ame urˇcen´e v´ahy kaˇzd´eho stavu, n´asleduje vybr´an´ı stavu s nejvˇetˇs´ı v´ahou a pˇridˇelen´ı tomuto stavu k´od v bin´arn´ı hodnotˇe 0. M˚ uˇze se ovˇsem st´at, ˇze dojde ke shodˇe maxim´aln´ıch vah. V tomto pˇr´ıpadˇe budeme hledat maxim´aln´ı hodnotu v matici DAG (obr´azek 3.15) u shodn´ ych vah stav˚ u. 8.krok: Kdyˇz jiˇz m´ame pˇridˇelen´ y bin´arn´ı k´od 0, nalezneme stav s nejsilnˇejˇs´ı vazbou k prv´emu stavu a pˇridˇel´ıme bin´arn´ı k´od 1. 9.krok: D´ale vytvoˇr´ıme z obr´azku 3.16 ne´ uplnou tabulkou pˇ riˇ razen´ı (IAT). Kaˇzd´a buˇ nka tabulky obsahuje hodnotu, kter´a se poˇc´ıt´a podle vztahu: Ps−1 Ps−1 i=0 j=0 D(Si , Sj )DAGij Hodnota buˇ nky (S0 , S2 ) tedy je: D(S0 , S1 )DAG01 + D(S0 , S2 )DAG02 = = D(010, 001)DAG01 + D(010, 000)DAG02 = = 2×1+1×3 = 2 + 3 = 5 Pozn.: Pozici DAG01 vybereme z tabulky DAG (obr´azek 3.15), pozice D(010, 001) je hodnota z tabulky vzd´alenosti prvk˚ u bin´arn´ıho k´odu (obr´azek 3.16), neboli Hammingova vzd´alenost.
22
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
Obr´azek 3.16: Vzd´alenost prvk˚ u bin´arn´ıho k´odu Hodnoty v ostatn´ıch pol´ıch se poˇc´ıtaj´ı obdobnˇe (tabulka 3.2). Po vyplnˇen´ı ne´ upln´e tabulky seˇcteme hodnoty v kaˇzd´e ˇr´adce. Stav, kter´ y vykazuje nejvˇetˇs´ı sumu v tabulce, nejv´ıce pˇrisp´ıv´a k cenˇe. Proto by mˇel b´ yt k´odov´an prioritnˇe. V ne´ upln´e tabulce pˇriˇrazen´ı hled´ame ˇr´adku s maxim´aln´ım ˇr´adkov´ ym souˇctem a vybereme buˇ nku s minim´aln´ı vahou. Pokud v tomto kroku nastane rovnost, vybereme n´ahodnˇe. Tabulka 3.2: Ne´ upln´a tabulka pˇriˇrazen´ı
9.krok: Nyn´ı zaˇcneme poˇc´ıtat ne´ uplnou tabulku pˇriˇrazen´ı od zaˇc´atku pro nezak´odovan´e stavy. Takto postupujeme dokud nezak´odujeme vˇsechny stavy (obr´azek 3.17).
3.5.2
Output-Based encoding (V´ ystupn´ı k´ odov´ an´ı)
Tento druh k´odov´an´ı spoˇc´ıv´a v jednoduch´em principu. K pˇriˇrazen´ı k´odu stav˚ um vyuˇz´ıv´a jejich v´ ystupy. Nicm´enˇe m˚ uˇze b´ yt automat, kter´ y m´a stejn´ y v´ ystup pro dva nebo v´ıce stav˚ u (viz obr´azek 2.3). Kaˇzd´ y stav mus´ı b´ yt zak´odov´an jinou hodnotou, proto algoritmus pˇrid´a dalˇs´ı bit (pro dva stejn´e v´ ystupy). Prvn´ımu stavu se pˇrid´a nejvyˇsˇs´ı bit 0 a druh´emu stavu pˇriˇrad´ıme 1. Pokud tedy budeme m´ıt stavy S0 , S4 a hodnota jejich v´ ystupu je 00. Tyto stavy zak´odujeme bin´arn´ım k´odem 000 pro stav S0 a 100 pro stav S4 [16]. 23
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
Obr´azek 3.17: Kodov´an´ı stav˚ u podle DAG
3.5.3
TOOL1
Toto k´odov´an´ı se ˇr´ıd´ı podle dvou pravidel. Ta urˇcuj´ı, kter´e stavy se budou liˇsit pouze v jednou bitu (nebo-li jejich Hammingova vzd´alenost bude rovna jedn´e) [13]: 1. Stavy, kter´e maj´ı spoleˇcn´e n´asledn´ıky (nebo-li dalˇs´ı stavy). Pˇr´ıklad je uveden na obr´azku 3.18, kde stavy state a a state b budou m´ıt Hammingovu vzd´alenost rovnou 1. 2. N´asledn´ıci, kteˇr´ı maj´ı stejn´ y p˚ uvodn´ı stav. Na obr´azku 3.19 to jsou stavy state a a state b. Tato pravidla n´am vytvoˇr´ı tzv. omezuj´ıc´ı matici. Kaˇzd´emu omezen´ı (1.pravidlo a 2.pravidlo) je pˇriˇrazen faktor hmotnosti, kter´ y urˇcuje, jak´emu pravidlu je d´ana pˇrednost. Nakonec je vybr´ano k´odov´an´ı, kter´e nejl´epe odpov´ıd´a tˇemto heuristick´ ym pravidl˚ um [13].
Obr´azek 3.18: 1. pravidlo
24
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
Obr´azek 3.19: 2. pravidlo
3.5.4
TOOL2
Tento druh k´odov´an´ı je rozˇs´ıˇren´ı metody TOOL1. TOOL2 m´a celkem 4 pravidla, podle kter´ ych se k´oduj´ı stavy automat˚ u [13]: 1. totoˇzn´e s 1.pravidlem metody TOOL1, 2. totoˇzn´e s 2.pravidlem metody TOOL1, 3. stavy se spoleˇcn´ ymi podm´ınˇen´ ymi v´ ystupy soused´ı pouze v pˇr´ıpadˇe, kdyˇz v´ ystupy jsou podm´ınˇeny stejn´ ym vstupem (obr´azek 3.20), 4. stavy se spoleˇcn´ ymi nepodm´ınˇen´ ymi v´ ystupy soused´ı pouze v pˇr´ıpadˇe, kdyˇz nastane situace z obr´azku 3.21. Pozn: • podm´ınˇ en´ y v´ ystup - v´ ystup, kter´ y je z´avisl´ y na souˇcasn´em stavu a aktu´aln´ı vstupn´ı kombinaci, • nepodm´ınˇ en´ y v´ ystup - z´avis´ı pouze na souˇcasn´em stavu. Jak jiˇz bylo uvedeno v metodˇe TOOL1, kaˇzd´a podm´ınka m´a sv˚ uj hmotnostn´ı faktor. Podm´ınka 3 a 4 by mˇela m´ıt vˇetˇs´ı prioritu, a proto vˇetˇs´ı hmotnostn´ı faktor. Tyto podm´ınky slouˇz´ı pro vytvoˇren´ı podm´ınkov´e matice, kter´a slouˇz´ı pro vybr´an´ı vhodn´eho k´odov´an´ı stav˚ u [13].
25
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
Obr´azek 3.20: 3. pravidlo
Obr´azek 3.21: 4. pravidlo
3.5.5
Mustang
Tato k´odovac´ı technika je zaloˇzena na minimalizaci spoleˇcn´e krychle. C´ılem algoritmu je naj´ıt k´odov´an´ı, kter´e maximalizuje poˇcet spoleˇcn´ ych krychl´ı. Dˇr´ıve neˇz bude uveden postup algoritmu Mustang [8], je potˇreba sezn´amit se s nˇekolika pojmy: Symbolick´ y implikant: pˇredstavuje pˇrechod od jednoho nebo v´ıce stav˚ u do dalˇs´ıho stavu podle vstup˚ u. Stavov´ a skupina: seskupen´ı stav˚ u, kter´e maj´ı stejn´e vstupy a stejn´e n´asledn´ıky. Krychle: pokud stavovou skupinu zak´odujeme bin´arn´ım k´odem tak, ˇze vˇsechny stavy ze stavov´e skupiny se budou liˇsit pouze v jednom bitu, pak tato skupina m˚ uˇze b´ yt realizov´ana jako krychle. FSM (koneˇcn´ y stavov´ y automat) je zde reprezentov´an dvˇema rovnocenn´ ymi strukturami: 1. Graf pˇrechodov´ ych stav˚ u G(V, E, W(E)), kde V je mnoˇzina vrchol˚ u 26
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
odpov´ıdaj´ıc´ı vˇsem stav˚ um, || E ||= Ns mohutnosti stav˚ u FSM hrany vi , vj a W (E) je sada popisk˚ u kaˇzd´e hrany, kaˇzd´ y popisek nese informaci o hodnotˇe vstupu. 2. Pˇrechodov´a stavov´a tabulka T(I, S, O), kde I jsou vstupy, S oznaˇcuje sadu stav˚ u a O jsou v´ ystupy. Tabulka m´a tolik ˇra´dk˚ u jako hran stavov´eho grafu a tolik sloupc˚ u jako Ni + No + 2, kde Ni je poˇcet bit˚ u pro zak´odov´an´ı vstup˚ u a No poˇcet bit˚ u pro zak´odov´an´ı v´ ystup˚ u.
Glob´ aln´ı strategie algoritmu Mustang Naˇs´ım c´ılem je vybudovat graf GM (V, EM , W (EM )), kde V je komunikace mezi stavy FSM, EM je kompletn´ı sada hran (kaˇzd´ y uzel je spojen ve vˇsemi uzly v FSM) a W (EM ) pˇredstavuje zisky, kter´e jsou dosaˇzeny t´ım, ˇze k´odov´an´ı vˇsech stav˚ u m´a co nejmenˇs´ı Hammingovu vzd´alenost (tyto zisky jsou nez´avisle vypoˇc´ıt´av´any z v´ yˇctu pˇr´ım´ ych vztah˚ u mezi vstupy, stavy a v´ ystupy). Algoritmus Mustang se vytvoˇr´ı pomoc´ı dvou struktur: 1. Fanout-oriented: maximalizuje velikost nejˇcastˇejˇs´ıch krychl´ı pˇred optimalizac´ı. 2. Fanin-oriented: maximalizuje poˇcet v´ yskyt˚ u nejvˇetˇs´ıch spoleˇcn´ ych krychl´ı pˇred optimalizac´ı.
Fanout-oriented algoritmus Algoritmus sestav´ı kompletn´ı graf GM (V, EM , W (EM )) s pr´azdnou hranovou vahou W (EM ). K t´eto v´aze pot´e pˇriˇc´ıt´ame konstanty (n nebo 1, kde n je poˇcet bit˚ u potˇrebn´ ych pro k´odov´an´ı). Pˇr´ıklad: pokud nastane situace z obr´azku 3.22, pˇriˇcteme k W (EM (S1, S3)) konstantu n, pokud budeme m´ıt stejn´ y v´ ystup j (viz obr´azek 3.23), pˇriˇcteme k W (EM (S1, S3)) konstantu 1. Pro vˇsechny ostatn´ı situace se v´ahy nemˇen´ı.
27
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
Obr´azek 3.22: 1.Fanout-orientovan´ y algoritmus
Obr´azek 3.23: 2.Fanout-orientovan´ y algoritmus Fanin-oriented algoritmus Jako algoritmus Fanout-oriented, bude Fanin-oriented algoritmus poˇc´ıtat hranov´e v´ahy. Pˇr´ıklad: k poˇc´ateˇcn´ı pr´azdn´e hranov´e v´aze se pˇriˇcte n/2 k W (EM (S2, S4)) (zn´azornˇeno na obr´azku 3.24) a konstanta 1 se pˇriˇcte pro W (EM (S2, S4)).
Obr´azek 3.24: 1.Fanin-orientovan´ y algoritmus
28
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
Obr´azek 3.25: 2.Fanin-orientovan´ y algoritmus Algoritmus vkl´ ad´ an´ı Algoritmus vkl´ad´an´ı pˇriˇrazuje skuteˇcn´e (bin´arn´ı) k´ody podle algoritmu Fanoutoriented a Fanin-oriented. Tento probl´em je klasick´a kombinatorick´a optimalizace, zvan´a vkl´adan´ı graf˚ u (graph embedding) GM (bude pops´an pseudok´odem n´ıˇze). GM mus´ı b´ yt vloˇzeno do booleovsk´e krychle tak, aby sousedn´ı stavy splˇ novaly heuristick´ y algoritmus wedge PNclusting. PNs Tento algoritmus s pouˇz´ıv´a k pˇriˇrazen´ı k´odu v GM minimalizaci i=0 j=i+1 we(eM (vi , vj )) ∗ dist(enc(vi ), (vj )), kde vk jsou vrcholy v GM , we(eM (vi , vj )) je v´aha hrany e mezi vrcholy vi a vj , enc(vk ) je k´odov´an´ı vrcholu a funkce dist() vrac´ı vzd´alenost mezi dvˇema bin´arn´ımi k´ody. Grafy generovan´e Fanout-oriented a Fanin-oriented algoritmem maj´ı urˇcitou strukturu. V tˇechto grafech jsou mal´e skupiny stav˚ u, kter´e jsou pevnˇe propojeny, tzn. internˇe (hrany mezi stavy ve stejn´e skupinˇe a vyznaˇcuj´ı se velkou v´ahou) a stavy, kter´e jsou pˇripojeni slabˇe, tzn. externˇe (hrany mezi stavy, kter´e nejsou ve stejn´e skupinˇe a vyznaˇcuj´ı se n´ızkou v´ahou). Heuristika vyuˇz´ıv´a povahu grafu t´ım, ˇze se pokouˇs´ı naj´ıt jeho uskupen´ı, a podle vah pˇriˇrad´ı stav˚ um v r´amci kaˇzd´e skupiny jedineˇcn´ y k´od. Algoritmus vkl´ad´an´ı prob´ıh´a n´asleduj´ıc´ım zp˚ usobem (pops´ano pseudok´odem): GG = GM while (GG nen´ı pr´azdn´y) { zvolte vl ∈ GG, yi ∈ GG tak
PNb
i=l
we(eM (vl , vi )) bylo maximum
zak´odujte yi a vl nevyuˇzit´ymi k´ody s minim´aln´ı vzd´alenost´ı k´od˚ u GG = GG = vl }
29
K´odov´an´ı stav˚ u logick´ych automat˚ u
Heuristick´e algoritmy
Algoritmus vkl´ad´an´ı zn´azorn´ıme na obr´azku 3.26 pomoc´ı 5 stav˚ u, kter´e maj´ı b´ yt k´odov´any pomoc´ı 3 bit˚ u. Pro zaˇca´tek si zvol´ıme jeden stav napˇr. st3. Tento stav m´a 3 hrany vedouc´ı ke stav˚ um st0, st1, st2 (hrana ke stavu st4 m´a nulovou v´ahu, proto se do grafu nezapoˇc´ıt´av´a). Stav st3 zak´odujeme nejniˇzˇs´ım bin´arn´ım k´odem 000. Ostatn´ı stavy budeme k´odovat tak, aby mˇely Hammingovu vzd´alenost rovnou 1 od stavu st3. Pro zak´odov´an´ı stavu st4 si uprav´ıme graf (obr´azek 3.27). Zjist´ıme, ˇze stav st4 m´a hrany ke stav˚ u st0, st1,st2. Proto stav st4 zak´odujeme tak, aby jeho Hammingova vzd´alenost byla 1 od stav˚ u st0, st1,st2.
Obr´azek 3.26: a) Pˇr´ıklad algoritmu vkl´ad´an´ı
Obr´azek 3.27: b) Pˇr´ıklad algoritmu vkl´ad´an´ı
3.5.6
Genetick´ e algoritmy
GA (genetick´e algoritmy) se snaˇz´ı pomoc´ı evoluˇcn´ıho principu biologie nal´ezt ˇreˇsen´ı sloˇzit´ ych probl´em˚ u. Tyto algoritmy jsou zaloˇzeny na dˇediˇcnosti, mutaci, pˇrirozen´eho v´ ybˇeru a kˇr´ıˇzen´ı [1]. Obecn´ y postup pro k´odov´an´ı stav˚ u GA je, ˇze zaˇcneme s populac´ı n´ahodn´ ych jedinc˚ u, kteˇr´ı jsou vybr´ani pro pouˇzit´ı kˇr´ıˇzen´ı (2 rodiˇce vygeneruj´ı potomka). Mutace n´ahodnˇe pˇrenese informace na potomka, kter´e se zpˇet vloˇz´ı do populace. Kdyˇz populace dos´ahne dan´e velikosti (obvykle dvakr´at oproti p˚ uvodn´ı), je dokonˇcena jedna generace. Pro sn´ıˇzen´ı velikosti populace (do p˚ uvodn´ı) se pouˇzije v´ ybˇerov´e ˇr´ızen´ı a opˇet m˚ uˇze zaˇc´ıt nov´a generace. Vˇsechny v´ ybˇery se prov´ad´ı podle pravdˇepodobnosti a vhodnosti kaˇzd´eho jednotlivce. Nˇekter´e u ´vahy proveden´e Whitley jsou platn´e i pro SAP [3]. 30
4 Implementace k´odovac´ıho algoritmu DAG Praktick´a ˇca´st t´eto pr´ace se zab´ yv´a v´ yvojem programu, kter´ y umoˇzn ˇuje zak´odovat stavy v´ yˇse uveden´ ymi metodami. Jeho v´ ystup byl pouˇzit pro srovn´an´ı ceny obvod˚ u testovan´ ych automat˚ u. Pro rychl´ y a snadn´ y v´ yvoj bylo vyuˇzito programovac´ıho jazyka C] a v´ yvojov´eho prostˇred´ı Microsoft Visual Studio 2010. Metoda DAG je algoritmicky n´aroˇcnˇejˇs´ı neˇz ostatn´ı metody, kter´e byly vyuˇzity pro porovn´av´an´ı cen obvod˚ u. Proto k´odov´an´ı stav˚ u metodou DAG bylo naprogramov´ano, u ostatn´ıch metod bylo k´odov´an´ı stav˚ u provedeno ruˇcnˇe.
4.1
Tˇ r´ıda Stav
Tato tˇr´ıda uchov´av´a informace o jednotliv´ ych stavech a obsahuje priv´atn´ı promˇenn´e: • n´azev stavu (p˚ uvodn´ı stav), • n´asleduj´ıc´ı stavy, • v´ ystupy.
4.1.1
Metoda ToString
Data pro tento program jsou zad´ana v textov´em souboru jako sada znak˚ u. Tyto znaky je tˇreba separovat a zaˇradit do pˇr´ısluˇsn´ ych pol´ı. Prvn´ı znak ˇr´adku je vˇzdy p˚ uvodn´ı stav, kter´ y je oddˇelen od n´asleduj´ıc´ıch stav˚ u znakem ; ” “. N´asleduj´ıc´ı stavy se mezi sebou oddˇeluj´ı znakem , “. Mezi posledn´ım ” n´asleduj´ıc´ım stavem a v´ ystupem je znak ; “. Konec ˇra´dky je znaˇcen ; “. ” ” T´ımto zp˚ usobem n´am vzniknou pole pro p˚ uvodn´ı stavy, n´asleduj´ıc´ı stavy a pole v´ ystupu, se kter´ ymi budeme d´ale pracovat.
31
Implementace k´odovac´ıho algoritmu DAG
4.2
Tˇr´ıda StavovaTrida
Tˇ r´ıda StavovaTrida
Stavov´a tˇr´ıda obsahuje priv´atn´ı promˇenn´e: • pole vˇsech p˚ uvodn´ıch stav˚ u • mocnina (urˇcuje kolik bit˚ u bude potˇreba k zak´odov´an´ı stav˚ u) V t´eto tˇr´ıdˇe najdeme vˇsechny metody pouˇz´ıvan´e pro v´ ypoˇcet matic, kter´e potˇrebujeme k urˇcen´ı k´odu stav˚ u.
4.2.1
Metoda VypoctiMaticiVystupu
Matice v´ ystupu se z´ısk´a z mnoˇziny v´ ystupn´ıch odd´ıl˚ u. Ty z´ısk´ame tak, ˇze z kaˇzd´eho v´ ystupu vezmeme prvn´ı bit, pokud se rovn´a 0 zap´ıˇseme do prvn´ıho pomocn´eho pole odpov´ıdaj´ıc´ı p˚ uvodn´ı stav. Pokud se rovn´a 1 zap´ıˇseme odpov´ıdaj´ıc´ı stav do druh´eho pomocn´eho pole. Tyto mnoˇziny pot´e zap´ıˇseme do matice v´ ystup˚ u pomoc´ı jedniˇcek pro dan´e indexy.
4.2.2
Metoda VypoctiMaticiNasledniku
Tato metoda si vytvoˇr´ı vazby mezi n´asleduj´ıc´ımi stavy dan´eho p˚ uvodn´ıho stavu. A to tak, ˇze postupnˇe projde vˇsechny p˚ uvodn´ı stavy, zjist´ı vˇsechny jejich n´asledn´ıky, a pokud n´asledn´ık nen´ı obsaˇzen v dan´e mnoˇzinˇe, zap´ıˇse se do mnoˇziny n´asleduj´ıc´ıch stav˚ u. Tyto mnoˇziny se pot´e zap´ıˇsou do matice n´asledn´ıku, tzn. do matice se na dan´ y index pˇriˇcte jedniˇcka.
4.2.3
Metoda VypoctiMaticiPredchudcu
Matici pˇredch˚ udc˚ u vytvoˇr´ı metoda tak, ˇze projde postupnˇe vˇsechny n´asleduj´ıc´ı stavy a zjist´ı jejich p˚ uvodn´ı stavy, kter´e zap´ıˇse do pole pˇredch˚ udc˚ u. Prvky tohoto pole se zap´ıˇs´ı do matice stejn´ ym zp˚ usobem, jak tomu bylo u matice n´asledn´ık˚ u.
32
Implementace k´odovac´ıho algoritmu DAG
4.2.4
Tˇr´ıda StavovaTrida
Metoda VypoctiMaticiPrechodu
Zde si metoda vytvoˇr´ı vazby mezi p˚ uvodn´ımi stavy a n´asleduj´ıc´ımi stavy. Vezme si prvn´ı stav, zjist´ı jeho prvn´ıho n´asledn´ıka a pˇriˇcte jedniˇcku na dan´e m´ısto v matici. Vezme dalˇs´ı n´asleduj´ıc´ı stav (pokud nˇejak´ y je) a opˇet pˇriˇcte jedniˇcku. Takto postupuje dokud neprojde vˇsechny n´asleduj´ıc´ı stavy p˚ uvodn´ıho stavu. Tento postup opakuje pro vˇsechny stavy a zapisuje do jedn´e spoleˇcn´e matice
4.2.5
Metoda VypoctiMaticiDAG
Matice DAG se poˇc´ıt´a podle zadan´eho kl´ıˇce, kter´ y urˇcuje jakou hodnotou se budou n´asobit matice v´ ystup˚ u, matice pˇredch˚ udc˚ u, matice n´asledn´ık˚ u a matice pˇrechod˚ u. Kl´ıˇc˚ u je celkem 5 a podle v´ ybˇeru uˇzivatele se rozhodne, jak´e budou konstanty pro n´asoben´ı matic.
4.2.6
Metoda HammingovaVzdalenost
K zak´odov´an´ı vˇsech stav˚ u, potˇrebujeme urˇcit´ y poˇcet bit˚ u. Podle tohoto poˇctu metoda udˇel´a vˇsechny variace s opakov´an´ım pro prvky 0 a 1. D´ale se vytvoˇr´ı doln´ı troj´ uheln´ıkov´a matice a do n´ı se podle index˚ u zap´ıˇse, o kolik bit˚ u se navz´ajem liˇs´ı tyto variace. To se provede tak, ˇze kaˇzd´a variace se bude proch´azet bit po bitu a porovn´avat s ostatn´ımi prvky, pokud hodnota dan´ ych bit˚ u se bude liˇsit, pˇriˇcte 1 do matice vzd´alenost´ı.
4.2.7
Metoda VypoctiPoleVah
Metoda pracuje s hodnotami, kter´e m´a uloˇzen´e v matici DAG. Seˇcte ˇra´dku a sloupec pro dan´ y stav a uloˇz´ı si hodnotu do pole pod indexem dan´eho stavu. Takto projde vˇsechny p˚ uvodn´ı stavy a zap´ıˇse do pole, kter´e se na konci cyklu seˇrad´ı sestupnˇe podle hodnot. Stav, kter´ y m´a nejvyˇsˇs´ı hodnotu (na nult´e pozici v poli) je zak´odov´an bin´arn´ım ˇc´ıslem 0. Pokud se stane, ˇze nejvyˇsˇs´ı hodnota v poli nen´ı jedin´a, zjist´ı nejvˇetˇs´ı hodnoty z matice DAG pro tyto stavy s nejvyˇsˇs´ı v´ahou. Stav, kter´emu n´aleˇz´ı nejvˇetˇs´ı hodnota z matice DAG (a tak´e nejvyˇsˇs´ı v´aha v poli) je zak´odov´an bin´arn´ım ˇc´ıslem 0. D´ale projdeme vˇsechny buˇ nky matice DAG, kter´e n´aleˇz´ı tomu stavu (s bin´arn´ım k´odem 0), 33
Implementace k´odovac´ıho algoritmu DAG
Tˇr´ıda StavovaTrida
zjist´ıme nejvyˇsˇs´ı hodnotu a pozici v matici. Tato pozice n´am oznaˇc´ı dalˇs´ı stav, kter´ y budeme k´odovat bin´arn´ım k´odem 1.
4.2.8
Metoda TabulkaPrirazeni
ˇ adky matice jsou oznaMetoda pracuje s matic´ı DAG a matic´ı vzd´alenosti. R´ ˇceny indexy p˚ uvodn´ıch stav˚ u a sloupce jsou oznaˇceny bin´arn´ımi k´ody. Dva stavy v tuto chv´ıli jsou zak´odovan´e bin´arn´ım k´odem 0 a 1, proto prvn´ı dva sloupce se inicializuj´ı na nulu. Pˇr´ısluˇsn´e ˇr´adky, kter´e odpov´ıdaj´ı zak´odovan´ ym stav˚ um se tak´e inicializuj´ ı na nulu. nky tabulky obsahuj´ı hodP Ps−1Ostatn´ı buˇ notu, kter´a vych´az´ı ze vzorce s−1 D(S , S )DAG i j ij , kde D(Si , Sj ) jsou i=0 j=0 hodnoty z matice vzd´alenost´ı a DAGij jsou hodnoty z DAG matice. T´ımto zp˚ usobem metoda vypln´ı celou tabulku a seˇcte sumu jednotliv´ ych ˇra´dk˚ u. Zjist´ı, kter´e ˇra´dce patˇr´ı nejvˇetˇs´ı suma, v t´eto ˇra´dce pot´e najde nejmenˇs´ı hodˇ adka (s nejvˇetˇs´ı notu, kter´a odpov´ıd´a dan´emu sloupci s bin´arn´ı hodnotou. R´ sumou) urˇcila, jak´ y stav se bude k´odovat a sloupec (nejniˇzˇs´ı hodnota v ˇr´adce) urˇcil, jak´ ym k´odem se tento stav bude k´odovat. Pokud program nalezne v´ıce prvk˚ u s nejniˇzˇs´ı nebo nejvyˇsˇs´ı hodnotou, vybere vˇzdy prvn´ı nalezen´ y. Bin´arn´ı hodnotu stavu zap´ıˇseme do pole a vymaˇzeme vˇsechny hodnoty v tabulce pˇriˇrazen´ı. Metoda si inicializuje buˇ nky na nulu: za 1. pro ˇra´dky, kter´e odpov´ıdaj´ı jiˇz zak´odovan´ ym stav˚ um a za 2. pro sloupce, jejichˇz k´ody jiˇz byly pouˇzity. Tento proces se opakuje, dokud vˇsechny stavy nejsou zak´odov´any a uloˇzeny v poli.
34
5 Porovn´an´ı metod k´odov´an´ı Pro lepˇs´ı pˇrehlednost bude kaˇzd´ y druh k´odov´an´ı zobrazen pomoc´ı grafu (k´odov´an´ı DAG obr. 5.1, k´odov´an´ı DAG1 obr. 5.2, k´odov´an´ı DAG2 obr. 5.3, k´odov´an´ı DAG3 obr. 5.4, k´odov´an´ı DAG4 obr. 5.5, bin´arn´ı k´odov´an´ı obr. 5.7, Gray˚ uv k´od obr. 5.6 a v´ ystupn´ı k´odov´an´ı obr. 5.8 ). Pomoc´ı mocninn´e spojnice trendu je v grafech vidˇet, ˇze cena obvodu roste st´alou rychlost´ı. Rovnice spojnice trendu je ve tvaru y = c×b , kde c a b jsou konstanty. Hodnota spolehlivosti grafu se znaˇc´ı R2 (ˇc´ım v´ıc se tato hodnota bl´ıˇz´ı k jedn´e, t´ım v´ıc se kˇrivka spolehlivˇejˇs´ı v˚ uˇci dat˚ um). D´ale je zobrazena tabulka vˇsech dosaˇzen´ ych v´ ysledk˚ u (cen obvod˚ u) 21 testovan´ ych automat˚ u (tabulka 5.4), kde jsou barevnˇe oznaˇceny nejlepˇs´ı v´ ysledky (tzn. nejmenˇs´ı cena) pro dan´ y automat. Pozn´amka: obr´azky vˇsech testovan´ych automat˚ u jsou uvedeny v pˇr´ıloze
Obr´azek 5.1: V´ ysledky k´odov´an´ı DAG Z tabulky 5.1 lze vyˇc´ıst, kter´e k´odov´an´ı m´a nejvˇetˇs´ı u ´spˇeˇsnost (co se t´ yˇce hodnoty ceny) pro testovan´e automaty. Tato tabulka pracuje pouze s tˇremi nejlepˇs´ımi v´ ysledky (ostatn´ı v´ ysledky cen zahazuje). Nejlepˇs´ı v´ ysledek (nejniˇzˇs´ı cena) se n´asob´ı konstantou 3, druh´ y nejlepˇs´ı se n´asob´ı konstantou 2 a tˇret´ı nejlepˇs´ı se n´asob´ı konstantou 1. Pomoc´ı tˇechto konstant se vypoˇc´ıt´a u ´ˇcinnost dan´eho k´odov´an´ı pro vˇsechny testovan´e automaty. 35
Porovn´an´ı metod k´odov´an´ı
Obr´azek 5.2: V´ ysledky k´odov´an´ı DAG1
Obr´azek 5.3: V´ ysledky k´odov´an´ı DAG2 D´ale rozdˇel´ıme tabulku na mal´e (do osmi stav˚ u) a velk´e (minim´alnˇe devˇet stav˚ u) automaty a pˇrepoˇc´ıt´ame u ´spˇeˇsnost pouˇzit´ ych k´odov´an´ı (tabulky 5.2 a 5.3). Zhodnocen´ı tˇechto v´ ysledk˚ u je uvedeno v kapitole 6 Z´ avˇ er.
36
Porovn´an´ı metod k´odov´an´ı
Obr´azek 5.4: V´ ysledky k´odov´an´ı DAG3
Obr´azek 5.5: V´ ysledky k´odov´an´ı DAG4
37
Porovn´an´ı metod k´odov´an´ı
Obr´azek 5.6: V´ ysledky bin´arn´ıho k´odov´an´ı
Obr´azek 5.7: V´ ysledky Grayova k´odu
38
Porovn´an´ı metod k´odov´an´ı
Obr´azek 5.8: V´ ysledky v´ ystupn´ıho k´odov´an´ı
´ cinnost k´odov´an´ı pro vˇsechny automaty Tabulka 5.1: Uˇ
39
Porovn´an´ı metod k´odov´an´ı
´ cinnost k´odov´an´ı pro automaty s max. poˇctem stav˚ Tabulka 5.2: Uˇ u8
´ cinnost k´odov´an´ı pro automaty s min. poˇctem stav˚ Tabulka 5.3: Uˇ u9
40
Porovn´an´ı metod k´odov´an´ı
Tabulka 5.4: V´ ysledky k´odov´an´ı
41
6 Z´avˇer Pˇredem je tˇreba poznamenat, ˇze nelze urˇcit, pro kter´ y druh automat˚ u (ˇc´ıtaˇc, obecn´ y automat,...) je jedno k´odov´an´ı lepˇs´ı neˇz druh´e. A ani neexistuje k´odov´an´ı, kter´e n´am 100% zaruˇc´ı nejniˇzˇs´ı cenu obvodu u vˇsech automat˚ u. Pro svou pr´aci jsem automaty rozdˇelila na dva druhy: mal´e automaty (do 8 stav˚ u) a velk´e automaty (minim´alnˇe 9 stav˚ u) a vypoˇc´ıtala jejich ceny obvod˚ uau ´ˇcinnosti pro k´odov´an´ı: DAG, DAG1, DAG2, DAG3, DAG4, bin´arn´ı k´odov´an´ı, Gray˚ uv k´od, v´ystupn´ı k´odov´an´ı. Kde DAG1, DAG2, DAG3, DAG4 je upraven´ y algoritmus DAG. Ve skupinˇe pro mal´e automaty se uk´azalo, ˇze nejlepˇs´ım k´odov´an´ım je DAG su ´spˇeˇsnost´ı 64.29%. Druh´ ym nejlepˇs´ım pˇriˇrazen´ım k´odu je v´ystupn´ı k´odov´an´ı su ´spˇeˇsnost´ı 57.14%. Je tˇreba podotknout, ˇze algoritmus DAG je na v´ ypoˇcet sloˇzitˇejˇs´ı neˇz v´ystupn´ı k´odov´an´ı. Nejh˚ uˇre dopadlo bin´arn´ı k´odov´an´ı a Gray˚ uv k´od, kde u ´ˇcinnost nepˇres´ahla ani 15%. U velk´ ych automat˚ u je nejlepˇs´ım pˇriˇrazen´ım k´odu v´ystupn´ı k´odov´an´ı s u ´ˇcinnost´ı 66.67%. Druh´ y nejlepˇs´ım k´odov´an´ım je DAG3 s u ´ˇcinnost´ı 47.62%. Nejhorˇs´ı k´odov´an´ı pro velk´e automaty je Gray˚ uv k´od s u ´ˇcinnost´ı 4.76%. Dalˇs´ım porovn´an´ım je k´odov´an´ı DAG, DAG1, DAG2, DAG3, DAG4. Pro mal´e automaty nejlepˇs´ım k´odov´an´ım je DAG, druh´ ym nejlepˇs´ım je DAG4 s ´ u ´spˇeˇsnost´ı 47.62%. Uspˇeˇsnost ostatn´ıch algoritm˚ u nepˇres´ahla 30%. Pro velk´e automaty je nejlepˇs´ım algoritmem DAG3 s u ´spˇeˇsnost´ı 47.62%, druh´ ym nejlepˇs´ım je DAG4 s u ´spˇeˇsnost´ı 42.86%. P˚ uvodn´ı algoritmus DAG pro velk´e automaty nepˇres´ahl u ´spˇeˇsnosti k´odov´an´ı ani 20%.
42
Pˇ rehled zkratek • CLK- [Clock] synchronizaˇcn´ı hodinov´ y pulz • SAP- [StateAssignmentP roblem] probl´em k´odov´an´ı stav˚ u • DAG- [DesiredAdjacencyGraf ] k´odov´an´ı stav˚ u podle grafu sousednosti • FSM- [F initeStateM achine] koneˇcn´ y stavov´ y automat • IAT- [IncompletAssignmentT able] ne´ upln´a tabulka pˇriˇrazen´ı • GA- [GeneticAlgorithm] genetick´e algoritmy • BIN- bin´arn´ı k´odov´an´ı • GRAY- Grayovo k´odov´an´ı • OUTPUT- v´ ystupn´ı k´odov´an´ı • KO- klopn´ y obvod • GM- [graphembedding] vkl´ad´an´ı graf˚ u
43
Seznam obr´ azk˚ u
2.1
Sign´aly a stavy v sekvenˇcn´ım obvodu . . . . . . . . . . . . . .
2
2.2
Graf . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.3
Stavov´a tabulka . . . . . . . . . . . . . . . . . . . . . . . . . .
3
2.4
Mooreho automat . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.5
Mealyho automat . . . . . . . . . . . . . . . . . . . . . . . . .
4
2.6
Karnaugova mapa pro prvn´ı stavovou promˇennou a1
. . . . .
8
2.7
Karnaugova mapa pro druhou stavovou promˇennou a2 . . . . .
9
2.8
Karnaugova mapa pro tˇret´ı stavovou promˇennou a3 . . . . . .
9
2.9
Karnaugova mapa pro prvn´ı v´ ystup . . . . . . . . . . . . . . . 10
2.10 Karnaugova mapa pro druh´ y v´ ystup
. . . . . . . . . . . . . . 10
3.1
Bin´arn´ı k´odov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.2
Grayovo k´odov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3
One-hot k´odov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.4
2-hot k´odov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.5
Zero-hot k´odov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.6
Johnsonovo k´odov´an´ı . . . . . . . . . . . . . . . . . . . . . . . 16 44
´ ˚ SEZNAM OBRAZK U
´ ˚ SEZNAM OBRAZK U
3.7
K´odov´an´ı m-n . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.8
N´ahodn´e k´odov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . 17
3.9
Obecn´ y postup pro k´odov´an´ı stav˚ u . . . . . . . . . . . . . . . 18
3.10 Pˇr´ıklad stavov´e tabulky
. . . . . . . . . . . . . . . . . . . . . 19
3.11 Graf sousednosti (DAG) n´asledn´ık˚ u . . . . . . . . . . . . . . . 20 3.12 Graf sousednosti (DAG) pˇredch˚ udc˚ u . . . . . . . . . . . . . . 20 3.13 Graf sousednosti (DAG) v´ ystup˚ u . . . . . . . . . . . . . . . . 21 3.14 Graf sousednosti (DAG) pˇrechod˚ u . . . . . . . . . . . . . . . . 21 3.15 Koneˇcn´a matice grafu sousednosti DAG . . . . . . . . . . . . . 22 3.16 Vzd´alenost prvk˚ u bin´arn´ıho k´odu . . . . . . . . . . . . . . . . 23 3.17 Kodov´an´ı stav˚ u podle DAG . . . . . . . . . . . . . . . . . . . 24 3.18 1. pravidlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 3.19 2. pravidlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.20 3. pravidlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.21 4. pravidlo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 3.22 1.Fanout-orientovan´ y algoritmus . . . . . . . . . . . . . . . . . 28 3.23 2.Fanout-orientovan´ y algoritmus . . . . . . . . . . . . . . . . . 28 3.24 1.Fanin-orientovan´ y algoritmus
. . . . . . . . . . . . . . . . . 28
3.25 2.Fanin-orientovan´ y algoritmus
. . . . . . . . . . . . . . . . . 29
3.26 a) Pˇr´ıklad algoritmu vkl´ad´an´ı . . . . . . . . . . . . . . . . . . 30 3.27 b) Pˇr´ıklad algoritmu vkl´ad´an´ı . . . . . . . . . . . . . . . . . . 30 5.1
V´ ysledky k´odov´an´ı DAG . . . . . . . . . . . . . . . . . . . . . 35
45
´ ˚ SEZNAM OBRAZK U
´ ˚ SEZNAM OBRAZK U
5.2
V´ ysledky k´odov´an´ı DAG1 . . . . . . . . . . . . . . . . . . . . 36
5.3
V´ ysledky k´odov´an´ı DAG2 . . . . . . . . . . . . . . . . . . . . 36
5.4
V´ ysledky k´odov´an´ı DAG3 . . . . . . . . . . . . . . . . . . . . 37
5.5
V´ ysledky k´odov´an´ı DAG4 . . . . . . . . . . . . . . . . . . . . 37
5.6
V´ ysledky bin´arn´ıho k´odov´an´ı . . . . . . . . . . . . . . . . . . . 38
5.7
V´ ysledky Grayova k´odu
5.8
V´ ysledky v´ ystupn´ıho k´odov´an´ı . . . . . . . . . . . . . . . . . . 39
. . . . . . . . . . . . . . . . . . . . . 38
46
Seznam tabulek
2.1
Pravdivostn´ı tabulka . . . . . . . . . . . . . . . . . . . . . . .
6
2.2
Zak´odovan´a stavov´a tabulka pro Karnaughovu mapu . . . . .
8
2.3
Cena obvodu . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.1
Poˇcet r˚ uzn´ ych k´odov´an´ı . . . . . . . . . . . . . . . . . . . . . 12
3.2
Ne´ upln´a tabulka pˇriˇrazen´ı . . . . . . . . . . . . . . . . . . . . 23
5.1
´ cinnost k´odov´an´ı pro vˇsechny automaty . . . . . . . . . . . . 39 Uˇ
5.2
´ cinnost k´odov´an´ı pro automaty s max. poˇctem stav˚ Uˇ u 8 . . . 40
5.3
´ cinnost k´odov´an´ı pro automaty s min. poˇctem stav˚ Uˇ u 9 . . . . 40
5.4
V´ ysledky k´odov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . 41
47
Literatura [1] Amaral, J.: Designing genetic algorithms for the state assignment problem. IEEE Wplore, 1995. [2] Amaral, J. N.; Cunha, W. C.: State assignment algorithm for incompletely speciffied finite state machines. In VLSI Design Methodologies, SPIE Proceedings, listopad 1990. [3] Amaral, J. N.; Tumer, K.; Ghosh, J.: Designing Genetic Algorithms for the State Assignment Problem. IEEE Transactions on Systems, prosinec 1995: s. 623–628. [4] Bambuˇskov´a, K.: Konstrukce koneˇcn´eho automatu III. Diplomov´a pr´ace, ˇ FEI, VSB-TU Ostrava, Ostrava, 2005. [5] Bokr, J.: Logick´e obvody a automaty. Katedra informatiky a v´ ypoˇcetn´ı techniky, 2003. [6] Bukka: Bmin - Program Visualizer of Boolean minimization. http://bukka.eu/cs/bmin/, online; citace 28.2.2011. [7] Bukka: Bmin Visualizer of Boolean minimization. http://bukka.eu/cs/bmin/1.0.1, online; citace 28.2.2011. [8] Devadas, S.: MUSTANG: State Assignment of Finite State Machines Targeting Multilevel Logic Implementations. Computer-Aided Design of Integrated Circuits and Systems, prosinec 1988: s. 1290–1300. [9] Dolotta, T.: The Coding of Internal States of Sequential Circuits. Electronic Computers, IEEE Transactions, ˇr´ıjen 1964: s. 549 – 652. [10] Egert, J.: Algoritmy pro k´odov´an´ı stav˚ u koneˇcn´eho automatu. Diplomov´a ˇ pr´ace, Cesk´e vysok´e uˇcen´ı technick´e v Praze, ˇcerven 2007.
48
LITERATURA
LITERATURA
[11] Ghosh, A.: Estimation of Average Swiching Activitz in Combinational and Sequential Circuits. Technick´a zpr´ava, Mitsubishi Electronics America, 1992. [12] Hartmais, J.: On the State Assignment Problem foe Sequential Machines. Electronic Computers, IRE Transactions, ˇcerven 1961: s. 157–165. [13] Makki, R.: Analysis and Characterization of State Assignment Techniques for Sequential Machines. VLSI Design, 1994: s. 81–88. ˇ ıslicov´e systmy a jazyk VHDL. 2006. [14] Pinker, J.: C´ ˇ e vy[15] Prokeˇs, M.: Diplomov´a pr´ace (FEL code). Diplomov´a pr´ace, Cesk´ sok´e uˇcen´ı technick´e v Praze, Praha, 2001. [16] Sentovich, E.: Sequential circuit design using synthesis and optimization. VLSI in Computers and Processors, ˇr´ıjen 1992: s. 328–333. [17] Spinellis, D.: Graphviz - Graph Visualization http://graphviz.org/, online; citace 28.2.2011.
Software.
[18] Story, J.: Optimum State Assignment for Synchronous Sequential Circuits. IEEE Transactions on Computers, prosinec 1972: s. 1365–1373. [19] Vavˇriˇcka, V.: Logick´e systemy, 2011, sekvenˇcn´ı obvody - Optimalizace koneˇcn´ ych automat˚ u.
49
Pˇ r´ılohy
Uˇ zivatelsk´ a pˇ r´ıruˇ cka Program na k´odov´an´ı stav˚ u spust´ıme pomoc´ı aplikace Projekt1.exe. Konzole n´as vyzve k zad´an´ı n´azvu stavov´e tabulky, kter´a je zad´ana v textov´em souboru. Aby program mohl spr´avnˇe pracovat, je potˇreba m´ıt stavovou tabulku ve spr´avn´em form´atu. Prvn´ı sloupec stavov´e tabulky jsou p˚ uvodn´ı stavy, d´ale n´asleduj´ıc´ı stavy a v´ ystupy. Kaˇzd´ y sloupec je oddˇelen znakem ;“. Pokud ” m´ame v´ıce n´asleduj´ıc´ıch stav˚ u oddˇelujeme je znakem ,“. Jednotliv´e bity v´ y” stupu tak´e oddˇelujeme znakem ,“. Konec ˇr´adky znaˇc´ıme ;“. Form´at stavov´e ” ” tabulky m˚ uˇze vypadat: puvodn´ıStav;nasledujic´ıStav1,n´asleduj´ıc´ıStav2;v´ystup1,v´ystup0; Pˇr´ıklad stavov´e tabulky: S0;S1,S2;0,0; S1;S4,S3;1,1; S2;S4,S3;1,0; S3;S4,S4;0,1; S4;S0,S0;0,0; Po zad´an´ı n´azvu stavov´e tabulky si vybereme druh k´odov´an´ı (obr´azek. 1): a) metoda DAG b) metoda DAG1 c) metoda DAG2
I
LITERATURA
LITERATURA
d) metoda DAG3 e) metoda DAG4
Obr´azek 1: uˇzivatelsk´a konzole Podle zvolen´e metody se provede druh k´odov´an´ı a zap´ıˇse se do souboru kodovani.csv. V souboru jsou uloˇzeny potˇrebn´e matice pro v´ ypoˇcet k´odov´an´ı, indexy stav˚ u, v´ahy stav˚ u a k´odov´an´ı dan´eho stavu. Pokud si nevybereme ani jeden druh k´odov´an´ı je moˇzn´e volbou x“ ukon” ˇcit program, popˇr´ıpadˇe volbou z“ zvolit si jinou stavovou tabulku. ” D´ale v bakal´aˇrsk´e pr´aci byl pouˇzit program na minimalizaci logick´ ych funkc´ı Bmin. Manu´al k tomuto programu nalezneme na internetov´ ych str´ank´ach http://bukka.eu/cs/bmin/1.0.1 [7] a program je moˇzn´e st´ahnout z adresy http://bukka.eu/cs/bmin/ [6].
II
Testovac´ı automaty Nejprve pro vykreslen´ı graf˚ u testovan´ ych automatu byl pouˇzit program Graphviz - Graph Visualization Software [17], bohuˇzel pro velk´em automaty v´ ystup toho programu nebyl ide´aln´ı (grafy automat˚ u byly velmi nepˇrehledn´e). Proto jsem zvolila z´apis automatu pomoc´ı tabulky pˇrechodu a v´ ystup˚ u. Zde jsou uvedeny vˇsechny testovac´ı automaty (vlevo je vˇzdy tabulka pˇrechod˚ u a vpravo v´ ystupy stav˚ u dan´eho automatu).
Obr´azek 2: Hektor
Obr´azek 3: Ponorka
III
LITERATURA
LITERATURA
ˇ Obr´azek 4: Spagetka
Obr´azek 5: Kocour
Obr´azek 6: Vˇcela
IV
LITERATURA
LITERATURA
Obr´azek 7: Bobina
Obr´azek 8: Brejlovec
Obr´azek 9: Ad´ela
V
LITERATURA
LITERATURA
Obr´azek 10: Raketa Obr´azek 11: Mandarinka
Obr´azek 12: Esmeralda
Obr´azek 13: Plech´aˇc VI
LITERATURA
LITERATURA
Obr´azek 14: Princezna
Obr´azek 15: Kredenc
Obr´azek 16: Delf´ın
VII
LITERATURA
LITERATURA
Obr´azek 17: Rohl´ık
ˇ Obr´azek 18: Zralok
VIII
LITERATURA
LITERATURA
Obr´azek 19: Sysel
IX
ˇ Obr´azek 20: Zehliˇ cka
X
LITERATURA
LITERATURA
Obr´azek 21: Ban´an
Obr´azek 22: Dvojˇce
XI