Teoria dei sistemi
Autore: LUCA ORRU'
1
Teoria dei Sistemi

Sistema combinatorio: sistema in cui le
uscite all’istante corrente dipendono
unicamente dagli ingressi applicati nello
stesso istante.
ingressi
uscite
Non si ha alcuna dipendenza dal tempo, vale a dire
che la variabile tempo non può influenzare il
comportamento del sistema
Autore: LUCA ORRU'
2
Sistema combinatorio

Il comportamento di un sistema combinatorio
può essere descritto tramite:


Una tabella di verità che specifica per ogni
combinazione delle variabili d’ingresso il valore
dell’uscita
Una funzione logica y
Autore: LUCA ORRU'
3
Tabella di verità

Esempio:
X
Y
Z
0
0
0
0
1
0
1
0
0
1
1
1
Questa tabella di verità descrive il funzionamento
della porta logica AND
Autore: LUCA ORRU'
4
Funzione logica


Z=XY
Sistema complesso:
Z=(abcd+ab)(a+bcd)
Autore: LUCA ORRU'
5
Teoria dei sistemi

Sistema sequenziale: sistema in cui le uscite all’istante
t dipendono oltre che dagli ingressi applicati allo stesso
istante, anche dallo stato del sistema, vale a dire dalla
storia passata del sistema, quindi dagli ingressi applicati
negli istanti precedenti. Il tempo è quindi una variabile
del sistema.
ingressi
uscite
Stati successivi
Stati attuali
Elementi di memoria
Autore: LUCA ORRU'
6
Sistema sequenziale

Un sistema sequenziale può essere descritto
tramite due forme diverse di
rappresentazione:



Tabella degli stati
Diagramma degli stati
Esempio di sistema sequenziale:
sommatore binario seriale
Autore: LUCA ORRU'
7
Sommatore binario seriale
0 1 1 0 0
0 1 1 1 0
X1
Z
1 1 0 1 0
X2
Esegue la somma tra due numeri a n bit in maniera seriale,
sommando prima i bit meno significativi e poi via via
quelli più significativi
Autore: LUCA ORRU'
8
Tabella degli stati
Sommatore binario seriale
Stati
attuali
A
B
Stati prossimi/uscita
X1,X2 ingressi
00
01
11
10
A/0 A/1 B/0 A/1
A/1 B/0 B/1 B/0
Gli stati possibili sono due: A e B
Lo stato A è lo stato del sommatore quando non si è
verificato un riporto all’istante precedente;
Lo stato B è lo stato del sommatore quando c’è stato
riporto all’istante precedente.
Autore: LUCA ORRU'
9
Diagramma degli stati

Sommatore binario seriale
11/0
01/1
00/0
10/1
A
B
01/0
10/0
11/1
00/1
Autore: LUCA ORRU'
10
Esempi di reti combinatorie

Semisommatore (Half Adder)
X1
X2
H.A
somma
CO= Carry Out o riporto in uscita
Realizza l’addizione binaria tra due bit fornendo
in uscita l’eventuale riporto e la somma.
Non tiene conto di eventuali riporti dagli stati precedenti
Autore: LUCA ORRU'
11
Half Adder

Tabella di verità
X1
0
0
1
1
X2
0
1
0
1
S
0
1
1
0
CO
0
0
0
1
La sintesi delle due uscite fornisce:
S=X1X2
CO=X1•X2
Autore: LUCA ORRU'
12
Half Adder

X1
Il circuito logico combinatorio è dunque:
CO (CARRY OUT)
X2
S (somma)
Autore: LUCA ORRU'
13
Full Adder (sommatore completo)

