Circuiti sequenziali

(1)

Università degli Studi dell’Insubria Dipartimento di Scienze Teoriche e Applicate

Architettura degli elaboratori

Circuiti sequenziali Marco Tarini

Dipartimento di Scienze Teoriche e Applicate marco.tarini@uninsubria.it

Circuiti sequenziali

Un circuito digitale è di tipo sequenziale se le sue uscite dipendono non solo dai valori correnti degli ingressi, ma anche da (alcuni di) quelli passati

Un circuito digitale sequenziale (o rete sequenziale) è pertanto dotato, in ogni istante di tempo, di uno stato che, insieme ai valori degli ingressi, ne determina il comportamento futuro

(2)

Circuiti sequenziali

Lo stato di un circuito sequenziale rappresenta, in un certo senso, una forma di memoria: esso contiene una sorta di descrizione della storia passata del circuito stesso

L’elemento funzionale elementare per la realizzazione di circuiti sequenziali è pertanto il bistabile, che è in grado di memorizzare un bit di informazione

Circuiti sequenziali

Architettura degli elaboratori - 3 -

Circuiti sequenziali: struttura

I circuiti sequenziali sono formati da:

Bistabili (di vario tipo)

funzione: memorizzareinformazione, ovvero dei bit Reti combinatorie,

funzione: elaborareinformazione

Il circuito sequenziale ha, in ogni dato istante, uno stato è determinato dai bit memorizzati nei bistabili

Stato successivo Circuito combinatorio

Ingressi Uscite

Elementi di memoria

Stato corrente

(3)

Circuiti sequenziali: famiglie

Esistono due famiglie di circuiti digitali sequenziali:

asincroni,

non fanno uso di clock sincroni,

necessitano di clock

Esempio di circuito sequenziale asincrono:

bistabile SR (non sincronizzato) a.k.a. SR-latch

I circuiti sequenziali asincroni sono impiegati raramente difficili da usare e controllare!

Circuiti sequenziali sincroni

I circuiti sequenziali sincroni sono invece universalmente diffusi Esempio di circuito sequenziale sincrono:

bistabile di tipo D (Flip-Flop)

il componente base dei circuiti sequenziali di tipo sincrono!

Circuito sequenziale (sincrono):

Flip-Flop (bistabili di tipo D sincroni) + reti combinatorie

Stato successivo Circuito combinatorio

Ingressi Uscite

Elementi di memoria

Stato corrente Clock

(4)

Progettazione di circuiti sequenziali

Come per le reti combinatorie, esistono delle procedure di sintesi anche per i circuiti sequenziali sincroni

Vedremo ora le basi di queste tecniche

Vediamo uno schema un po’ più dettagliato di un circuito sequenziale in generale

Circuiti sequenziali sincroni:

schema generale

Ingressi m

flip/flop memorizza

stato corrente n circuito

combinatorio determina

lo stato successivo

Clock

m

m m k Uscite

circuito combinatorio

determina le uscite n

n: numero ingressi m: numero bit di stato k: numero uscite se necessario

(5)

Circuiti sequenziali sincroni:

schema generale

Nel circuito compaiono due reti combinatorie La prima, decide lo stato successivo

a partire da:

gli input e i valori dei bit dello stato corrente La seconda, decide gli output,

a partire da:

i bit dello stato corrente

a volte, anche dall’input (non sempre è necessario)

Fra le due, un flip-flop memorizza ciascuno dei bit dello stato corrente Sincronizzato sul fronte! con il clock

Finché il clock non manda il segnale, lo stato successivo

(calcolato dalla prima rete combinatoria) non diventa lo stato corrente

Problema di esempio:

Definizione del problema

Consideriamo un problema di esempio: il controllo di un cancello motorizzato.

Il circuito di controllo ha tre ingressi:

CA: comando di apertura CC: comando di chiusura

FC: fine corsa (cancello completamente aperto o chiuso) e due uscite:

MO: motore on/off (1=movimento, 0=fermo) MA: motore avanti/indietro (1=apre, 0=chiude)

Il circuito deve controllare il motore, reagendo opportunamente ai comandi

Ipotesi: i comandi sono mutuamente esclusivi

(cioè in ogni istante al più uno di loro può essere vero)

(6)

Definizione del problema: macchina a stati

Per definire formalmente il problema utilizziamo una Macchina a Stati Finiti (FSM).

Nodi = stati

Archi = transizioni di stato, causate da eventi esterni (da input)

