Sinteza clasic ă a SLS

Capitolul 32010*Proiectarea sistemelor digitale

Tematica Etapele sintezei clasice a SLS sincrone Determinarea mainii reduse minime Sinteza cu ajutorul registrelor

2010*Proiectarea sistemelor digitale

Proiectarea sistemelor digitale

Etapele sintezei clasice2010*Proiectarea sistemelor digitaleE1. Pornind de la descrierea verbal se trece la descrierea formal prin diagrame de stare.

E2. Se trece de la diagrama de stare la tabelul de evoluie a strilor.

E3. Se ncearc reducerea numrului de stri.

E4. Se asigneaz strile, adic se trece de la reprezentarea prin nume simbolice, la reprezentarea codificat binar a strilor.

E5. Se trece de la tabelul de stare la tabelul de tranziie a strilor i tabelul de ieire.

E6. Din tabelul de ieire se sintetizeaz funciile de ieire printr-una dintre metodele cunoscute pentru sinteza SLC.

E7. Se alege tipul de bistabil utilizat pentru sintez.

E8. Pornind de la tabelul de tranziie a strilor i tabelul de excitaie a bistabilelor, se genereaz tabelul de excitaie al SLS sintetizate.


Etapele sintezei clasice2010*Proiectarea sistemelor digitaleE9. Din tabelul de excitaie se sintetizeaz funciile de excitaie printr-una dintre metodele cunoscute pentru sinteza SLC.

E10. Se deseneaz SLS sintetizat.

E11. Se analizeaz evoluia n spaiul strilor pentru a verifica corectitudinea sintezei i pentru a pune n eviden eventualele anomalii datorate caracterului incomplet specificat al funciilor de excitaie i de ieire. De obicei, astfel de anomalii pot fi rezolvate prin introducerea unei comenzi asincrone de iniializare dar, n anumite situaii, se poate recurge la reproiectare prin precizarea corespunztoare a valorilor nespecificate din tabelul de tranziie al strilor i n tabelul de ieire, care au generat anomalia.

E12. Din cataloagele de componente se aleg circuitele integrate utilizate pentru implementarea efectiv a schemei.

E13. n cazul unor scheme de mare complexitate sau care lucreaz la valori apropiate de valoarea maxim admis pentru frecvena impulsului de tact, este necesar i analiza temporal a schemei obinute. Eventualele anomalii puse n eviden aici pot conduce la necesitatea alegerii altor componente pentru implementare sau chiar la necesitatea alegerii unei alte metode de sintez a funciilor de excitaie i ieire.


Asignarea strilor2010*Proiectarea sistemelor digitalePrin asignarea strilor vom nelege asocierea de ctre proiectant a unei combinaii binare unice fiecrei stri simbolice a unei maini secveniale.

Se observ c procesul de asignare este un proces artificial i principial exist o infinitate de asignri posibile, cu condiia ca la dou stri diferite s fie asociate dou combinaii binare diferite.

n procesul de asignare se utilizeaz ca ipotez de lucru fundamental codificarea tuturor strilor cu combinaii binare avnd aceeai lungime.

n continuare vor fi analizate dou metode frecvent utilizate pentru asignarea strilor.


Asignarea cu codificare de lungime minim2010*Proiectarea sistemelor digitalePresupunnd c maina secvenial conine N stri, vor fi necesare n variabile de stare astfel nct numrul de combinaii binare s fie cel puin egal cu N adic

2n N

nlog(2)log(N) nlog2(N)

De obicei se alege valoarea minim

n= log2(N)Exemplu: Se consider o MS sincron cu N=3 stri notate A,B,C. Pentru codificarea strilor vor fi necesare n=log2(3)=2 variabile de stare notate y1y0.

Asignarea natural va avea forma:Combinaia 11 este o combinaie redundant.


2010*Proiectarea sistemelor digitaleAsignri particularen anumite situaii pot fi utilizate si alte codificari cu lungime minim sau nu , de exemplu codificarea Gray sau Johnson.

Exemplu: Daca o masin secvenial are 8 stari, numarul minim de variabile de stare necesare codificrii strilor este log2(8)=3. n acest caz, se poate utiliza o codificare Gray pe 3 bii sau o codificare Johnson pe 4 bii.

StareaCodificare GrayCodificare Johnsony2y1y0y3y2y1y0A0000000B0010001C0110011D0100111E1101111F1111110G1011100H1001000


Asignarea prin metoda ONE-HOT2010*Proiectarea sistemelor digitaleMetoda de asignare One-hot numit i metoda cu decodificre complet a strilor se deosebete fundamental de metoda prezentat anterior prin faptul c numrul de stri este egal cu numarul variabilelor de stare.

