SoluzioniEsame6Febbraio2001CanaleHZ < Architetture1/EO

---+ Esame di Architetture a degli Elaboratori Elettronici 1
---+ 6 Febbraio 2001, canale H-Z

<font color=red>le soluzioni sono in preparazione</font>

Vedi TestoEsame6Febbraio2001CanaleHZ e RisultatiEsame6Febbraio2001CanaleHZ.

----
%TOC%
----
---++ Prima parte

---+++ Esercizio 1 (15 punti)

Siano *X=x3 x2 x1 x0* ed *Y=y2 y1 y0* due numeri binari rispettivamente
di 4 e 3 bit.

	* Progettate il circuito che calcola:  *Y= (X*5---+1) mod 7*
	* Disegnate il circuito usando solo porte NAND.

*NOTA:* Vi ricordo che *(a mod b)* indica il *resto di a diviso b*.

---++++ Soluzione Esercizio 1

Tabella di verità:
| *X* | *Y* | *x3 x2 x1 x0* | *y2 y1 y0* |
|  0  |	1 |  0  0  0  0 |  0  0  1 |
|  1  |	6 |  0  0  0  1 |  1  1  0 |
|  2  |	4 |  0  0  1  0 |  1  0  0 |
|  3  |	2 |  0  0  1  1 |  0  1  0 |
|  4  |	0 |  0  1  0  0 |  0  0  0 |
|  5  |	5 |  0  1  0  1 |  1  0  1 |
|  6  |	3 |  0  1  1  0 |  0  1  1 |
|  7  |	1 |  0  1  1  1 |  0  0  1 |
|  8  |	6 |  1  0  0  0 |  1  1  0 |
|  9  |	4 |  1  0  0  1 |  1  0  0 |
| 10  |	2 |  1  0  1  0 |  0  1  0 |
| 11  |	0 |  1  0  1  1 |  0  0  0 |
| 12  |	5 |  1  1  0  0 |  1  0  1 |
| 13  |	3 |  1  1  0  1 |  0  1  1 |
| 14  |	1 |  1  1  1  0 |  0  0  1 |
| 15  |	6 |  1  1  1  1 |  1  1  0 |