Uscite associate o agli stati o alle transizioni

Q=0

Q=1

S=0 and R=0 S=1 and R=0 S=0 and R=0 S=0 and R=1

S=1 and R=0 S=0 and R=1

La macchina a stati finiti che descrive il bistabile SR

Definizione del problema: macchina a stati

Chiuso [MO=0, MA=X]

In apertura [MO=1, MA=1]

In chiusura [MO=1, MA=0]

Aperto [MO=0, MA=X]

CA

CC FC FC

FC, CA CA, CC

CC

FC, CC

SCELTA:

Per sicurezza, decidiamo di non chiudere un cancello

che si sta aprendo CA

(7)

FSM “binaria”

Nella FSM vista prima abbiamo usato simboli facilmente comprensibili.

Adesso passiamo alla notazione binaria.

Adottiamo alcune convenzioni (arbitrarie):

Gli ingressi siano ordinati in questo modo: CA,CC,FC Quindi 101 indica CA=1, CC=0, FC=1

L’ordine delle uscite sia MO, MA Numeriamo gli stati

Aperto = 11 In chiusura = 01 In apertura =10 Chiuso = 00

Associamo le uscite ad ogni stato

Questo perché in questo esempio le uscite non dipendono dagli input (ma solo dallo stato)

(altrimenti, le uscite sarebbero associate alle transizioni fra stati)

FSM

NB: gli ingressi “proibiti” non sono riportati.

Per completezza si potrebbe indicare esplicitamente che essi portano in uno stato “errore” da cui non si esce più.

00 [0X]

10 [11]

01 [10]

11 [0X]

10X

01X

001 101 011 0X1

00X, 10X 000 010 100

0X0

0XX

10X chiuso

aperto in apertura

in chiusura

(8)

Il circuito

S0

S1

D Q

Clock

MO MA CA

FC CC

Rete combinatoria

A

Rete combinatoria

B

Il circuito

S0

S1

D Q

Clock

MO MA CA

FC CC

Rete combinatoria

A

Rete combinatoria

B

Memoria (codifica dello stato -

qui, due bits) Segnale con lo

stato corrente Segnale con lo strato successivo

(verrà effettivamente memorizzato al prossimo ciclo di clock!)

Determina l’uscita in base allo stato

corrente Determina lo stato prossimo

in base agli ingressi e allo stato corrente

(9)

Calcolo delle uscite (la rete combinatoria B)

Riscriviamo la dipendenza tra stati e uscite come tavola delle verità NB: in questo caso particolare, le uscite dipendano solo dallo stato.

In generale, potrebbero dipendere anche dagli ingressi.

(allora la tabella verrebbe più grande!)

S1 S0 MO MA 0 0 0 X 0 1 1 0 1 0 1 1 1 1 0 X

MO = S1  S0

MA = S1 Aperto

In chiusura In apertura Chiuso

Calcolo dello stato successivo (la rete combinatoria A)

Trascriviamo la dipendenza dello stato successivo da stati e input in una tavola delle verità

Nota:

( S0 , S1 ) = stato corrente ( S0’ , S1’ ) = stato successivo

Guardando il diagramma dell’Automa a Stati finiti…

Per ogni stato corrente (ultime due colonne della tabella)

…e per ogni input (prime tre colonne della tabella)

…segniamo la codifica dello stato successivo (nelle due colonne di output)

Sono due tabelle di verità (una per S0’ e una per S1’) a cinque input ciascuna 2^5 = 32 colonne

(10)

Calcolo dello stato prossimo

Trascriviamo la dipendenza dello stato prossimo da stati e input in una tavola delle verità

CA CC FC S1 S0 S1’ S0’

1 0 0 0 0 1 0

1 0 0 0 1 1 0

1 0 0 1 0 1 0

1 0 0 1 1 1 1

1 0 1 0 0 1 0

1 0 1 0 1 1 0

1 0 1 1 0 1 1

1 0 1 1 1 1 1

1 1 0 0 0 X X

1 1 0 0 1 X X

1 1 0 1 0 X X

1 1 0 1 1 X X

1 1 1 0 0 X X

1 1 1 0 1 X X

1 1 1 1 0 X X

1 1 1 1 1 X X

0 0 0 0 0 0 0

0 0 0 0 1 0 1

0 0 0 1 0 1 0

0 0 0 1 1 1 1

0 0 1 0 0 0 0

0 0 1 0 1 0 0

