UkÄady sekwencyjne - pojÄ™cie automatu
UkÄÄady sekwencyjne - pojÄ™cie automatu
UkÄady sekwencyjne - pojÄ™cie automatu
Uk ady sekwencyjne - pojęcie automatu
Automat
v2
v1
v3
v " Vy " Y
S2/Y1
S1/Y2
v2
v1 v3 v1v2
v3
Y3 Y1 Y2
v1
v3
v1
S3/Y3
v2
jest definiowany przez określenie:
a) zbioru liter wejściowych V (X) i wyjściowych Y,
b) zbioru stanów wewnętrznych S,
I
T
P
c) funkcji przejść (ozn. ´),
W
ZPT
d) funkcji wyjść (ozn. ).
1
Funkcja przej%0
i wyj%0

unkcja przej%0
i wyj%0

unkcja przej%0
i wyj%0

unkcja przej%0
i wyj%0

Funkcja przejść: ´: S × X S
Funkcja wyjść:
: S × X Y (tzw. automat Mealy ego)
: S Y (tzw. automat Moore a)
I
Automat może być zupełny lub niezupełny
T
P
W
ZPT
2
Specyfikacja automatu
Tablica przejść-wyjść automatu:
Moore a
Mealy ego
v1 v2 v3 y
v1 v2 v1 v2
S1 S2 S1 S3 y2
S1 S2 S1 y1 y2
S2 S3 S1 S2 y1
S2 S3 S2 y3 y1
S3 S1 S3 S2 y3
S3 S2 S1 y2 y3
... i graf
Mealy ego:
Moore a:
wejście/wyjście
wejście
I
T stan/
stan
P
wyjści
W
e
ZPT
3
Specyfikacja automatu
Tablica przejść-wyjść automatu:
Moore a
Mealy ego
v1 v2 v3 y
v1 v2 v1 v2
S1 S2 S1 S3 y2
S1 S2 S1 y1 y2
S2 S3 S1 S2 y1
S2 S3 S2 y3 y1
S3 S1 S3 S2 y3
S3 S2 S1 y2 y3
v2
... i graf
v /y2
Moore a
2
S1
/y2
v1 v3
S
v /y1
1
1
Mealy ego
v2
v /y1
v3 v1 v1 S2 y1
2
S
v /y3 v /y2
I
2
2
1
T
S3 y3 v3
P
W
v /y3
1
S
v2
3
ZPT
4
Układ sekwencyjny
x1 x2 00 01 11
Q1Q2 v1 v2 v3 Y
Jak
01
S1 S1 S4 y2
000
zrealizować
S2 S5 S3 S1 y1 00
001
automat
S3 S4 S5 y3
10
010
S4 S1 S2 S3 y2
011 01
S5 S4 S2 y4
100
11
x1 y1 Zakodowane
Zakodowane
UK
litery wejÅ›
ściowe
Å›
Å›
ściowe
Å›
Å›
xn ym litery wyjÅ›
US
Zakodowane
Q1
q1
stany
BP
Qk
automatu qk
I
T
wejście synchronizuj ce
P
W
CLK
ZPT
W układach synchronicznych W układach asynchronicznych
5
Klasyfikacja układów sekwencyjnych
x1 y1
UK
xn ym
Q1
q1
BP
Qk
qk
CLK
wejście synchronizuj ce
Uk
 ady sekwencyjne:
 
