Mạch dãy - Phần 1

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:19

Thêm vào BST

Báo xấu

111
lượt xem 14
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tài liệu tham khảo chuyên đề kỹ thuật số về mạch dãy - phần 1 Otomat hữu hạn

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Mạch dãy - Phần 1

2. M CH DÃY 2.1 OTOMAT H U H N. 2.2 KHÁI NI M M CH DÃY. 2.3 CÁC LO I FLIP-FLOP. 2.4 THI T K M CH DÃY. 2.5 PHÂN TÍCH M CH DÃY. 2.6 THI T K M CH DÃY NG B . 2.7 THI T K M CH DÃY KHÔNG NG B . 2.8 M T S M CH DÃY THƯ NG G P.
2.1 OTOMAT H U H N 2.1.1 Khái ni m otomat h u h n. Các m ch logic ư c chia thành hai lo i chính là các m ch t h p và các m ch dãy. - Các m ch t h p là các m ch logic không có các ph n t nh , còn g i là các otomat không có nh . - Các m ch dãy (hay tu n t , k ti p..) là s k t h p c a các m ch logic và các m ch nh , còn g i là otomat có nh , g i t t là otomat.
Mô hình tr u tư ng c a otomat. Mô hình Otomat là m t b bi n i s có t p các tín hi u vào Z={z1,z2,...zi,...zF}, t p các tín hi u ra W={w1,w2,...wj,...wG}, t p các tr ng thái trong A={a1,a2,...ak,...aH}, hai hàm c trưng là hàm chuy n i tr ng thái δ và hàm u ra λ. A={a1,...aH} Z={z1,...zG} W={w1,...wG} w(t)=λ(a(t),z(t)) a(t+1)=δ(a(t),z(t))
- Otomat h u h n là otomat có các t p h p A, Z, W h u h n. - Otomat xác nh hoàn toàn là otomat mà ng v i m i c p (zi, ak) Є ZxA các hàm c trưng δ và λ là xác nh. - Otomat xác nh không hoàn toàn là otomat ch xác nh v i m t s c p (zi, ak) Є ZxA và không xác nh v i m t s c p (zm, an) Є ZxA khác.
2.1.2 Các d ng otomat và cách bi u di n. Hai d ng otomat: - Otomat Moore là otomat mà tín hi u u ra không ph thu c tín hi u u vào, mà ư c xác nh b ng tr ng thái trong c a nó t i cùng th i i m. - Otomat Mealy là otomat mà tín hi u ra ph thu c tín hi u vào và tr ng thái trong t i cùng th i i m.
Ba cách bi u di n các otomat: - Bi u di n b ng phương trình. Otomat Mealy: w(t)=λ(a(t),z(t)) a(t+1)=δ(a(t),z(t)) Otomat Moore: w(t)=λ(a(t)) a(t+1)=δ(a(t),z(t)) - Bi u di n b ng b ng. Otomat Mealy: A={a1,a2,a3,a4}, Z={z1,z2,z3} W={w1,w2,w3}
z(t) a(t) a1 a2 a3 a4 z1 a1 w1 a1 w1 a3 w2 a3 w1 z2 a4 w2 a1 w2 a4 w3 a1 w1 z3 a2 w1 a3 w1 a4 w2 a1 w3 + Ô nào mà tr ng thái chuy n n và t/h ra không xác nh thì tr ng. + Có th tách thành hai b ng riêng: b ng chuy n i tr ng thái và b ng u ra.
Otomat Moore: A={a1,a2,a3,a4}, Z={z1,z2,z3} W={w1,w2,w3,w4} w3 w4 w2 w1 z(t) a(t) a1 a2 a3 a4 z1 a2 a4 a4 a3 z2 a3 a2 a3 a3 z3 a4 a1 a2 a2
(z1;w1)+(z2;w2) - Bi u di n b ng z1;w1 hình. z3;w1 Otomat Mealy: a1 a2 M i nh là 1 z2;w1 z2;w2 tr ng thái trong. z3;w1 M i cung có z3;w3 chi u th hi n z2;w3 s chuy n i a4 a3 tr ng thái. Trên z3;w2 cung ghi t/h z1;w2 vào; t/h ra. z1;w1
z3 Otomat Moore: w4 w3 M i nh là 1 tr ng z1 a1 a2 thái trong, bên z2 z2 c nh ghi t/h ra. z1 z3 M i cung có chi u z3 z3 th hi n s chuy n z1 i tr ng thái. Trên a4 a3 w2 cung ghi t/h vào. w1 z1+z2 z2
2.1.3 T i thi u hóa các tr ng thái c a otomat. Hai tr ng thái tương ương là hai tr ng thái mà n u l y chúng làm tr ng thái ban u thì v i m i t/h vào có th có, chúng luôn cho tín hi u ra gi ng nhau và các tr ng thái chuy n n gi ng nhau ho c chuy n i cho nhau ho c ã là tương ương nhau. - N u nhi u tr ng thái tương ương v i nhau t ng ôi m t thì chúng tương ương v i nhau. Các phương pháp t i thi u hóa tr ng thái otomat. - PP Caldwell (otomat Mealy) hai c t trong b ng chuy n i tr ng thái và u ra s ư c k t h p v i nhau và ư c bi u di n b ng m t c t chung n u chúng có các t/h ra gi ng nhau, các tr ng thái chuy n n gi ng nhau, cùng nhóm ho c tương ương nhau.
A a1 a2 a3 a4 a5 a6 a7 x=0 a3/ 0 a5/ 0 a7/ 0 a1/ 1 a1/ 0 a1/ 1 a1/ 0 x=1 a2/ 0 a4/ 0 a6/ 0 a1/ 1 a1/ 0 a1/ 1 a1/ 0 A a1 a2 a3 a46 a57 x=0 a3/ 0 a57/ 0 a57/ 0 a1/ 1 a1/ 0 x=1 a2/ 0 a46/ 0 a46/ 0 a1/ 1 a1/ 0 A a1 a23 a46 a57 x=0 a23/ 0 a57/ 0 a1/ 1 a1/ 0 x=1 a23/ 0 a46/ 0 a1/ 1 a1/ 0
- PP phân ho ch (otomat Mealy): phân chia các tr ng thái thành các l p các tr ng thái tương ương r i thay b ng các tr ng thái chung, th c hi n phân chia t ng bư c: + B1: t b ng chuy n i tr. thái và u ra chia các tr ng thái trong thành t ng l p các tr. thái có t/h ra như nhau khi cùng m t t/h vào. + B2: trong m i l p B1, các tr. thái nào có tr. thái chuy n n ti p theo gi ng nhau ho c cùng trong 1 l p thì x p chung m t l p m i, tr. thái nào không th a mãn thì tách ra thành l p khác. + L p l i B2 t i khi các l p c a Bi+1 gi ng như c a Bi thì d ng. M i l p ư c thay b ng m t tr ng thái chung.
T ví d trên, th c hi n chia l p: - B1: (a1,a2,a3,a5,a7) (a4,a6); - B2: (a1) (a2,a3) (a5,a7) (a4,a6); - B3: (a1) (a2,a3) (a5,a7) (a4,a6). A a1 a2 a3 a4 a5 a6 a7 x=0 a3/ 0 a5/ 0 a7/ 0 a1/ 1 a1/ 0 a1/ 1 a1/ 0 x=1 a2/ 0 a4/ 0 a6/ 0 a1/ 1 a1/ 0 a1/ 1 a1/ 0 A a1 a23 a46 a57 x=0 a23/ 0 a57/ 0 a1/ 1 a1/ 0 x=1 a23/ 0 a46/ 0 a1/ 1 a1/ 0
2.1.4 Chuy n i gi a hai mô hình otomat. Chuy n t mô hình otomat Mealy sang otomat Moore. B1: Trong b ng chuy n i tr ng thái và u ra, m i c p a/w ư c thay b ng m t tr ng thái q tương ng c a mô hình Moore. B2: L p b ng chuy n i tr ng thái và u ra cho mô hình Moore căn c s chuy n bi n tr ng thái và t/h ra trong b ng c a mô hình Mealy. VD: Chuy n mô hình Mealy sau sang mô hình Moore:
1; 0 0; 0 x a a1 a2 a3 0; 0 a1 a2 0 a2/ 0 a2/ 0 a2/ 1 0; 1 1; 0 1; 0 1 a1/ 0 a3/ 0 a1/ 0 a3 Mealy Moore B1: Tr.thái/t.h ra Tr.thái t.h ra a1/ 0 q1 0 a2/ 0 q2 0 a2/ 1 q3 1 a3/ 0 q4 0
Mealy: a1/ 0 a2/ 0 a2/ 1 a3/ 0 B2: t.h ra: 0 0 1 0 x q q1 q2 q3 q4 0 q2 q2 q2 q3 1 q1 q4 q4 q1 0 0 0 q1 q2 1 0 1 1 0 0 1 1 q4 q3 0
Chuy n t mô hình otomat Moore sang otomat Mealy. Ghi thêm vào m i ô trong b ng chuy n i tr ng thái c a otomat Moore t/h ra, r i ti n hành t i thi u hóa các tr ng thái. Xét VD trên, t b ng chuy n i tr.thái c a otomat Moore: t.h ra: 0 0 1 0 x q q1 q2 q3 q4 0 q2/ 0 q2/ 0 q2/ 0 q3/ 1 1 q1/ 0 q4/ 0 q4/ 0 q1/ 0
T i thi u hóa b ng PP Caldwell x q q1 q23 q4 0 q23/ 0 q23/ 0 q23/ 1 1 q1/ 0 q4/ 0 q1/ 0