0 0 1 1 0 1 1

0 0 1 1 1 1 1

0 1 0 0 0 0 0

0 1 0 0 1 0 1

0 1 0 1 0 1 0

0 1 0 1 1 0 1

0 1 1 0 0 0 0

0 1 1 0 1 0 0

0 1 1 1 0 1 1

0 1 1 1 1 0 1

Calcolo dello stato prossimo

Trascriviamo la dipendenza dello stato prossimo da stati e input in una tavola delle verità

1 0 0 0 0 1 0

1 0 0 0 1 1 0

1 0 0 1 0 1 0

1 0 0 1 1 1 1

1 0 1 0 0 1 0

1 0 1 0 1 1 0

1 0 1 1 0 1 1

1 0 1 1 1 1 1

1 1 0 0 0 X X

1 1 0 0 1 X X

1 1 0 1 0 X X

1 1 0 1 1 X X

1 1 1 0 0 X X

1 1 1 0 1 X X

1 1 1 1 0 X X

1 1 1 1 1 X X

0 0 0 0 0 0 0

0 0 0 0 1 0 1

0 0 0 1 0 1 0

0 0 0 1 1 1 1

0 0 1 0 0 0 0

0 0 1 0 1 0 0

0 0 1 1 0 1 1

0 0 1 1 1 1 1

0 1 0 0 0 0 0

0 1 0 0 1 0 1

0 1 0 1 0 1 0

0 1 0 1 1 0 1

0 1 1 0 0 0 0

0 1 1 0 1 0 0

0 1 1 1 0 1 1

0 1 1 1 1 0 1

Da questo stato…

…con questo input…

…si raggiunge questo stato.

(11)

0 0

0 1

1 1

1 0

0 0 1 1 X X

0 1 1 1 X X

1 1 1 1 X X

1 0 1 1 X X

0 0

0 1

1 1

1 0

0 0 0 0 0 0

0 1 0 0 0 0

1 1 1 1 0 0

1 0 1 1 1 1

Sintesi della rete per S1’ con Karnaugh

S1’ = CA + S1 /CC + S1 /S0

S1 S0 CC FC S1 S0

CC FC

CA = 0 CA = 1

0 0

0 1

1 1

1 0

0 0 0 0 X X

0 1 0 0 X X

1 1 1 1 X X

1 0 0 1 X X

0 0

0 1

1 1

1 0

0 0 0 0 0 0

0 1 1 0 0 1

1 1 1 1 1 1

1 0 0 1 1 0

Sintesi della rete per S0’ con Karnaugh

S1 S0 CC FC S1 S0

CC FC

CA = 0 CA = 1

S0’ = /CA /FC S0 + S1 /FC + S1 S0

(12)

Il circuito

S0

S1

D Q

Clock

MO MA CA

FC

CC Rete

combinatoria

Rete combinatoria

MO = S1  S0 MA = S1

S0’ = /CA /FC S0 + S1 /FC + S1 S0 S1’ = CA + S1 /CC + S1 /S0

Soluzione alternativa

Nella soluzione vista, gli stati sono codificati col numero minimo di bit (4stati  bastano 2bit, perché 2²≥ 4).

Un’alternativa possibile è di utilizzare tanti flip-flop quanti sono gli stati.

In ogni istante, il bit corrispondente allo stato corrente, contiene il valore uno, tutti gli altri zero.

Es: codifichiamo gli stati con i quattro bit S₀, S₁, S₂, S₃ 1, 0 , 0 , 0 : aperto

0 , 1, 0 , 0 : in chiusura 0 , 0 , 1, 0 : in apertura 0 , 0 , 0 , 1: chiuso

Svantaggio di questa strategia: ci vogliono più flip-flop!

Vantaggio: forse (a volte) i circuiti vengono più semplici e più veloci

(13)

Il circuito

S0

D Q

MO RCout MA

CA

FC CC

RC0

S1

D Q

S2

D Q

S3

D Q

RC1 RC2 RC2

Clock

Assegnamento degli stati

Chiuso S0 vero, gli altri falsi In apertura S1 vero, gli altri falsi In chiusura S2 vero, gli altri falsi Aperto S3 vero, gli altri falsi

Clock

MO MA

CA FCCC

S0

D Q

S1

D Q

S2

D Q

S3

D Q

Aperto In chius In apert Chiuso

RCout

RC0 RC1 RC2 RC3

Chiuso In apertura In chiusura Aperto