Synchroniczne (BP zbudowany z przerzutników synchronicznych)
I
T
P
Asynchroniczne (BP realizuj opó nienia lub przerzutniki
W
asynchroniczne)
Brak sygnału zegarowego
ZPT
6
Synchroniczne układy sekwencyjne
x1
y1
xn
ym
UK
Q1 q1
Przerzutniki
Qk qk
BP
CLK
Q
I1
FF
I2
Q
Przerzutnik  to automat typu Moore a
o dwóch stanach wewnętrznych,
CLK
I
jednym lub dwóch wejściach informacyjnych,
T
P
dwóch wyjściach (prostym i zanegowanym)
W
ZPT oraz wejściu synchronizującym (zegarowym).
7
Przerzutniki
W zależności od rodzaju wejść informacyjnych
wyróżniamy przerzutniki typu: D, T, SR oraz JK.
Q
Q
S
J
Q
Q
FF
FF
D
T
R
K
FF
FF
Q
Q
Q
Q
CLK
CLK
CLK
CLK
Przerzutnik jest określony:
tablicą przejść,
równaniem charakterystycznym,
tablicą wzbudzeń.
I
T
P
W
ZPT
8
Przerzutniki  tablice przejść
T
D
0 1
0 1
Q
Q
0 0 1
0 0 1
1 1 0
1 0 1
Q'= TQ+TQ
Q = D
SR JK
00 01 11 10 00 01 11 10
Q Q
00 0  1 00 0 1 1
11 0  1 11 0 0 1
I
T
Równanie charakterystyczne: Q = f(I1,I2,Q)
P
W
ZPT
9
Przerzutniki  tablice wzbudzeń
Q Q D T S R J K
00 0 0 0  0 
011 11 0 1 
100 1 0 1  1
11 1 0 0  0
D  delay T  trigger
S  Set (wejście wł czaj ce)
R  Reset (wejście wył czaj ce)
I
T J  wejście wł czaj ce
P
W
K  wejście wył czaj ce
ZPT
10
Przebiegi czasowe  przerzutnik typu D
Q
D
FF
Q
CLK
CLK
D
D
Q
0 1
Q
0 0 1
1 0 1
I
T
P
W
ZPT
11
Przebiegi czasowe  przerzutnik typu T
Q
T
FF
Q
CLK
CLK
T
T
0 1
Q
Q
0 0 1
1 1 0
I
T
P
W
ZPT
12
Przebiegi czasowe - porównanie
CLK
D (T)
Q (D)
Q (T)
I
T
P
W
ZPT
13
Synteza układów sekwencyjnych
Etapy syntezy:
synteza abstrakcyjna (utworzenie tablicy przejść-wyjść)
redukcja (minimalizacja) liczby stanów
kodowanie stanów, liter wejściowych i wyjściowych
synteza kombinacyjna (obliczanie funkcji wzbudzeń
przerzutników i funkcji wyjściowych)
v2
v1
v3
S2 /
S1/Y2
x
Y
Y
x
v2
1
v3
v1 v2 v1 v2
v1
v3
v1
S1 S2 S1 y1 y2 Q1 Q0
Q1
T1 T0
S3/Y3
S2 S3 S2 y3 y1 Q0
Q1
Q1
v2
S3 S2 S1 y2 y3
I
T
P
W
CLK
ZPT
14
Synteza kombinacyjna&
Q Q
Prze
X
rzu
Y
UK we UK wy
tniki
CLK
Obliczanie funkcji wyjÅ›
ściowych
Å›
Å›
Obliczanie funkcji steruj ściami
cych wejÅ›
Å›
Å›
przerzutników (funkcje wzbudzeń
Å„)
Å„
Å„
I
Y = f(Q) (Moore)
T
P
Q = f(X,Q)
W
Y = f(X,Q) (Mealy)
ZPT
15
Przykład syntezy (detektor sekwencji)
Do zakodowania trzech symboli stanów potrzebne s dwie



zmienne binarne
czyli wystarcz dwa przerzutniki, oznaczamy je Q1, Q0



