Bài giảng Kỹ thuật số - Chương 4: Hệ tuần tự

ng đương:
Hai trạng thái tương đương là 2 trạng thái mà khi cùng
giá trị vào mà chúng có các giá trị ra giống nhau và các trạng
thái kế tiếp mà chúng chuyển tới tương đương nhau.
D
D
X = 1
C
C
X = 0
NSPS OUTPUT
X = 0 X = 1
A 0 1
B 0 1
NguyenTrongLuat 57
Ví dụ: Rút gọn bảng trạng thái sau
Ta cĩ: S3 ≡ S5 và S4 ≡ S6
⇒ S1 ≡ S2
TTHT TTKT Ngõ ra (Z)
X = 0 X = 1 X = 0 X = 1
S0
S1
S2
S3
S4
S5
S6
S1
S3
S5
S0
S0
S0
S0
S2
S4
S6
S0
S0
S0
S0
0
0
0
0
1
0
1
0
0
0
0
0
0
0
S3 S4
S1
TTHT TTKT Ngõ ra (Z)
X = 0 X = 1 X = 0 X = 1
S0
S1
S3
S4
S1
S3
S0
S0
S1
S4
S0
S0
0
0
0
1
0
0
0
0
Bảng rút gọn:
NguyenTrongLuat 58
* PP rút gọn bằng bảng kéo theo (Implication Table)
- Thành lập bảng kéo theo của
bảng có n trạng thái: có n-1 cột và
n-1 hàng. Mỗi ô vuông là cặp trạng
thái cần xét tương đương.
S0 S1 S2 S3 S4
S1
S2
S3
S4
S5
- Từ bảng trạng thái tìm các trạng
thái có ngõ ra giống nhau lập thành
nhóm có thể tương đương.
- Tại mỗi ô vuông của 2 trạng thái
không cùng nhóm thì sẽ không
tương đương⇒ gạch chéo ô vuông. 
- Tại mỗi ô vuông của 2 trạng thái cùng nhóm thì ta ghi điều kiện
trạng thái kế tiếp cần xét tương đương.
- Kiểm tra các điều kiện trong các ô vuông: gạch chéo các ô
không thỏa điều kiện. Các ô còn lại không bị gạch chéo là kết quả
tương đương.
S0-S4
S2-S3
NguyenTrongLuat 59
S0⇔S3 khi
S0⇔S4
S2⇔S3
PS NS Z
X=0 X=1
A D C 0
B F H 0
C E D 1
D A E 0
E C A 1
F F B 1
G B H 0
H C G 1
A B C D E F G
B
C
D
E
F
G
H
(A, B, D, G)
(C, E, F, H)
D - F
C - H
C - E
B - D
C - H
A - F
E - H
B - F
A - D
E - F
B - D
C - E
D - G
A - B
E - H
C - F
A - B
A - G
C - F
B - G
A
C A
* PP rút gọn bằng bảng kéo theo (Implication Table)
Theo ngõ ra: ta có 2 nhóm
Ta được: (A, D)
(C, E)
NguyenTrongLuat 60
3. Gán trạng thái:
4. Chọn FF và thiết kế phần tổ hợp:
Ngõ vào Trạng thái hiện tại Ngõ ra Trạng thái kế tiếp
- Chọn FF (D-FF, T-FF, JK-FF) và mạch tổ hợp (cổng logic, 
ROM, PLA, ..).
Mỗi trạng thái được gán bằng 1 tổ hợp các biến trạng thái
Ví dụ: Hệ có 3 trạng thái A, B, C
Ta cần 2 biến trạng thái Q1 và Q0 để gán cho 3 trạng thái
Tthái A: Q1Q0 = 00
B: Q1Q0 = 01
C: Q1Q0 = 11 CB
-A
Q1
Q0 0 1
0
1
- Lập bảng trạng thái
NguyenTrongLuat 61
TTHT TTKT Ngõ ra (Z)
X = 0 X = 1 X = 0 X = 1
S0
S1
S3
S4
S1
S3
S0
S4
S1
S4
S0
S0
0
0
0
1
0
0
0
0
Ví dụ: Thực hiện hệ tuần tự sau
S3S4
S1S0
Q1
Q0 0 1
0
1
Gán trạng thái
TTHT
(Q1Q0)
TTKT (Q+1Q+0) Ngõ ra (Z)
X = 0 X = 1 X = 0 X = 1
S0 : 00
S1 : 10
S3 : 11
S4 : 01
10
11
00
01
10
01
00
00
0
0
0
1
0
0
0
0
NguyenTrongLuat 62
* Lập bảng trạng thái
TTKT
Q+1 Q+0
Ngõ ra
Z
TTHT
Q1 Q0
Ng.vào
X
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
TTHT
(Q1Q0)
TTKT (Q+1Q+0) Ngõ ra (Z)
X = 0 X = 1 X = 0 X = 1
S0 : 00
S1 : 10
S3 : 11
S4 : 01
10
11
00
01
10
01
00
00
0
0
0
1
0
0
0
0
0 1 0
1 0 1
0 1 1
0 0 0
0 1 0
0 0 0
0 0 1
0 0 0
JK.FF
J1 K1 J0 K0
T.FF
T1 T0
* Chọn FF:
1
0
0
1
1
0
1
1
0
0
1
1
0
1
1
1
1 X
0 X
X 0 
X 1
1 X
0 X
X 1 
X 1
0 X
X 0
1 X 
X 1
0 X
X 1
1 X 
X 1
NguyenTrongLuat 63
* Thực hiện bằng ROM và T.FF kích cạnh lên:
CK
X A2
A1
A0
D2
D1
D0
Z
T1 Q1
T0 Q0
23 x 3 (bit)
Z T1 T0
D2 D1 D0
X Q1 Q0
A2 A1 A0
0 0 0
0 0 1
0 1 0
0 1 1
1 0 0
1 0 1
1 1 0
1 1 1
0 1 0
1 0 0
0 0 1
0 1 1
0 1 0
0 0 1
0 1 1
0 1 1
Bảng nạp ROM
NguyenTrongLuat 64
* Thực hiện bằng cổng logic và JK.FF kích cạnh xuống:
Từ bảng trạng thái, rút gọn:
Z = X Q1 Q0 
J1 = Q0 
J0 = Q1 
K0 = X + Q1 
K1 = X + Q0 
J1
K1
Q1
Q1
J0
K0
Q0
Q0
X
Z
CKNguyenTrongLuat 65
* Thực hiện bằng PLA và JK.FF kích cạnh lên:
Z J1 K1 J0 K0 X Q1 Q0
0 0 1
Bảng nạp PLA
CK
X
Q1
Q0
Z
J1
J0
Z
J1 Q1
K1
K0
K1
J0 Q0
K0
X
Z = X Q1 Q0 J1 = Q0 J0 = Q1 K0 = X + Q1 K1 = X + Q0 
1 0 0 0 0
- - 0
1 - -
- - 1 0 0 1 0 0
- 1 -
NguyenTrongLuat 66
0 1 0 0 0
0 0 1 0 1
0 0 0 1 1
1: is connected to output
0: no connection to output
1: asserted in term
0: negated in term
-: does not participate in term
OutputInput
Ví dụ: Cho hệ tuần tự cĩ 1 ngõ vào X và 2 ngõ ra Z1, Z0. Hệ cĩ
4 trạng thái A, B, C và D cĩ giản đồ trạng thái như hình vẽ. Với
phép gán trạng thái (mã hĩa trạng thái) A: Q1Q0=10, B: 
Q1Q0=00, C: Q1Q0=01 và D: Q1Q0=11. Biết rằng khi xung clock 
vào cĩ cạnh xuống hệ sẽ chuyển trạng thái. Hãy thiết kế hệ theo
2 cách:
Cách 1: JK_FF và cổng logic
Cách 2: D_FF và PLA. 
Lập bảng trạng thái
Dùng bìa K rút gọn
Vd: Thiết kế bộ (chuyển) đổi mã từ BCD sang BCD quá 3. 
Ngõ vào và ra là nối tiếp với LSB đi trước.
X: INPUT (BCD) Z: OUTPUT (BCD+3)
0 0 0 0 0 0 1 1
0 0 0 1 0 1 0 0
0 0 1 0 0 1 0 1
0 0 1 1 0 1 1 0
0 1 0 0 0 1 1 1
0 1 0 1 1 0 0 0
0 1 1 0 1 0 0 1
0 1 1 1 1 0 1 0
1 0 0 0 1 0 1 1
1 0 0 1 1 1 0 0
t0 t0t1 t1t2 t2t3 t3
NguyenTrongLuat 70
Thời
điểm
Chuỗi vào nhận được
(LSB được nhận đầu tiên)
T/ thái
hiện tại
T/thái kế Giá trị ra (Z)
X = 0 1 X = 0 1
t0 Reset A B 1C 0
B0
C1
t1
D 1
E 0
F 0
G 1
D0 0
E0 1
F1 0
G1 1
t2
H
H0 0 0
0
I
I0 0 1
1
J
J0 1 0
1
K
K0 1 1
1
L
L1 0 0
1
M
M1 0 1
0
N
N1 1 0
0
P
P1 1 1
0
t3
A 0
A 0
A 0
A 0
A 0
A 1
A 1
A 1
A 1
A 1
- -
- -
- -
- -
- -
- -
M
M
H
H
H
H
E
E
NguyenTrongLuat 71
* Bảng trạng thái được rút gọn của bộ chuyển đổi mã
Thời gian Trạng thái
hiện tại
Trạng thái kế
X=0 1
Giá trị ra (Z)
X=0 1
t0 A B C 1 0
t1 B
C
D E
E E
1 0
0 1
t2 D
E
H H
H M
0 1
1 0
t3 H
M
A A
A -
0 1
1 -
NguyenTrongLuat 72
- Hệ tuần tự còn được gọi là máy trạng thái thuật toán
(ASM - algorithmic state machine) hay đơn giản hơn là máy
trạng thái (SM - state machine), gọi tắt là SM.
IIX. LƯU ĐỒ MÁY TRẠNG THÁI:
- Lưu đồ SM được tạo bởi các khối SM; mỗi khối SM 
mô tả hoạt động của hệ trong 1 trạng thái. 
- Một khối SM bao gồm một Hộp trạng thái (state box),
các Hộp quyết định (decision box) và các Hộp xuất theo điều
kiện (conditional ouput box).
Hộp trạng thái
ĐIỀU KIỆN 10
Hộp quyết định Hộp xuất theo đkiện
NguyenTrongLuat 78
ĐIỀU KIỆN
10
STên trạng thái xxx Mã trạng thái
Liệt kê biến ra có giá trị 1 
(biến Moore)
Liệt kê biến ra có
giá trị 1 theo điều
kiện (biến Mealy)
Đường vào của khối SM
Các đường ra đến các khối SM khác
Một khối SM có chính xác một đường vào và một hoặc nhiều đường ra.
NguyenTrongLuat 79
Z1, Z2
S1
X1
X3Z3, Z4
X2
Z5
10
10
10
1 2 3 n
- Một đường dẫn đi qua khối SM từ ngõ vào đến ngõ ra được gọi
là đường dẫn liên kết (link path).
NguyenTrongLuat 80
- Khối SM có thể được biểu diễn bằng nhiều dạng khác nhau.
- Một lưu đồ SM có thể biểu diễn một hệ tổ hợp khi chỉ có
một trạng thái và không có sự thay đổi trạng thái xảy ra.
Z1 = A + A’BC = A + BC
NguyenTrongLuat 82
- Ta phải tuân theo một số qui tắc khi xây dựng một khối SM. 
* Không cho phép có đường hồi tiếp nội trong một khối SM. 
* Với mọi kết hợp các biến vào hợp lệ phải có chính xác
một đường ra được định nghĩa. Điều này là cần thiết vì mỗi tổ hợp
vào được cho phép phải dẫn đến một trạng thái kế duy nhất. 
NguyenTrongLuat 83
S0
Za
S1
Zb
S2
Zc
1/0
0/0
0/0
1/0
0/Z1
1/Z2
S0
S1
S2
Za
X
0 1
Zb
X0
1
X
0 1
Zc
Z1 Z2
00 = AB
01
11
NguyenTrongLuat 84
S0
Za
X0 1
Zb
X0 1
X0 1
Zc
Z1 Z2
S1
S2
Giản đồ định thì
Clock
State
X
Za
Zb
Zc
Z1
Z2
S0 S1 S2 S2 S0 S0
NguyenTrongLuat 85
CÀI ĐẶT LƯU ĐỒ MÁY TRẠNG THÁI:
- Việc cài đặt (realization) lưu đồ SM là tìm được phương trình
của các biến ra và các biến trạng thái kế tiếp. 
- Các bước thực hiện như sau:
* Thực hiện gán trạng thái cho các hộp trạng thái.
* Xác định phương trình của biến ra Zi
- Tìm các trạng thái có xuất hiện biến ra (Zi = 1)
- Nếu là biến MOORE thì ta được tích số (AND) của
các biến trạng thái; còn nếu là biến MEALY thì ta có tích số
của các biến trạng thái và biến điều kiện vào.
- Phương trình của biến ra bằng tổng (OR) các tích số
đã tìm thấy ở các bước trên lại với nhau.
NguyenTrongLuat 86
S0
S1
S2
Za
X
0 1
Zb
X0
1
X
0 1
Zc
Z1 Z2
00 = AB
01
11
* Gán trạng thái: 
S0: AB = 00; S1: AB = 01 và S2: AB = 11
* Phương trình của các biến ra:
Za = A B
Zb = A B
Zc = A B
Z1 = A B X
Z2 = A B X
NguyenTrongLuat 87
* Xác định phương trình các biến trạng thái kế Q+j
- Tìm ra tất cả các trạng thái trong đó Qj=1
- Tại mỗi trạng thái này, tìm tất cả các đường dẫn liên kết
(link path) mà dẫn vào trạng thái đó.
- Với mỗi đường dẫn liên kết này, tìm ra một số hạng là 1 
khi đi theo đường dẫn liên kết này. Nghĩa là, với đường dẫn
liên kết từ Sa đến Sb, số hạng sẽ là 1 tích số của các biến
trạng thái ở trạng thái Sa và các biến điều kiện để có thể
dẫn đến Sb.
- Biểu thức Q+j được tạo thành bằng cách lấy tổng (OR) các
tích số được tìm thấy ở bước trên lại với nhau
NguyenTrongLuat 88
S0
S1
S2
Za
X
0 1
Zb
X0
1
X
0 1
Zc
Z1 Z2
00 = AB
01
11
A+ = A B X
(S1→ S2)
* Phương trình các biến trạng thái kế:
+ A B X
(S2→ S2)
B+ = A B X + A B X
(S0→ S1)(S1→ S2) (S2→ S2)
+ A B X
NguyenTrongLuat 89
Ví dụ: Cho hệ tuần tự có lưu đồ máy trạng thái (lưu đồ SM) 
như hình vẽ. Xác định phương trình (hàm) trạng thái kế của
các biến trạng thái Q+1, Q+0 và phương trình ngõ ra Z1, Z2.