Ha tre ingressi e due uscite
X1
X2
somma
F.A
CO
Cin
SOMMA=(X1X2)CI
C0=X1•X2+CI•(X1X2)
Oppure
C0=X1•X2+X1•CI+X2•CI
Autore: LUCA ORRU'
X1
0
0
0
0
1
1
1
1
X2
0
0
1
1
0
0
1
1
CI
0
1
0
1
0
1
0
1
S
0
1
1
0
1
0
0
1
C0
0
0
0
1
0
1
1
1
14
Full Adder (la somma)
S  x1 x 2 CI  x1 x 2 CI  x1 x 2 CI  x1x 2CI
S  ( x1 x 2  x1x 2)CI  CI ( x1 x 2  x1x 2)
S  CI ( x1  x 2)  CI ( x1  x 2)
S=(X1X2)CI
Autore: LUCA ORRU'
15
Full Adder (il riporto)
CO  x1 x 2 CI  x1x 2 CI  x1x 2CI  x1x 2CI
CO  CI ( x1 x 2  x1x 2)  x1x 2(CI  CI )
CO  CI (x1  x 2 )  x1x 2
Usando le mappe di Karnaugh si può esprimere il riporto in uscita
con la seguente funzione logica
CO=X1X2+X1CI+X2CI
Autore: LUCA ORRU'
CON LE MAPPE DI
KARNAUGH
16
Circuito logico
Circuito logico relativo alla prima espressione logica di CO
x1
A
x2
s
D
CI
CO
C
E
B
Il circuito è su tre livelli
Autore: LUCA ORRU'
17
Livelli

Ad ogni porta logica è associato un livello



Le porte che ricevono direttamente gli ingressi del circuito
sono al primo livello
Tutte le altre porte del circuito hanno un livello pari al livello
della porta d’ingresso avente livello massimo, più 1
Nell’esempio precedente si ha:
 Porta A: primo livello
 Porta B: primo livello
 Porta C: secondo livello (livello di A + 1)
 Porta D: secondo livello (livello di A più 1)
 Porta E: terzo livello (livello di C più 1)
Autore: LUCA ORRU'
18
Schema alternativo del F.A

Considerando la seconda forma di
rappresentazione del riporto CO e
utilizzando una porta exor a tre ingressi per
rappresentare la somma, il circuito logico
rappresentativo del F.A diventa il seguente
CO=X1X2+X1CI+X2CI
Autore: LUCA ORRU'
19
Circuito logico
X1
X2
CI
somma
CO
CO ora è su due livelli
Autore: LUCA ORRU'
20
Ripple Carry Adder


Somma 2 numeri di n bit attraverso al
connessione di n full-adder in cascata
Architettura semplice ma non particolarmente
veloce


Il ritardo complessivo nella generazione del
risultato dipende dal numero di stadi e quindi dal
numero di bit delle parole d’ingresso
Per poter eseguire la somma dei bit in posizione iesima è necessario conoscere il riporto in uscita
dallo stadio precedente
Autore: LUCA ORRU'
21
Ripple Carry Adder



Ricordando che ogni Full Adder è realizzato con una
rete su due livelli, se indichiamo con T il ritardo di
commutazione introdotto da ogni porta logica, allora
il ritardo introdotto da ciascun F.A nella generazione
del riporto è pari a 2T
Il ritardo complessivo, ovvero il ritardo nella
generazione del riporto n-esimo è pari a 2T*n
Il numero di porte logiche necessarie è pari a 5*n e
quindi l’area necessaria per la realizzazione è
abbastanza contenuta
Autore: LUCA ORRU'
22
Ripple Carry Adder

Implementazione di una somma a 4 bit
X3 Y3
CI3
X2 Y2 CI2
F.A
CO3
S3
F.A
CO2
S2
X1 Y1 CI1
F.A
CO1 S1
X0 Y0 CI0
F.A
CO0
S0
Il primo F.A può essere sostituito da un H.A in quanto CI0=0
Autore: LUCA ORRU'
23
Sommatore carry look-ahead


