Appunti di Progettazione elettronica digitale

QUIZ:

Costruzione e completezza del diagramma a stati

Il diagramma a stati dev’essere completo:

- Ogni stato deve avere un arco uscente per ogni combinazione possibile di input. L’assenza di archi

per alcune combinazioni renderebbe il comportamento della macchina indefinito per quelle

configurazioni, compromettendo il determinismo richiesto dalle FSM.

- Se in un dato stato ci sono due ingressi possibili, ci devono essere due archi distinti, uno per ciascuno.

- I loop devono essere rappresentati esplicitamente, quando uno stato può restare se stesso per certi

input. L’omissione di queste transizioni renderebbe il diagramma incompleto e il comportamento

della macchina ambiguo per quelle configurazioni di ingresso.

- Non usare etichette generiche che coprono più input diversi; ogni condizione dev’essere chiaramente

specificata. L’utilizzo di etichette generiche impedirebbe la verifica di completezza e mutua

esclusività, compromettendo la precisione della specifica della macchina a stati.

Tabella degli stati:

La corrispondenza tra righe della tabella e termini delle funzioni dipende dai valori specifici assunti dalle

funzioni in quella configurazione. Solo le righe dove una particolare funzione di uscita assume valore

contribuiscono ai termini della sua forma canonica, mentre le righe con valore o “don’t care” non generano

termini diretti.

Minimizzazione e stati equivalenti:

Prima di codificare, è fondamentale semplificare la FSM effettuando la minimizzazione degli stati, prima di

procedere vero la sintesi finale. Si devono trovare stati equivalenti, cioè stati che: producono le stesse uscite

87

per ogni ingresso e transitatno verso stati equivalenti per tutti gli ingressi. Accorpare stati equivalenti riduce

il numero totale di stati, semplificando la macchina e l’hardware.

Stati che producono uscite diverse per le stesse condizioni di ingresso rappresentano comportamenti distinti

del sistema e non possono essere accorpati, anche se hanno pattern di transizione identici verso gli stessi

stati di destinazione.

Lo stato iniziale deve essere definito già in fase di progetto; posticiparlo compromette la correttezza del

comportamento. Lo stato iniziale stabilisce le condizioni di partenza e influenza tutte le successive evoluzioni

della macchina, per cui deve essere definito durante la progettazione astratta.

I “don’t care” possono restare nel modello e aiutano il processo di minimizzazione; non devono essere

eliminati a priori. Rappresentano gradi di libertà che possono essere sfruttati per ottimizzare la struttura della

macchina e facilitare l’accorpamento di stati durante la fase di minimizzazione.

Codifica degli stati: implementazione hardware

Non è obbligatorio usare codifica binaria sequenziale: si può usare binary, Gray, one-hot, ecc., in base allo

scopo (velocità, semplificazione logica). log

Il numero minimo di flip-flop segue la formula: Non è uguale al numero di stati

2

simbolici, ma al minimo necessario per codificarli.

Le condizioni di transizione devono essere mutuamente esclusive:

- Per ogni stato, per ogni input (o combinazione), esiste esattamente un arco uscente, garantendo il

comportamento deterministico.

- Non si possono usare etichette generiche; ogni condizione dev’essere chiara e distinta.

- Anche gli archi che rimangono nello stesso stato (loop) devono essere presenti se richiesti dalle

condizioni.

Sintesi finale di una FSM:

Dalla tabella degli stati codificata, ogni bit del nuovo stato futuro deve essere espresso come una funzione

booleana che usa come input: le variabili di stato presente (es. Q₂, Q₁, Q₀) ed eventuali ingressi esterni (es. x,

y). Queste funzioni vengono semplificate con K-map o metodi algebrici e poi implementate come logica

combinatoria. Ogni funzione così derivata diventa l’ingresso di eccitazione di un flip-flop (D, T, JK, ecc.).

Le scelte tecnologiche e implementative (tipo di codifica, flip-flop, ASIC o FPGA) devono essere fatte dopo la

definizione astratta della FSM, per permettere una progettazione indipendente dalla tecnologia.

Il numero di funzioni di eccitazione dipende dal tipo di flip-flop utilizzati. Se si utilizzano flip-flop di tipo D o

T, il numero di funzioni di eccitazione da implementare corrisponde al numero di flip-flop (entrambi i tipi

hanno un solo ingresso di eccitazione ciascuno), ma per k flip-flop di tipo JK, sono necessarie 2k funzioni di

eccitazione distinte ( e per ogni flip-flop i). L’affermazione non è quindi generalmente valida per tutti i

tipi di flip-flop."

FSM e temporizzatori integrati

Quando la FSM ha stati che richiedono attese temporizzate, deve:

1. Generare, al momento giusto, un segnale start_timer (ST) come uscita quando entra in stati

temporizzati

2. Attendere i segnali di completamento temporale (TS per intervalli brevi, TL per intervalli lunghi) che

indicano il raggiungimento della durata programmata e non devono rimanere attivi oltre il momento

della segnalazione.

a. Questi diventano ingressi della FSM, che determinano le transizioni verso gli stati successivial

completamento dell’intervallo temporale programmato

88

3. Usare questi segnali per effettuare le transizioni

I segnali temporali non vengono mantenuti attivi indefinitamente e il temporizzatore non genera segnali in

modo continuativo,ma sono eventi puntuali che indicano il completamento di specifici intervalli temporali.

