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ÁI 1. GIỚI THIỆU MÁY TRẠNG THÁI Sự 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ái Mạch logic trạng thái kế tiếp Mạch logic ngõ ra Máy trạng thái được chia làm hai mô hình: Mô hình Moore Mô hình Mealy 1. GIỚI THIỆU MÁY TRẠNG THÁI (tt) Mô hình Mealy Hình 1.1 Các mô hình máy trạng thái 1. GIỚI THIỆU MÁY TRẠNG THÁI (tt) Mô hình Moore Hình 1.1 Các mô hình máy trạng thái 1. 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 1. 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 2. PHÂN TÍCH MÁY TRẠNG THÁI Cá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). 2. 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 2. 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 2. 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: 2. 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: 2. 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ái 2. 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.1 3. THIẾT KẾ MÁY TRẠNG THÁI Cá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ái Gán (mã hóa) trạng thái Xây dựng bảng chuyển tiếp/ngõ ra Xây dựng bảng kích thích Dẫn ra các phương trình kích thích và ngõ ra Thực hiện mạch 3.1. XÂY DỰNG GIẢN ĐỒ TRẠNG THÁI Ví 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.2 3.1. XÂY DỰNG GIẢN ĐỒ TRẠNG THÁI (tt) Bảng trạng thái Trường hợp máy trạng thái kiểu Moore: 3.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.3 3.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. 3.2. RÚT GỌN BẢNG TRẠNG THÁI Tạ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) 3.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: 3.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: 3.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: 3.2.1. Phương pháp tìm hàng tương đương: (tt) Ví dụ 1.4: (tt) 3.2.1. Phương pháp tìm hàng tương đương: (tt) Ví dụ 1.4: (tt) 3.2.1. Phương pháp tìm hàng tương đương: (tt) Ví dụ 1.4: (tt) 3.2.1. Phương pháp tìm hàng tương đương: (tt) Ví dụ 1.4: (tt) 3.2.1. Phương pháp tìm hàng tương đương: (tt) Ví dụ 1.4: (tt) 3.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: 3.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: 3.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. 3.2.3. Phương pháp dùng bảng kéo theo Bả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. 3.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. 3.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: 3.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. 3.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  G Bài tập Rút gọn bảng trạng thái sau: 3.3. GÁN TRẠNG THÁI Số 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: 3.3.1. Gán quỹ tích trạng thái tối thiểu Sự 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 3.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. 3.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). 3.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). 3.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: 3.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)x2 Có thể gán theo 1 trong 2 cách sau: 3.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. 3.3.2. Gán trạng thái theo các quy tắc (tt) Ví dụ 1.11: (tt) 3.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: 3.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 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. Q&A