SoluzioniEsame12Giugno2001 < Architetture1/EO

---++ Esame di Architetture 1 - AA 2000-2001 - appello del 12-6-2001

Progettate il circuito sequenziale che realizza, 
  usando flip-flop di tipo \textbf{D}, l'automa di Mealy che:
		* riceve in input una variabile *X* a valori nell'alfabeto *S={a,b,c}*
		* da' in output una variabile binaria *Z* che vale "1" se e
		  solo se *gli ultimi 3 simboli ricevuti in input sono uguali*. 

	1 Minimizzate l'automa e disegnatelo in forma grafica.
	1 Codificate i simboli e gli stati dell'automa.
	1 Calcolate la tabella di transizione.
	1 Calcolate la forma minimizzata delle le funzioni di input dei flip-flop *D* e della funzione *Z*.
----
Vedi RisultatiEsame12Giugno2001.
----
---+++ Soluzione

L'automa ha la tabella di transizione seguente, e quindi non puo' essere
ulteriormente minimizzato perche' non ci sono coppie di righe identiche.

|		 | - | a	|  b  | c	| aa  | bb  | cc  |
|	 -  |	| a/0 | b/0 | c/0 |	  |	  |	  |
|	 a  |	|	  | b/0 | c/0 | a/0 |	  |	  |
|	 b  |	| a/0 |	  | c/0 |	  | b/0 |	  |
|	 c  |	| a/0 | b/0 |	  |	  |	  | c/0 |
|	 aa |	|	  | b/0 | c/0 | a/1 |	  |	  |
|	 bb |	| a/0 |	  | c/0 |	  | b/1 |	  |
|	 cc |	| a/0 | b/0 |	  |	  |	  | c/1 |

<IMG ALT="Automa" SRC="%WEBDOT%/%ATTACHURLPATH%/automa-12-6-2001.dot.png">

Se si scelgono (*ad esempio*) le seguenti codifiche dei simboli in input e degli
stati:
<table><tr valign="top"><td>
|	 Simbolo | codice |
|	 a  | 01 |
|	 b  | 10 |
|	 c  | 11 |
</td><td>
|	 Stato | codice |
|	 -  | 000 |		
|	 a  | 001 |
|	 b  | 010 |
|	 c  | 011 |
|	 aa | 100 |
|	 bb | 101 |
|	 cc | 110 |
</td></tr></table>

Si ottiene la tabella di transizione:

|	 *x1 x0* | *Q2 Q1 Q0* | *Q'2 Q'1 Q'0* | Z |
|	 0 0  | 0 0 0 |  0 0 1 | 0 |
|	 0 1  | 0 0 0 |  0 1 0 | 0 |
|	 1 0  | 0 0 0 |  0 1 1 | 0 |
|	 0 0  | 0 0 1 |  1 0 0 | 0 |
|	 0 1  | 0 0 1 |  0 1 0 | 0 |
|	 1 0  | 0 0 1 |  0 1 1 | 0 |
|	 0 0  | 0 1 0 |  0 0 1 | 0 |
|	 0 1  | 0 1 0 |  1 0 1 | 0 |
|	 1 0  | 0 1 0 |  0 1 1 | 0 |
|	 0 0  | 0 1 1 |  0 0 1 | 0 |
|	 0 1  | 0 1 1 |  0 1 0 | 0 |
|	 1 0  | 0 1 1 |  1 1 0 | 0 |
|	 0 0  | 1 0 0 |  1 0 0 | 1 |
|	 0 1  | 1 0 0 |  0 1 0 | 0 |
|	 1 0  | 1 0 0 |  0 1 1 | 0 |
|	 0 0  | 1 0 1 |  0 0 1 | 0 |
|	 0 1  | 1 0 1 |  1 0 1 | 1 |
|	 1 0  | 1 0 1 |  0 1 1 | 0 |
|	 0 0  | 1 1 0 |  0 0 1 | 0 |
|	 0 1  | 1 1 0 |  0 1 0 | 0 |
|	 1 0  | 1 1 0 |  1 1 0 | 1 |
|	 1 1  | - - - | - - -  | - |
|	 - -  | 1 1 1 | - - -  | - |

Da cui si ricavano le funzioni di input dei FF di tipo *D* e la *Z* :
(le minimizzazioni sono indicate dalle lettere corsive _a,b,c_ ...)
<table border=1>
<tr><th>Z</th><th>x1=0</th><th>x1=1</th></tr>
<tr><td></td><td>
| x0 q2 \ q1 q0 | 0 0 | 0 1 | 1 1 | 1 0 |
| 0 0 | 0	  | 0	  | 0	  | 0	  |
| 0 1 | 1 _a_ | 0	  | -	  | 0	  |
| 1 1 | 0	  | 1 _b_ | - _b_ | 0	  |
| 1 0 | 0	  | 0	  | 0	  | 0	  |
</td><td>
| x0 q2 \ q1 q0 | 0 0 | 0 1 | 1 1 | 1 0 |
| 0 0 | 0	  | 0	  | 0		| 0	  |
| 0 1 | 0	  | 0	  | - _c_  | 1 _c_ |
| 1 1 | -	  | - _b_ | - _bc_ | - _c_ |
| 1 0 | -	  | -	  | -		| -	  |
</td></tr>
</table>