La generazione continua di segnali temporali interferirebbe con il corretto funzionamento della FSM, che

deve poter distinguere tra completamenti temporali di cicli diversi e reagire appropriatamente alle transizioni

di stato determinate da ciascun evento temporale.

Il segnale di reset deve agire prioritariamente sulla FSM per riportarla allo stato iniziale predefinito. Anche se

il temporizzatore può essere resettato, la gestione del reset deve essere coordinata dalla logica di controllo

della FSM, e non affidato esclusivamente al timer, per garantire che tutto il sistema raggiunga una

configurazione iniziale coerente e sicura.

Conversione tra Moore e Mealy

Nelle macchine di Moore le uscite dipendono esclusivamente dallo stato presente, mentre nelle macchine di

Mealy le uscite dipendono sia dallo stato presente che dagli ingressi.

È sempre possibile convertire tra i due modelli, garantendo lo stesso comportamento funzionale (stesse

sequenze ingresso‑uscita), indipendentemente dalla complessità delle dipendenze delle uscite. Anche

quando le uscite dipendono da multiple variabili di ingresso, è possibile creare stati appropriati nella

macchina di Moore per rappresentare tutte le combinazioni necessarie di condizioni che determinano le

uscite.

Qualsiasi conversione tra modelli di FSM deve garantire equivalenza funzionale completa. Le sequenze di

uscita prodotte per le stesse sequenze di ingresso devono rimanere identiche, anche se la struttura interna

degli stati e delle transizioni può cambiare significativamente durante la trasformazione.

I due modelli hanno caratteristiche temporali diverse per natura. Le macchine di Moore sincronizzano le

uscite con il clock mentre le macchine di Mealy possono produrre cambiamenti di uscita asincroni in risposta

agli ingressi. La conversione mantiene l’equivalenza funzionale ma non necessariamente i tempi di risposta.

La conversione influenza più elementi dell’hardware, non solo il numero di flip-flop. Le differenze riguardano

anche la complessità della logica combinatoria per le uscite, i requisiti di temporizzazione, la gestione dei

segnali di clock, e le caratteristiche di risposta del sistema.

Circuiti aritmetici

I circuiti aritmetici sono un ottimo esempio di progetto di reti logiche. Sono reti logiche che permettono di

eseguire operazioni matematiche sui numeri binari. Le operazioni più comuni sono: somma, sottrazione,

moltiplicazione. Alcuni esempi fondamentali sono: somma binaria mediante half e full adder, circuito

moltiplicatore combinatorio. →

Decisioni di progetto sull’asse spazio/tempo Nel progettare circuiti aritmetici esiste un compromesso tra:

- Velocità di calcolo (tempo di esecuzione),

- Complessità e quindi spazio occupato dalla rete logica.

Esempio: se si vuole calcolare velocemente, servono reti più complesse.

Un esempio è il carry-lookahead adder, che accelera il calcolo del riporto riducendo la dipendenza

sequenziale.

Gli strumenti di base sono:

- Half Adder (HA) = "semisommatore" (somma due bit)

- Full Adder (FA) = "sommatore completo" (somma tre bit: due operandi + riporto)

89

→ Questi circuiti servono a costruire calcolatori, ALU, e CPU.

L’unità aritmetico-logica è un componente fondamentale di processori moderni, gestisce operazioni

aritmetiche e logiche, viene usata nel ciclo principale di quasi tutte le istruzioni di un processore.

Numerazione binaria – APPROFONDIMENTO

La rappresentazione dei numeri positivi è la medesima in tutti i casi. La differenza fondamentale deriva dal

modo con cui si vanno a rappresentare i numeri negativi. Quando lavori con numeri binari, devi decidere

come rappresentare i numeri negativi.

Metodo Come funziona? Problemi?

Modulo e segno 1° bit = segno (0 positivo, 1 negativo); gli Due zeri (+0 e -0),

altri bit = valore assoluto somma/sottrazione complicate

Complemento a 1 Negativi = inverti tutti i bit Ancora due zeri, gestione complicata

(CA1) del riporto

Complemento a 2 Come CA1, poi sommi 1 Solo uno zero, somma/sottrazione

(CA2) facilissime

Esempi a seguire assumono di lavorare con parole di 4 bit, per rappresentare un range di 16 valori equamente

distribuiti tra positivi e negativi. Facilmente estendibile al caso generico di parole a bit.

Le diverse rappresentazioni hanno impatto anche sulla realizzazione delle varie operazioni aritmetiche.

Rappresentazione in modulo e segno

Il bit più significativo (MSB) è il segno: 0 = positivo (o nullo), 1

= negativo I restanti bit meno significativi sono il modulo: da 0

−1

(000) a 7 (111). L’intervallo rappresentabile con bit = ±(2

− 1)

Problemi principali:

- Due rappresentazioni diverse per lo 0

- Somma e sottrazione sono complesse, perché serve

confrontare i moduli per decidere il segno

o Quando i segni sono uguali, basta sommare direttamente i due operandi. Il segno del

risultato è uguale a quelli degli operandi stessi

o Quando i segni sono diversi, bisogna sottrarre i due operandi ed il segno del risultato dipende

da quello dell’operando con il modulo più grande

90

Rappresentazione in complemento a 1 (CA1)

̅

Se è un numero positivo, è l’opposto ottenuto tramite CA1.

̅

(2 − 1) –

Formula: = equivale a calcolare il c