Cu alte cuvinte, fiecrei stri i corespunde o variabil de stare.Deoarece la un moment dat o MS poate s se afle ntr-o singur stare, rezult imediat c n fiecare moment trebuie s fie activ o singur variabil de stare. Dac presupunem c variabilele de stare sunt active pe nivel ridicat, nseamn c fiecare combinaie asignat va conine exact un 1.

Exemplu:Asignarea One-hot se va realiza cu 5 variabile de stare, ca n tabelul de mai jos

stareaABCDEA10000B01000C00100D00010E00001


A

C

D

B

E

INIT#

2010*Proiectarea sistemelor digitaleExemple de sintez


2010*Proiectarea sistemelor digitaleExemple de sintez S se sintetizeze un recunosctor de secven dinamic (RSD) care semnaleaz prin 0 logic la ieire ori de cte ori n irul binar de la intrare apare secvena 10110. Schema este prevzut i cu o intrare de iniializare asincron Clear activ pe nivel cobort. Se vor lua n considerare att varianta Mealy ct i varianta Moore.


2010*Proiectarea sistemelor digitaleExemple de sintez Modelul Mealy


RSD

S

CLK

TACT

E

S0

S1

S2

S4

S3

1/1

0/1

0/1

1/1

1/1

1/1

0/1

1/1

0/0

INIT#

Clear

INIT#

0/1



1

1

1

x

x

1

1

1

0

1

1

x

x

1

x

x

S

y1

y2

y0

00

10

11

01

00

10

11

01

0

0

x

1

0

0

x

x

0

1

x

x

0

0

x

x

S

y2

y1

y0

00

10

11

01

00

10

11

01

0

0

0

1

1

0

x

x

x

x

x

x

x

x

x

x

S

y2

y1

y0

00

10

11

01

00

10

11

01

E

J1

J2

x

x

x

x

x

x

x

x

0

1

x

x

1

0

x

x

S

y2

y1

y0

00

10

11

01

00

10

11

01

0

1

1

0

x

x

x

x

x

x

x

x

0

1

x

x

S

y2

y1

y0

00

10

11

01

00

10

11

01

x

x

x

x

1

0

x

x

1

1

x

x

x

x

x

x

S

y2

y1

y0

00

10

11

01

00

10

11

01

K1

K0

J0

2010*Proiectarea sistemelor digitaleExemple de sintez Modelul MealyAnaliza n spaiul strilor


2010*Proiectarea sistemelor digitaleExemple de sintez Modelul Moore


2010*Proiectarea sistemelor digitaleExemple de sintez Modelul MooreAnaliza n spaiul strilor


2010*Proiectarea sistemelor digitaleExemple de sintez Modelul Moore


2010*Proiectarea sistemelor digitaleExemple de sintez asignare ONE-HOTVom relua exemplul precedent (modelul Moore) i vom sintetiza schema folosind o asignare one-hot ca n tabelul de mai jos.Pentru sinteza se utilizeaza bistabile tip D conectate ca in schema urmatoare.

Atentie! La activarea semnalului de initializare bistabilul S0 trebuie sa treaca in starea 1 care devine strea activa dupa initializare. Celelalte bistabile trec in starea 0 (dezactivate).

stareaS0S1S2S3S4S5S0100000S1010000S2001000S3000100S4000010S5000001


2010*Proiectarea sistemelor digitaleExemple de sintez asignare ONE-HOTE=S5 Funciile de excitaie i de ieire se obin direct din diagrama de evoluie a MS.


INIT#

S

R

R

R

R

D Q

CLK

CLK

CLK

CLK

CLK

D Q

D Q

D Q

D Q

D0

D4

D3

D2

D1

S5

S4

S3

S1

S0

2010*Proiectarea sistemelor digitaleDeterminarea mainii reduse minime


2010*Proiectarea sistemelor digitaleConcepte fundamentaleFie s(t+1)=g(s(t),x(t))z(t)=f (s(t),x(t))

o MS sincron complet specifict i fie Si i Sj dou stri ale acestei maini secveniale.

Fie x o secven de intrare oarecare. Se numete x succesor al strii Si i se noteaz xSi starea n care ajunge maina secveniala pornind din starea Si dup aplicarea secvenei x.

Se spune c strile Si i Sj sunt k-echivalente dac pentru orice secven x de lungime k, xSi=xSj.

Se spune c strile Si i Sj sunt echivalente i se noteaz SiSj dac pentru orice secven x se obine xSi=xSj.

Se poate spune ca doua stari ale unei maini secveniale sunt echivalente dac nu exist nici un test prin care s ne putem da seama care dintre cele dou stri a fost starea iniial.


