Reti sequenziali

Le reti combinatorie non ricordano niente: la stessa combinazione di ingressi dà sempre la stessa uscita. Un calcolatore però deve memorizzare dati, istruzioni, lo stato di un'elaborazione. Questo modulo parte dalla rete più piccola capace di ricordare un bit, il latch SR, e arriva alle reti che evolvono al ritmo di un clock: registri, contatori, automi. In mezzo impariamo il Verilog, il linguaggio con cui all'esame si descrivono le reti.

La memoria e le reti asincrone

Il latch SR

Il latch SR ha due ingressi, s (set) e r (reset), e un'uscita q (più la sua negata q_N). Si costruisce con due porte NOR in retroazione: l'uscita di ciascuna torna all'ingresso dell'altra. Ragioniamo caso per caso:

• s = 1, r = 0: la NOR in alto ha un ingresso a 1, quindi q_N = 0; quella in basso riceve 0 e 0 e dà q = 1. L'uscita si setta;
• s = 0, r = 1: simmetricamente q = 0, q_N = 1. L'uscita si resetta;
• s = 0, r = 0: ciascuna NOR nega l'uscita dell'altra, e l'anello si tiene da solo nello stato in cui era: l'uscita conserva l'ultimo valore. È qui che nasce la memoria;
• s = 1, r = 1: entrambe le uscite valgono 0, contraddicendo la regola q_N = q. È uno stato di ingresso vietato.