(14)

Calcolo delle uscite

Riscriviamo la dipendenza tra stati e uscite come tavola delle verità NB: è un caso particolare che le uscite dipendano solo dallo stato.

Potrebbero dipendere anche dagli ingressi. Ma si può sempre

descrivere il comportamento desiderato con una macchina a stati in cui le uscite dipendono solo dagli stati.

S3 S2 S1 S0 MO MA

MO = S1 + S2 MA = S1 0 0 0 1

0 0 1 0 0 1 0 0 1 0 0 0 Chiuso

In apertura In chiusura Aperto

0 X 1 1 1 0 0 X

Il circuito

Clock

MO MA

CA

FC CC

S0

D Q

S1

D Q

S2

D Q

S3

D Q

RC0 RC1 RC2 RC3

chiuso In apertura In chiusura aperto

(15)

Definizione di RC0

RC0 produce il valore 1 quando lo stato prossimo è S0, 0 altrimenti CA falso in stato S0

CA falso e FC vero in stato S2

S0’ = 1 sse S0 /CA + S2 /CA FC

S0 [0X]

S1 [11]

S2 [10]

S3 [0X]

10X

01X

001 101 011 0X1

00X 10X 000 010 100

0X0 0XX

10X chiuso

aperto in apertura

in chiusura

Il circuito

RC0

Clock

MO MA

CA FCCC

S0

D Q

S1

D Q

S2

D Q

S3

D Q

RC1 RC2 RC3

S0’ = 1 sse S0 /CA + S2 /CA FC

(16)

Definizione di RC1

RC1 produce il valore 1 quando lo stato prossimo è S1, 0 altrimenti CA vero e CC falso in stato S0 o in stato S2

FC falso in stato S1

S1’ = 1 sse S2 CA /CC + S0 CA /CC + S1 (/CA /FC + /CC /FC) = CA /CC (S2 + S0) + S1 /FC (/CA + /CC)

S0 [0X]

S1 [11]

S2 [10]

S3 [0X]

10X

01X

001 101 011 0X1

00X 10X 000 010 100

0X0 0XX

10X chiuso

aperto in apertura

in chiusura

NB: /CA + /CC = 1, non potendo mai essere CA CC

Il circuito

Clock

MO MA

CA FCCC

S0

D Q

S1

D Q

S2

D Q

S3

D Q

RC2 RC3

RC1

RC0 S1’ = CA /CC (S2 + S0) + S1 /FC

(17)

Definizione di RC2

RC2 produce il valore 1 quando lo stato prossimo è S2, 0 altrimenti CA e FC entrambi falsi in stato S2

CA falso e CC vero in stato S3

S2’ = 1 sse S2 /CA /FC + S3 /CA CC

S0 [0X]

S1 [11]

S2 [10]

S3 [0X]

10X

01X

001 101 011 0X1

00X 10X 000 010 100

0X0 0XX

10X chiuso

aperto in apertura

in chiusura

Il circuito

Clock

MO MA

CA FCCC

S0

D Q

S1

D Q

S2

D Q

S3

D Q

RC3

RC0 RC1 RC2

S2’ = S2 /CA /FC + S3 /CA CC

(18)

Definizione di RC3

RC3 produce il valore 1 quando lo stato prossimo è S3, 0 altrimenti FC vero in stato S1

CC falso in stato S3

S3’ = 1 sse S3 /CC + S1 FC

S0 [0X]

S1 [11]

S2 [10]

S3 [0X]

10X

01X

001 101 011 0X1

X0X 000 010 100

0X0 0XX

10X chiuso

aperto in apertura

in chiusura

Il circuito

RC3

Clock

MOMA

CA FCCC

S0

D Q

S1

D Q

S2

D Q

S3

D Q

RC0 RC1 S3’ = S3 /CC + S1 FCRC2

(19)

Il circuito

RC3

Clock

MOMA

CA FCCC

S0

D Q

S1

D Q

S2

D Q

S3

D Q

RC0 RC1 RC2

Nota

I circuiti visti funzionano come specificato a regime.

Non abbiamo specificato come portare il circuito nello stato iniziale.

Si può usare un ulteriore ingresso di “reset”.

Nell’esempio visto, è particolarmente importante che lo stato del circuito rispecchi lo stato del cancello vero!

Nella realizzazione con un bistabile per ogni stato, bisogna assicurare che all’inizio uno e un solo bistabile contenga 1!