Piotr Kawalec

Wykład IX - 1

Wykład IX

Tworzenie i minimalizacja

tablic przejść- wyjść

Technika cyfrowa

Piotr Kawalec

Wykład IX - 2

Technika cyfrowa 

Przykłady tworzenia tablic przejść - 

wyjść



Przykład 2 - 

zbudować tablicę przejść - wyjść 

układu

     wykrywającego w dowolnie długim ciągu 

binarnym

     sekwencje 

1100



 Przykład 3 - 

Na wejście układu podawane są 

kolejno

     bit po bicie trzybitowe ciągi o wartościach od 

0 do 5.

     Na wyjściu ma się pojawić 1 gdy kolejny ciąg 

zawiera

     nieparzystą liczbę jedynek 

 

Piotr Kawalec

Wykład IX - 3

Technika cyfrowa 

Zamiana tablic przejść - wyjść 
automatu Mealy’ego w tablice 
automatu Moore’a



 Każdej parze stanów

 (s

i

, y

k

) 

wpisanych w 

klatki
    tablicy Mealy’ego przyporządkowujemy stan 

z

j 

    

automatu Moore’a, przy czym jednakowym 

parom
    stanów powinny odpowiadać te same stany  

z

j

.

  



 

Tworzymy tablicę przejść - wyjść automatu 

Moore’a,
     przypisując każdemu stanowi

 z

j 

sygnał 

y

k 

z 

pary
    

 

(s

i

, y

k

)

. Stany następne dla każdego 

x

 

przypisujemy
    

 

stanowi 

z

j 

takie, jakie miał stan 

s

i 

z tejże pary.

 

Piotr Kawalec

Wykład IX - 4

Technika cyfrowa 

Zamiana tablic przejść - wyjść 
automatu Moore’a w tablice 
automatu Mealy’ego 



 Zapisujemy w klatce tablicy przejść automatu 

    Moore’a, w której występował stan następny 

s

i

, 

    wartości wyjścia 

y

k

 

odpowiadające temu 

stanowi. 



 

Po utworzeniu tablicy przejść - wyjść 

automatu

    Mealy’ego usuwamy kolumnę wyjść.

 

Piotr Kawalec

Wykład IX - 5

Technika cyfrowa 

Minimalizacja tablic przejść - wyjść



 zbudowane tablice przejść - wyjść zwykle nie 

mają 
    minimalnej liczby wierszy (stanów)



 ponieważ od liczby stanów zależy wymagana

    wielkość pamięci, to układy zawierające 
minimalną
    liczbę stanów wewnętrznych będą prostsze i 
tańsze



 

Proces minimalizacji liczby stanów 

wewnętrznych 
     polega na zastępowaniu dwóch lub więcej 
wierszy
     w tablicy przejść - wyjść jednym wierszem, 
bez
     zmiany sposobu działania układu

 

Piotr Kawalec

Wykład IX - 6

Technika cyfrowa 

Podstawowe pojęcia



 

Dwa stany następne 

stanów s

i

 , s

j

 są 

niesprzeczne

 

     

jeśli są one jednakowe lub co najmniej jeden

     z nich jest nieokreślony (np. 

s

k

 

i

 s

k

; 

s

k

 

i

 --

 ; 

-- 

i

 --

 )



 

Dwa stany wyjścia y i y’ są 

niesprzeczne

,gdy 

     odpowiadające im sygnały są parami 

identyczne

     lub co najmniej jeden z nich jest 

nieokreślony 

     (

0 

i

 0

;

 1 

i

 1

;

 0 

i

 --

; 

1 

i

 --

;

  -- 

i

 -- 

)

Piotr Kawalec

Wykład IX - 7

Technika cyfrowa 

Podstawowe pojęcia cd



 Stany  s

i

 i s

j

 są 

zgodne

, jeżeli dla każdego 

ciągu

     liter wejściowych 

x 

stosowalnego zarówno 

dla s

i

 

     jak i

 

s

j

,

 

stany końcowe wygenerowanych 

ciągów

     wyjściowych są niesprzeczne



 

Dwa stany wewnętrzne 

s

i

 

i

 s

j

 

są 

zgodne

, 

jeżeli 



 

sygnały wyjściowe odpowiadające tym 

stanom 

     są niesprzeczne



 stany następne są niesprzeczne lub 

zgodne

Piotr Kawalec

Wykład IX - 8

Technika cyfrowa 

Przykład minimalizacji tablic przejść-

wyjść



 zminimalizować tablicę automatu 

x

s

x

1

x

2

x

3

x

4

y

1

 y

2

1

5

5

–

1

0   1

2

–

2

2

–

0   –

3

5

–

–

4

1   –

4

5

–

–

4

–   1

5

1

2

3

4

1   1

 stany 1 i 4 są zgodne

;  

stany 2 i 4 zgodne

;  

stany

 

3 i 4 zgodne

  

Piotr Kawalec

Wykład IX - 9

Technika cyfrowa 

Minimalizacja liczby stanów 
wewnętrznych metodą par (trójkątną 
tablicą zgodności)



 buduje się tablicę trójkątną 



 

klatkę o współrzędnych (i, j) wykreśla się 

jeżeli stany

     s

i 

i s

j 

mają sprzeczne wyjścia

 gdy zgodność pary stanów 

s

i 

i

 s

j 

jest 

warunkowana

    zgodnością 

 

innej pary 

