Lezione 2 Sintesi di circuiti sequenziali -...

L 2 – 1 Architetture Digitali Copyright: Federico Pedersini – DSI, UniMI

Corso di Architetture Digitali

Lezione 2

Sintesi di circuiti sequenziali

Federico Pedersini

Laboratorio di Architetture Digitali Dipartimento di Informatica

Università degli Studi di Milano

Riferimenti bibliografici: F. Fummi, M. Sami, C. Silvano, Progettazione Digitale, McGraw-Hill, capp. 6,7


Circuiti sequenziali

!  Circuiti combinatori = circuiti senza memoria "  Gli output al tempo t dipendono unicamente dagli input al tempo t

Uscita = f ( Ingresso )

!  Per consentire ad un dispositivo di mantenere le informazioni, sono necessari circuiti con memoria "  Esempio: distributore automatico

!  Deve ricordare quante e quali monete sono state inserite !  Deve comportarsi tenendo conto non solo delle monete inserite attualmente (ingresso) ma

anche di quelle inserite in precedenza (storia passata)

!  Circuiti sequenziali = circuiti con memoria (stato) "  La memoria contiene lo stato del sistema

Uscita = f ( Ingresso , Stato )


Macchine sequenziali

!  Macchina combinatoria: U = f ( I ) "  senza memoria, uscita dipende solo dagli ingressi

!  Macchina sequenziale: X* = f ( X, I ) U = g( X )

"  2 funzioni: uscita e stato prossimo "  esiste la memoria: lo STATO

U I U I

X

combinatoria sequenziale


Macchine sequenziali

!  Elemento necessario di ogni macchina sequenziale è la retroazione "  Uscita riportata in ingresso "  Bistabile: (macchina sequenziale elem.): 2 porte NOR +retroazione

S

R

Q

Q

Macchina sequenziale sincrona Impiega bistabili sincroni Es: Flip-Flop tipo DT

D

T

Q

I U

CLK

rete combinatoria

macchina sequenziale

retroazione


Latch & Bistabili

!  Elemento cardine dei circuiti sequenziali è lo stato "  Lo stato riassume il funzionamento negli istanti precedenti e deve essere

immagazzinato (memorizzato) "  Necessità della memoria (bistabili ! registri ! memorie)

!  Elemento base della memoria è il bistabile "  dispositivo in grado di mantenere indefinitamente il valore di input "  Il suo valore di uscita coincide con lo stato "  Memoria: insieme di bistabili (bistabili ! registri ! memorie)

!  Tipologie di bistabile "  Bistabili non temporizzati (asincroni) / temporizzati (sincroni). "  Bistabili (sincroni) che commutano sul livello (latch) o sul fronte (flip-flop)


Latch Set-Clear (Set-Reset) asincrono

!  Funzionamento: "  Set: C = 0, S ! 1 Q ! 1 (~Q ! 0) "  Reset: S = 0, C ! 1 Q ! 0 (~Q ! 1)

"  Comportamenti anomali: "  S = 1 , C: 0!1 Q=~Q=0 (anomalia)

Latch SC


!  Tabella delle transizioni: Q* = f(Q,I) = f(Q,S,C) "  Q: valore dell’uscita attuale: stato corrente "  Q*: uscita al tempo successivo: stato prossimo

Tabella delle transizioni

Q SC = 00 SC = 01 SC = 11 SC = 10

0 0 0 X 1

1 1 0 X 1

Q*

SET Clear / Reset Q* = Q

S C Q Q*

0 0 0 0

0 0 1 1

0 1 0 0

0 1 1 0

1 0 0 1

1 0 1 1

1 1 0 X

1 1 1 X


Latch SR sincrono

LATCH S-R sincrono: !  Latch SR + Porte AND tra il

clock e gli ingressi. "  Solo quando il clock è alto i

“cancelli” (porte AND) fanno passare gli input ! LATCH

S

R

CLK

Q

Q

S

R

CLK

Q

Q


Sintesi della funzione logica

TQ SR = 00 SR = 01 SR = 11 SR = 10