Minimizziamo y2, y1 e y0 con le mappe di Karnaugh: (con le lettere a..z indico le zone minimizzate nell'ordine)
| *y2*  | x1 x0 | | | |
| x3 x2 | 00	| 01	| 11	| 10  |
|  0 0  |  0	|  1 a |  0	|  1 b|
|  0 1  |  0	|  1 a |  0	|  0  |
|  1 1  |  1 c |  0	|  1 e |  0  |
|  1 0  |  1 cd|  1 d |  0	|  0  |

*y2 = n(x3) n(x1) x0---+ n(x3) n(x2) x1 n(x0) + x3 n(x1) n(x0) + x3 n(x2) n(x1) + x3 x2 x1 x0*

| *y1*  | x1 x0 | | | |
| x3 x2 | 00	| 01	| 11	| 10	|
|  0 0  |  0	|  1 a |  1 a |  0	|
|  0 1  |  0	|  0	|  0	|  1 b |
|  1 1  |  0	|  1 c |  1 c |  0	|
|  1 0  |  1 d |  0	|  0	|  1 d |

*y1 = n(x3) n(x2) x0---+ n(x3) x2 x1 n(x0) + x3 x2 x0 + x3 n(x2) n(x0)*

| *y0*  | x1 x0 | | | |
| x3 x2 | 00	| 01	| 11	| 10	|
|  0 0  |  1 a |  0	|  0	|  0	|
|  0 1  |  0	|  1 c |  1 c |  1 d |
|  1 1  |  1 b |  1 b |  0	|  1 d |
|  1 0  |  0	|  0	|  0	|  0	|

*y0 = n(x3) n(x2) n(x1) n(x0)---+ x3 x2 n(x1) + n(x3) x2 x0 + x2 x1 n(x0)*


---+++ Esercizio 2 (15 punti)

Si minimizzino algebricamente le funzioni booleane: 
	* y0 = n(x0(x0 n(x2)---+ x0(n(x1)x3 x2 + x2 x1 x3)))
	* y1 = x0(n(x1---+ x0) + x2(x1 + n(x2)))
	* y2 = x0(n(x1)---+ x0(x2 n(x1) + n(x3 x2)x0))
	* y3 = x3(x2 x0---+ x0 n(x2)) + n(x3) x2

---++++ Soluzione Esercizio 2

	* *y0* = n(x0(x0 n(x2)---+ x0(n(x1)x3 x2 + x2 x1 x3))) = <br>
		= n(x0(x0 n(x2)---+ x0(x3 x2 ))) = <br>
		= n(x0(x0( n(x2)---+ x3 x2))) = <br>
		= n(x0( n(x2)---+ x3 x2)) = <br>
		= n(x0 n(x2)---+ x0 x3 x2) = <br>
		= n(x0 n(x2))  n(x0 x3 x2) = <br>
		= (n(x0)---+ x2) ( n(x0) + n(x3) + n(x2) ) = <br>
		= n(x0)---+ n(x0) n(x3) + n(x0) n(x2) + x2 n(x0) + x2 n(x3) = <br>
		= *n(x0)---+ x2 n(x3)*

	* *y1* = x0(n(x1---+ x0) + x2(x1 + n(x2))) = <br>
		= x0(n(x1) n(x0)---+ x2 x1) = <br>
		= *x0 x2 x1*

	* *y2* = x0(n(x1)---+ x0(x2 n(x1) + n(x3 x2)x0)) = <br>
		= x0(n(x1)---+ x0(x2 n(x1) + (n(x3) + n(x2))x0)) = <br>
		= x0(n(x1)---+ x0(x2 n(x1) + x0 n(x3) + n(x2) x0)) = <br>
		= x0(n(x1)---+ x0 x2 n(x1) + x0 n(x3) + n(x2) x0) = <br>
		= x0 n(x1)---+ x0 x2 n(x1) + x0 n(x3) + n(x2) x0 = <br>
		= *x0 n(x1)---+ x0 n(x3) + n(x2) x0*

	* *y3* = x3(x2 x0---+ x0 n(x2)) + n(x3) x2 = <br>
		= *x3 x0---+ n(x3) x2* 

__NOTA:__ *n()* corrisponde alla negazione.

---++ Seconda Parte
---+++ Esercizio 3 (30 punti)

Progettate il circuito sequenziale che realizza, usando flip-flop di tipo *JK*, 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 4 bit ricevuti in input corrispondono ad una delle
	stringhe binarie: *1010, 1001, 0010*.
  
Disegnate in forma grafica l'automa *minimizzato* (oppure verificate che non sia minimizzabile).

Codificate gli stati dell'automa.

Calcolate la tabella di transizione.

Calcolate la forma minimizzata delle le funzioni di input dei 
flip-flop e della funzione $Z$.

Disegnate il circuito usando i Flip-flop JK ed una PLA.

---++++ Soluzione Esercizio 3

Per ricordare gli stati intermedi del riconoscimento delle 3 stringhe abbiamo bisogno degli stati *- 1 10 101 100 0 00 001*.

L'automa in forma tabellare (in cui indico con input/output i bit letti/scritti ) è:
| da->a | "-" | "1" | "10" | "101" | "100" | "0" | "00" | "001" |
| "-"	|	  | 1/0 |		|		 |		 | 0/0 |		|		 |
| "1"	|	  | 1/0 | 0/0  |		 |		 |	  |		|		 |
| "10"  |	  |	  |		|  1/0  |  0/0  |	  |		|		 |
| "101" |	  | 1/0 | 0/1  |		 |		 |	  |		|		 |
| "100" |	  |	  |		|		 |		 |	  | 0/0  |  1/1  |
| "0"	|	  | 1/0 |		|		 |		 |	  | 0/0  |		 |
| "00"  |	  |	  |		|		 |		 |	  | 0/0  |  1/0  |
| "001" |	  | 1/0 | 0/1  |		 |		 |	  |		|		 |
L'automa è minimizzabile perchè la riga "101" è uguale alla "001", chiamo "x01" lo stato ottenuto unendo "101" a "001".

Il nuovo automa, minimizzato, ha solo 7 stati ed è:
| da->a | "-" | "1" | "10" | "x01" | "100" | "0" | "00" |
| "-"	|	  | 1/0 |		|		 |		 | 0/0 |		|
| "1"	|	  | 1/0 | 0/0  |		 |		 |	  |		|
| "10"  |	  |	  |		|  1/0  |  0/0  |	  |		|
| "x01" |	  | 1/0 | 0/1  |		 |		 |	  |		|
| "100" |	  |	  |		|  1/1  |		 |	  | 0/0  |
| "0"	|	  | 1/0 |		|		 |		 |	  | 0/0  |
| "00"  |	  |	  |		|  1/0  |		 |	  | 0/0  |

<img alt="Automa minimizzato" src="/cgi-bin/webdot/%ATTACHURLPATH%/soluzione.dot.png">

<table><tr><td>
Scegliamo una codifica per gli stati:
| Stato | q2 q1 q0 |
| "-"	|  0  0  0 |
| "1"	|  0  0  1 |
| "10"  |  0  1  0 |
| "x01" |  0  1  1 |
| "100" |  1  0  0 |
| "0"	|  1  0  1 |
| "00"  |  1  1  0 |
</td><td>

Ricordo che la tabella di transizione di un flip-flop *JK* è:
| J | K | q | q' |
| 0 | 0 | 0 | 0  |
| 0 | 0 | 1 | 1  |
| 0 | 1 | 0 | 0  |
| 0 | 1 | 1 | 0  |
| 1 | 0 | 0 | 1  |
| 1 | 0 | 1 | 1  |
| 1 | 1 | 0 | 1  |
| 1 | 1 | 1 | 0  |

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

La tabella di transizione che ne deriva è (indico i don't care con - ):
| X | q2 | q1 | q0 || q2' | q1' | q0' || Z || J2 | K2 || J1 | K1 || J0 | K0 |
| 0 |  0 |  0 |  0 ||  1  |  0  |  1  || 0 || 1  | -  ||  0 |  - ||  1 |  - |
| 1 |  0 |  0 |  0 ||  0  |  0  |  1  || 0 || 0  | -  ||  0 |  - ||  1 |  - |
| 0 |  0 |  0 |  1 ||  0  |  1  |  0  || 0 || 0  | -  ||  1 |  - ||  -  | 1 |
| 1 |  0 |  0 |  1 ||  0  |  0  |  1  || 0 || 0  | -  ||  0 |  - ||  -  | 0 |
| 0 |  0 |  1 |  0 ||  1  |  0  |  0  || 0 || 1  | -  ||  -  | 1 ||  0  | - |
| 1 |  0 |  1 |  0 ||  0  |  1  |  1  || 0 || 0  | -  ||  -  | 0 ||  1 |  - |
| 0 |  0 |  1 |  1 ||  0  |  1  |  0  || 1 || 0  | -  ||  -  | 0 ||  -  | 1 |
| 1 |  0 |  1 |  1 ||  0  |  0  |  1  || 0 || 0  | -  ||  -  | 1 ||  -  | 0 |
| 0 |  1 |  0 |  0 ||  1  |  1  |  0  || 0 || -  | 0  ||  1 |  - ||  0  | - |
| 1 |  1 |  0 |  0 ||  0  |  1  |  1  || 1 || -  | 1  ||  1 |  - ||  1 |  - |
| 0 |  1 |  0 |  1 ||  1  |  1  |  0  || 0 || -  | 0  ||  1 |  - ||  -  | 1 |
| 1 |  1 |  0 |  1 ||  0  |  0  |  1  || 0 || -  | 1  ||  0  | - ||  -  | 0 |
| 0 |  1 |  1 |  0 ||  1  |  1  |  0  || 0 || -  | 0  ||  -  | 0 ||  0  | - |
| 1 |  1 |  1 |  0 ||  0  |  1  |  1  || 0 || -  | 1  ||  -  | 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  | 1 b | 0  |
| 01 | 0	| 0  | - b | 0  |
| 11 | 1 a | 0  | -	| 0  |
| 10 | 0	| 0  | 0	| 0  |

*Z = x q2 n(q1) n(q0)---+ n(x) q1 q0*

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

| J2 | 00	| 01  | 11  | 10	|
| 00 | 1 a  | 0	| 0	| 1 a  |
| 01 | - a  | -	| -	| - a  |
| 11 | -	 | -	| -	| -	 |
| 10 | 0	 | 0	| 0	| 0	 |

*J2 = n(x) n(q0)*

</td><td>

| K2 | 00	| 01  | 11  | 10	|
| 00 | -	 | -	| -	| -	 |
| 01 | 0	 | 0	| -	| 0	 |
| 11 | 1 a  | 1 a | - a | 1 a  |
| 10 | - a  | - a | - a | - a  |

*K2 = x*

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

| J1 | 00	| 01  | 11  | 10	|
| 00 | 0	 | 1 a | - a | -	 |
| 01 | 1 b  | 1 a | - a | - b  |
| 11 | 1 b  | 0	| -	| - b  |
| 10 | 0	 | 0	| -	| -	 |

*J1 = n(x) q0---+ q2 n(q0)*

</td><td>

| K1 | 00	| 01  | 11  | 10	|
| 00 | - a  | -	| 0	| 1 a  |
| 01 | -	 | -	| -	| 0	 |
| 11 | -	 | - b | - b | 0	 |
| 10 | -	 | - b | 1 b | 0	 |

*K1 = n(x) n(q2) n(q0)---+ x q0*

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

| J0 | 00	| 01	| 11  | 10	|
| 00 | 1 b  | - b  | -	| 0	 |
| 01 | 0	 | -	 | -	| 0	 |
| 11 | 1 a  | - a  | - a | 1 a  |
| 10 | 1 ab | - ab | - a | 1 a  |

*J0 = x---+ n(q2) n(q1)*

</td><td>

| K0 | 00	| 01  | 11  | 10	|
| 00 | - a  | 1 a | 1 a | - a  |
| 01 | - a  | 1 a | - a | - a  |
| 11 | -	 | 0	| -	| -	 |
| 10 | -	 | 0	| 0	| -	 |

*K0 = n(x)*

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

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


-- Users.AndreaSterbini - 08 Feb 2001 <br>

	* Set ALLOWTOPICCHANGE = Users.DocentiArcGroup
Attachments
Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
dot	soluzione.dot		manage	0.6 K	2001-06-06 - 09:52	UnknownUser	Automa minimizzato
This topic: Architetture1/EO > SoluzioniEsame6Febbraio2001CanaleHZ
Topic revision: r2 - 2001-06-06 - AndreaSterbini