La rete è sequenziale (con s = r = 0 l'uscita dipende dalla storia) e asincrona (si aggiorna continuamente). La tabella di applicazione, da non confondere con una tabella di verità, dice quale comando dare per far passare l'uscita da q a q':

q	q'	s	r	comando
0	0	0	–	conserva o resetta
0	1	1	0	setta
1	0	0	1	resetta
1	1	–	0	conserva o setta

Come si pilota un latch SR

Delle due regole di pilotaggio delle reti asincrone, la prima (cambiare gli ingressi solo a regime, dopo pochi nanosecondi) va rispettata. La seconda (stati di ingresso consecutivi adiacenti) per il latch SR è meno critica: passando da 10 a 01 si attraversa per un attimo 00 (conserva) o 11 (entrambe le uscite a 0 per un istante), e in entrambi i casi il latch arriva nello stato giusto. Il latch SR è robusto, ed è un bene, perché è alla base di registri e memorie.

Una sola cosa non deve mai succedere: passare da 11 a 00. Il primo ingresso che torna a 0 deciderebbe lo stato finale, e il latch memorizzerebbe di fatto un bit a caso. Prova nel diagramma temporale qui sotto, dove puoi disegnare gli ingressi cliccando sugli intervalli:

Il problema dello stato iniziale

All'accensione il contenuto di un latch è casuale. Per alcuni elementi di memoria va bene (le celle della RAM), per altri no: il registro che contiene l'indirizzo della prossima istruzione del processore deve partire da un valore preciso. Serve una fase di reset iniziale, distinta dal funzionamento normale, in cui ogni elemento di memoria si porta allo stato desiderato. Attenzione al doppio significato della parola: «reset» è sia il comando che azzera un latch, sia la fase di ritorno alla condizione iniziale, che non vuol dire mettere tutto a zero.

Per inizializzare un latch gli si aggiungono due ingressi attivi bassi, /preset e /preclear: a 1 entrambi il latch funziona normalmente; con /preset = 0 va a 1, con /preclear = 0 va a 0, qualunque cosa facciano s e r. Per inizializzare a 1 si collega /preset a /reset e /preclear a 1; per inizializzare a 0, il contrario.

Tabelle di flusso e grafi di flusso

Le reti sequenziali asincrone si descrivono con una tabella di flusso: sulle righe gli stati interni (per il latch SR, S0 in cui ricorda 0 e S1 in cui ricorda 1), sulle colonne gli stati di ingresso, e in ogni casella lo stato interno successivo in cui la rete transita con quello stato presente e quell'ingresso. Quando lo stato successivo coincide con quello presente, la rete è stabile e lo stato si cerchia (dimenticare il cerchio è un errore). Accanto si scrive l'uscita, che qui dipende solo dallo stato.

Tra parentesi gli stati stabili. Il grafo di flusso dice la stessa cosa con nodi (gli stati) e archi etichettati con gli stati di ingresso:

Il D-latch trasparente

Il D-latch ha un ingresso dati d e un ingresso di controllo c. Quando c = 1 è trasparente: l'uscita insegue d. Quando c = 0 è in conservazione: mantiene l'ultimo valore che d aveva con c = 1. Per memorizzare un bit si porta c a 1, si imposta d e si riporta c a 0. Si sintetizza mettendo davanti a un latch SR una piccola rete combinatoria: con c = 0 comando di conservazione (00), con c = 1 set se d = 1 e reset se d = 0. Quindi s = c·d e r = c·d.

Due regole di pilotaggio. Primo, d deve restare costante a cavallo della transizione di c da 1 a 0, per un tempo T_setup prima e T_hold dopo. Secondo, e più importante: siccome è trasparente, non si può memorizzare in un D-latch una funzione della sua stessa uscita. Se q torna su d attraverso un invertitore, finché c = 1 l'uscita oscilla, e quando c torna a 0 si ferma su un valore casuale. Le reti combinatorie, il latch SR e il D-latch sono tutte reti trasparenti.

Il D flip-flop

Gli elementi di memoria trasparenti si chiamano latch, quelli non trasparenti flip-flop. Il più importante è il D flip-flop positive edge-triggered, con ingressi d e p: «quando p ha un fronte di salita, memorizza d, aspetta un po' e adegua l'uscita». Il punto chiave è l'attesa: l'uscita cambia dopo che la rete ha smesso di essere sensibile all'ingresso.

• d deve restare costante a cavallo del fronte di salita di p, per T_setup prima e T_hold dopo;
• l'uscita si adegua dopo un tempo T_prop dal fronte, con T_prop > T_hold: è questa disuguaglianza a rendere la rete non trasparente;
• tra due fronti di salita deve passare abbastanza tempo perché l'uscita si adegui.

Siccome l'uscita non è mai collegata direttamente all'ingresso, un D flip-flop si può montare in qualsiasi modo: anche con d = q non succede niente di strano, e a ogni fronte di salita l'uscita semplicemente si inverte. Una realizzazione classica è la struttura master-slave:

Le memorie RAM statiche

Una RAM statica (S-RAM) è una matrice di D-latch: ogni riga è una locazione, che si legge o si scrive, mai le due cose insieme. Dall'esterno ha:

• i fili di indirizzo (ingressi): con 2²³ locazioni ne servono 23;
• i fili di dati, bidirezionali, forchettati con porte tri-state;
• i comandi attivi bassi /mr (memory read) e /mw (memory write), mai attivi insieme;
• il select /s, attivo basso: con /s = 1 la memoria ignora tutto. Serve, come l'enabler del decoder, a costruire memorie grandi con banchi piccoli.

Le RAM statiche sono velocissime (pochi nanosecondi: pochi livelli di logica) e si usano per le memorie cache; la memoria principale dei calcolatori è fatta di RAM dinamiche, costruite in tutt'altro modo. Due dettagli di temporizzazione: in lettura i dati sono buoni poco dopo che /s e /mr sono entrambi a 0, e tornano in alta impedenza quando /mr risale; in scrittura, che è distruttiva, indirizzi e /s devono essere stabili prima che /mw scenda, e i dati devono essere buoni a cavallo del fronte di salita di /mw.

Il select si genera da altri bit di indirizzo con una maschera. Esempio: su un bus indirizzi a 32 bit si vuole montare un modulo da 256M×8 (28 fili di indirizzo) a partire da 0xE0000000, cioè sugli indirizzi da 0xE0000000 a 0xEFFFFFFF. I 28 bit bassi vanno al modulo, i 4 alti alla maschera, che deve riconoscere 1110: /s = a₃₁a₃₀a₂₉a₂₈ = a₃₁ + a₃₀ + a₂₉ + a₂₈. Per questo il select si stabilizza sempre un po' dopo gli indirizzi.

Le memorie ROM

Una ROM (Read-Only Memory) di 2^N celle da M bit è, logicamente, una rete combinatoria a N ingressi e M uscite (con le tri-state per stare su un bus): al posto dei D-latch ci sono generatori di costante. Si realizza con il modello strutturale universale, un decoder e M porte OR collegate secondo il contenuto delle celle. Il contenuto si fissa in fabbrica (conveniente solo per grandi tirature) oppure è programmabile: PROM (fusibili che si bruciano una volta sola), EPROM (si cancellano con i raggi ultravioletti, attraverso la finestrella sul chip), EEPROM (si cancellano elettricamente, come la memoria delle impostazioni del BIOS). La riprogrammazione resta un'operazione lenta, limitata nel numero di volte e diversa dal normale funzionamento: per questo sono ROM e non RAM.

Il linguaggio Verilog

Moduli, fili e istanze

Per descrivere reti complesse serve una notazione testuale, compatta e interpretabile da un simulatore. Il corso usa il Verilog, in uno stile preciso e ristretto, introdotto con esempi. L'unità di base è il modulo, che dichiara ingressi e uscite; dentro un modulo si possono istanziare altri moduli e collegarli con fili (wire).

Le variabili a più bit si dichiarano con un intervallo, input [3:0] x3_x0;, e se ne prendono pezzi con x3_x0[1:0] o singoli bit con x3_x0[3]. Le parentesi graffe concatenano: {z1,z0} è una variabile a due bit. Per convenzione il nome di una variabile a più bit dice quali bit contiene (x3_x0, a22_a0).

Costanti, valori e commenti

• Il Verilog distingue maiuscole e minuscole; le parole chiave sono minuscole. Gli identificatori contengono lettere, cifre e _, e non iniziano con una cifra.
• Le costanti si scrivono n'Bvalore, n'Hvalore, n'Dvalore: n è il numero di bit (si può omettere), la lettera la base. 8'D32 è 32 su 8 bit; 16'B0010_1000_0101_1100 usa gli _ per leggibilità.
• Attenzione: la base predefinita è 10. Scrivere h=0101 assegna centouno; per i bit 0101 serve h='B0101.
• Una variabile può valere 0, 1, alta impedenza (1'BZ) o non specificato (1'BX, solo per le uscite).
• I commenti sono come in C++: // … e /* … */. Ogni istruzione finisce con ;.
• Le variabili attive basse, che nei disegni hanno la barra davanti (/reset), in Verilog prendono un _ in fondo: reset_.

Descrivere una rete combinatoria

Una rete combinatoria si descrive trascrivendo la tabella di verità nel modo più pedissequo possibile, con un assegnamento continuo assign: in ogni istante ciò che sta a sinistra si adegua a ciò che sta a destra, proprio come fa una rete asincrona. Il ritardo #T modella il tempo di attraversamento, utile in simulazione. Prendiamo la tabella a 3 ingressi e 2 uscite del modulo sulle reti combinatorie:

In alternativa si usa una function con un costrutto casex, che ammette default e il carattere ? per i bit irrilevanti. Regola d'esame: la function si usa solo per codificare tabelle di verità di reti combinatorie. Il Verilog non è un linguaggio di programmazione, e ogni altro uso è considerato un errore grave.

Descrizione o sintesi?

In Verilog si possono scrivere anche le sintesi, usando a destra di assign gli operatori logici & (AND), | (OR), ~ (NOT), ^ (XOR):

La differenza è fondamentale e va tenuta ben chiara in testa: una descrizione dice che cosa fa la rete e deve essere facile da verificare; una sintesi dice quali porte mettere. Per una rete combinatoria ricavare la tabella dal circuito è facile; per una rete sequenziale complessa è praticamente impossibile. Il fatto che il Verilog permetta entrambe le cose confonde: all'esame, quando si chiede una descrizione, si scrive una descrizione.

Le reti sequenziali sincronizzate

Il clock

Le reti sequenziali sincronizzate (RSS) evolvono solo in certi istanti, gli istanti di sincronizzazione, segnalati da un ingresso speciale: il clock. È un segnale periodico di periodo T (frequenza 1/T), con un rapporto tra tempo alto e periodo (duty cycle) non necessariamente del 50% ma né troppo piccolo né troppo grande. L'evento che sincronizza la rete è il fronte di salita. Non sono i cambiamenti degli ingressi a far evolvere una RSS, ma l'arrivo del clock.

I registri

Un registro a W bit è un insieme di W D flip-flop con ingressi e uscite indipendenti e il clock in comune. Lo stato di uscita è il contenuto del registro; usarlo come ingresso di una rete combinatoria è una lettura, memorizzare i bit in ingresso a un fronte del clock è una scrittura. Il contenuto iniziale si imposta collegando /preset e /preclear dei flip-flop a /reset o a 1.

Ne segue la regola che rende le reti sincronizzate così comode: tra due fronti di salita lo stato di ingresso ai registri può cambiare in qualunque modo, anche di più bit insieme, o non cambiare affatto (due fronti con lo stesso ingresso sono comunque due eventi distinti). La regola dell'adiacenza delle reti asincrone qui non esiste.

In Verilog un registro è una variabile reg; la scrittura si descrive con un assegnamento procedurale non bloccante <= dentro un blocco always, che dice quando avviene:

Da qui in avanti il ritardo di propagazione si scrive #3: conviene che sia maggiore di zero, altrimenti nelle simulazioni non si capisce che cosa succede prima e che cosa dopo.

Temporizzazione di una RSS

In prima approssimazione una RSS è un insieme di registri e reti combinatorie montati come si vuole, purché tutti i registri abbiano lo stesso clock e non ci siano anelli di sole reti combinatorie (sarebbero una rete asincrona); gli anelli che passano da un registro vanno benissimo.

Il clock non può andare veloce quanto si vuole: in ogni periodo bisogna lasciare il tempo a chi sta «a monte» di cambiare gli ingressi (T_{a_monte}), ai segnali di attraversare le reti combinatorie, a chi sta «a valle» di usare le uscite (T_{a_valle}). Chiamati T_{in_to_reg}, T_{reg_to_reg}, T_{in_to_out}, T_{reg_to_out} i tempi di attraversamento delle catene combinatorie più lunghe tra ingressi, registri e uscite, il periodo deve soddisfare quattro disuguaglianze:

1. T ≥ T_hold + T_{a_monte} + T_{in_to_reg} + T_setup (da ingresso a registro);
2. T ≥ T_prop + T_{reg_to_reg} + T_setup (da registro a registro);
3. T ≥ T_hold + T_{a_monte} + T_{in_to_out} + T_{a_valle} (da ingresso a uscita);
4. T ≥ T_prop + T_{reg_to_out} + T_{a_valle} (da registro a uscita).

La terza è spesso la più vincolante, perché somma insieme i tempi del mondo a monte e di quello a valle. Togliendo i collegamenti combinatori diretti tra ingressi e uscite scompare: è il modello di Moore. Prendendo le uscite direttamente da un registro scompare T_{reg_to_out}: è il modello di Mealy ritardato. (A rigore andrebbero aggiunti lo sfasamento tra i clock dei vari registri e il tempo perché tutti i bit di un registro cambino; li supporremo trascurabili.) Due reti con clock diversi non possono rispettare questi vincoli a vicenda: per farle parlare servono meccanismi di handshake, che vedremo nel modulo sulle reti complesse.

I contatori

Un contatore è una RSS il cui stato di uscita rappresenta un numero naturale a n cifre in base β; a ogni clock incrementa (contatore up), decrementa (down) o fa l'uno o l'altro secondo una variabile di comando, sempre modulo βⁿ. Si realizza con un registro e un sommatore. Con un ingresso di abilitazione ei conta solo quando ei = 1 (basta collegarlo al riporto entrante del sommatore), e con un'uscita eu, il riporto uscente, diventa espandibile. In base 2 il Verilog ha l'operatore +:

In una base generica il sommatore si descrive con una tabella. Un contatore espandibile a una cifra in base 3, con la codifica 0 = 00, 1 = 01, 2 = 10, ha un registro a due bit e una rete combinatoria con ingressi q₁q₀ ed e_i e uscite a₁a₀ (il nuovo valore) ed e_u:

I contatori dividono in frequenza: il bit più significativo di un contatore in base 3 è un'onda con periodo triplo del clock, e la cifra più significativa di un contatore a N bit ha periodo 2^NT. Un clock così si può prendere solo dall'uscita di un registro, mai da quella di una rete combinatoria come e_u, che potrebbe avere oscillazioni spurie.

I registri multifunzionali

Un registro multifunzionale memorizza a ogni clock una tra K funzioni combinatorie, scelta da ⌈log₂K⌉ variabili di comando: si fa con un multiplexer davanti al registro. Esempio classico: un registro a 4 bit che, secondo b₀, carica un nuovo valore oppure trasla a sinistra il proprio contenuto inserendo uno 0.

A destra di <= può stare qualsiasi espressione, anche con i bit del registro stesso; a sinistra ci va il registro intero. Scrivere OUTR[2] <= 'B1 non ha senso: il clock arriva a tutti i bit contemporaneamente.

Il modello di Moore

Definizione e struttura

Una rete di Moore ha N ingressi, M uscite, un insieme finito di stati interni di cui uno, in ogni istante, è marcato (lo stato presente), e due leggi:

• A: X × S → S, che dà lo stato successivo da ingresso e stato presente;
• B: S → Z, che dà l'uscita dal solo stato.

Al fronte del clock si calcola S' = A(S, X) con l'ingresso presente subito prima, si aspetta T_prop e si promuove S' a stato marcato; intanto si presenta continuamente in uscita B(S). Ogni rete di Moore si sintetizza con un registro di stato STAR (status register) e due reti combinatorie, RCA e RCB:

Le disuguaglianze di temporizzazione diventano tre: T ≥ T_hold + T_{a_monte} + T_A + T_setup; T ≥ T_prop + T_A + T_setup; T ≥ T_prop + T_Z + T_{a_valle}. La seconda è implicata dalla prima (perché T_prop ≈ T_hold e T_{a_monte} è molto più grande), ma all'orale si scrivono tutte e tre e poi si osserva che la seconda si può trascurare. In una rete di Moore l'uscita è sempre un clock in ritardo rispetto all'ingresso che l'ha prodotta: S[t_i+1] = A(X[t_i], S[t_i]) e Z[t_i] = B(S[t_i]).

Nelle reti sincronizzate non si cerchiano gli stati: il concetto di stabilità riguarda gli anelli combinatori delle reti asincrone. A ogni clock c'è una transizione, che può anche riportare nello stesso stato.

Il flip-flop JK

Il flip-flop JK è una RSS con due ingressi e un'uscita che, a ogni clock, guarda j e k: 00 conserva, 10 setta, 01 resetta, 11 commuta (inverte l'uscita). È una rete di Moore a due stati, S0 e S1, codificati con un bit y₀ uguale all'uscita (così RCB è un semplice filo). Dalla tabella di flusso si ricava RCA: a₀ = j·y₀ + k·y₀.