00 0 0 X 0 01 1 1 X 1 11 1 0 X 1 10 0 0 X 1

Tabella delle transizioni: Q*= f(S,R,T,Q) T Q S R Q* 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 X 0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 X 1 0 0 0 0 1 0 0 1 0 1 0 1 0 1 1 0 1 1 X 1 1 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 X

!

Q* = TQSR + TQSR + TQSR + TQSR + TQSR + TQSR +

= +TQSR + TQSR( ) =

= TQR + TQR + TQR + TQS =

= TQ+ T QR +QS( )clock alto ! Q* = Q~R + ~QS clock basso ! Q* = Q (status quo)


if CLK = 1 then Q*=D else Q*=Q

Latch D sincrono

!  LATCH D sincrono: "  Memorizza il valore presente all’ingresso dati quando il clock è alto

!  Clock BASSO: "  L’uscita Q rimane bloccata sull’ultimo valore assunto

!  Clock ALTO: "  L’uscita Q insegue l’ingresso D (con 3Δτ di ritardo)

D-Latch

D

CLK Q

Q

(T)

D

CLK Q

Q


La struttura del latch D

D

CLK Q

Q

D

CLK

Q _ Q

CLK alto

2!" !"

CLK basso




!  Dalla tabella delle transizioni Q* = f(T,Q,D) calcolo la corrispondente funzione logica:

Funzione logica: T Q D Q* 0 0 0 0 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 1

TDQT

TQDDQTQDTDQTQ

+=

=+++=*

Clock T basso ! Q* = Q (status quo)

Clock T alto: ! Q* = D (input)


!  I latch sono dispositivi trasparenti: "  Per tutto il tempo in cui il clock è attivo (alto), il valore di D viene riportato

in uscita: Q = D : uscita collegata all’ingresso

!  A noi interessa memorizzare l’informazione in un determinato istante

Latch: Bistabili level-sensitive

D

CLK Q

Q

if CLK = 1

then Q*=D

else Q*=Q


Bistabili “edge sensitive”: i Flip-Flop

!  Dispositivi attivi sul fronte del clock (edge sensitive): "  il loro stato (uscita) può commutare solo in corrispondenza del fronte di

salita o di discesa del clock.

Bistabile tipo DT – Configurazione “Master-Slave”

Flip-Flop – tipo DT

D

CLK

Qmaster = Dslave

Qmaster Q

Q

Dmaster Qslave Master Slave


Flip-flop: struttura master–slave

!  FLIP (clock ALTO): L’ingresso D viene memorizzato nel latch MASTER "  L’ingresso è aperto, ma l’uscita è bloccata

!  FLOP (clock BASSO): l’uscita stabile del latch MASTER viene propagato al latch SLAVE

"  L’ingresso è bloccato, l’uscita è stabile.

D

CLK Qm= Ds

Qm= Ds

Q

Q

CLK

Dm

Dm


Funzionamento: FLIP

D

CLK = 1 Qm= Ds

Qm= Ds

Q

Q

CLK

Dm

Dm Flip

CLK

D

Qm

CLK•D

Qm

t


Funzionamento: FLOP

D

CLK = 0 Qm= Ds

Qm= Ds

Q

Q

CLK

Dm

Dm Flop

CLK

Qm

Q

CLK•Qm

Q

t


Registri

Registro a N bit: N Flip-flop tipo DT SCRITTURA: "  L’impulso di CLK memorizza i dati

sugli ingressi D LETTURA: "  I dati memorizzati sono presenti

sulle uscite Q

Registro a scorrimento (shift register) L’ impulso di CLK fa scorrere i dati di una posizione lungo il registro

I = D2

CLK

Q2 = D1

Q Q Q

Q1 = D0 Q0 = U


Circuiti sincroni e asincroni

!  Architettura sincrona: le fasi di elaborazione e propagazione dei segnali sono scandite da un orologio comune a tutto il circuito (clock) "  Il Clock regola l’attività dei “cancelli” "  Il circuito ha il tempo di stabilizzarsi (transitori critici) fino al successivo impulso di

