Piotr Kawalec

Wykład III - 1

Wykład III

Przykłady kodowania

automatów

synchronicznych

z zastosowaniem rachunku

podziałów

Technika cyfrowa

Piotr Kawalec

Wykład III - 2

Technika cyfrowa

Etapy metody



Wyznaczyć zbiór par podziałów







,

gdzie



jest pewnym podziałem dwublokowym

lub w

szczególności prawidłowym



Narysować graf par podziałów



Zaznaczyć na grafie podziały dogodne ze

względu na wyjście



Wybrać rodzinę T

k opt.

o minimalnej cenie

Piotr Kawalec

Wykład III - 3

Technika cyfrowa

Przykłady kodowania z
zastosowaniem rachunku podziałów

Przykład 1



Zakodować automat zadany tablicą przejść-

wyjść

x x

1

x

2

x

1

x

2

s
1 1 3 0 1
2 4 2 1 --
3 3 1 1 0
4 1 4 -- 1

Piotr Kawalec

Wykład III - 4

Technika cyfrowa



Podziały zewnętrzne i grafy podziałów



(y)

=



x1

(y)

•



x2

(y)

={1, 23, (4)} • {14, 3,

(2)} =



14

x x

1

x

2



1



2



3



4



12



13



14

s
1 1 3 1
2 4 2 2
3 3 1 3
4 1 4 4



2



14



2

{12, 3, 4}



14



12

Piotr Kawalec

Wykład III - 5

Technika cyfrowa

Wyznaczenie rodzin końcowych i cen



Z grafu podziałów można wyznaczyć rodzinę

końcową

T

k

={



12

,



14

}, która jest

równocześnie

rodziną optymalną

T

k opt



Ceny podziałów

c(



12

)

= 1+1-1=1; c(



14

)

=1+2-1=2;

c(y)=1+1-1=1; c = 4



Kodowanie

s



12



14

1 0 1

2 0 0
3 1 0
4 1 1

Q

1

Q

2

Piotr Kawalec

Wykład III - 6

Technika cyfrowa



Zakodowana tablica przejść-wyjść

x

0 1

0 1

(s)

Q

1

Q

2

(2)

00

11 00

1 --

(1)

01

01 10

0 1

(4)

11

01 11

-- 1

(3)

10

10 01

1 0

Q

1

Q

2

y



Funkcja wyjść

y = x

Q

2

+ x

Q

2

Piotr Kawalec

Wykład III - 7

Technika cyfrowa



Tablice wzbudzeń przy realizacji na

przerzutnikach D

x

0 1

0 1

(s)

Q

1

Q

2

(2)

00

1 0

1 0

(1)

01

0 1

1 0

(4)

11

0 1

1 1

(3)

10

1 0

0 0

D

1

D

2



Funkcje wzbudzeń

D

1

= x

Q

2

+ x

Q

2

;

D

2

= x

Q

1

+

Q

1

Q

2

Piotr Kawalec

Wykład III - 8

Technika cyfrowa

Przykłady kodowania z
zastosowaniem rachunku podziałów

Przykład 2



Zakodować automat zadany tablicą przejść-

wyjść

x

s x

1

x

2

y

1

y

2

1 1 2 0 0
2 1 3 0 0
3 4 3 -- 0
4 5 3 1 1
5 1 3 0 1