Mạch dãy - Phần 1

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
Nội dung trích xuất từ tài liệu:
Mạch dãy - Phần 1 2. M CH DÃY2.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 N2.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 pcác tín hi u vào Z={z1,z2,...zi,...zF}, t p các tínhi u ra W={w1,w2,...wj,...wG}, t p các tr ng tháitrong 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 pA, 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 ctrư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 rakhô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;w1Otomat Mealy: a1 a2M i nh là 1 z2;w1 z2;w2tr ng thái trong. z3;w1M i cung có z3;w3chi u th hi n z2;w3s chuy n i a4 a3tr ng thái. Trên z3;w2cung ghi t/h z1;w2vào; t/h ra. z1;w1 z3Otomat Moore: w4 w3M i nh là 1 tr ng z1 a1 a2thái trong, bên z2 z2c nh ghi t/h ra. z1 z3M i cung có chi u z3 z3th hi n s chuy n z1 i tr ng thái. Trên a4 a3 w2cung ghi t/h vào. w1 z1+z2 z22.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 a7x=0 a3/ 0 a5/ 0 a7/ 0 a1/ 1 a1/ 0 a1/ 1 a1/ 0x=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áctr 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 chi n phân chia t ng bư c:+ B1: t b ng chuy n i tr. thái và u ra chiacá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áichuy n n ti p theo gi ng nhau ho c cùng trong1 l p thì x p chung m t l p m i, tr. thái nàokhô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 aBi thì d ng. M i l p ư c thay b ng m t tr ngthá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) ( ...