Clock

!  Architettura asincrona: l’elaborazione e propagazione dei segnali avviene in modo incontrollato, secondo le velocità di reazione dei circuiti "  Non ci sono cancelli "  Non devo mai aspettare l’impulso di clock → massima velocità

!  Progettazione sincrona "  il controllo dei transitori/cammini critici è limitato alla parte di circuito tra due

cancelli (porte di sincronizzazione)

!  Progettazione asincrona "  Devo progettare il circuito in modo che nessun transitorio/cammino critico causi

problemi → analisi di tutti i transitori critici possibili


Struttura di un circuito sincrono

Cancello ! Circuito combinatorio ! Cancello

!  Sincronizzazione: la logica combinatoria deve terminare la propria commutazione in tempo utile

Logica combinatoria D Q

flip-flop T

D Q flip-flop

T

CLK

In Out


Sincronizzazione mediante flip-flop

!  I “cancelli” devono disaccoppiare i diversi sottosistemi logici "  “raccogliere” i segnali, senza farli passare, e “rilanciarli” ad un determinato istante "  Cancello doppio: ingresso e uscita "  Mai aperti contemporaneamente

!  Cancelli = registri costituiti da gruppi di flip-flop


Macchina a Stati Finiti

!  Una Macchina a Stati Finiti (MSF) è definita dalla quintupla:

< X, I, Y, f(·), g(·) >

X: insieme degli stati (in numero finito). I: alfabeto di ingresso: l’insieme dei simboli che si possono presentare in ingresso.

Con n ingressi, avremo 2n possibili configurazioni. Y: alfabeto di uscita: l’insieme dei simboli che si possono generare in uscita.

Con m uscite, avremo 2m possibili configurazioni.

f(·): funzione stato prossimo: X* = f( X , I ) Definisce l’evoluzione della macchina nel tempo, in modo deterministico

g(·): funzione di uscita: Y= g( X ) (macchina di Moore) Y= g( X , I ) (macchina di Mealy)

"  Per il buon funzionamento della macchina è previsto uno stato iniziale, al quale la macchina può essere portata mediante un comando di reset.


i1 i2 … iN Y

x1 x*(x1,i1) x*(x1,i2) x*(x1,iN) y(x1)

x2 x*(x2,i1) x*(x2,i2) x*(x2,iN) y(x2)

… …

xM x*(xM,i1) x*(xM,i2) x*(xM,iN) y(xM)

State Transition Table (STT) - Macchina di MOORE

!  STT: State Transition Table (Tabella delle transizioni di stato) "  Per ogni coppia: <stato attuale, ingresso>

definisco uscita y e stato prossimo x*

(xi∈ X , ij∈ I) ! y(xi) ; x*( xi, ij )

"  Esempio: M stati (log2M bit di stato), N ingressi (log2M bit d’ingresso):


i1/Y i2/Y … iN/Y

x1 x*(x1,i1)/y11 x*(x1,i2)/y12 x*(x1,iN)/y1N

x2 x*(x2,i1)/y21 x*(x2,i2)/y22 x*(x2,iN)/y2N

…

xM x*(xM,i1)/yM1 x*(xM,i2)/yM2 x*(xM,iN)/yMN

State Transition Table (STT) - Macchina di MEALY

!  STT: State Transition Table (Tabella delle transizioni di stato) "  Per ogni coppia: <stato attuale, ingresso>

definisco uscita y e stato prossimo x*

(xi∈ X , ij∈ I) ! y(xi) ; x*( xi, ij )

"  Esempio: M stati (log2M bit di stato), N ingressi (log2M bit d’ingresso):


Macchina di MOORE: State Transition Graph (STG)

!  STG: State Transition Graph (Diagramma degli Stati o Grafo delle transizioni) "  Ad ogni nodo è associato uno stato: xi ∈ X

... ed un valore della funzione d’uscita: yi ∈ Y, yi=g(xi)

