1
I
T
P
W
ZPT
Układy sekwencyjne - pojęcie
automatu
Automat
a) zbioru liter wejściowych V (X)
b) zbioru stanów wewnętrznych S,
c) funkcji przejść (ozn. ),
d) funkcji wyjść (ozn. ).
i wyjściowych Y,
v V
y Y
jest definiowany przez określenie:
S
1
S
1
S
2
S
2
S
3
S
3
v
1
v
1
v
2
v
2
v
2
v
2
v
2
v
2
v
1
v
1
v
1
v
1
v
3
v
3
v
3
v
3
v
3
v
3
v
2
v
2
Y
2
Y
2
v
1
v
1
Y
1
Y
1
Y
3
Y
3
v
3
v
3
v
1
v
1
/Y
2
/Y
2
/
Y
1
/
Y
1
/Y
3
/Y
3
2
I
T
P
W
ZPT
Funkcja przejść i wyjść
Funkcja wyjść:
: S Y (tzw. automat
Moore’a)
Funkcja przejść: : S X S
: S X Y (tzw. automat Mealy’ego)
Automat może być zupełny lub niezupełny
3
I
T
P
W
ZPT
Specyfikacja automatu
Mealy’ego
Tablica przejść-wyjść automatu:
Moore’a
v
1
v
2
v
1
v
2
S
1
S
2
S
1
y
1
y
2
S
2
S
3
S
2
y
3
y
1
S
3
S
2
S
1
y
2
y
3
v
1
v
2
v
3
y
S
1
S
2
S
1
S
3
y
2
S
2
S
3
S
1
S
2
y
1
S
3
S
1
S
3
S
2
y
3
... i graf
Mealy’ego:
Moore’a:
stan/
wyjści
e
wejści
e
sta
n
wejście/wyjś
cie
4
I
T
P
W
ZPT
Specyfikacja automatu
Mealy’ego
Tablica przejść-wyjść automatu:
Moore’a
v
1
v
2
v
1
v
2
S
1
S
2
S
1
y
1
y
2
S
2
S
3
S
2
y
3
y
1
S
3
S
2
S
1
y
2
y
3
v
1
v
2
v
3
y
S
1
S
2
S
1
S
3
y
2
S
2
S
3
S
1
S
2
y
1
S
3
S
1
S
3
S
2
y
3
... i graf
Mealy’ego
Moore’a
v
v
v
v
v
v
v
v
v
1
1
1
2
2
3
3
2
3
y
y
1
3
2
S
S
S
3
1
/y
2
v / y
v / y
v / y
v / y
v / y
v / y
1
1
1
1
2
2
2
1
2
3
3
2
1
S
3
S
2
S
5
I
T
P
W
ZPT
x
1
x
n
y
1
y
m
Q
1
Q
k
q
1
q
k
Układ sekwencyjny
układ kombinacyjny
Układy sekwencyjne:
Synchroniczne
(BP zbudowany z przerzutników
synchronicznych)
wejście synchronizujące
Asynchroniczne
(BP realizują opóźnienia lub
przerzutniki asynchroniczne)
blok pamięci
UK
BP
CLK
US
Zakodowane litery wejściowe
Zakodowane litery wyjściowe
Zakodowane stany automatu
6
I
T
P
W
ZPT
x
1
x
n
y
1
y
m
Q
1
Q
k
q
1
q
k
Synchroniczne układy
sekwencyjne
UK
Przerzutniki
CLK
BP
7
I
T
P
W
ZPT
Przerzutniki
Przerzutnik
– to automat typu Moore’a
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.
FF
I
1
I
2
Q
Q
CLK
FF
D
Q
Q
CLK
FF
T
Q
Q
CLK
FF
S
R
Q
Q
CLK
FF
J
K
Q
Q
CLK
8
I
T
P
W
ZPT
Przerzutniki
Przerzutnik jest określony:
tablicą przejść,
równaniem charakterystycznym,
tablicą wzbudzeń.
FF
I
1
I
2
Q
Q
CLK
9
I
T
P
W
ZPT
Przerzutniki – tablice przejść
D
Q
0
1
0
0
1
1
0
1
Q’ = D
T
Q
0
1
0
0
1
1
1
0
Q
T
Q
T
Q'
SR
Q
0
0 01 11 10
0
0
0
–
1
1
1
0
–
1
JK
Q
0
0
01 11 10
0
0
0
1
1
1
1
0
0
1
Równanie charakterystyczne: Q’ = f(I
1
,I
2
,Q)
10
I
T
P
W
ZPT
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)
J – wejście włączające
K – wejście wyłączające
11
I
T
P
W
ZPT
Przebiegi czasowe – przerzutnik
typu D
D
Q
CLK
FF
D
Q
Q
CLK
D
Q
0 1
0 0 1
1 0 1
12
I
T
P
W
ZPT
Przebiegi czasowe – przerzutnik
typu T
T
Q
CLK
FF
T
Q
Q
CLK
T
Q
0
1
0
0
1
1
1
0
13
I
T
P
W
ZPT
Przebiegi czasowe - porównanie
D (T)
Q (D)
Q (T)
CLK
14
I
T
P
W
ZPT
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)
S
1
S
1
S
2
S
2
S
3
S
3
v
1
v
1
v
2
v
2
v
2
v
2
v
2
v
2
v
1
v
1
v
1
v
1
v
3
v
3
v
3
v
3
v
3
v
3
/Y
2
/Y
2
/
Y
1
/
Y
1
/Y
3
/Y
3
v
1
v
2
v
1
v
2
S
1
S
2
S
1
y
1
y
2
S
2
S
3
S
2
y
3
y
1
S
3
S
2
S
1
y
2
y
3
T1
Q1
Q1
Q1
Q1
T0
Q0
Q 0
CLK
x
x
Y
15
I
T
P
W
ZPT
Synteza kombinacyjna…
UK we
Prz
erz
u
tnik
i
UK wy
X
X
Y
Y
Obliczanie funkcji sterujących
wejściami przerzutników (funkcje
wzbudzeń)
Obliczanie funkcji wyjściowych
CLK
Q
Q
Q’
Q’
Q’ = f(X,Q)
Y = f(Q) (Moore)
Y = f(X,Q) (Mealy)
16
I
T
P
W
ZPT
Przykład syntezy (detektor
sekwencji)
X
S
0
1
0
1
A
B
A
0
0
B
C
A
0
0
C
C
A
0
1
X
S Q1Q0
0
1
0
1
A 00
01
00
0
0
B 01
11
00
0
0
C 11
11
00
0
1
(–) 10
– –
– –
–
–
Y
Wystarczą dwa
przerzutniki
Na razie staramy się spełnić wyłącznie
warunek jednoznaczności kodowania
17
I
T
P
W
ZPT
Obliczanie funkcji wzbudzeń i
wyjściowych
X
S Q1Q0
0
1
0
1
A 00
01
00
0
0
B 01
11
00
0
0
C 11
11
00
0
1
(–) 10
– –
– –
–
–
X
Q1Q0
0
1
X
Q1Q0
0
1
00
0
0
00
1
0
01
1
0
01
1
0
11
1
0
11
1
0
10
–
–
10
–
–
D1=Q1
’
D0=Q0’
Y
xQ1
Y
Q0
x
D1
Q1'
x
D0
Q0'
QQ’
D
00
0
01
1
10
0
11
1
18
I
T
P
W
ZPT
Schemat logiczny detektora
sekwencji
xQ1
Y
Q0
x
D1
x
D0
D 1
Q 1
Q 1
D 1
Q 1
Q 1
D 0
Q 0
Q 0
x
Y
19
I
T
P
W
ZPT
Przykład... Realizacja T
X
Q1Q0
0 1
00
0 0
01
1 0
11
1 0
10
–
–
X
Q1Q0
0 1
00
1 0
01
1 0
11
1 0
10
–
–
QQ’
T
00
0
01
1
10
1
11
0
X
Q1Q0
0 1
00
01
11
10
–
–
X
Q1Q0
0 1
00
01
11
10
–
–
Q1’
Q0’
T1
T0
xQ1
x
1Q0
Q
T1
xQ0
0
Q
x
T0
Y – jak poprzednio
0 0
0
0
1
1
0
0
0 1
1
1
20
I
T
P
W
ZPT
Schemat logiczny detektora (T)
xQ1
x
1Q0
Q
T1
xQ0
0
Q
x
T0
Y – jak poprzednio
T1
Q1
Q 1
Q1
Q 1
T0
Q0
Q 0
CLK
x
x
Y
21
I
T
P
W
ZPT
Schemat logiczny detektora (JK)
Q0
x
J1
x
J0
x
K1
x
K0
1
Q
J
K Q
0
K
J Q
Q
CLK
Y
Y – jak poprzednio
x
22
I
T
P
W
ZPT
Nie martwmy się ...
trzeba przetwarzać ogromne
tablice wypełnione
zerami i jedynkami.
Ale nie martwmy się!
Proces ten – w systemach
komputerowego projektowania
– jest całkowicie
zautomatyzowany.
Synteza kombinacyjna układów
sekwencyjnych może być
(i zazwyczaj jest) procesem żmudnym,
011
001
00
100
1 11
10
010
010
00
010
101
01
010
100
1 11
23
I
T
P
W
ZPT
Nie martwmy się ...
AHDL lub VHDL
…dalej automatycznie
…aż do zaprogramowania
jedyną czynnością użytkownika
jest ...
24
I
T
P
W
ZPT
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
AHDL
VHDL
25
I
T
P
W
ZPT
Na przykład licznik ze
sterowaniem...
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;
X
S
00
01
10
Y
S0
S1
S4
S0
0
S1
S2
S0
S0
0
S2
S3
S1
S0
0
S3
S4
S2
S0
0
S4
S0
S3
S0
1
zapisany w języku
AHDL,
po
wprowadzeniu...
26
I
T
P
W
ZPT
…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;
27
I
T
P
W
ZPT
i uruchomieniu kompilatora…
q0 _EQ001 = !q0 & q1 & !X1 & X2
# q2 & !X1 & X2
# !q0 & !q2 & !X1 & !X2;
q1 _EQ002 = q2 & !X1 & X2
# q0 & q1 & !X1 & X2
# !q0 & q1 & !q2 & !X1 & !X2
# q0 & !q1 & !q2 & !X1 & !X2;
q2 _EQ003 = !q0 & !q1 & !q2 & !X1 & X2
# q0 & q1 & !q2 & !X1 & !X2;
EPM7032
...zostanie automatycznie zrealizowany bez udziału
projektanta.
28
I
T
P
W
ZPT
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.