Un riconoscitore di sequenza

Progettiamo una rete con due ingressi x₁x₀ e un'uscita z che vale 1 solo dopo che si è presentata, in tre clock consecutivi, la sequenza 11, 01, 10: la serratura di una cassaforte a combinazione. La rete deve ricordare quanti passi corretti consecutivi ha visto, quindi per una sequenza di K passi servono K + 1 stati: S0 (nessun passo), S1 (ho visto 11), S2 (11, 01), S3 (sequenza completa, z = 1). Il punto delicato sono le transizioni «di errore»: se in S1 arriva di nuovo 11 la sequenza non è persa, perché quell'11 può essere l'inizio di una nuova, e si resta in S1; lo stesso vale da S2 e da S3.

Una nota importante: la sequenza deve presentarsi esattamente un passo per clock. Se gli ingressi cambiano più in fretta del clock, qualche passo va perso; se un valore resta per due clock, per la rete è una sequenza diversa. Le buone abitudini: scegliere la codifica degli stati guardando a che cosa semplifica RCB, e scrivere descrizioni (assign z=(STAR==S3)?1:0;), non sintesi travestite (assign z=STAR[1]&STAR[0];).

Per esercitarti, ecco un riconoscitore della sequenza 0, 0, 1, 0, 1, 1, 0 su un solo ingresso: 7 passi, quindi 8 stati. La specifica chiede di non perdere nessuna sequenza ma di non considerare valide quelle intrecciate: dopo un errore si riparte dal passo più lungo ancora compatibile (per esempio, da S4 con un 0 si torna in S2, perché gli ultimi due ingressi «0, 0» sono già l'inizio di una nuova sequenza), dopo il riconoscimento invece si riparte da capo.

Il modello di Mealy

L'uscita dipende anche dagli ingressi

Se la legge dell'uscita è più generale, B: X × S → Z, si ottiene una rete di Mealy: RCB riceve anche gli ingressi, e l'uscita reagisce a un cambiamento degli ingressi senza aspettare il clock. Si ha Z[t_i] = B(X[t_i], S[t_i]): l'uscita dipende anche dall'ultimo ingresso, quello del clock attuale. Il prezzo è nella temporizzazione: la disuguaglianza più vincolante diventa T ≥ T_hold + T_{a_monte} + T_RC + T_{a_valle}, che somma tutti e tre i tempi più lunghi, e in genere obbliga a un clock più lento. Nei grafi di flusso l'uscita si scrive sugli archi (ingresso/uscita).

Un contatore espandibile è una rete di Mealy: il riporto uscente dipende dallo stato e dal riporto entrante.

Il riconoscitore di 11, 01, 10 come rete di Mealy richiede un solo stato in meno: in S2, quando arriva 10, l'uscita va a 1 subito, e al clock si torna in S0.

Moore o Mealy?

Le due potenze descrittive sono identiche: ogni problema risolubile con un modello lo è anche con l'altro (da Mealy a Moore a volte servono più stati). Neanche la velocità fa la differenza: Mealy risponde un clock prima, ma con un clock più lento. Ciò che conta davvero è la trasparenza. Le reti di Mealy sono trasparenti (c'è una via combinatoria tra ingresso e uscita), quelle di Moore no. Collegando due RSS ad anello, l'anello è combinatorio, e quindi la rete diventa asincrona senza volerlo, se entrambe sono di Mealy: almeno una delle due deve essere di Moore.