"  Un arco orientato da uno stato xi ad uno stato xj, contrassegnato da un simbolo (di ingresso) iK, rappresenta una transizione che si verifica quando la macchina, essendo nello stato xi, riceve come ingresso iK

xI ∈ X xJ ∈ X

iK ∈ I

yI = g(xI) yJ = g(xJ) xJ = f(xI,iK)


Macchina di MEALY: State Transition Graph (STG)

!  STG: State Transition Graph (Diagramma degli Stati o Grafo delle transizioni) "  Ad ogni nodo è associato uno stato: xi ∈ X

... ed un valore della funzione d’uscita: yi ∈ Y, yi=g(xi)

"  Un arco orientato da uno stato xi ad uno stato xj, contrassegnato da un simbolo (di ingresso) iK, rappresenta una transizione che si verifica quando la macchina, essendo nello stato xi, riceve come ingresso iK

xI ∈ X xJ ∈ X

iK ∈ I

yIJ = g(xI,iK)

x*IJ = f(xI,iK)


La macchina sequenziale di Huffman - sincrona

Stato

io i1 iM

yo y1 yN

" ‘ x*1

xK

x1

x*K

Ingressi Uscite

Stato prossimo


Progetto con macchina di Moore

Esempio: controllore di un semaforo SEMAFORO: !  Incrocio tra 2 strade: nord-sud (NS) ed est-ovest

(EO) controllate da un semaforo "  per semplicità consideriamo solamente rosso e verde

!  Il semaforo può commutare ogni 30 secondi "  Macchina sincrona, clock con frequenza = ?

!  E’ presente un sensore in grado di “leggere”, per ogni direttrice, se esiste almeno un’auto in attesa, oppure un’auto che si accinga ad attraversare (condizioni trattate allo stesso modo).

!  Il semaforo deve cambiare colore, da rosso a verde, quando esiste un’auto in attesa sulla sua direttrice.

!  Se ci sono auto in attesa sulle entrambe le direttrici il semaforo deve cambiare colore (al termine del tempo di commutazione)

auto NS sì / no

auto EO sì / no


SEMAFORO: Stato, Ingresso, Uscita

STATO "  Semaforo NS VERDE, semaforo EO ROSSO "  Semaforo NS ROSSO, semaforo EO VERDE

→ 1 bit di STATO (1 flip-flop)

INGRESSI "  Auto NS presente / non presente

!  AutoNS=1/0 "  Auto EO presente / non presente

!  AutoEO = 1/0

→ 4 configurazioni di INGRESSO → 2 bit

USCITE: = STATO "  LuceEO verde (LuceNS rossa) "  LuceNS verde (LuceEO rossa)

→ 2 configurazioni d’uscita → 1 bit

auto NS sì / no

auto EO sì / no


STG – State Transition Graph

!  Funzione stato prossimo: VerdeNS* = VerdeNS · ~autoEO + VerdeEO · autoNS VerdeEO* = VerdeEO · ~autoNS + VerdeNS · autoEO

!  Funzione uscita: Y = X

AutoEO = 1

AutoNS = 1

AutoEO = 0 AutoNS = 0

VerdeEO VerdeNS

LuceVerde NS

LuceVerde EO


STT – State Transition Table

~autoEO ~autoNS

~autoEO autoNS

autoEO ~autoNS

autoEO autoNS Uscita

VerdeNS VerdeNS VerdeNS VerdeEO VerdeEO Luce VerdeNS

VerdeEO VerdeEO VerdeNS VerdeEO VerdeNS Luce VerdeEO

I X

Funzione stato prossimo: X* = f(X, I)

Funzione uscita: Y = g(X)

!  È una rappresentazione equivalente allo STG


STT del semaforo: CODIFICA binaria

!  Stato: "  (VerdeNS/RossoEO, RossoNS/VerdeEO) → (0, 1)

!  Ingresso: "  2 Variabili: AutoNS, AutoEO → 1 =“presente”, 0 =“assente” "  4 Configurazioni: (00, 01, 10, 11)

