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ÁIDÙNG LƯU ĐỒ ASMBài giảng mơn Kỹ thuật số 21Giảng viên: Nguyễn Hữu Chân Thành1. CẤU TRÚC CỦA LƯU ĐỒ ASMLư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) Bài giảng mơn Kỹ thuật số 22Giảng viên: Nguyễn Hữu Chân Thành1. 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. Bài giảng mơn Kỹ thuật số 23Giảng viên: Nguyễn Hữu Chân Thành1. 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).Bài giảng mơn Kỹ thuật số 24Giảng viên: Nguyễn Hữu Chân Thành1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt)Bài giảng mơn Kỹ thuật số 25Giảng viên: Nguyễn Hữu Chân Thành1. 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. Bài giảng mơn Kỹ thuật số 26Giảng viên: Nguyễn Hữu Chân Thành1. 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.Bài giảng mơn Kỹ thuật số 27Giảng viên: Nguyễn Hữu Chân Thành1. 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 Bài giảng mơn Kỹ thuật số 28Giảng viên: Nguyễn Hữu Chân Thành1. 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. Bài giảng mơn Kỹ thuật số 29Giảng viên: Nguyễn Hữu Chân Thành1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt)Biểu đồ ASM với các đường nối saiBài giảng mơn Kỹ thuật số 210Giảng viên: Nguyễn Hữu Chân Thành1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt)Một vài cấu trúc biểu đồ ASM đúngBài giảng mơn Kỹ thuật số 211Giảng viên: Nguyễn Hữu Chân Thành1. 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. Bài giảng mơn Kỹ thuật số 212Giảng viên: Nguyễn Hữu Chân Thành1. 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. Bài giảng mơn Kỹ thuật số 213Giảng viên: Nguyễn Hữu Chân Thành1. CẤU TRÚC CỦA LƯU ĐỒ ASM (tt)Bài giảng mơn Kỹ thuật số 214Giảng viên: Nguyễn Hữu Chân Thành1. 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:Bài giảng mơn Kỹ thuật số 215Giảng viên: Nguyễn Hữu Chân Thành1. 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 giảng mơn Kỹ thuật số 216Giảng viên: Nguyễn Hữu Chân ThànhBài tậpHoàn tất giản đồ thời gian cho lưu đồ ASM sau:Bài giảng mơn Kỹ thuật số 217Giảng viên: Nguyễn Hữu Chân Thành2. THÀNH LẬP LƯU ĐỒ ASMCá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. Bài giảng mơn Kỹ thuật số 218Giảng viên: Nguyễn Hữu Chân Thành2. THÀNH LẬP LƯU ĐỒ ASM (tt)Lưu đồ ASM cho ví dụ 2.2: Bài giảng mơn Kỹ thuật số 219Giảng viên: Nguyễn Hữu Chân Thành2. 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. Bài giảng mơn Kỹ thuật số 220Giảng viên: Nguyễn Hữu Chân Thành2. THÀNH LẬP LƯU ĐỒ ASM (tt)Lưu đồ ASM cho ví dụ 2.3: Bài giảng mơn Kỹ thuật số 221Giảng viên: Nguyễn Hữu Chân Thành3. THÀNH LẬP BẢNG ASMXét lưu đồ ASM sau:Bài giảng mơn Kỹ thuật số 222Giảng viên: Nguyễn Hữu Chân Thành3. THÀNH LẬP BẢNG ASM (tt)Các khối ASM và các đường nối:Bài giảng mơn Kỹ thuật số 223Giảng viên: Nguyễn Hữu Chân Thành3. THÀNH LẬP BẢNG ASM (tt)Các bảng trạng thái kế tiếp Bài giảng mơn Kỹ thuật số 224Giảng viên: Nguyễn Hữu Chân Thành3. THÀNH LẬP BẢNG ASM (tt)Bảng đầu ra trạng thái Bài giảng mơn Kỹ thuật số 225Giảng viên: Nguyễn Hữu Chân Thành3. THÀNH LẬP BẢNG ASM (tt)Bảng đầu ra điều kiệnBài giảng mơn Kỹ thuật số 226Giảng viên: Nguyễn Hữu Chân Thành3. THÀNH LẬP BẢNG ASM (tt)Bảng ASM kết hợp Bài giảng mơn Kỹ thuật số 227Giảng viên: Nguyễn Hữu Chân Thành3. THÀNH LẬP BẢNG ASM (tt)Các bảng hàm hệ thống cho ASM Bài giảng mơn Kỹ thuật số 228Giảng viên: Nguyễn Hữu Chân Thành4. LIÊN KẾT CÁC MÁY TRẠNG THÁITá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ộ Bài giảng mơn Kỹ thuật số 229Giảng viên: Nguyễn Hữu Chân Thành4. 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ọiBài giảng mơn Kỹ thuật số 230Giảng viên: Nguyễn Hữu Chân Thành4. 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 nhauBài giảng mơn Kỹ thuật số 231Giảng viên: Nguyễn Hữu Chân Thành4. LIÊN KẾT CÁC MÁY TRẠNG THÁI (tt)Liên kết song songBài giảng mơn Kỹ thuật số 232Giảng viên: Nguyễn Hữu Chân ThànhBài tậpMột thuật toán máytrạng thái được xác địnhbởi lưu đồ ASM cho trênhình. Vẽ mỗi khối ASMvà các đường nối. Xâydựng bảng ASM kết hợp. Bài giảng mơn Kỹ thuật số 233Giảng viên: Nguyễn Hữu Chân ThànhGiảiCác khối ASM và các đường nốiBài giảng mơn Kỹ thuật số 234Giảng viên: Nguyễn Hữu Chân ThànhGiảiBảng ASM kết hợpBài giảng mơn Kỹ thuật số 235Giảng viên: Nguyễn Hữu Chân ThànhMột thuật toán máytrạng thái được xác địnhbởi lưu đồ ASM cho trênhình. Vẽ mỗi khối ASMvà các đường nối.Xây dựng bảng ASMkết hợp. Bài giảng mơn Kỹ thuật số 236Giảng viên: Nguyễn Hữu Chân Thành5. NÉN BẢNG KARNAUGHCó thể chuyển bảngKarnaugh của các hàmnhiều biến thành bảngnhỏ hơn bằng cách nhậpcác biến dư vào bảng.Ví dụ: Bảng Karnaugh3 biến được nén thành dạng2 biến Bài giảng mơn Kỹ thuật số 237Giảng viên: Nguyễn Hữu Chân Thành5. NÉN BẢNG KARNAUGH (tt)Ba cách nén hàm 3 biến:Bài giảng mơn Kỹ thuật số 238Giảng viên: Nguyễn Hữu Chân Thành5. NÉN BẢNG KARNAUGH (tt)Bốn cách nén hàm 4 biến thành 3 biến:Bài giảng mơn Kỹ thuật số 239Giảng viên: Nguyễn Hữu Chân Thành5. NÉN BẢNG KARNAUGH (tt)Nén thành bảng 2 biến:Bài giảng mơn Kỹ thuật số 240Giảng viên: Nguyễn Hữu Chân Thành5. NÉN BẢNGKARNAUGH (tt)Sáu khả năngnén bảng 4 biếnthành 2 biến:Bài giảng mơn Kỹ thuật số 241Giảng viên: Nguyễn Hữu Chân Thành5. NÉN BẢNG KARNAUGH (tt)Áp dụng để rút ra bảng Karnaugh nén từ bảng ASM:Bài giảng mơn Kỹ thuật số 242Giảng viên: Nguyễn Hữu Chân Thành5. NÉN BẢNG KARNAUGH (tt)Áp dụng để rút ra bảng Karnaugh nén từ bảng ASM:Bài giảng mơn Kỹ thuật số 243Giảng viên: Nguyễn Hữu Chân Thành5. 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:Bài giảng mơn Kỹ thuật số 244Giảng viên: Nguyễn Hữu Chân Thành5. 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:Bài giảng mơn Kỹ thuật số 245Giảng viên: Nguyễn Hữu Chân Thành5. NÉN BẢNG KARNAUGH (tt)Ví dụ 2.4: (tt)Bài giảng mơn Kỹ thuật số 246Giảng viên: Nguyễn Hữu Chân Thành5. 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:Bài giảng mơn Kỹ thuật số 247Giảng viên: Nguyễn Hữu Chân Thành5. 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:Bài giảng mơn Kỹ thuật số 248Giảng viên: Nguyễn Hữu Chân Thành5. 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.Bài giảng mơn Kỹ thuật số 249Giảng viên: Nguyễn Hữu Chân Thành5. 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:Bài giảng mơn Kỹ thuật số 250Giảng viên: Nguyễn Hữu Chân Thành5. 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 giảng mơn Kỹ thuật số 251Giảng viên: Nguyễn Hữu Chân ThànhBà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: Bài giảng mơn Kỹ thuật số 252Giảng viên: Nguyễn Hữu Chân Thành6. CÀI ĐẶT ASM6.1. Cài đặt bằng cổng rời rạcVí dụ 2.8: Cài đặt mạch cho bảng ASM trong ví dụ 2.4:Bài giảng mơn Kỹ thuật số 253Giảng viên: Nguyễn Hữu Chân Thành6.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 Bài giảng mơn Kỹ thuật số 254Giảng viên: Nguyễn Hữu Chân Thành6.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 Bài giảng mơn Kỹ thuật số 255Giảng viên: Nguyễn Hữu Chân Thành6.2. Cài đặt bằng ULM (tt)Ví dụ 2.10: Sử dụng MUX 4:1 như một ULM3 Bài giảng mơn Kỹ thuật số 256Giảng viên: Nguyễn Hữu Chân Thành6.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 Bài giảng mơn Kỹ thuật số 257Giảng viên: Nguyễn Hữu Chân Thành6.2. Cài đặt bằng ULM (tt)Ví dụ 2.12: Các cấu trúc có thể của ULM5 Bài giảng mơn Kỹ thuật số 258Giảng viên: Nguyễn Hữu Chân Thành6.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 Bài giảng mơn Kỹ thuật số 259Giảng viên: Nguyễn Hữu Chân Thành6.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-FFBài giảng mơn Kỹ thuật số 260Giảng viên: Nguyễn Hữu Chân Thành6.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 Bài giảng mơn Kỹ thuật số 261Giảng viên: Nguyễn Hữu Chân Thành6.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 giảng mơn Kỹ thuật số 262Giảng viên: Nguyễn Hữu Chân ThànhBài tậpThực hiện bảng ASM sau chỉ dùng ULM và D-FF: Bài giảng mơn Kỹ thuật số 263Giảng viên: Nguyễn Hữu Chân ThànhQ&ABài giảng mơn Kỹ thuật số 264Giảng viên: Nguyễn Hữu Chân Thành