Podręcznik
5. Przykłady syntezy
5.2. Przykład 2
Automat z tablicy 4.43 zrealizować w strukturze UMA/ROM, stosując ROM o możliwie najmniejszej pojemności. W rozwiązaniu podać wyrażenie boolowskie funkcji modyfikującej adres oraz zawartość ROM.
Tablica 4.43
|
|
v1 |
v2 |
v3 |
v4 |
v5 |
|
a |
d |
– |
c |
c |
d |
|
b |
b |
b |
– |
a |
– |
|
c |
a |
d |
d |
d |
– |
|
d |
– |
c |
b |
– |
b |
Dla danego automatu należy wstępnie przyjąć
U = {</span></span></span></span><i><span lang="DE" style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif"><span style="color:black">q</span></span></span></span></i><sub><span lang="DE" style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif"><span style="color:black">1</span></span></span></span></sub><span lang="DE" style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif"><span style="color:black">,<i>q</i><sub>2</sub></span></span></span></span><span style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif"><span style="color:black">} V= {</span></span></span></span><span style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif"><span style="color:black"> <i>x</i><sub>1</sub>,<i>x</i><sub>2,</sub><i>x</i><sub>3</sub></span></span></span></span><span style="font-size:12.0pt"><span style="line-height:115%"><span style="font-family:"Calibri",sans-serif"><span style="color:black">}
co spowoduje ponumerowanie komórek pamięci, jak w tab. 4.44 i schemat dekompozycji, jak na rys. 4.19.
Tablica 4.44
Rys. 4.19. Schemat dekompozycji do przykładu 4.6
\(P_{F} =\left(\overline{1,4,9,10,11} ;\overline{2,3,12} ;\overline{5,6,13,14} ;\overline{7,8}\right)\)
\(P( U) |P_{F} =\left(\overline{( 1,4)( 2,3)} ;\overline{( 5,6)( 7)} ;\overline{( 8)( 9,10,11)} ;\overline{( 12)( 13,14)}\right)\)
\(P( V) =\left(\overline{1,5,8} ;\overline{6,9,12} ;\overline{2,10,13} ;\overline{3,7,11} ;\overline{4,14,}\right)\)
Podział PG tworzymy z bloków P(V):
- blok \(\overline {1,5,8}; \overline{4,14}; \overline {6,9,12}\)
- blok \(\overline {2,10,13}; \overline {3,7,11}\)
Konflikty wymagają rozdzielenia elementów 6, 12 od 9 oraz 4 od 14, co można uzyskać za pośrednictwem zmiennej q2. Dlatego dla dekompozycji nierozłącznej wybieramy q2 i liczymy podział P(q2):
\(P\left(q_2\right)=\left(\overline{1,2,3,4,8,9,10,11};\overline{5,6,7,12,13,14}\right)\)
co ułatwia obliczenie P(V’):
\(P( V\prime ) =P( V) \cdot \ P( q_{2}) =\left(\overline{1,8} ;\overline{5} ;\overline{6,12} ;\overline{9} ;\overline{2,10} ;\overline{13} ;\overline{3,11} ;\overline{7} ;\overline{4} ;\overline{14}\right)\)
Z bloków P(V’) łatwo można utworzyć P’G:
\(\Pi ^{\prime }_{G} =\left(\overline{1,4,5,6,8,12} ;\overline{2,3,7,9,10,11,13,14}\right)\)
\(\begin{array}{{>{\displaystyle}l}} P( U) \cdot \Pi ^{\prime }_{G} =P( q_{1} ,q_{1}) \cdot \Pi ^{\prime }_{G} =\\ =\left(\overline{1,2,3,4} ;\overline{5,6,7} ;\overline{8,9,10,11} ;\overline{12,13,14}\right) \cdot \left(\overline{1,4,5,6,8,12} ;\overline{2,3,7,9,10,11,13,14}\right) =\\ =\left(\overline{1,4} ;\overline{2,3} ;\overline{5,6} ;\overline{7} ;\overline{8} ;\overline{9,10,11} ;\overline{12} ;\overline{13,14}\right) \end{array}\)
Na tej podstawie możemy wyznaczyć tablice prawdy bloków układu modyfikacji (tab. 4.45 dla G) oraz układu adresowania pamięci ROM (tab. 4.46 dla H), zgodnie z rys. 4.19.
Tablica 4.45.
|
|
q2x1x2x3 |
g |
|
1,8 |
0000 |
0 |
|
4 |
0100 |
0 |
|
5 |
1000 |
0 |
|
6,12 2,10 3,11 7 9 13 14 |
1001 0010 0011 1011 0001 1010 1100 |
0 1 1 1 1 1 1 |
Tablica 4.46.
|
|
q1 q2g |
Stan |
|
1,4 |
000 |
d |
|
2,3 |
001 |
c |
|
5,6 |
010 |
b |
|
7 |
011 |
a |
|
8 |
100 |
a |
|
9,10,11 |
101 |
a |
|
12 |
110 |
c |
|
13,14 |
111 |
b |