!  Uscita: "  (Luce_VerdeNS, Luce_VerdeEO) → (0, 1)

00 01 10 11 Uscita Y

0 0 0 1 1 0

1 1 0 1 0 1

I X


XY

IXIX

IIXIXIIIXIIXX

=

+=

=+++=

10

11010010*

00 01 10 11 Y

0 0 0 1 1 0

1 1 0 1 0 1

Sintesi della MSF del semaforo

I X

!  Mediante la STT codificata in binario, posso esprimere X* e Y come somma di prodotti: "  cerco i mintermini:


MSF del semaforo: sintesi del circuito

XY

IXIX

IIXIXIIIXIIXX

=

+=

=+++=

10

11010010*

i0

i1

X

X*

Y

rete combinatoria

TCLK = 30 sec

2 reti combinatorie:

X* = f (X,I) Y = g (X’)

I

X X*

Clock

D Q

T

Y i0

i1


Esercizi: sintesi di macchine sequenziali

!  Contatore modulo 4 di impulsi "  Si sintetizzi una macchina a stati finiti (di Moore) che realizza un

contatore modulo 4 così strutturato: !  L’ingresso è costituito da una linea di 1 bit che viene osservata ogni millisecondo. !  L’uscita è costituita da 4 linee, che rappresentano i 4 valori assumibili dal

contatore: ciascuna uscita va a “1” solo quando il contatore contiene il valore da essa rappresentato.

!  Il contatore incrementa il proprio valore in corrispondenza di ogni fronte di salita dell’ingresso.

"  I = { “0” , “1” } "  Y = { “1000” (0) , “0100” (1) , “0010” (2) , “0001” (3) }

"  X = { 0 , 1 , 2 , 3 } (è un contatore...)


Esercizi: sintesi di macchine sequenziali

!  Tastiera a combinazione "  Si sintetizzi una macchina a stati finiti che gestisce una tastiera a

combinazione segreta. La macchina genera un segnale di “apertura” soltanto soltanto quando si premono in sequenza i tasti: “1,2,3”. (suggerimento: si consideri una sola linea d’ingresso per tutti i tasti diversi da 1,2,3)

"  Semplificazione: non considero il tempo... "  I = { “nessun tasto”, “1”, “2”, “3”, “altri tasti” } "  Y = { “0” , “1” (apertura) }


Esercizio: sintesi di macchine sequenziali

!  Riconoscitore sequenza "  Progettare e sintetizzare una macchina che accetti in ingresso un

carattere binario (0 o 1) e sia caratterizzata da tre uscite, di cui: !  la prima si porta a “1” quando gli ultimi 3 bit della sequenza in ingresso siano

stati: “110”, !  la seconda si porta a “1” quand’essi abbiano assunto il valore: “011”, !  la terza si porta a “1” quand’essi abbiano assunto il valore: “111”.


Macchina a Stati Finiti

!  Una Macchina a Stati Finiti (MSF) è definita dalla quintupla:

< X, I, Y, f(·), g(·) >

X: insieme degli stati (in numero finito). I: alfabeto di ingresso: l’insieme dei simboli che si possono presentare in ingresso.

Con n ingressi, avremo 2n possibili configurazioni. Y: alfabeto di uscita: l’insieme dei simboli che si possono generare in uscita.

Con m uscite, avremo 2m possibili configurazioni.

f(·): funzione stato prossimo: X* = f( X , I ) Definisce l’evoluzione della macchina nel tempo, in modo deterministico

g(·): funzione di uscita: Y= g( X ) (macchina di Moore) Y= g( X , I ) (macchina di Mealy)

"  Per il buon funzionamento della macchina è previsto uno stato iniziale, al quale la macchina può essere portata mediante un comando di reset.


Macchine sincrone – Minimizzazione degli stati

!  Date 2 macchine sincrone: M1= <X1,I1,Y1,f1,g1> M2= <X2,I2,Y2,f2,g2>

!  M1 e M2 sono equivalenti sse: !xa " X1 , #xb " X2 tale che:

ponendo al tempo t=0: M1 in xa e M2 in xb ed applicando una qualsiasi sequenza di ingresso I(t) a entrambe le macchine, $ Y1(t) = Y2(t), !t>0

!  Due stati sono equivalenti o indistinguibili xi ~ xj sse: "  partendo da xi o da xj, per ogni sequenza d’ingresso, le uscite sono uguali "  Proprietà riflessiva, simmetrica, transitiva # partizione su X

!  Macchina M è minima sse:

se, cioè, non esistono stati equivalenti in M. "  Si dimostra che la macchina minima M è unica

!

" xi,x j # X xi ~ x j


Minimizzazione degli stati - Algoritmo di Paull-Unger

!  Algoritmo di Paull-Unger: "  metodo operativo per l’identificazione di stati equivalenti:

"  xi ~ xj se e solo se: – MEALY: #ia$ I, f(xi,ia) = f(xj,ia); g(xi ,ia) = g(xj ,ia) – MOORE: #ia$ I, f(xi,ia) = f(xj,ia); g(xi) = g(xj)

"  Definizione recursiva di equivalenza: si rimanda all’equivalenza degli stati prossimi "  Se: N=|X| # devo effettuare N2 confronti (su tutti gli ingressi) "  rifl. + simm. # mi bastano: N(N – 1) / 2 confronti

!  Tabella delle implicazioni: "  Tabella triangolare: N–1 righe, N–1 colonne "  Ogni cella rappresenta una coppia di stati distinti: < xi , xj >, i ! j "  In ogni cella scrivo:

‘~’ se: xi ~ xj (i due stati sono EQUIVALENTI) ‘X’ se: ¬( xi ~ xj ) (i due stati sono DISTINGUIBILI) (xA , xB ) se: xA ~ xB ! xi ~ xj (distinguibilità/equivalenza VINCOLATA)


Algoritmo di Paull-Unger

Analisi ricorsiva della tabella delle implicazioni

1.  Riempio la tabella

2.  Analizzo recursivamente ogni caso di vincolo

3.  Dopo un n. finito di passi, arrivo ad una delle seguenti 3 soluzioni: "  tutte le coppie sono state dichiarate equivalenti o distinguibili

"  Circolarità di vincolo: xA~ xB ! xi ~ xj ! ... ! xA ~ xB

# tutte le coppie incluse

s2 X

...

sN–1 X ~

sN ~ (sA,sB) X

s1 s2 ... sN–1

Esempio: N=|X|=5


Algoritmo di Paull-Unger

Esempio: FSM di Mealy a 5 stati Step I: Equivalenti: (C,E)

Condizionati: (A,B) # (B,C) (A,D) # (A,E) (B,D) # (A,E) e (C,B)

Step II: Condizionati: (B,C)=X # (A,B)=X (A,E)=X , (B,C)=X # (B,D)=X $ ne basta uno distinguibile

Risultato: Mmin = { A, B, (C,E), D }

Step I Step II STT minima (4 stati)

STT originaria (5 stati)


Esempio minimizzazione stati

!  Segnapunti Tennis "  Si progetti una FSM che memorizzi il punteggio di un “game” di

una partita di tennis. "  2 linee d’ingresso: “punto A”, “punto B” "  2 linee d’uscita: “game A”, “game B” (a livelli)

"  Determinare la macchina minima.


Sintesi di macchine sequenziali asincrone "  macchine in modo impulsivo

"  macchine in modo fondamentale


Macchine sequenziali asincrone

Esistono 2 categorie di FSM asincrone:

!  FSM asincrone in modo impulsivo "  reagiscono ad impulsi in ingresso

"  Uscite: a livelli (FSM asincrone di Moore) a impulsi (FSM asincrone di Mealy)

"  Memoria: bistabili asincroni (Latch SC, FF Toggle)

"  Per la sintesi di queste FSM si può ancora utilizzare il formalismo delle FSM sincrone, con opportune modifiche.

!  FSM asincrone in modo fondamentale "  Reagiscono ai livelli in ingresso

