Reti Logiche
Realizzazione di FSM
Capitolo 10: Realizzazione
di Macchine a Stati Finiti
Reti Logiche
Contemporary Logic Design
Randy H. Katz
University of California, Berkeley
May 1993
Trasparenze tradotte da:
Luciano Lavagno
Universita’ di Udine
Settembre 1998
© R.H. Katz 10-1
Riassunto del capitolo
Reti Logiche
Realizzazione di FSM
• Strategie di realizzazione
Logica a porte singole
Progetto con contatori e ROM
Logica programmabile:
PAL
FPGA: Altera, Actel, Xilinx
© R.H. Katz 10-2
Strategie di realizzazione
Reti Logiche
Realizzazione di FSM
• Logica a porte singole
E’ stata l’oggetto principale fino a questo punto
• Logica MSI (p.es. contatori)
• Logica strutturata (p.es. PLA/PAL, ROM)
• Field Programmable Gate Array (FPGA)
La funzione puo’ essere configurata “al volo” o sul campo
Sia flipflop/registri, sia porte singole su uno stesso curcuito.
© R.H. Katz 10-3
Strategie di realizzazione
Progetto di FSM con logica strutturata
Logica
combinatoria
Ingressi
Reti Logiche
Realizzazione di FSM
Registri
Funzione
di uscita
Uscite
Schema a blocchi per macchina
di Moore (o “Mealy sincrona”)
Funzione di
Stato futuro
Stato
Realizzazione a ROM
ROM
A0
Registri
D0
Ingressi
Uscite
An-1
Dk-1
An
Dk
An+m-1 Dk+m-1
• Ingressi e stato presente
sono gli indirizzi
• Bit di dato della ROM sono
uscite e stato futuro
Stato
© R.H. Katz 10-4
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto a ROM
Esempio: convertitore seriale da BCD ad eccesso-3
Processo di conversione
I bit sono presentati in modo seriale
partendo col bit meno significativo
Un ingresso X, un’uscita Z
BCD Codice eccesso-3
0000
0011
0001
0100
0010
0101
0011
0110
0100
0111
0101
1000
0110
1001
0111
1010
1000
1011
1001
1100
© R.H. Katz 10-5
Strategie di realizzazione
Convertitore da BCD ad eccesso-3
Stato presente
S0
S1
S2
S3
S4
S5
S6
Stato futuro
X=0 X=1
S1
S2
S3
S4
S4
S4
S5
S5
S5
S6
S0
S0
S0
--
Uscita
X=0 X=1
1
0
1
0
0
1
0
1
1
0
0
1
1
--
Reti Logiche
Realizzazione di FSM
Tabella delle transizioni
Reset
0/1
S1
0/1
S0
S2
1/0
0/0,
1/1
0/1
0/0,
1/1
S5
Diagramma degli stati
S4
S3
0/0,
1/1
1/0
1/0
S6
0/1
© R.H. Katz 10-6
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Convertitore da BCD ad eccesso-3
Realizzazione a ROM
Indirizzo ROM
X Q2 Q1 Q0
0 0 0 0
0 0 0 1
0 0 1 0
0 0 1 1
0 1 0 0
0 1 0 1
0 1 1 0
0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
Uscita ROM
Z D2 D1 D0
1 0 0 1
1 0 1 1
0 1 0 0
0 1 0 1
1 1 0 1
0 0 0 0
1 0 0 0
X X X X
0 0 1 0
0 1 0 0
1 1 0 0
1 1 0 1
0 1 1 0
1 0 0 0
X X X X
X X X X
1
CLK
1
0
X
conv erter ROM
Z
X
D2
Q2
D1
Q1
D0
Q0
1
0
9
13
12
5
4
CLK
D
C
B
A
QD
175 QD
QC
QC
QB
QB
1 CLR
\Reset
15
14
10
11
Z
7
6
2
QA
3
QA
Realizzazione circuitale
74175 = 4 FF D attivi sul fronte di salita
Tabella di verita’ (ingressi/uscite ROM)
In progetti a ROM non serve considerare l’assegnazione degli stati!!
© R.H. Katz 10-7
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Convertitore da BCD ad eccesso-3
LSB
MSB
Comportamento nel tempo per ingressi 0 0 0 0 (0) e 1 1 1 0 (7)
0
0
1
0000
LSB
0
1
0
0
1100
1
0
1
0
1110
1
1
0
0
1
0101
LSB
© R.H. Katz 10-8
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Convertitore da BCD ad eccesso-3
Progetto a PLA
Codiifca degli stati con NOVA
0
1
0
1
0
1
0
1
0
1
0
1
0
S0
S0
S1
S1
S2
S2
S3
S3
S4
S4
S5
S5
S6
S1
S2
S3
S4
S4
S4
S5
S5
S5
S6
S0
S0
S0
1
0
1
0
0
1
0
1
1
0
0
1
1
File di ingresso di NOVA
S0 = 000
S1 = 001
S2 = 011
S3 = 110
S4 = 100
S5 = 111
S6 = 101
Codifica degli stati
derivata da NOVA
Realizzazione con
9 termini prodotto
© R.H. Katz 10-9
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Convertitore da BCD ad eccesso-3
.i 4
.o 4
.ilb x q2
.ob d2 d1
.p 16
0 000 001
1 000 011
0 001 110
1 001 100
0 011 100
1 011 100
0 110 111
1 110 111
0 100 111
1 100 101
0 111 000
1 111 000
0 101 000
1 101 --0 010 --1 010 --.e
.i 4
.o 4
.ilb x q2 q1 q0
.ob d2 d1 d0 z
.p 9
0001 0100
10-0 0100
01-0 0100
1-1- 0001
-0-1 1000
0-0- 0001
-1-0 1000
--10 0100
---0 0010
Uscita di Espresso .e
Ingresso di Espresso
q1 q0
d0 z
1
0
1
0
0
1
0
1
1
0
0
1
1
-
© R.H. Katz 10-10
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Convertitore da BCD ad eccesso-3
D2 = Q2 • Q0 + Q2 • Q0
D1 = X • Q2 • Q1 • Q0 + X • Q2 • Q0 + X • Q2 • Q0 + Q1 • Q0
D0 = Q0
Z = X• Q1 + X • Q1
1
CLK 9
1
0
X
conv erter PLA
X
Q2
Q1
Q0
Z
D2
D1
D0
1
0
13
12
5
4
CLK
175
D
C
B
A
1 CLR
\Reset
15
QD
14
QD
10
QC
11
QC
7
QB
6
QB
2
QA
3
QA
Z
© R.H. Katz 10-11
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Convertitore da BCD ad eccesso-3
PAL 10H8: 10 ingressi, 8 uscite, 2 termini prodotto per porta OR
D1 = D11 + D12
D11 = X • Q2 • Q1 • Q0 + X • Q2 • Q0
D12 = X • Q2 • Q0 + Q1 • Q0
0 1 2 3
45
89
12 13 16 17 20 21 24 25
28 29 30 31
X
0. Q2 • Q0
1. Q2 • Q0
8. X • Q2 • Q1 • Q0
9. X • Q2 • Q0
16. X • Q2 • Q0
17. Q1 • Q0
24. D11
25. D12
32. Q0
33. non usata
40. X • Q1
41. X • Q1
0
1
D2
8
9
D11
16
17
D12
24
25
D1
32
33
D0
40
41
Z
Q2
Q1
Q0
D11
D12
© R.H. Katz 10-12
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Convertitore da BCD ad eccesso-3
0 1 2 3
45
89
12 13 16 17 20 21 24 25
28 29 30 31
X
0
1
D2
8
9
D11
16
17
D12
24
25
D1
32
33
D0
40
41
Z
Q2
Q1
Q0
D11
D12
© R.H. Katz 10-13
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Architetture PAL avanzate
Output enable
controllato da
ingresso o
termine prodotto
Architettura PAL sequenziale (con registri)
CLK
OE
Q2 • Q0 + Q2 • Q0
Q2 • Q0
Q2 • Q0
D2
Q2+
Q2+
DQ
Q
Q2+
Q2 • Q0 + Q2 • Q0
X
Q2 Q2
D2 = Q2 • Q0 + Q2 • Q0
Q0 Q0
Reazione con stato
presente negato
D1 = X • Q2 • Q1 • Q0 + X • Q2 + X • Q0 + Q2 • Q0 + Q1 • Q0
D0 = Q0
Z = X • Q1 + X • Q1
© R.H. Katz 10-14
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Architetture PAL avanzate
PAL XOR, con polarita’ di uscita programmabile
CLK
OE
Ingresso XOR puo’ essere:
1 (coprire gli 1)
0 (coprire gli 0)
termine prodotto
DQ
Q
Vantaggio di PAL XOR: parita’ ed operazioni aritmetiche
AB
AB
AB
AB
AB
AB
AB
AB
C
C
C
C
C
C
C
C
D
D
D
D
D
D
D
D
A  B  C  D
AB
AB
A  B  C  D
CD
CD
© R.H. Katz 10-15
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Esempio di PAL XOR
Esempio di PAL a registri
INCREMEN
T
INCREMEN
T
1
1
0
0
FIRST
FUSE
NUMBER
4
8
12
16
20
24
28
32
36
0
40
D
Q
23
80
120
FIRST
FUSE
NUMBER
S
Q
2
4
8
12
16
20
24
28
0
32
64
96
128
160
192
224
19
2
160
200
D
240
280
Q
22
256
288
320
352
384
416
448
480
Q
3
320
360
D
400
440
Q
21
512
544
576
608
640
672
704
736
4
D
560
600
Q
20
D
720
760
Q
18
Q
D
Q
17
Q
4
Q
768
800
832
864
896
928
960
992
5
640
680
Q
3
Q
480
520
D
19
Q
D
Q
16
Q
5
6
800
840
D
880
920
Q
1024
1056
1088
1120
1152
1184
1216
1248
18
Q
7
D
Q
15
Q
6
960
1000
D
Q
17
1280
1312
1344
1376
1408
1440
1472
1504
1040
1080
Q
8
1120
1160
D
Q
16
1536
1568
1600
1632
1664
1696
1728
1760
Q
9
D
Q
15
1360
1400
D
Q
1792
1824
1856
1888
1920
1952
1984
2016
14
1520
1560
Q
13
11
INCREMEN
T
0
4
8
12
16
20
24
28
32
14
Q
D
Q
13
Q
8
Q
10
1440
1480
Q
7
1200
1240
1280
1320
D
9
12
11
36
NOTE: FUSE NUMBER = FIRST FUSE NUMBER +
INCREMENT
© R.H. Katz 10-16
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Specifica di PAL in Abel
PAL P10H8
module bcd2excess3
title 'BCD to Excess 3 Code Converter State Machine'
u1 device 'p10h8';
"Input Pins
X,Q2,Q1,Q0,D11i,D12i
pin
1,2,3,4,5,6;
"Output Pins
D2,D11o,D12o,D1,D0,Z
pin
19,18,17,16,15,14;
INSTATE = [Q2, Q1, Q0];
S0 = [0, 0, 0];
S1 = [0, 0, 1];
S2 = [0, 1, 1];
S3 = [1, 1, 0];
S4 = [1, 0, 0];
S5 = [1, 1, 1];
S6 = [1, 0, 1];
Equazioni esplicite
per funzioni di
uscita partizionate
equations
D2 = (!Q2 & Q0) # (Q2 & !Q0);
D1 = D11i # D12i;
D11o = (!X & !Q2 & !Q1 & Q0) # (X & !Q2 & !Q0);
D12o = (!X & Q2 & !Q0) # (Q1 & !Q0);
D0 = !Q0;
Z = (X & Q1) # (!X & !Q1);
end bcd2excess3;
© R.H. Katz 10-17
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Specifica di PAL in Abel
PAL P12H6
module bcd2excess3
title 'BCD to Excess 3 Code Converter State Machine'
u1 device 'p12h6';
"Input Pins
X, Q2, Q1, Q0
pin
1, 2, 3, 4;
"Output Pins
D2, D1, D0, Z
pin
17, 18, 16, 15;
INSTATE = [Q2, Q1,
S0in = [0, 0, 0];
S1in = [0, 0, 1];
S2in = [0, 1, 1];
S3in = [1, 1, 0];
S4in = [1, 0, 0];
S5in = [1, 1, 1];
S6in = [1, 0, 1];
Equazioni piu’
semplici
Q0]; OUTSTATE = [D2, D1, D0];
S0out = [0, 0, 0];
S1out = [0, 0, 1];
S2out = [0, 1, 1];
S3out = [1, 1, 0];
S4out = [1, 0, 0];
S5out = [1, 1, 1];
S6out = [1, 0, 1];
equations
D2 = (!Q2 & Q0) # (Q2 & !Q0);
D1 = (!X & !Q2 & !Q1 & Q0) # (X & !Q2 & !Q0) #
(!X & Q2 & !Q0) # (Q1 & !Q0);
D0 = !Q0;
Z = (X & Q1) # (!X & !Q1);
end bcd2excess3;
© R.H. Katz 10-18
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Specifica di PAL in Abel
PAL P16R4
module bcd2excess3
title 'BCD to Excess 3 Code Converter'
u1 device 'p16r4';
state_diagram SREG
state S0: if Reset then S0
else if X then S2 with Z = 0
else S1 with Z = 1
"Input Pins
state S1: if Reset then S0
Clk, Reset, X, !OE
pin 1, 2, 3, 11;
else if X then S4 with Z = 0
else S3 with Z = 1
"Output Pins
state S2: if Reset then S0
D2, D1, D0, Z
pin 14, 15, 16, 13;
else if X then S4 with Z = 1
else S4 with Z = 0
SREG = [D2, D1, D0];
state S3: if Reset then S0
S0 = [0, 0, 0];
else if X then S5 with Z = 1
S1 = [0, 0, 1];
else S5 with Z = 0
S2 = [0, 1, 1];
state S4: if Reset then S0
S3 = [1, 1, 0];
else if X then S6 with Z = 0
S4 = [1, 0, 0];
else S5 with Z = 1
S5 = [1, 1, 1];
state S5: if Reset then S0
S6 = [1, 0, 1];
else if X then S0 with Z = 1
else S0 with Z = 0
state S6: if Reset then S0
PAL con registri
else if !X then S0 with Z = 1
diagramma degli stati
end bcd2excess3;
© R.H. Katz 10-19
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con contatori
Contatori sincroni: CLR, LD, CNT
0
Quattro tipi di transizioni di stato:
(1) allo stato 0 (CLR)
CLR
(2) al prossimo stato in sequenza (CNT)
(3) ad un qualsiasi altro stato (LD)
(4) allo stesso stato
Nessun
segnale
attivato
n
CNT
n+1
LD
m
E’ necessaria una codifica molto attenta
per usare al meglio la sequenza di conteggio
© R.H. Katz 10-20
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con contatori
Rivediamo il convertitore eccesso-3
Reset
0/1
1
0/1
0
4
1/0
0/0,
1/1
0/1
3
0/0,
1/1
Notate la natura “sequenziale”
della codifica degli stati
5
2
0/0,
1/1
1/0
1/0
6
0/1
© R.H. Katz 10-21
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con contatori
Convertitore eccesso-3
Ingressi e
Stato
Stato presente
futuro
X Q2 Q1 Q0 Q2+ Q1+ Q0+
0 0 0 0
0
0
1
0 0 0 1
0
1
0
0 0 1 0
0
1
1
0 0 1 1
0
0
0
0 1 0 0
1
0
1
0 1 0 1
0
1
1
0 1 1 0
0
0
0
0 1 1 1
X X X
1 0 0 0
1
0
0
1 0 0 1
1
0
1
1 0 1 0
0
1
1
1 0 1 1
0
0
0
1 1 0 0
1
0
1
1 1 0 1
1
1
0
1 1 1 0
X X X
1 1 1 1
X X X
Uscite
Z CLR LD
1 1 1
1 1 1
0 1 1
0 0 X
1 1 1
0 1 0
1 0 X
X X X
0 1 0
0 1 0
1 1 1
1 0 X
0 1 1
1 1 1
X X X
X X X
EN
1
1
1
X
1
X
X
X
X
X
1
X
1
1
X
X
C
X
X
X
X
X
0
X
X
1
1
X
X
X
X
X
X
B
X
X
X
X
X
1
X
X
0
0
X
X
X
X
X
X
A
X
X
X
X
X
0
X
X
0
1
X
X
X
X
X
X
Il segnale CLR domina su LD, che a sua volta domina CNT
© R.H. Katz 10-22
Strategie di realizzazione
Reti Logiche
Realizzazione di FSM
Progetto di FSM con contatori
Convertitore eccesso-3
.i 5
Ingresso di Espresso .i 5
.o 7
.o 7
.ilb res x q2 q1 q0
.ilb res x q2 q1 q0
.ob z clr ld en c b a
.ob z clr ld en c b a
.p 17
.p 10
1---- -0----0-001 0101101
00000 1111---0-01 1000000
00001 1111---11-0 1000000
00010 0111--0-0-0 0101100
00011 00-----000- 1010000
00100 0111---0--0 0010000
00101 110-011
0-10- 0101011
00110 10------11- 1000000
00111 -------11-- 0010000
01000 010-100
-1-1- 1010000
01001 010-101
.e
01010 1111--Uscita di Espresso
01011 10----01100 1111--01101 0111--01110 ------01111 ------.e
© R.H. Katz 10-23
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con contatori
Schema del convertitore eccesso-3
CLK
1
0
1
0
excess 3 PLA
X
Rese t
X
Q2
Q1
Q0
Z
\CLR
\L D
EN
C
B
A
7
P
10
163
T
RCO15
2
CLK
6 D
QD 11
5 C
QC 12
4 B
QB 13
3 A
14
QA
9 LOAD
1
D Q
Z
C Q
CLR
Registro di uscita sincrono
© R.H. Katz 10-24
Strategie di realizzazione
Reti Logiche
Realizzazione di FSM
Progetto di FSM con PLD complessi
Dispositivi logici programmabili (Programmable Logic Device, PLD)
PAL, PLA = 10 - 100 porte logiche equivalenti
Matrici logiche programmabili (Field Programmable Gate Array, FPGA)
• Famiglia MAX Altera
• Matrice Logica Programmabile Actel
(Programmable Logical Array)
• Matrice Logica Programmabile Xilinx
(Logical Cell Array, LCA)
100 - 10.000 porte logiche equivalenti!
© R.H. Katz 10-25
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con PLD complessi
EPLD Altera (Erasable Programmable Logic Devices)
Prospettiva “storica”:
PAL: stessa tecnologia di PROM TTL
(programmabili una sola volta tramite fusibili)
EPLD: stessa tecnologia di EPROM cancellabili CMOS
(cancellate con raggi Ultravioletti)
Blocco base Altera: MACROCELL
CLK
MUX
clock
Matrice AND/OR
8 termini prodotto
+
MUX
programmabili
Matr.
AND
MUX
uscita
Q
Piedino
I/O
Contr.
invers.
MUX
reaz.
Polarita’ programmabile
pad
Blocco
logico
sequenziale
Reazione programmmabile
© R.H. Katz 10-26
Strategie di realizzazione
Progetto di FSM con PLD complessi
Reti Logiche
Realizzazione di FSM
Gli EPLD Altera contengono da 8 a 48 macrocelle indipendenti
Programmazione clock/Output Enable usando bit di EPROM:
Global
CLK
Clk
MUX
Modo sincrono
1
Flipflop controllato
dal clock globale
OE/Local CLK
Q
EPROM
Cell
Global
CLK
Clk
MUX
segnale locale usato
come Output enable
Modo “asincrono”
1
OE/Local CLK
Q
Flipflop controllato
dal clock generato
localmente
EPROM
Cell
Logica sequenziale: puo’ essere FF D, FF T, attivo sul fronte di
salita o di discesa; un termine prodotto realizza il reset
© R.H. Katz 10-27
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con PLD complessi
Strutture AND-OR sono piuttosto limitate:
non possono condividere termini prodotto tra macrocelle
Soluzione Altera: Multiple Array Matrix (MAX)
Logic
Array
Block
(simili a
macrocelle)
LAB A
LAB H
LAB B
LAB C
LAB D
LAB G
P
I
A
LAB F
Connessione
globale:
Programmable
Interconnect
Array
EPM5128:
8 ingressi fissi
52 piedini I/O
8 LAB
16 Macrocelle/LAB
32 Expander/LAB
LAB E
© R.H. Katz 10-28
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con PLD complessi
Architettura di un LAB
I/O Pad
Macrocell
ARRAY
I
N
P
U
T
S
I/O
Block
I/O Pad
P
I
A
Expander
Product
Term
ARRAY
Termini prod.
macrocella
Termini prod.
expander
Termini prodotto dell’Expander
condivisi tra tutte le macrocelle
all’interno di un LAB
© R.H. Katz 10-29
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
PAL P22V10
INCREMENT
2904
1
0
0
FIRST
FUSE
NUMBERS
4
8
12
16
20
24
28
32
36
2948
2992
3036
3080
3124
3168
3212
3256
3300
3344
3388
3432
3476
3520
3564
3608
40
ASYNCHRONOUS RESET
(TO ALL REGISTERS)
44
88
132
176
220
264
308
352
396
1 1
1 0
AR
D
Q
0 0
Q
0 1
23
5808
SP
P
R
1
0
5809
OUTPUT
LOGIC
MACROCEL
L
18
P - 5818
R - 5819
6
440
3652
484
528
572
616
660
704
748
792
836
880
OUTPUT
LOGIC
MACROCELL
3696
3740
3784
3828
3872
3916
3960
4004
4048
4092
4136
4180
4224
4268
22
P - 5810
R - 5811
2
924
968
1012
1056
1100
1144
1188
1232
1276
1320
1364
1408
1452
P - 5820
R - 5821
4312
OUTPUT
LOGIC
MACROCELL
4356
4400
4444
4488
4532
4576
4620
4664
4708
4752
4796
4840
21
P - 5812
R - 5813
1496
OUTPUT
LOGIC
MACROCEL
L
16
P - 5822
R - 5823
8
4884
OUTPUT
LOGIC
MACROCELL
4928
4972
5016
5060
5104
5148
5192
5236
5280
5324
20
P - 5814
R - 5815
4
OUTPUT
LOGIC
MACROCEL
L
15
P - 5824
R - 5825
9
5368
2156
2200
2244
2288
2332
2376
2420
2464
2508
2552
2596
2640
2684
2728
2772
2816
2860
5
17
7
3
1540
1584
1628
1672
1716
1760
1804
1848
1892
1936
1980
2024
2068
2112
OUTPUT
LOGIC
MACROCEL
L
OUTPUT
LOGIC
MACROCELL
5412
5456
5500
5544
5588
5632
5676
5720
OUTPUT
LOGIC
MACROCEL
L
14
P - 5826
R - 5827
19
10
P - 5816
R - 5817
SYNCHRONOUS
PRESET
(TO ALL REGISTERS)
5764
11
INCREMEN
T
13
0
4
8
12
16
20
24
28
32
36
40
Puo’ avere molti termini prodotto per ogni uscita
Registro, reazione ed Output Enable per ogni uscita
© R.H. Katz 10-30
Strategie di realizzazione
Progetto di FSM con PLD complessi
Reti Logiche
Realizzazione di FSM
Programmable Gate Array Actel
Usa anti-fusibili per creare
interconnessioni lunghe
a partire da brevi segmenti
Buffer I/O, logica programm. e collaudo
Tecnologia ad anti-fusibile:
programmabile
una sola volta
Buffer I/O, logica programm. e collaudo
Buffer I/O, logica programm. e collaudo
Righe di blocchi
logici programmabili
+
righe di interconnessione
Buffer I/O, logica programm. e collaudo
Blocco logico
Connessioni
Blocchi logici combinatori con 8 ingressi ed 1 uscita
FF creati da porte logiche con reazione
© R.H. Katz 10-31
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Blocco logico Actel (Actel Logic Module)
S0
SOA
D0
0
D1
1
Blocco logico base e’ un
multiplexer 4:1 modificato
S1
2:1 MUX
0
D2
2:1 MUX
Y
1
0
2:1 MUX
D3
1
R
SOB
Esempio:
realizzazione di un latch R-S
0
2:1 MUX
"0"
1
0
Q+ = R’ 0 + R (S’ 1 + S Q) =
= R S’ + R S Q =
= R S’ + R Q =
= (R + (S + Q)’)’
"0"
"1"
2:1 MUX
Q
1
0
2:1 MUX
1
S
© R.H. Katz 10-32
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Connessione Actel
Blocco logico
Pista
orizzontale
Anti-fusibile
Pista
verticale
Schema di interconnessione
© R.H. Katz 10-33
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Esempio di interconnessione Actel
Blocco logico
Ingresso
Uscita
Blocco logico
Blocco logico
Ingresso
Servono “deviazioni” per girare intorno ad una pista gia’ usata
Minimizzare il numero di deviazioni per connessioni a ritardo
piu’ critico (clock, reti a molti livelli)
Bastano 2 - 3 segmenti per la maggior parte delle connessioni
© R.H. Katz 10-34
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con PLD complessi
Matrici logiche Xilinx (Xilinx Logic Cell Array)
Tecnologia RAM statica CMOS: programmabile “al volo”!
Tutti i bit di programmazione collegati come registro a scorrimento
Programmazione fa scorrere una stringa di 1 e 0 all’accensione
IOB
IOB
CLB
IOB
CLB
IOB
canali di
interconnessione
CLB
CLB
IOB
Architettura generale del
circuito:
• blocchi logici (CLB)
• blocchi di I/O (IOB)
• canali di interconnessione
IOB
IOB
IOB
© R.H. Katz 10-35
Strategie di realizzazione
Progetto di FSM con PLD complessi
Architettura LCA Xilinx: blocco di ingresso/uscita (IOB)
Ingressi:
- abilitazione tri-state
uscita (OE),
- dato in uscita,
- clock
Uscita:
dato in ingresso
FF interni per ingresso
ed uscita
Program Controlled Options
OUT
INV
TS
INV
OUTPUT
SOURCE
SLEW
RATE
PASSIVE
PULLUP
Vcc
Enable
Output
PAD
MUX
Out
D
Q
Output
Buffer
R
Direct In
Uscite lente/veloci:
tempo di salita di
30 ns o 5 ns
Reti Logiche
Realizzazione di FSM
Q
D
Registered In
TTL or CMOS
Input Buffer
R
Pull-up interno per
IOB non utilizzati
Clocks
Global Reset
© R.H. Katz 10-36
Reti Logiche
Strategie di realizzazione
Realizzazione di FSM
Progetto di FSM con PLD complessi
Architettura LCA Xilinx: blocco logico configurabile (CLB)
2 flipflop
Reset
DIN
Qualsiasi funzione
con fino a 5 variabili
Q1
A
B
C
D
E
Reset globale
Clock e abilitazione
D RD
Q
CE
F
Mux
X
Mux
Y
Generatore
di funzioni
combinatorie
Q2
G
Mux
Clock
Ingresso esterno
ai flipflop (DIN)
Mux
Mux
D RD
Q
CE
Clock
Enable
© R.H. Katz 10-37
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con PLD complessi
Architettura LCA Xilinx: generatore di funzioni del CLB
Q1
A
B
Q1
A
B
Mux
Funzione
F
Mux
C Mux
D
E
Q2
Funzione
di 5
variabili
C
D
E
di 4
variabili
F
Mux
Q2
G
Qualsiasi funzione di 5 variabili
Mux
Q1
A
B
Mux
Funzione
C
D
E
Mux
di 4
variabili
G
Mux
Q2
Due funzioni indipendenti
di 4 variabili ciascuna
© R.H. Katz 10-38
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con PLD complessi
Architettura LCA Xilinx: generatore di funzioni del CLB
Q1
A
B
Mux
C
Mux
Funzione
di 4
variabili
D
Alcune funzioni
(limitate) di 6 variabili
E
F
Q2
Mux
Q1
A
B
C
G
Mux
Mux
Funzione
di 4
variabili
D
Q2
© R.H. Katz 10-39
Strategie di realizzazione
Progetto di FSM con PLD complessi
Reti Logiche
Realizzazione di FSM
Esempi di uso di Xilinx
Generatore di parita’ a 5 bit
Realizzato con 1 CLB:
F = A xor B xor C xor D xor E
(non e’ lo stesso generatore visto nel capitolo 8!)
Comparatore a 2 bit: A B = C D o A B > C D
Realizzato con 1 CLB:
(=)
F=AC + ABD + BCD
(>)
G=ABCD + ABCD + ABCD + ABCD
© R.H. Katz 10-40
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con PLD complessi
Esempi di uso di Xilinx
Funzione “maggioranza ad n ingressi”: uscita ad 1 se n/2 (o piu’) ingressi ad 1
Maggioranza a 7 ingressi
Maggioranza a 5 ingressi
CLB
CLB
CLB
CLB
Funzione “parita’ ad n ingressi”:
5 ingressi per CLB => 2 livelli di CLB forniscono fino a 25 ingressi!
Parita’ a 9 ingressi
CLB
CLB
© R.H. Katz 10-41
Strategie di realizzazione
Progetto di FSM con PLD complessi
Reti Logiche
Realizzazione di FSM
Esempi di uso di Xilinx
Sommatore binario a 4 ingressi
A3
B3
A2
CLB
Cout
B2
A1
CLB
S3
A3 B3 A2 B2
CLB
A0
CLB
S2
C2
B1
C1
Sommatore a riporto:
4 ritardi di CLB per
riporto finale in uscita
CLB
S1
C0
S0
A1 B1 A0 B0 Cin
S2
CLB
S0
S3
Cout
B0 Cin
2 sommatori a 2 bit (3 CLB
ciascuno) danno solo
2 ritardi di CLB per
riporto finale in uscita!!
S1
C2
© R.H. Katz 10-42
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con PLD complessi
Architettura LCA Xilinx
Interconnessione:
Connessioni
dirette
DI CE A
B
X
C CLB0
K
Y
E D R
(1) Connessione diretta
(2) Connessione con
linee lunghe globali
(3) Connessione con
linee lunghe verticali
ed orizzontali
(4) Connessione con
matrice
DI CE A
B
X
C CLB1
K
Y
E D R
Linee lunghe
orizzontali
Matrice
conness.
Linee lunghe
orizzontali
DI CE A
B
X
C CLB3
K
Y
E D R
DI CE A
B
X
C CLB2
K
Y
E D R
Linee lunghe
verticali
Linea lunga
globale
© R.H. Katz 10-43
Strategie di realizzazione
Progetto di FSM con PLD complessi
Architettura LCA Xilinx
Reti Logiche
Realizzazione di FSM
Realizzazione FSM conversione da BCD ad eccesso-3
Q2+ = Q2 • Q0 + Q2 • Q0
Q1+ = X • Q2 • Q1 • Q0 + X • Q2 • Q0 + X • Q2 • Q0 + Q1 • Q0
Q0+ = Q0
Z = Z • Q1 + X • Q1
Nessuna funzione richiede piu’ di 4 variabili
4 FF richiedono 2 CLB
Macchina di Moore (Mealy sincrona)
Uso del reset globale
Mettere Q2+, Q0+ nel primo CLB
Q1, Z nel secondo CLB
massimizzare l’uso di connessioni dirette e tramite matrice
© R.H. Katz 10-44
Reti Logiche
Realizzazione di FSM
Strategie di realizzazione
Progetto di FSM con PLD complessi
Architettura LCA Xilinx
Realizzazione FSM conversione da BCD ad eccesso-3
Clk
Clk
X
CE
CE
A
CE
DI
B
X
Q2
Q0
FG
DI
Q2
B
C
C
Y
K
Q0
FG
E
Q0
K
X
Q2
Q1
Q0
X
Q1
A
X
FG
Y
Q1
Z
FG
E
D
RES
D
CLB1
RES
CLB2
© R.H. Katz 10-45
Esempio di progetto
Controllore di semaforo
Reti Logiche
Realizzazione di FSM
Decomposizione in sotto-blocchi piu’ semplici
• FSM di controllo:
funzioni di stato futuro e di uscita
registro di stato
• Contatore per intervallo lungo ed
intervallo corto
• Sensore dei veicoli
• Decodificatore di uscita e luci
© R.H. Katz 10-46
Reti Logiche
Realizzazione di FSM
Esempio di progetto
Controllore di semaforo
Schema a blocchi
Reset
Clk
TS
Contatore
intervallo
lungo e corto
TL
FSM controllo
Logica
2
stato futuro 2
ed uscita
Reset
C (asinc.)
Clk
ST
Sensore
veicoli C (sinc.)
2
2
F
Segnali
Decodifica
luci
luci
codificati
3
3
H
Registro
di stato
© R.H. Katz 10-47
Reti Logiche
Realizzazione di FSM
Esempio di progetto
Controllore di semaforo
0
Logica dei sotto-blocchi
Pres ent
D
Decodificatore
delle
F0
luci
C
Q
F1
RQ
\Pre sent
1
FG FY FR
+
Cin
0
2 A
3 B
1 G
\Res et
Y0
Y1
Y2
Y3
139a
4
5
6
7
1
0
0
HG HY HR
+
H0
CLK
Sensore veicoli
(de-rimbalzatore + sincronizzatore)
H1
1 A
Y0
1
4 B
Y1
3
Y2
1 G
Y3
5
139b
1
1
2
1
09
+
CLK
Temporizzatore
degli intervalli
(contatore)
Reset
7 P
10 T 163
1
2 CLK RCO
5
6 D
QD 11
5 C
QC 12
4 B
QB 13
3 A
QA 14
9 LOAD
CLR 1
CLR
TL
TS
ST
© R.H. Katz 10-48
Esempio di progetto
Controllore di semaforo
Reti Logiche
Realizzazione di FSM
Logica di stato futuro della FSM di controllo
Codifica degli stati: HG = 00, HY = 10, FG = 01, FY = 11
P1 = C TL Q1 + TS Q1 Q0 + C Q1 Q0 + TS Q1 Q0
P0 = TS Q1 Q0 + Q1 Q0 + TS Q1 Q0
ST = C TL Q1 + C Q1 Q0 + TS Q1 Q0 + TS Q1 Q0
HL[1] = TS Q1 Q0 + Q1 Q0 + TS Q1 Q0
HL[0] = TS Q1 Q0 + TS Q1 Q0
FL[1] = Q0
FL[0] = TS Q1 Q0 + TS Q1 Q0
Realizzazione a PAL/PLA:
servono 5 ingressi, 7 uscite, 8 termini prodotto
PAL 22V10: 11 ingressi, 10 I/O programmabili,
da 8 a 14 termini per ogni OR
Realizzazione a ROM:
ROM da 32 parole di 8 bit (256 bit)
Reset potrebbe raddoppiare la ROM...
© R.H. Katz 10-49
Reti Logiche
Realizzazione di FSM
Esempio di progetto
Controllore di semaforo
Logica di stato futuro della FSM di controllo
Realizzazione a contatore:
HG
TL•C / ST
HY
TS / ST
FG
TL+C / ST
TS
TL
\C
TL
C
2 MUX 4:1
1 GA
3 A3
4 A2
5 A1
6 A0
13
12
11
10
B3
B2
B1
B0
15 GB
153
YA 7
YB 9
S1 SO
2 14
ST
+
7
10 P 163
T
15
2 CLK RCO
6
5
4
3
D
C
B
A
QD
QC
QB
QA
11
12
13
14
Q1
Q0
9 LOAD
\Reset 1 CLR
FY
Realizzazione TTL con MUX e contatore
TS / ST
Si puo’ ridurre il numero di integrati con un MUX 8:1?
ST = abilitazione al conteggio per entrambi i contatori (controllo e intervalli)
© R.H. Katz 10-50
Reti Logiche
Realizzazione di FSM
Esempio di progetto
Controllore di semaforo
Logica di uscita della FSM di controllo
Realizzazione a contatore:
Possiamo evitare il costo delle funzioni di uscita?
Perche’ non decodificare le uscite direttamente
dallo stato presente?
HG HY HR
1
1 G
Q1
Q0
3B
2A
Y3
Y2
Y1
Y0
0
0
FG FY FR
0
0
1
7
6
5
4
139a
ST e’ un’uscita di Mealy sincrona
Le luci sono uscite di Moore
© R.H. Katz 10-51
Esempio di progetto
Reti Logiche
Realizzazione di FSM
Controllore di semaforo
Realizzazione con LCA Xilinx
Realizzazione a partire dalle equazioni gia’ derivate:
Nessuna delle funzioni ha piu’ di 5 variabili
P1, ST hanno 5 variabili (1 CLB ciascuna)
P0, HL1, HL0, FL0 hanno 3 variabili (1/2 CLB ciascuna)
FL1 ha 1 variabile (1/2 CLB)
4.5 CLB in totale!
© R.H. Katz 10-52
Reti Logiche
Realizzazione di FSM
Esempio di progetto
Controllore di semaforo
Realizzazione con
LCA Xilinx
TL C TS
TS
TS
Q0
DI CE A
B
X
C F0
K
Y
E D R
Q0
TL
DI CE A
B
X
C
K
Y
E D R
F1
Q0
Q1
Piazzare le funzioni
in modo da rendere
massimo l’uso di
connessioni dirette
TS
Q1
DI CE A
B
X
C Q1
K
Y
E D R
Q0
Q1
TS
DI CE A
B
X
C
K
Y
E D R
H1
H0
C
Q1
TL
TS
C
Q0
DI CE A
B
X
C ST
K
Y
E D R
DI CE A
B
X
C
K
Y
E D R
© R.H. Katz 10-53
Esempio di progetto
Reti Logiche
Realizzazione di FSM
Controllore di semaforo
Realizzazione con LCA Xilinx
Realizzazione con contatore e multiplexer:
MUX 4:1 MUX, contatore a 2 bit
MUX: 6 variabili (4 dati, 2 controllo)
ma questa e’ esattamente una delle funzioni di 6 variabili
che possono essere realizzate con 1 CLB!
Serve un secondo CLB per realizzare TL • C e TL + C'
Notate che ST/Cnt e’ in realta’ funzione di TL, C, TS, Q1, Q0:
basta 1 CLB per realizzare questa funzione di 5 variabili!
Contatore a 2 bit: 2 funzioni di 3 variabili (2 bit di stato + Cnt)
anche qui basta 1 CLB
Decodificatori delle luci: funzioni di 2 variabili (Q1, Q0)
2 per CLB, richiedono 3 CLB per le 6 luci
Totale: 5 CLB
© R.H. Katz 10-54
Riassunto del capitolo
Reti Logiche
Realizzazione di FSM
• Ottimizzazione e realizzazione di FSM
Minimizzazione degli stati: corrispondenza tra righe e tabella
delle implicazioni
Codifica degli stati: euristiche e programmi CAD
• Problemi di realizzazione
Scelta dei flipflop
Realizzazioni con logica strutturata
basati su ROM
basati su PLA/PAL
basati su contatori
PLD piu’ complessi: Altera, Actel, Xilinx
© R.H. Katz 10-55