Esercizio tipico: una rete di Mealy con ingressi x₁x₀ che dà z = x₁·x₀ se l'ingresso è uguale al precedente e z = x₁ ⊕ x₀ altrimenti. Lo stato deve ricordare l'ingresso precedente, quindi servono 4 stati; codificandoli proprio con l'ingresso precedente, la rete dello stato successivo si riduce a due fili: a₁ = x₁, a₀ = x₀.

Il modello di Mealy ritardato

Un registro sulle uscite

Si parte da una rete di Mealy e si mette un registro OUTR sulle uscite. Ora le uscite cambiano solo al clock (dopo T_prop), in modo netto e senza oscillazioni, restano stabili per un intero periodo e non sono trasparenti. La legge di temporizzazione:

S[t_i+1] = A(X[t_i], S[t_i])     Z[t_i+1] = B(X[t_i], S[t_i])

Da capire bene, perché senza questo i compiti d'esame sono impossibili: lo stato di uscita cambia dopo il clock, e il suo valore dipende dallo stato di ingresso e dallo stato interno precedenti al clock. Le disuguaglianze si riducono a T ≥ T_hold + T_{a_monte} + T_RC + T_setup (la più vincolante), T ≥ T_prop + T_RC + T_setup e T ≥ T_prop + T_{a_valle}.

La tabella di flusso è identica a quella di Mealy: cambia il modo in cui la legge B diventa operativa. In Verilog l'uscita non è più un assign, ma un assegnamento procedurale al registro OUTR, nello stesso blocco always di STAR:

Gli assegnamenti tra begin e end diventano veri tutti insieme all'arrivo del clock: l'ordine in cui sono scritti non conta (non è il C++), e se a destra di STAR <= compare OUTR, si usa il suo valore prima del fronte. Le reti di Mealy ritardato si possono collegare in cascata senza limiti e senza problemi di temporizzazione: le uscite di una sono stabili per tutto il periodo e pilotano la successiva rispettando la disuguaglianza da registro a registro, che è già verificata.

I tre modelli a confronto

Verifica