Analisi e Sintesi di circuiti sequenziali

Definizione

•  Una macchina sequenziale è un sistema nel quale, detto

•  I(t) l'insieme degli ingressi in t, O(t) l'insieme delle uscite in t, e M(t) una funzione di

•  I(t-1), I(t-2)...(i=1,..n) detta memoria, si ha:

•  oi(t)=F(I(t),M(t)) , oi∈ O

Porte logichecombinatorie

Elementidi memoria

Ingressi esterni

Uscite combinatorie Uscite di memoria

Automi a stati finiti

0

1

0

1

0,1

Q0 Q1 Q2Q2

Un automa a stati finiti è una quintupla (Q,Σ,δ,q0, F) dove: • Q è un insieme finito di stati, • Σ è un alfabeto finito di simboli, • q0 è lo stato iniziale, F ⊂ Q è il set di stati finali, e • δ è la funzione di transizione QxΣ --> Q (QxΣ e' il prodotto cartesiano, ovvero l'insieme delle coppie q,a ); δ(q,a) rappresenta uno stato raggiunto dall'automa, per ogni ogni stato di partenza q e simbolo di ingresso a.

Esempio: distributore di bibite

•  Ogni bibita costa 30c •  Accetta monete da 20 e da 10 •  Non dà resto •  Cosa deve memorizzare il circuito in ogni “stato”? •  L’ammontare ricevuto •  Quanti stati diversi della memoria? •  0c, 10c, 20c,≥30c → 4 stati

Automa:

•  4 stati, S0, S1, S2, S3 •  Alfabeto di Input: 0c, 10c, 20c •  Alfabeto di output: 0 bibite, 1 bibita •  Stato iniziale: S0

Stato 0: M=0

Stato 0: M=0

Stato 1: M=10

Stato 2: M=20

Input=10c

Input=20c

Stato 0: M=0

Stato 1: M=10

Stato 2: M=20

Input=10c

Input=20c

10c Stato 3: M≥30

20c

10c o 20c

Stato 0: M=0

Stato 1: M=10

Stato 2: M=20

Input=10c

Input=20c

10c Stato 3: M≥30

20c

10c o 20c

Output=bibita

Stato 0: M=0

Stato 1: M=10

Stato 2: M=20

Input=10c

Input=20c

10c Stato 3: M≥30

20c

10c o 20c

Output=bibita

Input=0

Input=0

Input=0

Input=0

Stato 0: M=0

Stato 1: M=10

Stato 2: M=20

Input=10c

Input=20c

10c

Stato 3: M≥30

20c

10c o 20c

Output=bibita

Input=0

Input=0 Input=0

Input=0

Funzione di transizione d: QxI→Q d(S0,0)=S0 d(S0,10)=S1 d(S0,20)=S2 d(S1,0)=S1 d(S1,10)=S2 d(S1,20)=S3 d(S2,0)=S2 d(S2,10)=S3 d(S2,20)=S3 d(S3,0)=S0

Rappresentazione tabellare

•  Alternativamente, un automa si può rappresentare mediante una tabella delle transizioni, o stati futuri:

• 

Input=10 Input=20 Input=0 Stato 0

Stato 1 Stato 2 Stato 0

Stato 1

Stato 2 Stato 3 Stato 1

Stato 2

Stato 3 Stato 3 Stato 2

Stato 3

- - Stato 0

La tabella è esattamente la funzione d(QxI)

Macchine di Moore

•  DEF Una macchina di Moore è una sestupla (Q,Σ,Δ,δ,λ,q0) dove Δ è un alfabeto di output, e λ è una funzione di transizione λ : Q → Δ, che associa un simbolo di output ad ogni stato. Per ogni stato, λ(qi)=aj, aj∈Δ.

•  Un automa deterministico a stati finiti può essere visto come un caso speciale di macchina di Moore dove Δ=(0,1) e λ(qi)=1 se qi∈F.

•  Notare che nelle macchine con output non occorre una distinzione fra stati di accettazione e non.

q0 q1,a q2,b

,a

d

d

d

