SoluzioneEsame20Febbraio2001CanaleHZ < Architetture1/EO

---++ Esame di Architetture 1 del 20 febbraio 2001 canale H-Z

Vedi: SoluzioneEsame20Febbraio2001CanaleHZ, RisultatiEsame20Febbraio2001CanaleHZ.

Progettate il circuito sequenziale che realizza, usando flip-flop di tipo *SR*, 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: *0010, 0001, 1010, 1001*
  
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 SR ed una PLA.

----

---++ Soluzione

Per riconoscere le stringhe c'è bisogno dei 9 stati: *-, 0, 00, 000, 001, 1, 10, 101, 100*

La tabella di transizione è:
| *da->a* |-	|0	|00	|000	|001	|1	|10	|101	|100	| *righe uguali* |
|-	|	|0/0	|	|	|	|1/0	|	|	|	|	|
|0	|	|	|0/0	|	|	|1/0	|	|	|	|	|
|00	|	|	|	|0/0	|1/0	|	|	|	|	|	|
|000	|	|	|	|0/0	|1/1	|	|	|	|	|a	|
|001	|	|	|	|	|	|1/0	|0/1	|	|	|b	|
|1	|	|	|	|	|	|1/0	|0/0	|	|	|	|
|10	|	|	|	|	|	|	|	|1/0	|0/0	|	|
|101	|	|	|	|	|	|1/0	|0/1	|	|	|b	|
|100	|	|	|	|0/0	|1/1	|	|	|	|	|a	|

Due coppie di righe sono uguali, quindi, fondendo i corrispondenti stati si ottiene l'automa seguente, formato dai 7 soli stati: *-, 0, 00, x00, x01, 1, 10*.
| *da->a* |-	|0	|00	|x00	|x01	|1	|10	| *righe uguali* |
|-	|	|0/0	|	|	|	|1/0	|	|	|
|0	|	|	|0/0	|	|	|1/0	|	|	|
|00	|	|	|	|0/0	|1/0	|	|	|a	|
|x00	|	|	|	|0/0	|1/1	|	|	|	|
|x01	|	|	|	|	|	|1/0	|0/1	|	|
|1	|	|	|	|	|	|1/0	|0/0	|	|
|10	|	|	|	|0/0	|1/0	|	|	|a	|

L'automa è ulteriormente minimizzabile i 6 stati sono: *-, 0, x0, x00, x01, 1*
| *da->a* |-	|0	|x0	|x00	|x01	|1	| *righe uguali* |
|-	|	|0/0	|	|	|	|1/0	|	|
|0	|	|	|0/0	|	|	|1/0	|a	|
|x0	|	|	|	|0/0	|1/0	|	|	|
|x00	|	|	|	|0/0	|1/1	|	|	|
|x01	|	|	|0/1	|	|	|1/0	|	|
|1	|	|	|0/0	|	|	|1/0	|a	|

Ed ancora, i 5 stati necessari sono: *-, x, x0, x00, x01*
<table><tr valign="top"><td>
| *da->a* | - | x | x0|x00|x01|
|-		  |	|-/0|	|	|	|
|x		  |	|1/0|0/0|	|	|
|x0		 |	|	|	|0/0|1/0|
|x00		|	|	|	|0/0|1/1|
|x01		|	|1/0|0/1|	|	|
</td><td>
<img alt="Automa minimizzato" src="/cgi-bin/webdot/%ATTACHURLPATH%/soluzione.dot.png">
</td></tr></table>

L'automa non è ulteriormente minimizzabile.


Codifichiamo gli stati:
| "-"	| 000 |
| "x"	| 001 |
| "x0"  | 010 |
| "x00" | 011 |
| "x01" | 100 |

Ricordo la tabella di transizione di un flip-flop SR:
| *S* | *R* | *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 | - |

Quindi per ottenere le diverse transizioni bisogna usare i seguenti valori di SR:
| *Q Q'* | *S R* |
|  0 0	|  0 -  |
|  0 1	|  1 0  |
|  1 0	|  0 1  |
|  1 1	|  - 0  |

La tabella di transizione è:
| *x* | *q2 q1 q0* | *q2' q1' q0'* | *Z* | *S2 R2* | *S1 R1* | *S0 R0* |
| 0	|	0  0  0  |	0	0	1	|  0  |	0  -  |	0  -  |	1  0  |
| 1	|	0  0  0  |	0	0	1	|  0  |	0  -  |	0  -  |	1  0  |
| 0	|	0  0  1  |	0	1	0	|  0  |	0  -  |	1  0  |	0  1  |
| 1	|	0  0  1  |	0	0	1	|  0  |	0  -  |	0  -  |	-  0  |
| 0	|	0  1  0  |	0	1	1	|  0  |	0  -  |	-  0  |	1  0  |
| 1	|	0  1  0  |	1	0	0	|  0  |	1  0  |	0  1  |	0  -  |
| 0	|	0  1  1  |	0	1	1	|  0  |	0  -  |	-  0  |	-  0  |
| 1	|	0  1  1  |	1	0	0	|  1  |	1  0  |	0  1  |	0  1  |
| 0	|	1  0  0  |	0	1	0	|  1  |	0  -  |	1  0  |	0  -  |
| 1	|	1  0  0  |	0	0	1	|  0  |	0  -  |	0  -  |	1  0  |
| 0	|	1  0  1  |  -	-	 -	|  -  |	-  -  |	-  -  |	-  -  |
| 1	|	1  0  1  |  -	-	 -	|  -  |	-  -  |	-  -  |	-  -  |
| 0	|	1  1  0  |  -	-	 -	|  -  |	-  -  |	-  -  |	-  -  |
| 1	|	1  1  0  |  -	-	 -	|  -  |	-  -  |	-  -  |	-  -  |
| 0	|	1  1  1  |  -	-	 -	|  -  |	-  -  |	-  -  |	-  -  |
| 1	|	1  1  1  |  -	-	 -	|  -  |	-  -  |	-  -  |	-  -  |

Come vedete, grazie al basso numero di stati ed all'uso di flip-flop SR ci sino molti dont' care.

<font color=red size="---+2"> ... segue ...</font>


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

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