2010*Proiectarea sistemelor digitaleConcepte fundamentaleT1Dou stri sunt k+1 echivalente dac sunt k-echivalente i toi 1 succesorii lor sunt stri k-echivalente.

Aceast teorem ofer mecanismul de determinare iterativ a claselor de echivalen, pornind de la mulimea tuturor strilor considerate iniial ca fiind stri echivalente.

Vom numi partiie de ordinul k i vom nota k reuniunea tuturor claselor de stri k-echivalente ale unei MS date.

T2 k-1 = k k = k+1

Aceast teorem ne ofer criteriul de oprire a procesului iterativ de determinare a partiiei de ecchivalen. k se va numi partiie de echivalen.

T3ntotdeauna n-1 = n (n numrul de stri ale MS date)

Aceast proprietate ne arat c procesul iterativ de determinare a claselor de echivalen este un proces finit.


2010*Proiectarea sistemelor digitaleAlgoritmul MooreP1. Se pornete de la tabelul de stare al MS i se pun n eviden strile 1-echivalente prin compararea vectorilor de ieire. P2.Se reface tabelul de stare grupnd strile 1-echivalente ntr-un singur bloc i eliminnd vectorii de ieire. Pentru fiecare stare urmtoare se precizeaz blocul din care aceasta face parte.P3.n noul tabel se compar liniile din fiecare bloc pentru a verifica dac sunt echivalente. Dac n fiecare coloan strile urmtoare fac parte din acelai bloc, strile comparate sunt echivalente. Dac n cel puin o coloan strile urmtoare fac parte din blocuri diferite, cele dou stri vor face parte din blocuri diferite.P4. Se reface tabelul prin punerea n eviden a noilor blocuri i se reia de la pasul precedent. Procesul se reia pn cnd nu mai poate fi generat nici un bloc. n ultimul tabel strile din acelai bloc sunt stri echivalene deci a fost generat partiia de echivalen.


2010*Proiectarea sistemelor digitaleMaina redus echivalentFie MS1 i MS2 dou maini secveniale sincrone complet specificate i fie dou stri oarecare SiMS1 i SkMS2. Se spune c strile Si i Sk sunt echivalente dac secven x aplicat celor dou stri considerate ca stri iniiale, se vor obine secvene de ieire identice.Se spune c MS1 i MS2 sunt dou maini secveniale echivalente dac fiecrei stri din MS1 i corespunde o stare echivalent n MS2 i reciproc.Se spune c MS2 este maina secvenial redus echivalent cu MS1 dac este echivalent cu MS1 iar numrul de stri ale lui MS2 nu mai poate fi redus.


2010*Proiectarea sistemelor digitaleMaina redus echivalent - exemplu


2010*Proiectarea sistemelor digitaleMaina redus echivalent - exemplu (A,E) (B,D,F) (C,G)


2010*Proiectarea sistemelor digitaleMaina redus echivalent - exemplu


2010*Proiectarea sistemelor digitaleProiectarea SLS cu registre


2010*Proiectarea sistemelor digitaleVariante de proiectare cu registre


CLC

registru paralel-paralel

k

x(t)

m

n

z(t)

INIT

k

registru deplasare

CLC

ISDD

INIT

TACT

x(t)

z(t)

y(t)

2010*Proiectarea sistemelor digitaleRegistrul 74LS194 evoluia strilor


0000

0110

1001

1010

0101

1100

0011

1111

1110

1101

1011

0111

1000

0100

0010

0001

1

1

0

0

0

0

0

0

0

0

1

1

1

0

0

1

1

1

0

0

1

1

0

0

1

1

1

1

1

0

2010*Proiectarea sistemelor digitaleSinteza cu registru - exempluUtiliznd un registru 74LS194 s se proiecteze un numrtor Johnson modulo 8 (cu 8 stri).


0000

0110

1001

1010

0101

1100

0011

1111

1110

1101

1011

0111

1000

0100

0010

0001

1

1

0

0

0

0

0

0

0

0

1

1

1

0

0

1

1

1

0

0

1

1

0

0

1

1

1

1

1

0

2010*Proiectarea sistemelor digitaleSinteza cu registru - exemplu

y0y1y2y3IS00001000100010x001100100x0101x0110x01110100011001x1010x1011x110011101x1110111110


74HCT194

Q0

Q3

Q2

Q1

IS

D0

D3

D2

D1

S1

SR

S0

0

1

INIT#

0

CLEAR

CLK

TACT

y0

y3

y2

y1

2010*Proiectarea sistemelor digitaleSinteza cu registru - exemplu


2010Proiectarea sistemelor digitale*


***************************************

Sinteza clasic ă a SLS

Documents

Transcript of Sinteza clasic ă a SLS