c Σ = c,d}{Δ = a,b}{

c c

Macchine di Mealy

•  DEF Una macchina di Mealy è una sestupla (Q,Σ,Δ,δ,λ,q0) , dove λ è un mapping da

•  QxΣ->Δ, ovvero λ(qi,bk)=aj, bk∈Σ, aj∈Δ.

q0 q1 q2 c,a

d,b

d,a

d,a c,a

c,b

Equivalenza fra macchine di Moore e Mealy

•  Teorema. Se M1= (Q,Σ,Δ,δ,λ,q0) é una macchina di Moore, allora esiste una macchina di Mealy equivalente M2.

•  Dimostrazione. sia M2=(Q,Σ,Δ,δ,λ',q0) e definiamo: λ'(q,a)=λ(δ(q,a))

•  Allora, M2 è equivalente a M1 e segue le stesse transizioni, emettendo ad ogni transizione l'output associato allo stato di arrivo in M1.

Equivalenza Mealy Moore •  Teorema. Se M1= (Q,Σ,Δ,δ,λ,q0) é una macchina di Mealy, allora esiste una

macchina di Moore equivalente M2.

•  Dimostrazione. sia M2=(QxΔ,Σ,Δ,δ',λ',(q0 b0)), dove b0 é un qualsiasi carattere di Δ. Gli stati M2 sono coppie rappresentate da stati di M1 e simboli di Δ. Definiamo δ'((q, b),a) = (δ(q,a), λ(q,a)) e λ'((q,b))=b

•  I due automi sono equivalenti, infatti le transizioni di M2 da uno stato all'altro sono determinate solo dal primo elemento della coppia che identifica lo stato, e dal valore dell'input. Ovvero, da uno stato (q, b), quando si riceve il simbolo a, si transita in uno stato (q', c) il cui primo elemento rappresenta lo stato in cui transita M1 quando da q riceve a ed il cui secondo elemento rappresenta l'output che , nella macchina di Mealy, avrebbe assunto l'output transitando in quello stato dallo stato q a fronte di un certo input a.

Minimizzazione degli ASF

•  Poiché, come vedremo, un automa é un modello astratto di una macchina sequenziale, é intuitivo il fatto che sia conveniente minimizzare un automa, ovvero trovare un automa equivalente che abbia il minimo numero di stati. Ridurre il numero di stati infatti equivale a ridurre il numero di componenti di memoria nel circuito corrispondente.

Distinguibilità

•  Sia dato un automa di Moore M (Q,Σ,Δ,δ,λ,q0). Due stati p e q si dicono distinguibili in una macchina di Moore se gli output associati a p e q sono diversi, o se per qualche sequenza di simboli a1a2..an ricevuti a partire da p e q, si transita in due stati p' e q' caratterizzati da output diversi.

Esempio 1

•  Gli stati q0 e q1 sono indistinguibili

q0 q1 q2 c,a

d,b

d,a

d,a c,a

c,b

Esempio 2

•  (q3,q4) (q0,q2)

q0 q1 q2

d,b

d,a

d,a c,a

q3 q4

c,b c,b

d,b d,b c,a

c,a

Passo 1; tabella triangolare

•  Si traccia, a partire dall'automa o dalla sua tabella degli stati futuri, una tabella triangolare che permetta, ai suoi incroci, di indicare il risultato del confronto di ogni possibile coppia di stati.

q0 q1 q2 q3

q1 q2 q3 q4

Passo 2: marcatura delle celle

•  Si esaminano una dopo l'altra tutte le possibili coppie di righe della tabella degli stati futuri, inserendo nel corrispondente incrocio della tabella triangolare:

–  una X se in almeno una colonna risultano specificate uscite diverse

–  la denominazione della coppia di stati futuri individuati colonna per colonna se in tutte le colonne le uscite risultano uguali.

–  non si scrive nulla nel caso in cui le indicazioni di stato futuro siano identiche o coincidano con la denominazione della coppia di stati presa in esame

q0 q1 q2

d,b

d,a

d,a c,a

q3 q4

c,b c,b

d,b d,b c,a

c,a

q0 q1 q2 q3

q1 q2 q3 q4

x 3,4 x x

x x x

x x

Osservazioni Le caselle con X individuano stati distinguibilisulla base di un solo simbolo di ingresso, oppuredel simbolo di uscita.Le caselle con indicazione di una o più coppie distati futuri indicano stati indistinguibili persequenze di ingresso di lunghezza 1. Per questistati, la decisione deve essere rimandata.Le caselle vuote (o col pallino) viceversaindividuano stati indistinguibili per sequenze diingresso di lunghezza qualsiasi.

Passo 3 : marcatura progressiva delle celle “sospese”

•  Ogni qual volta si marca una casella (qi,qj) con una X o con un •, si verifica se qualcuna delle caselle precedentemente esaminate contiene la coppia (qi,qj) , e eventualmente, si aggiorna la marcatura di quella casella

q0 q1 q2 q3

q1 q2 q3 q4

x 3,4 x x

x x x

x x

x

x x

x x x

x x

Passo 4: classi di indistinguibilità

•  Procedendo da destra verso sinistra si esaminano una dopo l'altra le colonne della tabella triangolare contenente caselle con il pallino e si costruisce un corrispondente sottoinsieme S con la denominazione della colonna stessa e delle righe relative

•  Si controllano via via i sottoinsiemi che risultano contenuti in sottoinsiemi individuati. Questi sottoinsiemi prendono il nome di classi di indistinguibilità. Es: S1: q0,q2 e S2: q3, q4

•  Si costruisce la tabella degli stati futuri minima (o il grafo) copiando solo le righe della tabella di partenza che corrispondono al primo stato di ciascuna classe di indistinguibilità, e correggendo di conseguenza le indicazioni dello stato futuro.

Esempio

q0 q1 q2

d,b

d,a

d,a c,a

q3 q4

c,b c,b

d,b d,b c,a

c,a

q’0

q1

q’3

d,a

d,b

c,b

c,a

d,b

c,a

Esempio: Semplificare e costruire l’automa di Moore corrispondente

0/1

1/1

1/0

s2

0/0

0/0

1/1 s0 s1

Tabella triangolare

S1

S2

S0 S1

x

x

S0,S2 S1

Automa di Mealy Minimizzato

S0=S2 S1

1/1

1/0

0/0 0/1

Mealy-to-Moore Stati dell’automa di Moore: (S0,0) (S0,1) (S1,0) (S1,1)

Funzione di output: λmoore(S0,0)=0 λmoore(S0,1)=1 λmoore(S1,0)=0 λmoore(S1,1)=1

Funzione di transizione: δmoore((S0,0),0)=(S0,0) δmoore((S0,0),1)=(S1,1) δmoore((S0,1),0)=(S0,0) δmoore((S0,1),1)=(S1,1) δmoore((S1,0),0)=(S1,1) δmoore((S1,0),1)=(S1,1) δmoore((S1,1),0)=(S0,0) δmoore((S1,1),1)=(S1,1)

indistinguibili

δmoore((Si,ok),ij)=(δmealy(Si,ij),λmealy(Si,ij)) ok∈Δ e ij∈Σ

λmoore((Si,ok))= λmealy( ok) , ok∈Δ)

Automa di Moore equivalente

S0,0 S1,1

0 0 1

1