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ście
W
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
Zakodowane litery wejściowe
Zakodowane litery wyjściowe
x1 y1
UK układ kombinacyjny
xn ym
US
Q1
q1
BP blok pamięci
Qk
qk
Zakodowane stany automatu
CLK
wejście synchronizujące
Układy sekwencyjne:
Synchroniczne (BP zbudowany z przerzutników synchronicznych)
I
T
P
Asynchroniczne (BP realizują opóz
nienia lub przerzutniki
W
asynchroniczne)
ZPT
5
Synchroniczne układy sekwencyjne
x1
y1
xn
ym
UK
Q1 q1
Przerzutniki
Qk qk
BP
CLK
I
T
P
W
ZPT
6
Przerzutniki
Przerzutnik
Q
I1
FF
I2
Q
 to automat typu Moore a
CLK
o dwóch stanach wewnętrznych,
jednym lub dwóch wejściach informacyjnych,
dwóch wyjściach (prostym i zanegowanym)
oraz wejściu synchronizującym (zegarowym).
W zależności od rodzaju wejść informacyjnych
wyróżniamy przerzutniki typu: D, T, SR oraz JK.
Q
Q
S
J
Q
Q
I FF
FF
D
T
R
K
FF
FF
T
Q
Q
P
Q
Q
W
CLK
CLK
ZPT
CLK
CLK
7
Przerzutniki
Q
I1
FF
I2
Q
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
0 0 0  1 0 0 0 1 1
1 1 0  1 1 1 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 
01 1 1 1 0 1 
10 0 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
Q1
Q1 Q0
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ących wejściami
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)
WystarczÄ… dwa przerzutniki
X
X
0 1 0 1
0 1 0 1
S
S Q1Q0
A
B A 0 0
A 00 01 00 0 0
B
C A 0 0
B 01 11 00 0 0
C
C A 0 1 C 11 11 00 0 1
( ) 10      
Y
Na razie staramy się spełnić wyłącznie warunek
jednoznaczności kodowania
I
T
P
W
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
01 1
B 01 11 00 0 0
10 0
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
01 1 0 01 1 0
11 1 0 11 1 0
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
I
T
D1= xQ0
D0 = x Y = xQ1
P
W
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
01 1 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
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
21
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
22
Nie martwmy siÄ™ ...
jedyną czynnością użytkownika jest ...
AHDL lub VHDL
& dalej automatycznie
& aż do zaprogramowania
I
T
FPGA
FPGA
FPGA
FPGA
P
W
ZPT
23
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
24
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
po wprowadzeniu...
zapisany w języku AHDL,
P
W
ZPT
25
& 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
26
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
27
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
28