Bài giảng Tổng hợp luận lý vi mạch - Chương 2: Mạch tổ hợp 2 mức

Nội dung text: Bài giảng Tổng hợp luận lý vi mạch - Chương 2: Mạch tổ hợp 2 mức

1. dce dce 2008 2008 Giới thiệu •Mạch tổ hợp 2 mức có thể được biểu diễn ở nhiều dạng khác nhau: – Sum-of-Product – Product-of-Sum Chương 2: Mạch tổ hợp 2 mức – NAND-NAND – NOR-NOR ¾Giới thiệu – ¾Mảng logic lập trình được BK • Sum-of-Product TP.HCM ¾ Các tính chất căn bản và dư thừa –Mức thứ nhất của các cổng là AND ¾ Các phép toán Bool trên các hàm logic –Mức thứ hai của các cổng là OR ¾ Biến đổi trên Cube và Cover –Cóthể xem là mạch tổ hợp 3 mức nếu tính cả cổng not ¾ Độ phức tạp của mạch 2 mức Logic Synthesis 2 dce dce 2008 Giới thiệu 2008 Thuật ngữ-Căn bản • Đại số Boole gồm một tập giá trị B = {0, 1} và hai phép toán “+” và “⋅” •Mỗi biến Boole nhận một trong hai giá trị 0 hoặc 1 •Mỗi biến Boole a có phần Sum-of-Product NAND-NAND bù kí hiệu a’ •Một không gian nhiều chiều được bao phủ bởi một tập hợp n biến Boole được biểu diễn bằng Bn •Mỗi điểm trong không gian Bn được gọi là đỉnh và được biểu diễn bởi một vector nhị Product-of-Sum NOR-NOR phân n chiều Logic Synthesis 3 Logic Synthesis 4
2. dce dce 2008 Thuật ngữ-Cube 2008 Thuật ngữ-Minterm •Một cube cũng có thể biểu diễn theo một vector nhị phân. • Minterm: là một cube mà trong đótất cả các •Một cube của một hàm Bool f với N ngõ nhập và M ngõ xuất biến đều xuất hiện được biểu diễn là: • Minterm có thể được biểu diễn bởi một đỉnh c = [c1, , cN, cN+1, , cN+M] với 1 ≤ i ≤ N: trong N-cube c là 0 nếu biến x là bù trong c i i • Minterm m1 là lớn hơn ci là 1 nếu biến xi không bù trong c (dominate) m2 (m1>m2) ci là _ hoặc x nếu xi không xuất hiện trong c với N+1 ≤ i ≤ N+M nếu mỗi vị trí mà m2 có 1 c là 0 nếu c thuộc tập OFF-set của ngõ xuất i-N của f i thì m1 cũng có 1 ci là 1 nếu c thuộc tập ON-set của ngõ xuất i-N của f ci là _ nếu c thuộc tập DC-set của ngõ xuất i-N của f Logic Synthesis 9 Logic Synthesis 10 dce dce 2008 Thuật ngữ-Cover 2008 Thuật ngữ-Implicant • Cover: được định nghĩa là một tập các cube và • Implicant: 1 cube chỉ chứa các tập đỉnh ON-set và được biểu diễn dưới dạng tổng các tích DC-set của hàm Bool f thì được gọi là một Implicant –Vídụ: tập 2 cube {{a, b, c}, {d, e, f}} là một cover đơn ngõ • Prime implicant/prime: là một implicant mà nhập được biểu diễn: abc+def – không chứa bất kỳ một implicant khác nào của f • Contains (chứa): cube q là chứa cube r khi và chỉ –vàcũng không hoàn toàn chứa trong DC-set của f. khi: • Essential Prime implicant/essential prime là một –Tập các literal của q là tập con của tập literal của r prime mà chứa 1 hoặc nhiều tập ON-set mà không – Các output của q là tập cha của các output của r chứa trong bất kỳ một prime implicant nào khác –Vídụ: • Optional prime implicant là một prime implicant mà • cube [0- , 1] contains (chứa) cube[00, 1] • Cube[0-, 11] contains cube[0-,10] tất cả các đỉnh được chứa trong các prime implicant khác Logic Synthesis 11 Logic Synthesis 12
3. dce dce 2008 Biến đổi trên Cube và Cover 2008 Biến đổi trên Cube và Cover • Phép giao trên cube •Giải thuật Disjoint SHARP –q = c ∩ d •Ký hiệu: Ө –Tập literal là hội của literal trong c và d • Được sử dụng để tính C – D hay C ∩ D với C, D là –qi = ci nếu (ci = di ∨ di = X) các cover. –qi = di nếu ci = X –Nếu (ci = 1 ∧ di = 0) ∨ (ci = 0 ∧ di = 1) thì q = φ –Vídụ: • 11X ∩ X10 = 110 • 11X ∩ X0X = φ • Phép giao trên cover: thực hiện phép giao trên từng cặp cube của các cover đó Logic Synthesis 17 Logic Synthesis 18 dce dce 2008 Biến đổi trên Cube và Cover 2008 Biến đổi trên Cube và Cover •Giải thuật Disjoint SHARP •Vídụ: cho d là _ _ 11, c là _ _ _ _ •Thực hiện phép trừ một cube c cho một cube d (c Ө •c Ө d = ? d) –Nếu c ∩ d = φ thì c Ө d = c –Ngược lại: 1. Q = φ , q = c 2. i= 0 3. i = i + 1, nếu i > N (số literal) đến bước 7 4. Nếu (qi = di) ∨ (di là x) thì đến bước 3 5. Nếu qi = x, gán p = q, loại trừ pi= d i , Q = Q ∨ p di 6. Gán qi vào di trở lại bước 3 7. c Ө d đã được tính trong Q Logic Synthesis 19 Logic Synthesis 20