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

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ểu diễn bằng hình vuông.
– Đỉnh nonterminal biểu diễn bằng hình tròn.
– Đỉnh con low được trỏ đến bởi cạnh 0.
– Đỉnh con high được trỏ đến bởi cạnh 1.
• OBDD biểu diễn OFF-set và ON-set của một
hàm dưới dạng các cover tách biệt nhau.
– Mỗi cube của cover: đường từ đỉnh gốc đến đỉnh
terminal của cây
pdf 37 trang thamphan 27/12/2022 1840
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Mạch tổ hợp nhiều mức", để tải tài liệu gốc về máy hãy click vào nút Download ở trên.

File đính kèm:

  • pdfbai_giang_mach_to_hop_nhieu_muc.pdf

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