Soluzioni del secondo esonero (a.a. 2000-2001, canale H-Z)
Vedi anche
SecondoEsonero2000HZ e
RisultatiSecondoEsonero2000HZ.
Attenzione!
Gli esercizi proposti hanno più di una possibile soluzione a seconda della codifica scelta per gli stati, per cui le soluzioni qua sotto sono indicative del metodo di soluzione.
Esercizio A
Progettate il circuito sequenziale che realizza, usando flip-flop di tipo
D, l'automa di Mealy che:
- riceve in input una variabile binaria X
- dà in output una variabile binaria Z che vale "1" se e solo se gli ultimi quattro bit ricevuti in input corrispondono ad una delle stringhe binarie:
- Disegnate in forma grafica l'automa minimizzato
- Codificate gli stati dell'automa
- Calcolate la tabella di transizione
- Calcolate la forma minimizzata delle funzioni di input dei flip-flop e della funzione Z
- Disegnate il circuito usando porte AND, OR, NOT e flip-flop D.
Soluzione A
L'automa in forma tabellare (in cui indico con input/output i bit letti/scritti ) è:
da->a |
"-" |
"0" |
"01" |
"010" |
"011" |
"1" |
"11" |
"110" |
"-" |
|
0/0 |
|
|
|
1/0 |
|
|
"0" |
|
0/0 |
1/0 |
|
|
|
|
|
"01" |
|
|
|
0/0 |
1/0 |
|
|
|
"010" |
|
0/0 |
1/1 |
|
|
|
|
|
"011" |
|
|
|
|
|
|
1/1 |
0/0 |
"1" |
|
0/0 |
|
|
|
|
1/0 |
|
"11" |
|
|
|
|
|
|
1/0 |
0/0 |
"110" |
|
0/0 |
1/1 |
|
|
|
|
|
L'automa è minimizzabile perchè la riga "010" è uguale alla "110", chiamo "x01" lo stato ottenuto unendoli "010" a "110".
Il nuovo automa, minimizzato, ha solo 7 stati ed è:
da->a |
"-" |
"0" |
"01" |
"x10" |
"011" |
"1" |
"11" |
"-" |
|
0/0 |
|
|
|
1/0 |
|
"0" |
|
0/0 |
1/0 |
|
|
|
|
"01" |
|
|
|
0/0 |
1/0 |
|
|
"x10" |
|
0/0 |
1/1 |
|
|
|
|
"011" |
|
|
|
0/0 |
|
|
1/1 |
"1" |
|
0/0 |
|
|
|
|
1/0 |
"11" |
|
|
|
0/0 |
|
|
1/0 |
Scegliamo una codifica per gli stati:
Stato |
q2 q1 q0 |
"-" |
0 0 0 |
"0" |
0 0 1 |
"01" |
0 1 0 |
"x10" |
0 1 1 |
"011" |
1 0 0 |
"1" |
1 0 1 |
"11" |
1 1 0 |
La tabella di transizione che ne deriva è (indico i don't care con - ):
X |
q2 |
q1 |
q0 |
q2'=D2 |
q1'=D1 |
q0'=D0 |
Z |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
- |
- |
- |
- |
1 |
1 |
1 |
1 |
- |
- |
- |
- |
Le mappe di Karnaugh per Z e per gli input dei flip-flop sono (indico con le lettere a..z le aree minimizzate nell'ordine):
Z |
00 |
01 |
11 |
10 |
00 |
0 |
0 |
0 |
0 |
01 |
0 |
0 |
- |
0 |
11 |
1 a |
0 |
- b |
0 |
10 |
0 |
0 |
1 b |
0 |
Z = x d2 n(d1) n(d0)---+ x d1 d0
|
D2 |
00 |
01 |
11 |
10 |
00 |
0 |
0 |
0 |
0 |
01 |
0 |
0 |
- |
0 |
11 |
1 ab |
1 a |
- a |
1 ab |
10 |
1 b |
0 |
0 |
1 b |
D2 = x d2---+ x n(d0)
|
D1 |
00 |
01 |
11 |
10 |
00 |
0 |
0 |
0 |
1 c |
01 |
1 a |
0 |
- |
1 ac |
11 |
1 a |
1 b |
- b |
1 a |
10 |
0 |
1 b |
1 b |
0 |
D1 = d2 n(d0)---+ x d0 + n(x) d1 n(d0)
|
D0 |
00 |
01 |
11 |
10 |
00 |
1 ab |
1 a |
1 a |
1 a |
01 |
1 a |
1 a |
- a |
1 a |
11 |
0 |
0 |
- |
0 |
10 |
1 b |
0 |
0 |
0 |
D0 = n(x)---+ n(d2) n(d1) n(d0)
|
Esercizio B
Come sopra, ma riconoscendo le stringhe
1001, 1011, 1100
Soluzione B
L'automa in forma tabellare (in cui indico con input/output i bit letti/scritti ) è:
da->a |
"-" |
"1" |
"10" |
"100" |
"101" |
"11" |
"110" |
"-" |
0/0 |
1/0 |
|
|
|
|
|
"1" |
|
|
0/0 |
|
|
1/0 |
|
"10" |
|
|
|
0/0 |
1/0 |
|
|
"100" |
0/0 |
1/1 |
|
|
|
|
|
"101" |
|
|
0/0 |
|
|
1/1 |
|
"11" |
|
|
|
|
|
1/0 |
0/0 |
"110" |
|
|
|
0/1 |
1/0 |
|
|
L'automa non è minimizzabile perchè nessuna coppia di righe ha gli stessi input/output nelle stesse caselle.
Scegliamo una codifica per gli stati:
Stato |
q2 q1 q0 |
"-" |
0 0 0 |
"1" |
0 0 1 |
"10" |
0 1 0 |
"100" |
0 1 1 |
"101" |
1 0 0 |
"11" |
1 0 1 |
"110" |
1 1 0 |
La tabella di transizione che ne deriva è (indico i don't care con - ):
X |
q2 |
q1 |
q0 |
q2'=D2 |
q1'=D1 |
q0'=D0 |
Z |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
- |
- |
- |
- |
1 |
1 |
1 |
1 |
- |
- |
- |
- |
Le mappe di Karnaugh per Z e per gli input dei flip-flop sono (indico con le lettere a..z le aree minimizzate nell'ordine):
Z |
00 |
01 |
11 |
10 |
00 |
0 |
0 |
0 |
0 |
01 |
0 |
0 |
- b |
1 b |
11 |
1 a |
0 |
- c |
0 |
10 |
0 |
0 |
1 c |
0 |
Z = x d2 n(d1) n(d0)---+ n(x) d2 d1 + x d1 d0
|
D2 |
00 |
01 |
11 |
10 |
00 |
0 |
0 |
0 |
0 |
01 |
0 |
1 b |
- b |
0 |
11 |
1 a |
1 abc |
- ab |
1 ad |
10 |
0 |
1 c |
0 |
1 d |
D2 = x d2---+ d2 d0 + x n(d1) d0 + x d1 n(d0)
|
D1 |
00 |
01 |
11 |
10 |
00 |
0 |
1 b |
0 |
1 c |
01 |
1 a |
1 ab |
- a |
1 ac |
11 |
0 |
0 |
- |
0 |
10 |
0 |
0 |
0 |
0 |
D1 = n(x) d2---+ n(x) n(d1) d0 + n(x) d1 n(d0)
|
D0 |
00 |
01 |
11 |
10 |
00 |
0 |
0 |
0 |
1 a |
01 |
0 |
0 |
- |
1 a |
11 |
1 b |
1 bc |
- c |
0 |
10 |
1 b |
1 bc |
1 c |
0 |
D0 = n(x) d1 n(d0)---+ x n(d1) + x d0
|
Esercizio C
Come sopra, ma riconoscendo le stringhe
0001, 0101, 0111
Soluzione C
L'automa in forma tabellare (in cui indico con input/output i bit letti/scritti ) è:
da->a |
"-" |
"0" |
"00" |
"000" |
"01" |
"010" |
"011" |
"-" |
1/0 |
0/0 |
|
|
|
|
|
"0" |
|
|
0/0 |
|
1/0 |
|
|
"00" |
|
|
|
0/0 |
1/0 |
|
|
"000" |
|
|
|
0/0 |
1/1 |
|
|
"01" |
|
|
|
|
|
0/0 |
1/0 |
"010" |
|
|
0/0 |
|
1/1 |
|
|
"011" |
1/1 |
0/0 |
|
|
|
|
|
L'automa non è minimizzabile perchè nessuna coppia di righe ha gli stessi input/output nelle stesse caselle.
Scegliamo una codifica per gli stati:
Stato |
q2 q1 q0 |
"-" |
0 0 0 |
"0" |
0 0 1 |
"00" |
0 1 0 |
"000" |
0 1 1 |
"01" |
1 0 0 |
"010" |
1 0 1 |
"011" |
1 1 0 |
La tabella di transizione che ne deriva è (indico i don't care con - ):
X |
q2 |
q1 |
q0 |
q2'=D2 |
q1'=D1 |
q0'=D0 |
Z |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
- |
- |
- |
- |
1 |
1 |
1 |
1 |
- |
- |
- |
- |
Le mappe di Karnaugh per Z e per gli input dei flip-flop sono (indico con le lettere a..z le aree minimizzate nell'ordine):
Z |
00 |
01 |
11 |
10 |
00 |
0 |
0 |
0 |
0 |
01 |
0 |
0 |
- |
0 |
11 |
0 |
1 a |
- abc |
1 b |
10 |
0 |
0 |
1 c |
0 |
Z = x d2 d0---+ x d2 d1 + x d1 d0
|
D2 |
00 |
01 |
11 |
10 |
00 |
0 |
0 |
0 |
0 |
01 |
1 a |
0 |
- |
0 |
11 |
1 a |
1 b |
- b |
0 |
10 |
0 |
1 b |
1 bc |
1 c |
D2 = d2 n(d1) n(d0)---+ x d0 + x n(d2) d1
|
D1 |
00 |
01 |
11 |
10 |
00 |
0 |
1 b |
1 bc |
1 c |
01 |
0 |
1 b |
- b |
0 |
11 |
1 a |
0 |
- |
0 |
10 |
0 |
0 |
0 |
0 |
D1 = x d2 n(d1) n(d0)---+ n(x) d0 + n(x) n(d2) d1
|
D0 |
00 |
01 |
11 |
10 |
00 |
1 a |
0 |
1 b |
1 ab |
01 |
1 a |
0 |
- b |
1 ab |
11 |
0 |
0 |
- |
0 |
10 |
0 |
0 |
0 |
0 |
D0 = n(x) n(d0)---+ n(x) d1
|
Esercizio D
Come sopra, ma riconoscendo le stringhe
0011, 1100 1110
Soluzione D
L'automa in forma tabellare (in cui indico con input/output i bit letti/scritti ) è:
da->a |
"-" |
"0" |
"00" |
"001" |
"1" |
"11" |
"110" |
"111" |
"-" |
|
0/0 |
|
|
1/0 |
|
|
|
"0" |
|
|
0/0 |
|
1/0 |
|
|
|
"00" |
|
|
0/0 |
1/0 |
|
|
|
|
"001" |
|
0/0 |
|
|
|
1/1 |
|
|
"1" |
|
0/0 |
|
|
|
1/0 |
|
|
"11" |
|
|
|
|
|
|
0/0 |
1/0 |
"110" |
|
|
0/1 |
|
1/0 |
|
|
|
"111" |
|
|
|
|
|
|
0/1 |
1/0 |
L'automa non è minimizzabile perchè nessuna coppia di righe ha gli stessi input/output nelle stesse caselle.
Scegliamo una codifica per gli stati:
Stato |
q2 q1 q0 |
"-" |
0 0 0 |
"0" |
0 0 1 |
"00" |
0 1 0 |
"001" |
0 1 1 |
"1" |
1 0 0 |
"11" |
1 0 1 |
"110" |
1 1 0 |
"111" |
1 1 1 |
La tabella di transizione che ne deriva è (indico i don't care con - ):
X |
q2 |
q1 |
q0 |
q2'=D2 |
q1'=D1 |
q0'=D0 |
Z |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
Le mappe di Karnaugh per Z e per gli input dei flip-flop sono (indico con le lettere a..z le aree minimizzate nell'ordine):
Z |
00 |
01 |
11 |
10 |
00 |
0 |
0 |
0 |
0 |
01 |
0 |
0 |
1 a |
1 a |
11 |
0 |
0 |
0 |
0 |
10 |
0 |
0 |
1 b |
0 |
Z = n(x) d2 d1---+ x n(d2) d1 d0
|
D2 |
00 |
01 |
11 |
10 |
00 |
0 |
0 |
0 |
0 |
01 |
0 |
1 a |
1 a |
0 |
11 |
1 bc |
1 abcd |
1 abd |
1 b |
10 |
1 c |
1 cd |
1 d |
0 |
D2 = d2 d0---+ x d2 + x n(d1) + x d0
|
D1 |
00 |
01 |
11 |
10 |
00 |
0 |
1 a |
0 |
1 cd |
01 |
0 |
1 ab |
1 b |
1 c |
11 |
0 |
1 b |
1 b |
0 |
10 |
0 |
0 |
0 |
1 d |
D1 = n(x) n(d1) d0---+ d2 d0 + n(x) d1 n(d0) + n(d2) d1 n(d0)
|
D0 |
00 |
01 |
11 |
10 |
00 |
1 a |
0 |
1 e |
0 |
01 |
1 a |
0 |
0 |
0 |
11 |
1 c |
1 c |
1 b |
0 |
10 |
0 |
0 |
1 bde |
1 d |
D0 = n(x) n(d1) n(d0)---+ x d1 d0 + x d2 n(d1) + x n(d2) d1 + n(d2) d1 d0
|
--
AndreaSterbini - 11 Jan 2001