Algoritmisk tillståndsmaskin

Algoritmisk tillståndsmaskin ( ASM )-metoden är en metod för att designa finita tillståndsmaskiner (FSM) som ursprungligen utvecklades av Thomas E. Osborne vid University of California, Berkeley (UCB) sedan 1960, introducerades till och implementerades på Hewlett-Packard 1968, formaliserad och utökad sedan 1967 och skriven om av Christopher R. Clare sedan 1970. Den används för att representera diagram över digitala integrerade kretsar . ASM-diagrammet är som ett tillståndsdiagram men mer strukturerat och därmed lättare att förstå. Ett ASM-diagram är en metod för att beskriva sekventiell drift av ett digitalt system.

ASM-metod

ASM-metoden består av följande steg:

1 . Skapa en algoritm med hjälp av pseudokod för att beskriva enhetens önskade funktion.

2 . Konvertera pseudokoden till ett ASM-diagram .

3 . Designa datavägen baserat på ASM-diagrammet.

4 . Skapa ett detaljerat ASM-diagram baserat på datasökvägen.

5 . Designa kontrolllogiken baserat på det detaljerade ASM-diagrammet.

ASM-diagram

Ett ASM-diagram består av en sammankoppling av fyra typer av grundläggande element: tillståndsnamn, tillståndsbox, beslutsbox och villkorlig utdatabox. Ett ASM-tillstånd, representerat som en rektangel, motsvarar ett tillstånd i ett reguljärt tillståndsdiagram eller finita tillståndsmaskin. Moore - typutgångarna listas i rutan.

Statens namn

Statsnamn: Namnet på staten anges inuti cirkeln och cirkeln placeras i det övre vänstra hörnet eller namnet placeras utan cirkeln.

Statlig låda

State Box: Utdata från tillståndet indikeras inuti rektangelrutan

Beslutsruta som används i ett ASM-diagram

Beslutsruta: En diamant indikerar att det angivna tillståndet/uttrycket ska testas och utgångsvägen ska väljas därefter. Villkorsuttrycket innehåller en eller flera ingångar till FSM (Finite State Machine). En ASM-tillståndskontroll, indikerad av en romb med en ingång och två utgångar (för sant och falskt), används för att villkorligt överföra mellan två tillståndsboxar, till en annan beslutsbox eller till en villkorlig utdatabox. Beslutsrutan innehåller det angivna villkorsuttrycket som ska testas, uttrycket innehåller en eller flera ingångar från FSM.

Villkorlig utmatningslåda

Villkorlig utmatningsbox : En oval betecknar utsignalerna som är av Mealy -typ. Dessa utgångar beror inte bara på tillståndet utan också på ingångarna till FSM.

Datapath

När väl den önskade operationen för en krets har beskrivits med användning av RTL- operationer, kan datavägskomponenterna härledas. Varje unik variabel som tilldelas ett värde i RTL-programmet kan implementeras som ett register. Beroende på den funktionella operationen som utförs vid tilldelning av ett värde till en variabel, kan registret för den variabeln implementeras som ett enkelt register, ett skiftregister, en räknare eller ett register som föregås av ett logiskt kombinationsblock. Kombinationslogikblocket associerat med ett register kan implementera en adderare, subtraherare, multiplexerare eller någon annan typ av kombinationslogikfunktion.

Detaljerat ASM-diagram

När datavägen är designad konverteras ASM-diagrammet till ett detaljerat ASM-diagram. RTL - notationen ersätts av signaler definierade i datavägen.

Se även

Sunggu Lee: Computer Design: An Example of Advanced Digital Logic Design , Prentice-Hall 2000, ISBN 0-13-040267-2 .
Sunggu Lee: Advanced Digital Logic Design: Using VHDL, State Machines, and Synthesis for FPGAs , Thomson 2006, ISBN 0-534-46602-8 .
Stephen D. Brown, Zvonko Vranesic : Grunderna i digital logik med VHDL-design .
- 2:a, McGraw Hill 2004; ISBN 978-0-07-249938-4 .
- 3:a, McGraw Hill 2009; ISBN 978-0-07-352953-0 .
Bjørner, Dines (december 1970) [1970-05-04, 1970-04-07, 1970-02-04]. "Flödesschemamaskiner" . BIT Numerisk matematik . IBM Research Laboratory, San Jose, Kalifornien. 10 (4): 415–442. doi : 10.1007/BF01935563 . S2CID 189767592 . RJ-685 (nr 13346).
Lee, Samuel C. (1976). Digitala kretsar och logikdesign . Englewood Cliffs, New Jersey, USA: Prentice-Hall .
Santrakul, Krayim (1983). Multi Values LSI/VLSI Logic Design (PDF) . University of Oklahoma. Arkiverad (PDF) från originalet 2016-08-17 . Hämtad 2021-02-17 .

Vidare läsning

