Chương 2
THIẾT KẾ MÁY TRẠNG THÁI
BẰNG LƯU ĐỒ MÁY TRẠNG THÁI
I. LƯU ĐỒ MÁY TRẠNG THÁI:
Người ta còn gọi hệ tuần tự 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 - sate machine), ở đây ta
gọi tắt là SM. Lưu đồ SM được tạo bởi các khối SM; mỗi khối SM mô tả hoạt
động trong 1 trạng thái.
22 trang |
Chia sẻ: hoang10 | Lượt xem: 641 | Lượt tải: 0
Bạn đang xem trước 20 trang tài liệu Cơ khí chế tạo máy - Chương 2: Thiết kế máy trạng thái bằng lưu đồ máy trạng thái, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
Chương 2
THIẾT KẾ MÁY TRẠNG THÁI
BẰNG LƯU ĐỒ MÁY TRẠNG THÁI
I. LƯU ĐỒ MÁY TRẠNG THÁI:
Người ta còn gọi hệ tuần tự 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 - sate machine), ở đây ta
gọi tắt là SM. Lưu đồ SM được tạo bởi các khối SM; mỗi khối SM mô tả hoạt
động trong 1 trạng thái.
- Trạng thái của hệ thống được biểu diễn bằng một Hộp trạng thái (state
box). Hộp trạng thái có thể chứa một Danh sách xuất (output list), Mã
trạng thái (state code), Tên trạng thái (state name), Hộp quyết định
(decision box), Điều kiện trong hộp quyết định là một biều thức Boole, Hộp
xuất theo điều kiện (conditional ouput box) chứa danh sách các biến xuất
theo điều kiện.
Điều kiện
Mã trạng thái Tên trạng thái
Hộp trạng thái Danh sách xuất
ở trạng thái này
Danh sách xuất
theo điều kiện
Hộp điều kiện
xxx X
Hộp xuất
theo điều kiện
Đường vào khối ASM
Các đường ra đến
các khối ASMkhác
T F
- Một khối SM chứa chính xác một hộp trạng thái cùng với các hộp quyết
định và các hộp xuất theo điều kiện liên hệ với trạng thái đó. Một khối
SM có chính xác một đường vào và một hoặc nhiều đường ra. 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).
Theo hình ta có: khi vào trạng thái S1, các giá trị ra Z1 và Z2 bằng 1.
Nếu các giá trị vào X1 và X2 đều bằng 0, Z3 và Z4 cũng bằng 1, và ở cuối thời
gian trạng thái, máy đi vào trạng thái kế qua đường ra 1. Ngược lại nếu X1=1
và X3=0, giá trị ra Z5=1 và đi vào trạng thái kế qua đường ra 3.
- Khối SM có thể được vẽ 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
- Ta phải tuân theo một số qui tắc nhất định khi xây dựng 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.
* Không cho phép có đường hồi tiếp nội trong một khối SM.
(a) Sai (b) Đúng
- Khối SM có 2 dạng: song song và nối tiếp
Ta có thể chuyển dễ dàng giản đồ trạng thái của máy tuần tự sang lưu
đồ SM tương đương.
Ta khảo sát giản đồ định thì cho lưu đồ SM ở hình trên với chuỗi vào
X=1, 1, 1, 0, 0, 0. Trong thí dụ này, tất cả các thay đổi trạng thái xảy ra ngay
sau cạnh lên của xung nhịp. Vì các biến ra Moore (Za, Zb, Zc) phụ thuộc vào
trạng thái, chúng chỉ có thể thay đổi sau một thay đổi trạng thái. Các biến ra
Mealy (Z1, Z2) có thể thay đổi ngay sau một thay đổi trạng thái hoặc một thay
đổi giá trị vào. Trong bất cứ trường hợp nào, tất cả các giá trị ra sẽ có giá trị
đúng của chúng ở cạnh tích cực của xung nhịp.
S0 00
Za
X
S1 01
Zb
X
S2 11
Zc
X
Z1 Z2
0 1
0 1
0 1
S0
Za
S1
Zb
S2
Zc
1/0
0/0
0/0
1/0
0/Z1
1/Z2
II. 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).
• Tại mỗi trạng thái, 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.
- 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.
• Đối với mỗi trạng thái này, tìm ra tất cả các đường dẫn liên kết
(link path) mà dẫn đến 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
Chú ý:
Các phương trình biến ra và biến trạng thái kết tiếp có thể được đơn giản hoá
bằng cách rút gọn bằng bìa Karnaugh với các trạng thái không sử dụng làm
điều kiện don’t care
Ví dụ: Thực hiện lưu đồ SM sau bằng cổng logic và kích cạnh lênD-FF
+ Gán trạng thái: AB = 00 cho S0, AB = 01 cho S1, và AB = 11 cho S2.
+ Phương trình của các biến ra:
Biến ra Moore: Za = A’B’ (chỉ có trong trạng thái S0)
Zb = A’B (chỉ có trong trạng thái S1)
Zc = A B (chỉ có trong trạng thái S2)
Biến ra Mealy: Z1 = A B X’ ø (tại trạng thái S2 và điều kiện X = 0)
Z2 = A B X (tại trạng thái S2 và điều kiện X = 1)
+ Phương trình các biến trạng thái kế:
Có 3 đường dẫn liên kết (link1, link2 và link3) trạng thái có B =1:
B+ = A’B’X (link 1) + A’BX (link 2) + ABX (link 3) = (A’ + B) X
Có 2 đường dẫn liên kết dẫn tới trạng thái có A=1:
A+ = A’BX + ABX = BX
S0 00 = AB
Za
X
S1 01
Zb
X
S2 11
Zc
X
Z1 Z2
0 1
0 1
0 1
Link 1
Link 2
Link 3
Các phương trình biến ra và trạng thái kế có thể được đơn giản hóa hơn
bằng bảng Karnaugh với trạng thái không sử dụng (AB=10) làm điều kiện
“don’t care”, khi đó:
Za = A’B’ + (AB’) = B’
Zb = A’B
Zc = AB + (AB’) = A
Z1 = ABX’ + (AB’X’) = AX’
Z2 = ABX + (AB’X) = AX
A+ = BX
B+ = A’B’X + A’BX + ABX + (AB’X) = X
DA QA
CK QA
X
Z1
Clock
DB QB
CK QB
Zb
Z2
Zc
Za
Ví dụ: Thực hiện hệ tuần tự có bảng trạng thái sau bằng lưu đồ SM; sử
dụng PLA và JK-FF kích cạnh lên
Hiện tại Kế tiếp Ngõ ra (Z1Z2)
Q1Q2 X1X2 = 00 01 10 11 X1X2 = 00 01 10 11
00 S0 S1 S1 S2 S0 11 11 11 01
01 S1 S1 S2 S1 S2 00 01 00 01
11 S2 S2 S2 S0 S0 10 10 11 11
Thành lập lưu đồ SM
Ta có:
Z1 = Q1 Q2 X1 + Q1 Q2 X1 X2 + Q1 Q2 X1
Z2 = Q1 Q2 + Q1 Q2 X2 + Q1 Q2
Q1+ = Q1 Q2 X1 + Q1 Q2 X2 + Q1 Q2 X1 X2 + Q1 Q2 X1 + Q1 Q2 X1
Q2+ = Q1 Q2 X1 X2 + Q1 Q2 X2 + Q1 Q2 X1
Rút gọn với trạng thái không gán làm don’t care
S0 00 = Q1Q2
Z2
X1 0 1
Z1 X2
Z1 S1 10
X2
Z2
S2 11
Z1 0 1
X1
Z2
0
1
0
1
Z1 = Q2 + Q1 X1 + Q1 X2 Z2 = Q1 + Q2 X1 + Q2 X2
J1 = X1 + X2 J2 = Q1 X2 + Q1 X1 X2
K1 = Q2 X1 K2 = X1
Q1 Q2 X1 X2 Z1 Z2 J1 K1 J2 K2
- 1 - - 1 0 0 0 0 0
0 - 0 - 1 0 0 0 0 0
0 - - 0 1 0 0 0 0 0
0 - - - 0 1 0 0 0 0
- 1 1 - 0 1 0 0 0 0
- 0 - 1 0 1 0 0 0 0
- - 0 - 0 0 1 0 0 0
- - - 0 0 0 1 0 0 0
- 1 1 - 0 0 0 1 0 0
1 - - 1 0 0 0 0 1 0
0 - 1 0 0 0 0 0 1 0
- - 1 - 0 0 0 0 0 1
X1X2
Z1
00 01
X
X
1 00
1 01
11 10
1
1
X
X
11
1 10
1
1
Q1Q2
X1X2
Z2
00 01
X
X
100
101
11 10
1
X
X
111
110
11
1
Q1Q2
X1X2
Q1+
00 01
X
X
1 00
1 01
11 10
1
1
1
1
X
X
11
1 10
1
1
Q1Q2
X1X2 00 01
X
X
00
01
11 10
1
1
1
X
X
11
110
1
Q1Q2
Q2+
J1 J1 Q1
J2 Q2 J2
Q1
Q2
CK
X2
PLA
K2 K2
K1 K1
X1
Z2
Z1
KTS2-C2-Tr.11
* ĐƠN GIẢN HOÁ HÀM BOOLE BẰNG CÁCH THÊM BIẾN VÀO BÌA KARNAUGH
Khi dùng bảng Karnaugh, nếu ta có số biến vào lớn hơn 4 biến thì sự rút
gọn trên bảng Karnaugh bắt đầu hơi phức tạp. Để giải quyết vấn đề trên,
người ta đưa các biến vào trong bảng Karnaugh.
Nếu biến Pi được đặt trong ô mj của bảng Karnaugh của hàm, có nghĩa
là F = 1 khi Pi = 1 và các biến được chọn để mj =1.
Cho trước một bảng với các biến P1, P2, được đưa vào một số ô, dạng
tối thiểu tổng các tích của F có thểm được tìm như sau:
F = MS0 + P1 MS1 + P2 MS2 +
+ MS0 là tổng tối thiểu (Minimum Sum) có được bằng cách đặt
P1 = P2 = = 0.
+ MS1 là tổng tối thiểu có được bằng cách đặt P1 =1, các Pj = 0 (j ≠ 1), và
thay thế tất cả các 1 trên bảng bằng các “don’t care” (X).
+ MS2 là tổng tối thiểu có được bằng cách đặt P2 =1, các Pj = 0 (j ≠ 2), và
thay thế tất cả các 1 trên bảng bằng các “don’t care” (X).
Biểu thức này sẽ là tối thiểu miễn là các giá trị của các biến được đưa
vào bảng có thể được gán một cách độc lập.
Ví dụ: Cho hàm sau:
G(A, B, C, D, E, F) = m0 + m2 + m3 + E m5 + E m7 + F m9 + m11 + m15
+ (m1 + m11 + m13)
Ta có kết quả: G = A’B’ + A C D + E A’D + F A D
KTS2-C2-Tr.12
Ví dụ: F(A, B, C, D) = A’B’C + A’BC + A’BC’D + ABCD + (AB’C)
F = A’C + D (C + A’B) = A’C + C D + A’B D
Ví dụ: F(A, B, C, D, E) = m(0, 4, 5, 7, 9) + d(6, 11) + E (m1 + m15)
F(A, B, C, D, E) = A’B + A’C’D’ + A B’D + A’C E + B C D E
Ví dụ: F(A, B, C, D, E) = A’B D’ + A’B’C’D’E + (A B)
Biến đưa vào bìa K có thể là hàm của nhiều biến.
Với P = C’E, ta có F (A, B, D, P) = m2 + P m0 + (m6 + m7)
F = B D’ + A’D’P = B D’ + A’C’D’E
CD
F
00 01
1
1
100
E01
11 10
1
1
X
11
10
XE
AB
D
F
00 01
1P 0
1
11 10
X
X
AB
KTS2-C2-Tr.13
III. THÀNH LẬP LƯU ĐỒ MÁY TRẠNG THÁI:
Ví dụ 1: Lập lưu đồ SM cho bộ chia nhị phân song song
Ta xét thiết kế bộ chia song song cho các số nhị phân dương. Thí dụ ta
sẽ thiết kế 1 hệ chia số bị chia (dividend) 6 bit cho số chia (divisor) 3 bit để có
được thương số 3 bit.
Minh họa cho quá trình chia:
Ta nhận thấy việc chia có thể thực hiện được bằng các phép toán trừ và
dịch. Để xây dựng bộ chia ta sẽ dùng thanh ghi số bị chia 7 bit và thanh ghi số
chia 3 bit có sơ đồ khối như sau:
Tín hiệu vào St (Start): St = 1 cho phép bắt đầu chạy hệ thống. Nó sẽ là 1
trong thời gian 1 xung nhịp, và rồi sẽ giữ là 0 cho đến khi hệ điều khiển quay
về trạng thái ban đầu.
KTS2-C2-Tr.14
Tín hiệu vào C: là ngõ ra của bộ so sánh; nếu “số chia” lớn hơn 4 bit tận
cùng bên trái của “số bị chia” thì C = 0, ngược lại C=1. Mạch điều khiển tạo
ra chuỗi các tín hiệu “dịch” và “trừ” mong muốn. Bất cứ khi nào C=1, tín
hiệu “trừ” được tạo ra và bit thương số được đặt lên 1.
Tín hiệu ra V (Overflow): Nếu ban đầu x7x6x5x4 ≥ y3y2y1 (nghĩa là nếu 4 bit
trái của thanh ghi “số bị chia” vượt quá hoặc bằng số chia), thương số sẽ lớn
hơn 7 và xảy ra tràn trên (overflow).
Do vậy, nếu giá trị ban đầu của C là 1, thương số sẽ cần 4 bit trở lên. Do
đó bộ chia dừng và báo hiệu tràn trên bằng cách cho biến V=1.
Tín hiệu dịch Sh (Shift): khi Sh = 1 sẽ dịch “số bị chia” sang trái một vị
trí.
Tín hiệu trừ Su (Subtract): Bất cứ khi nào C = 1, tín hiệu Su = 1. Khi đó
hệ sẽ trừ “số chia” cho 4 bit tận cùng bên trái của thanh ghi “số bị chia” và
đặt bit thương số (bit tận cùng bên phải trong thanh ghi “số bị chia”) lên 1.
KTS2-C2-Tr.15
Lưu đồ SM của bộ chia nhị phân.
00 = AB
01
10
11
KTS2-C2-Tr.16
Ví du 2ï: Thành lập lưu đồ SM cho phần điều khiển bộ nhân.
Ta sẽ thiết kế bộ nhân song song cho các số nhị phân dương, nhân nhị
phân chỉ cần các phép toán dịch và cộng.
Minh hoạ cho bài toán nhân nhị phân:
Nhân hai số 4 bit cần 1 thanh ghi “số bị nhân” (multiplicand register) 4
bit, 1 thanh ghi “số nhân” (multiplier) 4 bit và thanh ghi 8 bit dành cho số
hạng tích. Thanh ghi tích số làm việc như thanh ghi tích lũy là tổng tích lũy
các “tích từng phần”. Thay vì phải dịch “số bị nhân” sang trái trước khi
cộng, người ta sẽ dịch thanh ghi tích sang phải.
Ta có sơ đồ khối của bộ điều khiển nhân
Ad: tín hiệu cộng; Sh: tín hiệu dịch; Clk: xung nhịp; M: bit của số nhân;
St: tín hiệu bắt đầu; Done: thực hiện xong; C: số nhớ (carry)
Số bị nhân
Số nhân
KTS2-C2-Tr.17
Thí dụ nhân (13 x 11) được làm lại sau đây chỉ vị trí các bit trong các
thanh ghi ở mỗi thời điểm xung nhịp.
Nội dung ban đầu của thanh ghi tích:
(Cộng “số bị nhân” vì M=1)
Sau khi cộng
Sau khi dịch
(Cộng “số bị nhân” vì M=1)
Sau khi cộng
Sau khi dịch
(bỏ qua cộng vì M=0)
Sau khi dịch
(Cộng “số bị nhân” vì M=1)
Sau khi cộng
Sau khi dịch (Đáp số):
Giản đồ trạng thái cho phần điều khiển bộ nhân.
Đường chia giữa số nhân và tích số
KTS2-C2-Tr.18
Trong trường hợp tổng quát hơn, nếu cần nhân số bit lớn, người ta chia
hệ điều khiển thành bộ đếm và điều khiển “cộng - dịch”.
- Phần điều khiển “cộng - dịch” có trạng thái S1 là trạng thái sau khi
dịch, và trạng thái S2 là trạng thái sau khi cộng.
- Phần bộ đếm tạo ra tín hiệu K.
Tín hiệu hoàn tất (K) có từ bộ đếm để làm dừng bộ nhân sau khi đã
hoàn tất đủ số lần dịch. Để xác định xem khi nào hoàn tất việc “nhân”, mỗi
lần tín hiệu “dịch” được tạo ra sẽ làm tăng bộ đếm. Nếu bộ nhân có n bit,
tổng số lần dịch cần là n. Ta sẽ thiết kế bộ đếm để tín hiệu hoàn tất (K) được
tạo ra sau khi xảy ra (n-1) lần dịch.
(a) Điều khiển bộ nhân (b) Giản đồ trạng thái cộng-dịch
(c) Giản đồ trạng thái cuối cùng của bộ điều khiển cộng dịch
KTS2-C2-Tr.19
Ở trạng thái S1, là trạng thái có được sau khi dịch, nếu K = 0 thì hoạt
động bình thường. Nếu K=1, ta kiểm tra M: nếu M = 0, ta xuất tín hiệu dịch
cuối cùng và dừng lại; còn nếu M=1, ta cộng trước khi “dịch” và đi vào trạng
thái S2.
Ở trạng thái S2, nếu K=1, ta xuất ra thêm 1 tín hiệu dịch nữa và rồi đi
vào trạng thái S3. Tín hiệu “dịch” cuối cùng sẽ reset bộ đếm về 0, đồng thời
điều khiển “cộng-dịch” quay về trạng thái dừng.
Bộ đếm đếm số lần dịch và xuất K=1 vừa trước khi lần dịch cuối cùng
xảy ra.
Lưu đồ SM của bộ nhân nhị phân.
S3 10
S0 00 = Q1Q2
St 0 1
S2 01
Sh
M
Ad
0
0
Load
S1 11
Sh
1
K
K
1
1 0
Done
KTS2-C2-Tr.20
Ví dụ 3: Thiết kế trò chơi xúc xắc điện tử.
Sơ đồ khối trò chơi xúc xắc.
Như vậy sau khi gieo xúc xắc (roll), tổng của các giá trị trong 2 bộ đếm
nằm trong dãi từ 2 đến 12. Các qui tắc chơi như sau:
1. Sau lần gieo xúc xắc (roll) lần thứ nhất, người chơi thắng nếu tổng là 7
hoặc 11. Người chơi thua nếu tổng là 2, 3, hoặc 12. Ngược lại tổng có
được trong lần “roll” thứ nhất được xem như “điểm” của người chơi và
phải “roll” xúc xắc lần nữa.
2. Ở lần “roll” thứ hai hoặc kế tiếp, người chơi thắng nếu tổng bằng
“điểm” của người chơi và thua nếu tổng là 7. Ngược lại người chơi phải
“roll” lần nữa cho đến khi cuối cùng người chơi thắng hoặc thua.
3. Sau khi thắng hoặc thua, người chơi phải ấn nút Reset để bắt đầu trò
chơi mới.
Có 2 nút nhấn: Rb (Roll button=nút gieo) và Reset. Reset được dùng để
khởi động trò chơi mới. Khi ấn nút “roll” (giữ Rb), các bộ đếm xúc xắc đếm ở
tốc độ cao, vì vậy không thể đọc được trên hiển thị. Khi nhả nút Rb, các giá
trị trong 2 bộ đếm được hiển thị và trò chơi có thể tiến hành. Nếu đèn “Win”
(thắng) hoặc đèn “Lose” (thua) không sáng, người chơi ấn nút “roll” lần nữa.
KTS2-C2-Tr.21
Các tín hiệu vào hệ điều khiển được định nghĩa như sau:
D7 = 1 nếu tổng của xúc xắc là 7.
D11 = 1 nếu tổng của xúc xắc là 11.
D2312 = 1 nếu tổng của xúc xắc là 2, 3, hoặc 12.
Eq=1 nếu tổng của xúc xắc bằng số điểm cất trong thanh ghi điểm.
Rb = 1 khi ấn nút gieo xúc xắc Rb.
Reset = 1 khi ấn nút Reset.
Các biến ra của hệ điều khiển được định nghĩa như sau:
Roll = 1 cho phép các bộ đếm xúc xắc.
Sp = 1 sẽ cất tổng vào thanh ghi điểm (Sp=Save points).
Win = 1 làm cho đèn “Win” sáng (thắng).
Lose = 1 làm cho đèn “Lose” sáng (thua).
Lưu đồ trò chơi xúc xắc.
KTS2-C2-Tr.22
Lưu đồ SM của trò chơi xúc xắc
D711
S4 100
S0 000 = ABC
Rb 0 1
S3 011
Lose
Rb
1
1
Roll
S1 001
Sh
0
Rb 0
D2312
0
0
1
S2 010
Win
Reset 0 1
Reset 0 0
S5 101
Rb 1
Roll
Eq 1
D7
0
0
0
1