SoluzioniSecondoEsonero2000HZ < Architetture1/EO

Tags: view all tags

---++ Soluzioni del secondo esonero (a.a. 2000-2001, canale H-Z)

Vedi anche SecondoEsonero2000HZ e RisultatiSecondoEsonero2000HZ.

<font color=red size="---+2">Attenzione!</font>

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.

----
%TOC%
----

---+++ 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
	1 Codificate gli stati dell'automa
	1 Calcolate la tabella di transizione
	1 Calcolate la forma minimizzata delle funzioni di input dei flip-flop e della funzione Z
	1 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  |

<img alt="Automa minimizzato (compito A)" src="%WEBDOT%/%ATTACHURLPATH%/soluzioneA.dot.png">

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):
<table><tr><td>
| 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*

</td><td>

| 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)*

</td></tr>
<tr><td>

| 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)*

</td><td>

| 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)*

</td></tr></table>

----
---+++ 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.

<img alt="Automa minimizzato (compito B)" src="%WEBDOT%/%ATTACHURLPATH%/soluzioneB.dot.png">

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):
<table><tr><td>
| 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*

</td><td>

| 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)*

</td></tr>
<tr><td>

| 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)*

</td><td>

| 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*

</td></tr></table>

----
---+++ 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.

<img alt="Automa minimizzato (compito C)" src="%WEBDOT%/%ATTACHURLPATH%/soluzioneC.dot.png">

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):
<table><tr><td>
| 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*

</td><td>

| 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*

</td></tr>
<tr><td>

| 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*

</td><td>

| 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*

</td></tr></table>

----
---+++ 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.

<img alt="Automa minimizzato (compito D)" src="%WEBDOT%/%ATTACHURLPATH%/soluzioneD.dot.png">

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):
<table><tr><td>
| 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*

</td><td>

| 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*

</td></tr>
<tr><td>

| 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)*

</td><td>

| 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*

</td></tr></table>


-- Users.AndreaSterbini - 11 Jan 2001 <br>

	* Set ALLOWTOPICCHANGE = Users.DocentiArcGroup

Attachments

Topic attachments
I	Attachment	Action	Size	Date	Who	Comment
dot	soluzioneA.dot	manage	0.6 K	2001-06-06 - 09:57	UnknownUser	Automa minimizzato (compito A)
dot	soluzioneB.dot	manage	0.6 K	2001-06-06 - 10:01	UnknownUser	Automa minimizzato (compito B)
dot	soluzioneC.dot	manage	0.6 K	2001-06-06 - 10:06	UnknownUser	Automa minimizzato (compito C)
dot	soluzioneD.dot	manage	0.7 K	2001-06-06 - 10:09	UnknownUser	Automa minimizzato (compito D)