Schultz, GW (mars 1969). Skriven på Central Data Systems, Inc., Sunnyvale, Kalifornien, USA. "En algoritm för syntes av komplexa sekventiella nätverk" . Datordesign . Vol. 8, nr. 3. Concord, Massachusetts, USA: Computer Design Publishing Corporation. s. 49–55. ISSN 0010-4566 . OCLC 828863003 . Hämtad 2021-02-22 . (7 sidor) (OBS. Denna artikel orsakade ett antal brev till redaktören i efterföljande nummer av tidningen.)
Schultz, GW (1969). Skriven på Central Data Systems, Inc., Sunnyvale, Kalifornien, USA. "Till redaktören" . Brev till redaktören. Datordesign . Vol. 8, nr. 5–12?. Concord, Massachusetts, USA: Computer Design Publishing Corporation. sid. 10. ISSN 0010-4566 . OCLC 828863003 . sid. 10: […] I ditt aprilnummer publicerade du ett brev av RL Dineley som beskrev en enkel metod för att behandla logiska uttryck av produkt-av-summor . […] En ännu enklare metod lärs ut av DA Huffman . Denna metod är baserad på att inse att det booleska uttrycket kommer att vara noll när någon av faktorerna i formen produkt-av-summor är noll. Att rita nollor av faktorer på ett Veitch-diagram eller en Karnaugh-karta är lika enkelt som att hitta sådana för ett uttryck för summa-of-products . […] För att illustrera, med Dineleys exempel (A+BC)(A+C): […] Nollorna från A+BC kommer att placeras där både A och BC är noll. Därför lokaliserar vi på kartan uttrycket A * BC (som är lika med A * B + A * C ). På liknande sätt är nollorna för A+C lokaliserade och plottade vid A * C . Med alla nollor placerade kan resten av kartan fyllas med ettor. Man kan vara lite mer formell och algebraiskt räkna ut det logiska komplementet till uttrycket i fråga och sedan rita nollor för det resulterande uttrycket. I en enkel produkt-av-summor-representation kan de kompletterande villkoren dock skrivas genom inspektion; eller så kan nollorna ritas genom inspektion utan att skriva det fullständiga uttrycket […] "Classical Reduction Involving Infrequently Used Variables" 11 oktober 1968. University of Santa Clara […] Mr. Osbornes arbete har nära likhet med det jag presenterade i denna artikel och skulle därför definitivt vara av intresse för de läsare som söker ytterligare information. Jag förstår att han har arbetat med att tillämpa tekniken med sällsynta variabler på designen av sekventiella nätverk konstruerade från skrivskyddat minne . Eftersom han ännu inte har publicerat något om detta område, om läsarna vill ha ytterligare information, kan de skriva till Mr. Osborne på: […] Thomas E. Osborne […] Building 1U […] 1501 Page Mill Road […] Palo Alto , Kalifornien […] Tack för möjligheten att publicera med dig. […] GW Schultz […] Central Data Systems, Inc. […] Sunnyvale, Kalifornien (1 sida) (OBS. Osbornes metod publicerades senare av Clare. ^[B] )
Langdon, Jr., Glen G. (1974). "Kapitel 4. Interrelationships, D. Logic Design and Switching Theory, 3. Flödestabellen som utgångspunkt för design" . Skriven på IBM Corporation, San Jose, Kalifornien, USA. I Ashenhurst, Robert "Bob" Lovett [på Wikidata] (red.). Logic Design - En genomgång av teori och praktik . ACM Monograph Series (1 upplaga). New York, USA: Academic Press, Inc. - Ett dotterbolag till Harcourt Brace Jovanovich, Publishers . sid. 149. ISBN 0-12-436550-7 . ISSN 0572-4252 . LCCN 73-18988 . Arkiverad från originalet 2021-04-17 . Hämtad 2021-04-17 . sid. 149: […] Ett viktigt bidrag till anpassningen av teori till praktik gjordes av Schultz [20] ; han bygger på designerns grundläggande förståelse av problemet och kräver att han identifierar de " sällsynta variablerna" . Löst definierade relaterar dessa variabler inte till alla interna tillstånd, dvs de behövs inte för att definiera varje tillstånd. I huvudsak är de sällsynta variablerna relevanta för endast ett fåtal (kanske ett eller två) tillstånd eller tillståndsövergångar. Schultz föreslår att designern först översätter det verbala problemet till en tillståndsövergångsgraf som reduceras. De interna tillstånden kodas och sedan läggs information om sällsynta variabler till de lämpliga tillståndsövergångarna. En "första approximation" till flip-flop- ingångsekvationer görs, endast baserat på de frekventa variablerna. Schultz visar hur dessa ekvationer senare kan modifieras för att inkorporera övergångar som styrs av de sällsynta variablerna. I Schultz exempel är de sällsynta variablerna alla insignaler, men denna idé gäller även för inre tillståndsvariabelsignaler som kan anses vara "sällsynta". I detta fall, till exempel, kan en sällsynt intern tillståndsvariabel vippa ställas in av en speciell omständighet och återställas någon gång senare. Utsignalen från vippan kan nu behandlas som en sällsynt ingångsvariabel. […] (ix+1+179+3 sidor)

externa länkar