X
X
0 1 0 1
0 1 0 1
Q1Q0
S
A
A 00 01 00 0 0
B A 0 0
B B 0111 00 0 0
C A 0 0
C
C 11 11 00 0 1
C A 0 1
( ) 10     
Y
Samo przyporz dkowanie symbolom stanów słów
binarnych jest zazwyczaj dowolne, gdyż staramy się
I
T
spełnić wył cznie warunek jednoznaczności
P
W
kodowania, ale&
ZPT
16
Obliczanie funkcji wzbudzeń i wyjściowych
X
QQ D
0 1 0 1
S Q1Q0
00 0
A 00 01 00 0 0
011
B 0111 00 0 0
100
C 11 11 00 0 1
11 1
( ) 10     
X X Y
0 1 0 1
Q1Q0 Q1Q0
Y = xQ1
00 0 0 00 1 0
Tworzymy tabelki
dla funkcji wzbudze
011 0011 0
poszczeg%7Å„lnych
11 1 0 11 1 0
przerzutnik%7Å„w
I
10  10 
T
P
D1=Q1 D0=Q0
W
Q0' = D0 = x
Q1' = D1= xQ0
ZPT
17
Schemat logiczny detektora sekwencji
x
Y
Q1
Q1 Q0
D1
D1 D0
Q1
Q1 Q0
CLK
CLK
CLK
CLK
I
Schemat logiczny rysujemy na podstawie obliczonych funkcji wzbudze :
T
P
W
D1= xQ0
D0 = x Y = xQ1
ZPT
18
Przykład... Realizacja T
X
X
0 1
0 1
QQ T
Q1Q0
Q1Q0
00 1 0 00 0
00 0 0
01 1 0
01 1
011 0
11 1 0
11 1 0
10 1
10 
10  
11 0
Q0
Q1
X
X
0 1
0 1
Q1Q0
Q1Q0
00 0 0
00 1
0
0
01 1
0
01
1
11 0 1
11 0
1
10 
10 
I
T1
T0
T
P
W
T1= Q1Q0x + xQ1 T0 = xQ0+ xQ0
Y  jak poprzednio
ZPT
19
Schemat logiczny detektora (T)
x
Y
x
Q1
Q1 Q0
T1 T0
Q0
Q1
Q1
CLK
I
T
P
Y  jak poprzednio
T1= Q1Q0x + xQ1
T0 = xQ0+ xQ0
W
ZPT
20
Przykład... Realizacja JK
X X
QQ J K
0 1 0 1
Q1Q0 Q1Q0
00 0 
00 0 0 00 1 0
01 1 
011 0 01 1 0
10  1
11 1 0 11 1 0
11  0
10 
10  
Q1
Q0
Q1Q0 0 1 Q1Q0 0 1 Q1Q0 0 1 Q1Q0 0 1
0
1
00 00 00 00
0 0    
   
01 0 01 01 01 0 1
1
 
