Bài giảng Mạch tổ hợp nhiều mức

Nội dung text: Bài giảng Mạch tổ hợp nhiều mức

1. Mạch tổ hợp nhiều mức TrầnAnhĐiền 10070475 Hoàng Văn Long 10070485 Võ Bảo Hùng 09070441 1
2. Cây quyết định nhị phân thứ tự • OBDD (Order Binary Decision Diagram) –Làmột đồ thị không có chu trình. – Đỉnh terminal biểudiễnbằng hình vuông. – Đỉnh nonterminal biểudiễnbằng hình tròn. – Đỉnh con low đượctrỏđếnbởicạnh 0. – Đỉnh con high đượctrỏđếnbởicạnh 1. •OBDD biểudiễn OFF-set và ON-set củamột hàm dướidạng các cover tách biệt nhau. –Mỗi cube củacover: đường từđỉnh gốc đến đỉnh terminal củacây. 3
3. Cây quyết định nhị phân thứ tự •Thứ tự a = 1, b = 2, c = 3 Thứ tự c = 1, a = 2, b =3 5
4. Xây dựng BDD dùng khai triển Shannon 7
5. Rút gọn OBDD 9
6. Ví dụ 11
7. Các định nghĩa •Một OBDD G là rút gọn (reduced) nếunó – Không chứa đỉnh v nào với low(v) = high(v) – Không chứahaiđỉnh v, w nào mà đồ thị con có đỉnh gốclàv và w là đẳng cấu. 13
8. Mạch tương đương sử dụng ROBDD •Phương pháp kiểmtrasự tương đương giữa hai mạch luận lý 2 hay nhiềumức •Lựachọnthứ tự giống nhau cho các ngõ nhậpcơ bản của2 mạch •Xâydựng ROBDD cho các ngõ xuấtcơ bảncủa2 mạch •Kiểm tra tính đẳng cấucủa 2 ROBDD đãxâydựng để xác định sự tương đương của2 mạch 15
9. Ảnh hưởng của thứ tự biến 17
10. Cofactor •Cofactor của ROBDD đốivớibiếnxi •Thaythế tấtcả các đỉnh v với index(v) = i bằng high(v) •Cofactor của ROBDD đốivớibiếnx’i •Thaythế tấtcả các đỉnh v với index(v) = i bằng low(v) 19
11. Cofactor • Thay thế tấtcả các đỉnh v với index(v) = i bằng low(v) a1 a1 b1 Cofactor a2 a2 theo b1’ a2 b2 b2 b2 0 1 0 1 0 1 F = a1b1 + a2b2 Fb'1= a2b2 21
12. Cạnh đảo F = a.b.x + a'.y + b'.y = a.b.x + (a.b)'.y x x y y a a a b b b 0 1 0 1 0 1 23
13. Toán tử APPLY – Giải thuật thực hiện • Độ phứctạp hàm mũ theo số biến ngõ nhập •Mỗilầngọi APPLY cho đỉnh nonterminal: gọi2 lần đệ qui •2 phương pháp tinh chế •Ápdụng các trường hợp đặcbiệt •Tạobảng lưutrữ các node đãtạotrước đó • Độ phứctạp: O(|G1|.|G2|) 25
14. Toán tử APPLY – Ví dụ F = a AND c a1 a (a1,c1) a a AND (a3,c1) c1 c c c 0 1 0 1 0.c 1.0 1.1 0 1 a2 a3 c2 c3 (a2,c1) (a3,c2) (a3,c3) • APPLY(a1,c1) • APPLY(a2,c1) • APPLY(a2,c2)=0, APPLY(a2,c3)=0 • APPLY(a3,c1) • APPLY(a3,c2)=0, APPLY(a3,c3)=1 27
15. Toán tử APPLY – Ví dụ 29
16. Mạng Multiplexor-based •Mỗi multiplexor hiệnthực cho hàm luậnlý f = x.p + x’.q •Mạng multiplexor-based • Thành phầncơ bảnlàcácmulitplexor •liênhệ trựctiếpvới BDD và tương đương với hàm luậnlýbiểudiễnbởiBDD p f q x 31
17. Mạng Multiplexor-based Mạch 2 mức BDD tương ứng b a f a c c c b 0 1 33
18. Mạng Multiplexor-based a b c a F1 F1 b c c • Đỉnh a •low(a)= c 0 1 • high(a) = 1 Multiplexor thay thế cho đỉnh a f = a’.f + a.f = c + a low(a) high(a) 35
19. ThankThank youyou 37