Consente di ridurre i tempi di ritardo tipici del
Ripple-Carry dovuti all’attesa per la
propagazione del riporto da uno stadio
all’altro
Disponendo in anticipo di tutti i riporti, la
somma sui vari bit dei numeri da sommare
potrebbe essere eseguita in parallelo, cioè
contemporaneamente
Autore: LUCA ORRU'
24
Sommatore carry look-ahead

Per ottenere i riporti in anticipo si introducono due
funzioni booleane definite nel modo seguente
Pi  xi  yi
Gi  xi  yi
Le due funzioni sono chiamate rispettivamente funzione di propagazione e
funzione di generazione
Le due funzioni non dipendono dai riporti e quindi possono essere calcolate
immediatamente e contemporaneamente in quanto dipendono solo dai bit
che compongono i due numeri da sommare che naturalmente sono noti
Autore: LUCA ORRU'
25
Sommatore carry look-ahead

Si può esprimere il riporto in uscita dallo
stadio i-esimo nel modo seguente
Ci  1  xi yi  xi ci  yi ci  xiyi  xi  yi ci  Gi  Pi ci
Si noti la dipendenza di Ci+1 da Ci. Iterando il procedimento si ottiene però:
Ci  xi  1 yi  1  xi  1 ci  1  yi  1 ci  1 
 xi  1 yi  1   xi  1  yi  1 ci  1  Gi  1  Pi  1 ci  1
Ci  1  Gi  Pi ci  Gi  Pi Gi  1  Pi  1 ci  1
Ci  1  Gi  Pi Gi  1  Pi Pi  1 ci  1
Autore: LUCA ORRU'
26
Sommatore carry look-ahead

In conclusione:


iterando fino a C0 si riesce a ricondurre il riporto
Ci+1 a dipendere solo da C0 oltre che dalle funzioni
di generazione e di propagazione.
Nel caso di un sommatore a 4 bit si
ottengono le seguenti espressioni
Autore: LUCA ORRU'
27
carry look-ahead a 4 bit
C1  G 0  P 0c 0
C 2  G1  P1 G 0  P1P 0c 0
C 3  G 2  P 2G1  P 2 P1G 0  P 2 P1P 0c 0
C 4  G 3  P 3G 2  P 3 P 2G1  P 3 P 2 P1G 0  P 3 P 2 P1P 0c 0
Ora tutti i riporti sono noti ed è possibile eseguire la
somma usando 4 full adder in cascata
Nella slide successiva è rappresentato lo schema circuitale del
carry look-ahead a 4 bit
Autore: LUCA ORRU'
28
Sommatore carry look-ahead a 4 bit
x3
y3
x2
y2
x1
y1
X0
y0
Circuito di generazione e propagazione
P3
G3
P2
G2
P1
G1
P0
G0
C0
Circuito che fornisce i riporti anticipati
x3
C4
y3 C3
x2
y2 C2
x1
y1 C1
x0
Y0
F.A 4
F.A 3
F.A 2
F.A 1
S3
S2
S1
S0
Autore: LUCA ORRU'
C0
29
Sommatore carry look-ahead a 4 bit





Il circuito di generazione e di propagazione e su un
solo livello ed è costituito da 4 porte OR e 4 porte
AND
Il circuito che fornisce i riporti anticipati è su due
livelli (es. C4 è generato con 4 porte AND e una OR
a 5 ingressi)
I Full Adder sono su due livelli
In conclusione, il circuito ha un ritardo pari a 5T con
T ritardo di ciascuna porta logica ed è in teoria
indipendente dal numero di bit da sommare
(lunghezza delle parole)
Un Ripple Carry a 4 bit ha invece un ritardo di 8T
Autore: LUCA ORRU'
30
Sommatore carry look-ahead a 4 bit

La maggiore velocità si paga con una
complessità circuitale superiore rispetto al
Ripple Carry


Il numero di porte cresce notevolmente al
crescere della dimensione delle parole da
sommare e quindi cresce l’area richiesta
Questo pone un limite al numero di ritardi che
possono essere generati in anticipo
Autore: LUCA ORRU'
31