"  Uscite: a livelli

"  Memoria: retroazione sui circuiti (non necessariamente bistabili)

"  I metodi di sintesi di queste FSM sono differenti e più complessi.


FSM asincrone ad impulsi – bistabili asincroni

Bistabile SET-CLEAR asincrono:

!  Un impulso su SET porta lo stato a “1” !  Un impulso su CLEAR porta lo stato a “0”

S

C

Q

Q

LatchSC

S

C

Q t

V(t)


Bistabile TOGGLE

Bistabile TOGGLE

!  Realizzato mediante un flip-flop tipo D retroazionato

!  Ogni impulso in ingresso commuta lo stato del bistabile

FF D-T

T Q

Q D

Q T

FF tipo T

FF tipo T

Q T

T

Q t

V(t)

Master: store ‘1’

Slave: out ‘1’ # Q=0


FSM asincrone – modo impulsivo

Procedura di sintesi FSM asincrone in modo impulsivo:

1.  Definizione della macchina

Uscite a stati # MOORE Uscite impulsive # MEALY

2.  Costruzione STG, STT esattamente come nel caso di FSM sincrone

3.  Codifica binaria STT

NON codifico gli ingressi – non sono valori stazionari, ma impulsi (eventi): i(t)

4.  Scelta bistabile (SC, T) e sintesi della tabella delle eccitazioni

Tabella delle eccitazioni: ESC/T = h( ingresso, stato ) (dipende dal tipo di bistabile adottato)

5.  Sintesi circuitale (Rete Combinatoria): funzione delle eccitazioni, funzione uscita.


Tabella delle eccitazioni

!  Tabella delle transizioni: definisce il valore di ingresso ai bistabili sincroni

FSM sincrone: transizione comandata dal clock. È sufficiente presentare lo stato prossimo agli ingressi dei bistabili.

FSM asincrone: manca un comando esplicito di transizione. È necessario generare segnali agli ingressi dei bistabili, che li portino allo stato prossimo. # eccitazioni

!  Tabella delle eccitazioni: definisce il valore in ingresso ai bistabili asincroni (eccitazione)

"  Dipende dal tipo di bistabile:

!  TOGGLE:

!  SET-CLEAR:

!

STT : xik* = f xi,ik( ) , "xi # X, ik # I

!

ET(Toggle) : tik* = f xi,ik( ) , "xi # X, ik # Itik* =1 sse xik

* = f xi,ik( ) = xi

!

ET(SC) : sik = fS xi,ik( ) ;cik = fC xi,ik( ) , "xi # X, ik # Isik =1, cik = 0 sse xik

* = f xi,ik( ) =1 (, xik = 0)

cik =1, sik = 0 sse xik* = f xi,ik( ) = 0 (, xik =1)

$ % &

' &


Esempio di sintesi FSM impulsiva

Esempio: Progetto FSM asincrona, con ingressi impulsivi, uscite a livelli. !  Macchina con 2 ingressi A,B ed un’uscita Z a livelli.

"  Z è ‘1’ quando gli ingressi si alternano "  Z è ‘0’ quando arrivano 2 ingressi uguali "  Stato iniziale: “AA”

------------------------- "  ingressi impulsivi, uscite a livelli # MOORE "  ...



Esempio: Progetto FSM asincrona, ingressi e uscite a impulsi !  Macchina con 2 ingressi impulsivi A,B ed un’uscita impulsiva Z.

"  Z produce un impulso a partire dal 2º impulso consecutivo su A "  per ogni nuovo impulso sugli ingressi, Z ha un impulso... "  ... finché non si presentano due impulsi consecutivi su B.

------------------------- "  ingressi impulsivi, uscite a impulsi # MEALY ...



Esempio: Contatore asincrono di impulsi, modulo 8

!  Ingresso a impulsi; !  Uscita (valore del contatore) a livelli; " Macchina di Moore

...

Lezione 2 Sintesi di circuiti sequenziali -...

Documents

Transcript of Lezione 2 Sintesi di circuiti sequenziali -...