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

19 trang thamphan 3380

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:

bai_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

Chapter 6: Multilevel Combinational Circuits Name: Lương Văn Minh No. : 09070452
Overview 6.1 Boolean Networks 6.2 Special Classes of Circuits 6.3 Binary Decision Diagrams 3
6.1 Boolean Networks (cont.) Directed acyclic graph (DAG) G = (V, E) example: 5
6.1 Boolean Networks (cont.) Boolean Networks example: ➜ 7
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.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
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
Overview 6.1 Boolean Networks 6.2 Special Classes of Circuits 6.3 Binary Decision Diagrams 15
6.3 Binary Decision Diagrams (cont.) BDDs example: 17
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