›
›

Bài giảng Tổng hợp luận lý vi mạch - Chapter 6: Multilevel Combinational Circuits - Lương Văn Minh


6.1 Boolean Networks
A combinational logic circuits is represented as
a labeled, directed, acyclic graph (DAG)
G = (V, E).
Each vertex v labeled with the name of a
primitive gate such as AND, OR, or NOT, or
with name of a primary input or output
Each gate and edge in the circuit has an
associated delay 
pdf 19 trang thamphan 27/12/2022 2900
Download
Bạn đang xem tài liệu "Bài giảng Tổng hợp luận lý vi mạch - Chapter 6: Multilevel Combinational Circuits - Lương Văn Minh", để 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_tong_hop_luan_ly_vi_mach_chapter_6_multilevel_comb.pdf

Nội dung text: Bài giảng Tổng hợp luận lý vi mạch - Chapter 6: Multilevel Combinational Circuits - Lương Văn Minh

  1. Chapter 6: Multilevel Combinational Circuits Name: Lương Văn Minh No. : 09070452
  2. Overview 6.1 Boolean Networks 6.2 Special Classes of Circuits 6.3 Binary Decision Diagrams 3
  3. 6.1 Boolean Networks (cont.) Directed acyclic graph (DAG) G = (V, E) example: 5
  4. 6.1 Boolean Networks (cont.) Boolean Networks example: ➜ 7
  5. 6.2 Special Classes of Circuits 6.2.1 Fan-out-Free Circuits 6.2.2 Leaf-DAG Circuits 6.2.3 Algebraically Factored Circuits 6.2.4 Multiplexor-Based Circuits 9
  6. 6.2.1 Fan-out-Free Circuits (cont.) Many testability results have been proven. These are: 1. There exists a set of tests which detect all single and multiple stuck-at fault and is of minimal cardinality among all test sets for single faults. 2. The number of tests required to detect all stuck-at faults is bounded above by n:1 and is bounded below by 2√n where n is the number of circuit inputs. 3. A set of tests which detect all stuck-at faults on circuit inputs will detect all single stuck-at faults 11
  7. 6.2.3 Algebraically Factored Circuits An algebraically factored circuit is a circuit which is derived by a sequence of algebraic transformations from a two-level sum-of- products representation. For example, the circuit (a + b) . ( c + d) is an algebraic factorization of the sum-of-products expression a.c + a.d + b.c + b.d 13
  8. Overview 6.1 Boolean Networks 6.2 Special Classes of Circuits 6.3 Binary Decision Diagrams 15
  9. 6.3 Binary Decision Diagrams (cont.) BDDs example: 17
  10. 6.3 Binary Decision Diagrams (cont.) BDDs can be categorized based on two additional properties: 1. Freedom: When traversing any path from a terminal vertex to the root vertex we encounter each decision variable at most one 2. Ordered: place the restriction that for any nonterminal vertex v. if low(v) is also nonterminal then must have index(v) < index(low(v)) if high(v) is also nonterminal then must have index(v) < index(high(v)) 19