Bài giảng môn kỹ thuật số 2 chương 2 thiết kế máy trạng thái dùng lưu đồ asm

Chương 2 THIẾT KẾ MÁY TRẠNG THÁI DÙNG LƯU ĐỒ ASM 1. CẤU TRÚC CỦA LƯU ĐỒ ASM Lưu đồ ASM được xây dựng từ 3 biểu tượng cơ bản là: Hộp trạng thái (state box) Hộp quyết định (decision box) Hộp ngõ ra có điều kiện (conditional output box) 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) Khối ASM: chỉ chứa chính xác một hộp trạng thái và có thể có các hộp quyết định và các hộp ngõ ra điều kiện. Một lưu đồ ASM được xây dựng từ các khối ASM. Mỗi khối ASM minh họa hoạt động của máy trong trạng thái hiện tại. 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) Một khối ASM có một đường vào và một hay nhiều đường ra. Mỗi đường ra phải dẫn đến một trạng thái. Mỗi khi hệ thống đi vào một trạng thái tương ứng với một khối ASM thì các ngõ ra trong hộp trạng thái sẽ được kích hoạt. Các điều kiện trong hộp quyết định sẽ được định trị để xác định đi theo đường nào qua khối ASM. Trên đường đi theo điều kiện nếu gặp hộp ngõ ra điều kiện thì các ngõ ra trong hộp đó sẽ được kích hoạt. Một đường đi qua khối ASM từ ngõ vào đến ngõ ra được gọi là đường nối (link path). 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) Mỗi đường nối tương ứng một biểu thức Boole góp vào biểu thức hoàn chỉnh cho hàm ngõ ra điều kiện hoặc hàm trạng thái kế tiếp. Trong một khối ASM, hộp trạng thái là phần tử duy nhất chỉ thị yếu tố thời gian, tất cả các hộp khác xem như được kích hoạt đồng thời. Lưu đồ ASM chỉ có một trạng thái → biểu diễn hệ tổ hợp. 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) Tổng quát thì một khối ASM có thể được vẽ theo nhiều dạng khác nhau. 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) Phải đảm bảo mỗi trạng thái chỉ dẫn đến một trạng thái kế tiếp duy nhất ứng với mỗi tập hợp xác định các điều kiện vào. Một vài cấu trúc biểu diễn ASM sai Cấu trúc ASM đúng của hình b 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) Không cho phép hồi tiếp nội trong một khối ASM. Không bố trí các hộp quyết định dẫn đến các điều kiện logic không thỏa mãn. 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) Biểu đồ ASM với các đường nối sai 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) Một vài cấu trúc biểu đồ ASM đúng 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) Có thể sử dụng liên kết dạng nối tiếp hoặc song song tương đương cho các hộp quyết định trong một khối ASM. 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) Cho phép các khối ASM dùng chung các hộp quyết định hoặc các hộp ngõ ra điều kiện. 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) Bài tập: Xác định các lỗi trong lưu đồ ASM sau: 1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt) Ví dụ 2.1: Xét lưu đồ ASM: Giản đồ thời gian: Bài tập Hoàn tất giản đồ thời gian cho lưu đồ ASM sau: 2. THÀNH LẬP LƯU ĐỒ ASM Các bước thực hiện: Vẽ sơ đồ khối của hệ thống. Xác định các tín hiệu vào/ra cần cho hệ. Xây dựng lưu đồ ASM. Ví dụ 2.2: Vẽ lưu đồ ASM cho bộ đếm đồng bộ 2-bit kích bằng cạnh lên của xung clock. Bộ đếm thực hiện đếm lên khi ngõ vào là 0 và đếm xuống khi ngõ vào là 1. 2. THÀNH LẬP LƯU ĐỒ ASM (tt) Lưu đồ ASM cho ví dụ 2.2: 2. THÀNH LẬP LƯU ĐỒ ASM (tt) Ví dụ 2.3: Vẽ lưu đồ ASM cho một máy trạng thái đồng bộ phát hiện hướng xe đi qua một con đường vào bãi đậu xe như trên hình. Hai chùm tia sáng đặt cách nhau một khoảng nhỏ hơn chiều dài của xe hơi. Các cảm biến X1, X2 cho mức logic 0 khi chùm tia sáng không bị cắt và cho mức logic 1 khi chùm tia sáng bị cắt và được đưa vào các ngõ vào của máy trạng thái. Giả sử đường xe đi hẹp chỉ cho phép mỗi lần một xe hơi đi vào hay đi ra. Hệ thống có 2 ngõ ra: Z1 =1 nếu xe đi vào bãi đậu xe và ngược lại Z2 =1 nếu xe đi ra khỏi bãi đậu xe. 2. THÀNH LẬP LƯU ĐỒ ASM (tt) Lưu đồ ASM cho ví dụ 2.3: 3. THÀNH LẬP BẢNG ASM Xét lưu đồ ASM sau: 3. THÀNH LẬP BẢNG ASM (tt) Các khối ASM và các đường nối: 3. THÀNH LẬP BẢNG ASM (tt) Các bảng trạng thái kế tiếp 3. THÀNH LẬP BẢNG ASM (tt) Bảng đầu ra trạng thái 3. THÀNH LẬP BẢNG ASM (tt) Bảng đầu ra điều kiện 3. THÀNH LẬP BẢNG ASM (tt) Bảng ASM kết hợp 3. THÀNH LẬP BẢNG ASM (tt) Các bảng hàm hệ thống cho ASM 4. LIÊN KẾT CÁC MÁY TRẠNG THÁI Tách ASM của một hệ thống lớn thành một số ASM nối với nhau theo một cách nào đĩ. Sự tương tác của hai ASM cĩ thể là nối tiếp hoặc song song. Đầu ra của một ASM là đầu vào điều khiển của một ASM khác và ngược lại. Liên kết nối tiếp 2 ASM đồng bộ 4. LIÊN KẾT CÁC MÁY TRẠNG THÁI (tt) Liên kết nối tiếp có nhiều lần gọi 4. LIÊN KẾT CÁC MÁY TRẠNG THÁI (tt) Liên kết nối tiếp với các phép gọi lồng nhau 4. LIÊN KẾT CÁC MÁY TRẠNG THÁI (tt) Liên kết song song Bài tập Một thuật toán máy trạng thái được xác định bởi lưu đồ ASM cho trên hình. Vẽ mỗi khối ASM và các đường nối. Xây dựng bảng ASM kết hợp. Giải Các khối ASM và các đường nối Giải Bảng ASM kết hợp Một thuật toán máy trạng thái được xác định bởi lưu đồ ASM cho trên hình. Vẽ mỗi khối ASM và các đường nối. Xây dựng bảng ASM kết hợp. 5. NÉN BẢNG KARNAUGH Có thể chuyển bảng Karnaugh của các hàm nhiều biến thành bảng nhỏ hơn bằng cách nhập các biến dư vào bảng. Ví dụ: Bảng Karnaugh 3 biến được nén thành dạng 2 biến 5. NÉN BẢNG KARNAUGH (tt) Ba cách nén hàm 3 biến: 5. NÉN BẢNG KARNAUGH (tt) Bốn cách nén hàm 4 biến thành 3 biến: 5. NÉN BẢNG KARNAUGH (tt) Nén thành bảng 2 biến: 5. NÉN BẢNG KARNAUGH (tt) Sáu khả năng nén bảng 4 biến thành 2 biến: 5. NÉN BẢNG KARNAUGH (tt) Áp dụng để rút ra bảng Karnaugh nén từ bảng ASM: 5. NÉN BẢNG KARNAUGH (tt) Áp dụng để rút ra bảng Karnaugh nén từ bảng ASM: 5. NÉN BẢNG KARNAUGH (tt) Ví dụ 2.4: Rút ra bảng Karnaugh cho các hàm kích thích ứng với các loại D-FF, JK-FF và SR-FF cho bảng ASM sau: 5. NÉN BẢNG KARNAUGH (tt) Ví dụ 2.4: Rút ra bảng Karnaugh cho các hàm kích thích ứng với các loại D-FF, JK-FF và SR-FF cho bảng ASM sau: 5. NÉN BẢNG KARNAUGH (tt) Ví dụ 2.4: (tt) 5. NÉN BẢNG KARNAUGH (tt) Ví dụ 2.5: Rút ra bảng Karnaugh cho các hàm trạng thái kế tiếp cho bảng ASM trong hình sau: 5. NÉN BẢNG KARNAUGH (tt) Ví dụ 2.5: Rút ra bảng Karnaugh cho các hàm trạng thái kế tiếp cho bảng ASM trong hình sau: 5. NÉN BẢNG KARNAUGH (tt) Các bước để rút ra các hàm được biểu diễn bằng phương pháp đưa biến vào bảng Karnaugh: Đặt tất cả các biến dư (hay hàm dư) bằng 0 và đơn giản hóa trên các số 1 còn lại trên bảng. Phục hồi lại các biến, đặt các số 1 thành don’t care và tối thiểu hóa với mỗi biến hoặc hàm dư. Kết hợp các biểu thức được tạo ra ở bước 1 và 2 để có biểu thức hoàn chỉnh của hàm. 5. NÉN BẢNG KARNAUGH (tt) Ví dụ 2.6: Rút ra các hàm trạng thái kế tiếp cho ví dụ 2.4: 5. NÉN BẢNG KARNAUGH (tt) Ví dụ 2.7: Rút ra các hàm ngõ ra cho ví dụ 2.4: Bài tập Dẫn ra các phương trình trạng thái kế tiếp và phương trình ngõ ra ở dạng tối thiểu dùng phương pháp đưa biến vào bảng Karnaugh cho lưu đồ ASM sau: 6. CÀI ĐẶT ASM 6.1. Cài đặt bằng cổng rời rạc Ví dụ 2.8: Cài đặt mạch cho bảng ASM trong ví dụ 2.4: 6.2. Cài đặt bằng ULM (Universal Logic Module) Ký hiệu, bảng sự thật, và mạch bên trong cho MUX 2:1 và 4:1 6.2. Cài đặt bằng ULM (tt) Tổng quát MUX 2k:1 có thể thực hiện được các hàm (k+1) biến → được xem là ULMk+1. Ví dụ 2.9: Thực hiện các hàm hai biến trên MUX 2:1 6.2. Cài đặt bằng ULM (tt) Ví dụ 2.10: Sử dụng MUX 4:1 như một ULM3 6.2. Cài đặt bằng ULM (tt) Khai triển Shannon: Có thể khai triển tiếp cho các biến X2, X3, … Ví dụ 2.11: Các cấu trúc có thể của ULM4 6.2. Cài đặt bằng ULM (tt) Ví dụ 2.12: Các cấu trúc có thể của ULM5 6.2. Cài đặt bằng ULM (tt) Ví dụ 2.13: Thiết kế ASM của ví dụ 2.4 bằng các phần tử ULM4 6.2. Cài đặt bằng ULM (tt) Ví dụ 2.13: Thiết kế hàm kích thích của ví dụ 2.4 dùng JK-FF 6.2. Cài đặt bằng ULM (tt) Trường hợp hàm dư có nhiều hơn 1 biến: Ví dụ 2.14: Thiết kế hàm trạng thái kế tiếp cho ví dụ 2.5 6.2. Cài đặt bằng ULM (tt) Dạng tổng quát của thiết kế ASM dùng ULM: Bài tập Thực hiện bảng ASM sau chỉ dùng ULM và D-FF: Q&A