*Z= x1n x0n q2 q1n q0n---+ x0 q2 q0 + x1 q2 q1*

<table  border=1>
<tr><th>D2=Q'2</th><th>x1=0</th><th>x1=1</th></tr>
<tr><td></td><td>
| x0 q2 \ q1 q0 | 0 0 | 0 1 | 1 1 | 1 0 |
| 0 0 | 0	  | 1 _a_ | 0	  | 0	  |
| 0 1 | 1 _b_ | 0	  | -	  | 0	  |
| 1 1 | 0	  | 1 _c_ | - _c_ | 0	  |
| 1 0 | 0	  | 0	  | 0	  | 1 _d_ |
</td><td>
| x0 q2 \ q1 q0 | 0 0 | 0 1 | 1 1 | 1 0 |
| 0 0 | 0	  | 0	  | 1 _e_	| 0	  |
| 0 1 | 0	  | 0	  | - _ef_  | 1 _f_ |
| 1 1 | -	  | - _c_ | - _cef_ | - _f_ |
| 1 0 | -	  | -	  | - _e_	| - _d_ |
</td></tr>
</table>

*D2= x1n x0n q2n q1n q0---+ x1n x0n q2 q1n q0n + x0 q2 q0 + x0 q2n q1 q0n + x1 q1 q0 + x1 q2 q1*

<table border=1>
<tr><th>D1=Q'1</th><th>x1=0</th><th>x1=1</th></tr>
<tr><td></td><td>
| x0 q2 \ q1 q0 | 0 0 | 0 1 | 1 1 | 1 0 |
| 0 0 | 0	  | 0	  | 0	  | 0	  |
| 0 1 | 0	  | 0	  | -	  | 0	  |
| 1 1 | 1 _a_ | 0	  | - _c_ | 1 _c_ |
| 1 0 | 1 _a_ | 1 _b_ | 1 _b_ | 0	  |
</td><td>
| x0 q2 \ q1 q0 | 0 0 | 0 1 | 1 1 | 1 0 |
| 0 0 | 1 _d_  | 1 _d_  | 1 _d_  | 1 _d_  |
| 0 1 | 1 _d_  | 1 _d_  | - _d_  | 1 _d_  |
| 1 1 | - _ad_ | - _d_  | - _cd_ | - _cd_ |
| 1 0 | - _ad_ | - _bd_ | - _bd_ | - _d_  |
</td></tr>
</table>

*D1= x0 q1n q0n---+ x0 q2n q0 + x0 q2 q1 + x1*

<table  border=1>
<tr><th>D0=Q'0</th><th>x1=0</th><th>x1=1</th></tr>
<tr><td></td><td>
| x0 q2 \ q1 q0 | 0 0 | 0 1 | 1 1 | 1 0 |
| 0 0 | 1 _a_ | 0	  | 1 _b_  | 1 _abd_ |
| 0 1 | 0	  | 1 _c_ | - _bc_ | 1 _b_	|
| 1 1 | 0	  | 1 _c_ | - _c_  | 0		 |
| 1 0 | 0	  | 0	  | 0		| 1 _d_	|
</td><td>
| x0 q2 \ q1 q0 | 0 0 | 0 1 | 1 1 | 1 0 |
| 0 0 | 1 _ae_ | 1 _e_  | 0	  | 1 _ad_ |
| 0 1 | 1 _e_  | 1 _ce_ | - _c_ | 0		|
| 1 1 | - _e_  | - _ce_ | - _c_ | -		|
| 1 0 | - _e_  | - _e_  | -	  | - _d_  |
</td></tr>
</table>

*D0= x0n q2n q0n---+ x1n x0n q1 + q2 q0 + q2n q1 q0n + x1 q1n*



-- Users.AndreaSterbini - 18 Jun 2001 <br>

<!--
	* Set ALLOWTOPICCHANGE = Users.DocentiArcGroup
-->
Attachments
Topic attachments
I	Attachment	History	Action	Size	Date	Who	Comment
dot	automa-12-6-2001.dot		manage	0.8 K	2001-06-18 - 13:31	UnknownUser	Automa soluzione in formato WebDot
This topic: Architetture1/EO > SoluzioniEsame12Giugno2001
Topic revision: r1 - 2001-06-18 - AndreaSterbini