11 11 0 1 11   11 0 1
10   10   10   10 
I
J1 K1 J0 K0
T
P
J1= xQ0 K1= x J0 = x K0 = x
W
ZPT
21
Schemat logiczny detektora (JK)
J J
Q Q
0
1
Q Q
K
K
CLK
Y
x
J1= xQ0 J0 = x K0 = x
K1= x
I
T
P
Y  jak poprzednio
W
ZPT
22
Zadanie: licznik mod. 5 ze sterowaniem
x1 a  up  liczenie do przodu
Licznik
y
x2
b  down  liczenie do ty u
(up, down, clear)
clk
c  clear  zerowanie
b  down  liczenie do ty u
a  up liczenie do zerowanie
c  clear  przodu
X X
a b c Y 00 01 11 10
S Q2Q1Q0
S0 S1 S4 S0 0 000 001 100 000 000
S1 S2 S0 S0 0 001 010 000 000 000
S2 S3 S1 S0 0 010 011 001 000 000
I
T
P
S3 S4 S2 S0 0 011 100 010 000 000
W
S4 S0 S3 S0 1 100 000 011 000 000
ZPT
23
Licznik ze sterowaniem&
x1x2
X
00 01 11 10
Q2Q1Q0 00 01 11 10
Q2Q1Q0
000 001 100 000 000
000 001 100 000 000
010 000 000 000
001
001 010 000 000 000
100 010 000 000
011
010 011 001 000 000
011 001 000 000
010
011 100 010 000 000
110
--- --- --- ---
100 000 011 000 000
111 --- --- --- ---
--- --- --- ---
101
000 011 000 000
100
Q2 Q1 Q0
I
T
Q2 Q1 Q0
P
W
ZPT
24
x1x2
00 01 11 10
Przerzutniki D
Q2Q1Q0
000 001 100 000 000
001 010 000 000 000
011 100 010 000 000
Dla przerzutników
010 011 001 000 000
typu D: Q = D
110 --- --- --- ---
111 --- --- --- ---
101 --- --- --- ---
100 000 011 000 000
Q2 Q1 Q0
x1x2 00 01 11 10 x1x2 00 01 11 10 x1x2 00 01 11 10
Q2Q1Q0 Q2Q1Q0 Q2Q1Q0
000 0 1 0 0 000 0 0 0 0 000 1 0 0 0
001 0 0 0 0 001 1 0 0 0 001 0 0 0 0
011 1 0 0 0 011 0 1 0 0 011 0 0 0 0
010 0 0 0 0 010 1 0 0 0 010 1 1 0 0
110     110     110    
I
111     111     111    
T
101     101     101    
P
W
100 0 0 0 0 100 0 1 0 0 100 0 1 0 0
ZPT
= D0
Q2 Q1 Q0
= D2 = D1
25
Licznik ze sterowaniem - przerzutniki D
x1x2 00 01 11 10 x1x2 00 01 11 10 x1x2 00 01 11 10
Q2Q1Q0 Q2Q1Q0 Q2Q1Q0
000 0 1 0 0 000 0 0 0 0 000 1 0 0 0
001 0 0 0 0 001 1 0 0 0 001 0 0 0 0
011 1 0 0 0 011 0 1 0 0 011 0 0 0 0
010 0 0 0 0 010 1 0 0 0 010 1 1 0 0
110     110     110    
111     111     111    
101     101     101    
100 0 0 0 0 100 0 1 0 0 100 0 1 0 0
D2 D1 D0
D2 = Q1Q0x1x2
D1 = Q1Q0x x +Q1Q0x x Q1Q0x
D0 =
I
1 2 1 2 1
T
P
+Q2Q1Q0x x
+Q1Q0x x +Q2x x
+Q2Q0x x
W 1 2
1 2 1 2
1 2
+Q2x x
ZPT
1 2
26
Licznik ze sterowaniem - przerzutniki JK
I
T
P
W
ZPT
27
QQ J K
Licznik ze sterowaniem - JK
00 0 
011 
10 1
11  0
x1x2
x1x2 x1x2
00 01 11 10
00 01 11 10 00 01 11 10
Q2Q1Q0
Q2Q1Q0 Q2Q1Q0
000 0 1 0 0
000 0 1 0 0 000    
001 0 0 0 0
001 0 0 0 0 001    
011 1 0 0 0
011 1 0 0 0 011    
010 0 0 0 0
010 0 0 0 0 010    
110    
110     110    
111    
111     111    
101    
101     101    
100 0 0 0 0
100     100 1 1 1 1
I
T
J2 K2
P
Q2
W
Q1Q0x x
J2 = K2 = 1
+Q1Q0x x
ZPT
1 2
1 2
28
QQ J K
Licznik ze sterowaniem - JK
00 0 
011 
10 1
11  0
x1x2
x1x2 0 x1x2
00 01 11 10
01 11 10 00 01 11 10
0
Q2Q1Q0
Q2Q1Q0 Q2Q1Q0
000 0 0 0 0
000 0 0 0 0 000    
001 1 0 0 0
001 1 0 0 0 001    
011 0 1 0 0
011     011 1 0 1 1
010 1 0 0 0
010     010 0 1 1 1
110    
110     110    
111    
111     111    
101    
101     101    
I
100 0 1 0 0
100 0 1 0 0 100    
T
P
J1 K1
W
Q1
J1 = Q0x x x1 +Q0x +Q0x
K1 =
+Q2x x
1 2
ZPT
1 2
2
2
29
QQ J K
Licznik ze sterowaniem - JK
00 0 
011 
10 1
11  0
x1x2
x1x2 x1x2
00 01 11 10
00 01 11 10 00 01 11 10
Q2Q1Q0
Q2Q1Q0 Q2Q1Q0
000 1 0 0 0
000 1 0 0 0 000    
001 0 0 0 0
001     001 1 1 1 1
011 0 0 0 0
011     011 1 1 1 1
010 1 1 0 0
010 1 1 0 0 010    
110    
110     110    
111    
111     111    
101    
101     101    
I
100 0 1 0 0
T 100 0 1 0 0 100    
P
J0 K0
W
Q0
+Q1x
Q2x x
J0 = K0 = 1
ZPT
1+Q2x1x2
1 2
30
Nie martwmy siÄ™ ...
Synteza kombinacyjna układów
sekwencyjnych może być
(i zazwyczaj jest) procesem żmudnym,
trzeba przetwarzać ogromne
tablice wypełnione
zerami i jedynkami.
Ale nie martwmy siÄ™
Ä™!
Ä™
Ä™
Proces ten  w systemach
komputerowego projektowania 
I
T
jest całkowicie
P
W
zautomatyzowany.
ZPT
31
Nie martwmy siÄ™ ...
jedyn czynnoÅ› u
ści ytkownika jest ...
Å›
Å›
AHDL lub VHDL
& dalej automatycznie
& a do zaprogramowania



