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:
  • 0101, 0111, 1101

1. Disegnate in forma grafica l'automa minimizzato
2. Codificate gli stati dell'automa
3. Calcolate la tabella di transizione
4. Calcolate la forma minimizzata delle funzioni di input dei flip-flop e della funzione Z
5. 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

• Set ALLOWTOPICCHANGE = DocentiArcGroup