s

k 

i

 s

l 

to indeksy 

k,l 

wpisujemy

    do klatki o współrzędnych 

(i,j)

. Nie wpisuje się 

    indeksów pary stanów warunkujących 

zgodność 

    samej siebie

Piotr Kawalec

Wykład IX - 10

Technika cyfrowa 

Minimalizacja liczby stanów 
wewnętrznych metodą par (trójkątną 
tablicą zgodności) cd 



 wpisuje się warunki i wykreśla wszystkie 

klatki

     o sprzecznych wyjściach 



 

następnie wykreśla się te wszystkie klatki, w 

których

    jako jeden z warunków występuje para 

indeksów

    odpowiadająca klatce wykreślonej na 

poprzednim

    etapie 

 klatki niewykreślone, bez względu na 

zawartość,

    odpowiadają parom stanów zgodnych

Piotr Kawalec

Wykład IX - 11

Technika cyfrowa 

Wyznaczanie maksymalnych grup 
stanów zgodnych



 dla automatu zupełnego wszystkie stany 

parami

     zgodne można zastąpić jednym stanem 



 

dla automatu niezupełnego na podstawie 

tablicy

    trójkątnej tworzony jest zbiór (klasa) 

maksymalnych

    grup stanów zgodnych (grup w których 

wszystkie

    stany są parami zgodne) 

 zbiór maksymalnych grup stanów zgodnych

    oznaczamy 



Piotr Kawalec

Wykład IX - 12

Technika cyfrowa 

Wyznaczanie zbioru maksymalnych 
grup stanów zgodnych 





 z grafu relacji zgodności

 

tworzymy graf relacji zgodności łącząc ze 

sobą 

     stany odpowiadające parom indeksów 

opisujących

     niewykreślone klatki tablicy trójkątnej



 

wychodząc z każdego

 

stanu tworzymy

     

maksymalne grupy stanów zgodnych 

zawierające

  

   

wszystkie stany połączone każdy z każdym 



 tworzymy zbiór 

 

Piotr Kawalec

Wykład IX - 13

Technika cyfrowa 



  z tablicy trójkątnej



 wybieramy kolumnę o najwyższym 

numerze w

     której nie wszystkie klatki są wykreślone i 

dla niej 

     wypisujemy zbiory par indeksów

     niewykreślonych klatek



 

jeśli dla kolejnej kolumny w zbiorze wierszy

     o niewykreślonych klatkach mieszczą się

     utworzone poprzednio zbiory, to 

rozszerzamy

     je o numer  rozpatrywanej kolumny

Piotr Kawalec

Wykład IX - 14

Technika cyfrowa 



  z tablicy trójkątnej cd



pozostałe niewykreślone klatki kolumny 

opisuje

    się zbiorami par indeksów



 

czynności te powtarza się dla wszystkich

    dalszych kolumn, analizując możliwość

    rozszerzenia dowolnego z wcześniej 

    wypisanych zbiorów lub ich podzbiorów


 

postępowanie to kończymy wypisaniem 

zbioru 

     

maksymalnych grup stanów zgodnych

   

  zawierającego wszystkie stany automatu

 

Piotr Kawalec

Wykład IX - 15

Technika cyfrowa 

Wyznaczanie optymalnego zbioru 
maksymalnych grup stanów zgodnych 



opt



  dla automatów zupełnych automat 

wyznaczony na 
      podstawie maksymalnych grup stanów 
zgodnych jest
      minimalny



  

dla automatów niezupełnych można 

wyznaczyć

     optymalny zbiór grup zgodnych

 



opt  

zawierający
     mniejszą liczbę grup  

Piotr Kawalec

Wykład IX - 16

Technika cyfrowa 

Wyznaczanie optymalnego zbioru 
maksymalnych grup stanów 
zgodnych 



opt



szukany zbiór grup zgodnych musi spełniać 

warunki:

   

 każdy stan musi wchodzić co najmniej do

     jednej grupy 

(warunek pełności zbioru)

 

dla każdej pary każdego zbioru muszą być

    spełnione wymogi zgodności warunkowej 

Piotr Kawalec

Wykład IX - 17

Technika cyfrowa 

Przykłady minimalizacji liczby 
stanów wewnętrznych (trójkątną 
tablicą zgodności)



Przykład 1  zminimalizować tablicę automatu

 

x

s

x

1

x

2

x

3

x

4

y

1

 y

2

1

5

5

–

1

0   1

2

–

2

2

–

0   –

3

5

–

–

4

1   –

4

5

–

–

4

–   1

5

1

2

3

4

1   1

Piotr Kawalec

Wykład IX - 18

Technika cyfrowa 

 

tablica trójkątna

 

Piotr Kawalec

Wykład IX - 19

Technika cyfrowa 

 

graf zgodności

 

1

2

3

4

5

 

wyznaczanie zbioru

  

  i 

opt

 

= {{1,4}; {2,4}; {3,4}; {5}}

 



opt 

= {{1,4}; {2}; {3};{5}}

Piotr Kawalec

Wykład IX - 20

Technika cyfrowa 

 

minimalna tablica przejść - wyjść

 

x

s

x

1

x

2

x

3

x

4

y

1

 y

2

{1,4}   

1

4

4

–

1

0   1

{2}      

2

–

2

2

–

0   –

{3}      

3

4

–

–

1

1   –

{5}      

4

1

2

3

1

1   1