I
T
FPGA
FPGA
FPGA
FPGA
P
W
ZPT
32
Specyfikacja automatu
Nie wnikaj c w szczegóły takiego zapisu (będ one
omawiane na innych wykładach) trzeba podkreślić, że
jest to wierne odwzorowanie tablicy przejść wyjść
automatu.
AHDL
VHDL
I
T
P
W
ZPT
33
Na przykład licznik ze sterowaniem...
TABLE
% current current next next %
% state input state output %
s, v[] => s, y;
X
00 01 10 Y
s0, B"00 => s1, 0;
S
s0, B"01 => s4, 0;
s0, B"1X => s0, 0;
S0 S1 S4 S0 0
s1, B"00 => s2, 0;
S1 S2 S0 S0 0 s1, B"01 => s0, 0;
s1, B"1X => s0, 0;
S2 S3 S1 S0 0
s2, B"00 => s3, 0;
s2, B"01 => s1, 0;
S3 S4 S2 S0 0
s2, B"1X => s0, 0;
s3, B"00 => s4, 0;
S4 S0 S3 S0 1
s3, B"01 => s2, 0;
s3, B"1X => s0, 0;
s4, B"00 => s0, 1;
s4, B"01 => s3, 1;
s4, B"1X => s0, 1;
END TABLE;
I
T
zapisany w jÄ™ po wprowadzeniu...
ęzyku AHDL,
Ä™
Ä™
P
W
ZPT
34
& specyfikacji do edytora tekstowego
TABLE
% current current next next %
% state input state output %
s, v[] => s, y;
s0, B"00 => s1, 0;
s0, B"01 => s4, 0;
s0, B"1X => s0, 0;
s1, B"00 => s2, 0;
s1,B"01 => s0, 0;
s1,B"1X => s0, 0;
s2, B"00 => s3, 0;
s2, B"01 => s1, 0;
s2, B"1X => s0, 0;
s3, B"00 => s4, 0;
s3, B"01 => s2, 0;
s3, B"1X => s0, 0;
s4, B"00 => s0, 1;
s4, B"01 => s3, 1;
s4, B"1X => s0, 1;
END TABLE;
I
T
P
W
ZPT
35
i uruchomieniu kompilatora&
...zostanie automatycznie zrealizowany bez udzia
 u projektanta.
 
q0 _EQ001 = !q0 & q1 & !X1 & X2
# q2 & !X1 & X2
# !q0 & !q2 & !X1 & !X2;
q1 _EQ002 = q2 & !X1 & X2
I
# q0 & q1 & !X1 & X2
T
# !q0 & q1 & !q2 & !X1 & !X2
EPM7032
P
# q0 & !q1 & !q2 & !X1 & !X2;
W
q2 _EQ003 = !q0 & !q1 & !q2 & !X1 & X2
# q0 & q1 & !q2 & !X1 & !X2;
ZPT
36
Wniosek
Skoro kompilator oblicza funkcje wzbudzeń
Å„
Å„
Å„
automatycznie, to umieję ść
ętność ta nie jest w
ę ść
ę ść
dzisiejszych czasach spraw najważ .
żniejsz
ż
ż
Lepiej skoncentrować się na tych metodach
ć ę
ć ę
ć ę
i procedurach syntezy logicznej, które nie s



jeszcze wbudowane do systemów komercyjnych.
I
T
P
W
ZPT
37