Bài giảng môn Kỹ thuật số 2 - Chương 1: Thiết kế máy trạng thái

Chương 1 THIẾT KẾ MÁY TRẠNG THÁIg(X,Y)f(X,Y)XYWZg(X,Y)f(Y)XYWZBài giảng mơn Kỹ thuật số 21Giảng viên: Nguyễn Hữu Chân Thành1. GIỚI THIỆU MÁY TRẠNG THÁISự khác biệt giữa mạch tổ hợp và mạch tuần tự.Mạch tuần tự còn được gọi là máy trạng thái hữu hạn FSM (Finite State Machine) hay gọi tắt là máy trạng thái.Các thành phần của một FSM:Bộ nhớ trạng tháiMạch logic trạng thái kế tiếpMạch logic ngõ raMáy trạng thái được chia làm hai mô hình:Mô hình Moore Mô hình Mealy Bài giảng mơn Kỹ thuật số 22Giảng viên: Nguyễn Hữu Chân Thành1. GIỚI THIỆU MÁY TRẠNG THÁI (tt)Mô hình MealyHình 1.1 Các mô hình máy trạng tháig(X,Y)f(X,Y)XYWZBài giảng mơn Kỹ thuật số 23Giảng viên: Nguyễn Hữu Chân Thành1. GIỚI THIỆU MÁY TRẠNG THÁI (tt)Mô hình MooreHình 1.1 Các mô hình máy trạng tháig(X,Y)f(Y)XYWZBài giảng mơn Kỹ thuật số 24Giảng viên: Nguyễn Hữu Chân Thành1. GIỚI THIỆU MÁY TRẠNG THÁI (tt)Máy trạng thái lưu lại ở mỗi trạng thái trong một khoảng được gọi là thời gian trạng thái (state time) Thời gian trạng thái = Thời gian chuyển biến + Thời gian ổn định Hình 1.2 Biểu đồ thời gian của máy trạng thái Bài giảng mơn Kỹ thuật số 25Giảng viên: Nguyễn Hữu Chân Thành1. GIỚI THIỆU MÁY TRẠNG THÁI (tt)Các phương trình trong khoảng thời gian ổn định:W(iT) = g[X(iT), Y(iT)]Z(iT) = f [X(iT), Y(iT)] (Mealy)Hay Z(iT) = f [Y(iT)] (Moore)Ngõ ra dạng đường ống (pipelined outputs) Hình 1.3 Máy trạng thái Mealy với ngõ ra dạng đường ống g(X,Y)f(X,Y)XYWZZpBài giảng mơn Kỹ thuật số 26Giảng viên: Nguyễn Hữu Chân Thành2. PHÂN TÍCH MÁY TRẠNG THÁICác bước phân tích:Xác định các phương trình kích thích (excitation equations)Xác định các phương trình chuyển tiếp (transition equations) Xây dựng bảng chuyển tiếp (transition table) Xác định các phương trình ngõ ra (output equations) Xây dựng bảng chuyển tiếp/ngõ ra.Xây dựng bảng trạng thái/ngõ ra.(Tùy chọn) Vẽ giản đồ trạng thái (state diagram/graph).Bài giảng mơn Kỹ thuật số 27Giảng viên: Nguyễn Hữu Chân Thành2. PHÂN TÍCH MÁY TRẠNG THÁI (tt)Ví dụ: Phân tích máy trạng thái sau: Hình 1.4 Máy trạng thái đồng bộ dùng D flip-flop kích cạnh lên Bài giảng mơn Kỹ thuật số 28Giảng viên: Nguyễn Hữu Chân Thành2. PHÂN TÍCH MÁY TRẠNG THÁI (tt)Phương trình kích thích:Phương trình đặc tính của D-FF: Q+ = D Bảng chuyển tiếp Bài giảng mơn Kỹ thuật số 29Giảng viên: Nguyễn Hữu Chân Thành2. PHÂN TÍCH MÁY TRẠNG THÁI (tt)Phương trình ngõ ra: MAX = Q1.Q0.EN Bảng trạng thái/ngõ ra:Bài giảng mơn Kỹ thuật số 210Giảng viên: Nguyễn Hữu Chân Thành2. PHÂN TÍCH MÁY TRẠNG THÁI (tt)Giản đồ trạng thái: Trường hợp ngõ ra kiểu Moore:Bài giảng mơn Kỹ thuật số 211Giảng viên: Nguyễn Hữu Chân Thành2. PHÂN TÍCH MÁY TRẠNG THÁI (tt)Giản đồ trạng thái kiểu Moore:Giản đồ thời gian:Hình 1.7 Giản đồ thời gian cho ví dụ phân tích máy trạng tháiBài giảng mơn Kỹ thuật số 212Giảng viên: Nguyễn Hữu Chân Thành2. PHÂN TÍCH MÁY TRẠNG THÁI (tt)Bài tập Phân tích máy trạng thái đồng bộ được cho trên hình P1.1. Viết các phương trình kích thích/ngõ ra, bảng chuyển tiếp/ngõ ra, bảng trạng thái/ngõ ra và vẽ giản đồ trạng thái (dùng các tên trạng thái A-D cho Q1Q2= 00 - 11). Hình P1.1Bài giảng mơn Kỹ thuật số 213Giảng viên: Nguyễn Hữu Chân Thành3. THIẾT KẾ MÁY TRẠNG THÁICác bước thiết kế:Xây dựng giản đồ trạng thái hay bảng trạng thái/ngõ ra(Tùy chọn) Tối thiểu hóa số trạng tháiGán (mã hóa) trạng tháiXây dựng bảng chuyển tiếp/ngõ raXây dựng bảng kích thíchDẫn ra các phương trình kích thích và ngõ raThực hiện mạch Bài giảng mơn Kỹ thuật số 214Giảng viên: Nguyễn Hữu Chân Thành3.1. XÂY DỰNG GIẢN ĐỒ TRẠNG THÁIVí dụ 1.2: Dẫn ra giản đồ trạng thái cho một mạch phát hiện chuỗi có sơ đồ khối như trên hình 1.9. Khi chuỗi vào là 101 thì Z=1, ngược lại Z=0.Hình 1.9 Sơ đồ khối của mạch phát hiện chuỗi ví dụ 1.2 Hình 1.12 Giản đồ Mealy cho ví dụ 1.2Bài giảng mơn Kỹ thuật số 215Giảng viên: Nguyễn Hữu Chân Thành3.1. XÂY DỰNG GIẢN ĐỒ TRẠNG THÁI (tt)Bảng trạng tháiTrường hợp máy trạng thái kiểu Moore: Bài giảng mơn Kỹ thuật số 216Giảng viên: Nguyễn Hữu Chân Thành3.1. XÂY DỰNG GIẢN ĐỒ TRẠNG THÁI (tt)Ví dụ 1.3: Dẫn ra giản đồ trạng thái cho một mạch phát hiện chuỗi có sơ đồ khối như trên hình 1.9. Ngõ ra Z = 1 nếu chuỗi ngõ vào tận cùng là 010 hay 1001, ngược lại Z = 0. Hình 1.18 Giản đồ Mealy hoàn chỉnh cho ví dụ 1.3Bài giảng mơn Kỹ thuật số 217Giảng viên: Nguyễn Hữu Chân Thành3.1. XÂY DỰNG GIẢN ĐỒ TRẠNG THÁI (tt)Bài tập: Dẫn ra giản đồ trạng thái cho một mạch phát hiện chuỗi có sơ đồ khối như trên hình. Ngõ ra Z = 1 nếu chuỗi ngõ vào tận cùng là 0010 hay 100, ngược lại Z = 0. Ví dụ : X = 1 1 0 0 1 0 0 1 0 1 0 0 1 0 1 Z = 0 0 0 1 0 1 1 0 1 0 0 1 0 1 0 Chú ý là mạch sẽ không reset về trạng thái ban đầu khi xảy ra Z = 1. Gợi ý: lời giải tối thiểu cần 6 trạng thái.Bài giảng mơn Kỹ thuật số 218Giảng viên: Nguyễn Hữu Chân Thành3.2. RÚT GỌN BẢNG TRẠNG THÁITại sao nên rút gọn bảng trạng thái?Số FF cần là ít nhất.Số trạng thái ít nhất cĩ thể tận dụng được nhiều don’t care hơn → giảm số cổng cần để cài đặt.Định nghĩa: Hai trạng thái Si và Sj được gọi là tương đương nhau nếu và chỉ nếu:Ứng với mỗi tổ hợp ngõ vào tác động sẽ cho các ngõ ra giống nhau.Ứng với mỗi tổ hợp ngõ vào tác động sẽ tạo ra cặp trạng thái kế tiếp tương đương nhau.Giới thiệu các qui trình rút gọn trạng thái:Tìm hàng tương đương (row matching)Phân nhóm tương đương (equivalence partitioning)Bảng kéo theo (implication table/chart) Bài giảng mơn Kỹ thuật số 219Giảng viên: Nguyễn Hữu Chân Thành3.2. RÚT GỌN BẢNG TRẠNG THÁI (tt)3.2.1. Phương pháp tìm hàng tương đương:Ví dụ 1.4: Dẫn ra giản đồ trạng thái cho một mạch phát hiện chuỗi có sơ đồ khối như trên hình 1.9. Ngõ ra Z = 1 nếu chuỗi ngõ vào tận cùng là 1010 hay 0110, ngược lại Z = 0. Mạch sẽ reset sau mỗi 4-bit vào. Ví dụ về đáp ứng vào-ra:Bài giảng mơn Kỹ thuật số 220Giảng viên: Nguyễn Hữu Chân Thành3.2.1. Phương pháp tìm hàng tương đương: (tt)Ví dụ 1.4: (tt)Giản đồ trạng thái:Bài giảng mơn Kỹ thuật số 221Giảng viên: Nguyễn Hữu Chân Thành3.2.1. Phương pháp tìm hàng tương đương: (tt)Ví dụ 1.4: (tt) Bảng trạng thái/ngõ ra ban đầu:Bài giảng mơn Kỹ thuật số 222Giảng viên: Nguyễn Hữu Chân Thành3.2.1. Phương pháp tìm hàng tương đương: (tt)Ví dụ 1.4: (tt)Bài giảng mơn Kỹ thuật số 223Giảng viên: Nguyễn Hữu Chân Thành3.2.1. Phương pháp tìm hàng tương đương: (tt)Ví dụ 1.4: (tt)Bài giảng mơn Kỹ thuật số 224Giảng viên: Nguyễn Hữu Chân Thành3.2.1. Phương pháp tìm hàng tương đương: (tt)Ví dụ 1.4: (tt)Bài giảng mơn Kỹ thuật số 225Giảng viên: Nguyễn Hữu Chân Thành3.2.1. Phương pháp tìm hàng tương đương: (tt)Ví dụ 1.4: (tt)Bài giảng mơn Kỹ thuật số 226Giảng viên: Nguyễn Hữu Chân Thành3.2.1. Phương pháp tìm hàng tương đương: (tt)Ví dụ 1.4: (tt)Bài giảng mơn Kỹ thuật số 227Giảng viên: Nguyễn Hữu Chân Thành3.2.1. Phương pháp tìm hàng tương đương: (tt)Ví dụ 1.4: Bảng trạng thái rút gọn và giản đồ trạng thái tương ứng:Bài giảng mơn Kỹ thuật số 228Giảng viên: Nguyễn Hữu Chân Thành3.2.2. Phương pháp phân nhóm tương đương Ví dụ 1.5: Rút gọn bảng trạng thái được cho trên hình sau:Bài giảng mơn Kỹ thuật số 229Giảng viên: Nguyễn Hữu Chân Thành3.2.2. Phương pháp phân nhóm tương đương (tt)Phương pháp phân nhóm tương đương có thể được tóm tắt như sau:Bắt đầu với P0 chứa tất cả các trạng thái của mạch trong một nhóm.Xác định các nhóm của P1 bằng cách quan sát phần ngõ ra của bảng trạng thái/ngõ ra và nhóm các trạng thái với các giá trị ngõ ra giống nhau vào chung một nhóm.Xác định các nhóm của Pi từ Pi – 1, i > 1:Xác định các trạng thái kế tiếp của mỗi nhóm trong Pi – 1 ứng với mỗi tổ hợp ngõ vào.Nếu chúng nằm trong cùng một nhóm trong Pi – 1 thì không tách nhóm tương tứng.Nếu không, tách nhóm tương ứng sao cho các nhóm được tách có các trạng thái kế tiếp nằm trong cùng một nhóm của Pi – 1.Lặp lại cho tất cả các tổ hợp ngõ vào.Lặp lại bước 3 cho đến khi không thể tách nhóm được nữa. Bài giảng mơn Kỹ thuật số 230Giảng viên: Nguyễn Hữu Chân Thành3.2.3. Phương pháp dùng bảng kéo theoBảng kéo theo cung cấp một cấu trúc để so sánh mỗi trạng thái với các trạng thái còn lại trong bảng trạng thái để xác định tính tương đương của chúng.Bài giảng mơn Kỹ thuật số 231Giảng viên: Nguyễn Hữu Chân Thành3.2.3. Phương pháp dùng bảng kéo theo (tt)Nội dung trong mỗi ô phụ thuộc vào sự tương đương của cặp trạng thái tọa độ:(1) Dấu “X” biểu thị cặp trạng thái tọa độ của ô là không tương đương;(2) Dấu “” cho biết cặp trạng thái tọa độ của ô là tương đương không điều kiện; (3) Các cặp trạng thái kế tiếp tương ứng với các tổ hợp ngõ vào, biểu thị sự tương đương có điều kiện.Bài giảng mơn Kỹ thuật số 232Giảng viên: Nguyễn Hữu Chân Thành3.2.3. Phương pháp dùng bảng kéo theo (tt)Ví dụ 1.6: Rút gọn bảng trạng thái được cho trên hình của vd 1.6:Bài giảng mơn Kỹ thuật số 233Giảng viên: Nguyễn Hữu Chân Thành3.2.3. Phương pháp dùng bảng kéo theo (tt)Phương pháp dùng bảng kéo theo có thể tóm tắt như sau:Vẽ bảng kéo theo và điền vào mỗi ô với dấu “X”, dấu “” hay các cặp trạng thái kế tiếp tùy thuộc vào các cặp trạng thái tọa độ.Duyệt qua bảng từ trên xuống dưới, từ trái qua phải và đánh dấu “X” vào các ô nếu có ít nhất một cặp trạng thái trong các ô đó tương ứng với một ô đã có dấu “X” trong bảng.Lặp lại bước 2 cho đến khi không còn ô nào có thể đánh dấu “X” nữa.Các trạng thái tọa độ tương ứng với các ô không có dấu “X” là tương đương.Kết hợp các cặp trạng thái tương đương đạt được ở bước 4, nếu được, để tạo thành các nhóm tương đương lớn hơn bằng cách dùng điều kiện bắc cầu.Loại bỏ và thay thế các trạng thái tương đương trong bảng trạng thái để đạt được bảng trạng thái rút gọn. Bài giảng mơn Kỹ thuật số 234Giảng viên: Nguyễn Hữu Chân Thành3.2.3. Phương pháp dùng bảng kéo theo (tt)Ví dụ 1.7: Rút gọn bảng trạng thái được cho trên hình sau:E  F, E  G, F  G → E  F  GBài giảng mơn Kỹ thuật số 235Giảng viên: Nguyễn Hữu Chân ThànhBài tậpRút gọn bảng trạng thái sau:Bài giảng mơn Kỹ thuật số 236Giảng viên: Nguyễn Hữu Chân Thành3.3. GÁN TRẠNG THÁISố biến trạng thái m được chọn sao cho với n là số trạng thái Gán trạng thái là quá trình phân phối 1 trong tổ hợp có thể của mã m-bit cho một trong các trạng thái sao cho mỗi trạng thái tương ứng với một từ mã m-bit duy nhất. Bảng gán trạng thái (state map): có một ô cho một mã trạng thái, để quan sát tính kế cận trong khi gán.Ví dụ 1.8: Phép gán trạng thái cho giản đồ với 5 trạng thái: Bài giảng mơn Kỹ thuật số 237Giảng viên: Nguyễn Hữu Chân Thành3.3.1. Gán quỹ tích trạng thái tối thiểuSự thay đổi số bit ít hơn có thể dẫn đến tối thiểu hóa việc tính toán và tăng độ tin cậy. Cố gắng đạt được quỹ tích tối ưu bằng việc gán các mã cách-1. Ví dụ 1.9: Phép gán quỹ tích trạng thái tối thiểu cho giản đồ trên Bài giảng mơn Kỹ thuật số 238Giảng viên: Nguyễn Hữu Chân Thành3.3.2. Gán trạng thái theo các quy tắc(1) Các trạng thái có cùng trạng thái kế tiếp ứng với cùng tác động ngõ vào nên được mã hóa kế cận.(2) Các trạng thái là trạng thái kế tiếp của cùng một trạng thái nên được mã hóa kế cận.(3) Các trạng thái có cùng ngõ ra ứng với cùng tác động ngõ vào nên được mã hóa kế cận.Bài giảng mơn Kỹ thuật số 239Giảng viên: Nguyễn Hữu Chân Thành3.3.2. Gán trạng thái theo các quy tắc (tt)Ví dụ 1.10: Gán trạng thái cho các giản đồ sau:S0 và S3 nên được gán kế cận (qui tắc 1).S1 và S5 nên được gán kế cận (qui tắc 2). S0, S1, S3 và S4 nên được gán kế cận (qui tắc 3).Bài giảng mơn Kỹ thuật số 240Giảng viên: Nguyễn Hữu Chân Thành3.3.2. Gán trạng thái theo các quy tắc (tt)Một số lưu ý khi điền vào bảng: Nên gán trạng thái khởi đầu (trạng thái reset) là 0 trên bảng.Các điều kiện kế cận ở quy tắc 1 và các điều kiện kế cận xuất hiện nhiều lần nên được ưu tiên thỏa mãn trước.Khi cần có nhiều trạng thái kế cận nhau thì nên đặt các trạng thái này trong nhóm các ô kế cận trong bảng gán trạng thái.Trường hợp có 2 hay nhiều biến ngõ ra thì cũng có thể lấy ưu tiên kế cận theo quy tắc 3 cao hơn (nếu quan tâm đến rút gọn các hàm ngõ ra). Bài giảng mơn Kỹ thuật số 241Giảng viên: Nguyễn Hữu Chân Thành3.3.2. Gán trạng thái theo các quy tắc (tt)Ví dụ 1.11: Gán trạng thái cho bảng trạng thái sau:Bài giảng mơn Kỹ thuật số 242Giảng viên: Nguyễn Hữu Chân Thành3.3.2. Gán trạng thái theo các quy tắc (tt)Ví dụ 1.11: (tt)Tập các trạng thái kế cận rút ra theo quy tắc 1 và 2: (S0, S1, S3, S5); (S3, S5); (S4, S6); (S0, S2, S4, S6)(S1, S2); (S2, S3); (S1, S4); (S2, S5)x2; (S1, S6)x2Có thể gán theo 1 trong 2 cách sau:Bài giảng mơn Kỹ thuật số 243Giảng viên: Nguyễn Hữu Chân Thành3.3.2. Gán trạng thái theo các quy tắc (tt)Ví dụ 1.11: (tt)Giả sử dùng phép gán ở hình a.Bài giảng mơn Kỹ thuật số 244Giảng viên: Nguyễn Hữu Chân Thành3.3.2. Gán trạng thái theo các quy tắc (tt)Ví dụ 1.11: (tt)Bài giảng mơn Kỹ thuật số 245Giảng viên: Nguyễn Hữu Chân Thành3.3.2. Gán trạng thái theo các quy tắc (tt)Ví dụ 1.12: Gán trạng thái cho bảng trạng thái sau:Bài giảng mơn Kỹ thuật số 246Giảng viên: Nguyễn Hữu Chân Thành3.3.2. Gán trạng thái theo các quy tắc (tt)Ví dụ 1.12: (tt)Hai phép gán có thể dùng:Phép gán (a) không thỏa các kế cận (b,f), (c,e) và (e,f); phép gán (b) không thỏa các kế cận (d,f) và (e,f)Bài giảng mơn Kỹ thuật số 247Giảng viên: Nguyễn Hữu Chân ThànhBài tập 1. Một mạch tuần tự có một ngõ vào (X) và một ngõ ra (Z). Vẽ giản đồ trạng thái Mealy cho mỗi trường hợp sau: a) Ngõ ra Z =1 nếu tổng số bit 1 nhận được chia hết cho 3. b) Ngõ ra Z =1 nếu tổng số bit 1 nhận được chia hết cho 3 và tổng số bit 0 nhận được là một số chẵn lớn hơn 0. 2. Thiết kế một mạch tuần tự đồng bộ kiểm tra ngõ vào X và tạo ngõ ra là Z = 1 khi phát hiện chuỗi ngõ vào tận cùng là 0101, với điều kiện không xảy ra chuỗi 110. Ví dụ : X = 0 1 0 1 0 1 1 0 1 0 1 Z = 0 0 0 1 0 1 0 0 0 0 0 Chú ý là mạch sẽ không reset về trạng thái ban đầu khi xảy ra Z = 1.Bài giảng mơn Kỹ thuật số 248Giảng viên: Nguyễn Hữu Chân ThànhQ&ABài giảng mơn Kỹ thuật số 249Giảng viên: Nguyễn Hữu Chân Thành