DOC PREVIEW
MIT 6 111 - Logic Synthesis

This preview shows page 1-2-3-27-28-29 out of 29 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 29 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Logic Synthesis • Truth tables and sum-of-products • Primitive logic gates, universal gates • Logic simplification • Karnaugh Maps, Quine-McCluskey • General implementation techniques: muxes and look-up tables (LUTs) 6.111 Fall 2008 1 Lecture 2 Reminder: Lab #1 due this Thursday!Functional Specifications Output “1” if at least 2 out of 3 of my inputs are a “1”. Otherwise, output “0”. I will generate a valid output in no more than 2 minutes after seeing valid inputs input A input B input C output Y A B C Y 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 An concise, unambiguous technique for giving the functional specification of a combinational device is to use a truth table to specify the output value for each possible combination of input values (N binary inputs -> 2N possible combinations of input values). 3 binary inputs so 23 = 8 rows in our truth table 6.111 Fall 2008 2 Lecture 2Here’s a Design Approach -it’s systematic! -it works! -it’s easy! -are we done yet??? 1. Write out our functional spec as a truth table 2. Write down a Boolean expression with terms covering each ‘1’ in the output: This approach creates equations of a particular form called SUM-OF-PRODUCTS Sum (+): ORs Products (•): ANDs € Y = A ⋅ B ⋅ C + A ⋅ B ⋅ C + A ⋅ B ⋅ C + A ⋅ B ⋅ CA B C Y 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 6.111 Fall 2008 3 Lecture 2S-O-P Building Blocks INVERTER: € = A A Z 0 1 1 0 AND: € = A ⋅ BA B Z 0 0 0 0 1 0 1 0 0 1 1 1 OR: € = A + BA B Z 0 0 0 0 1 1 1 0 1 1 1 1 Bubble indicates inversion 6.111 Fall 2008 4 Lecture 2Straightforward Synthesis We can use SUM-OF-PRODUCTS to implement any logic function. Only need 3 gate types: INVERTER, AND, OR Propagation delay: • 3 levels of logic • No more than 3 gate delays assuming gates with an arbitrary number of inputs. But, in general, we’ll only be able to use gates with a bounded number of inputs (bound is ~4 for most logic families). 6.111 Fall 2008 5 Lecture 2ANDs and ORs with > 2 inputs € = A ⋅ B ⋅ C€ = A ⋅ B ⋅ C ⋅ D€ = A ⋅ B ⋅ C ⋅ DWhich one should I use? Chain: Propagation delay increases linearly with number of inputs Tree: Propagation delay increases logarithmically with number of inputs Replace 2-input AND gates with 2-input OR gates to create large fan-in OR gates 6.111 Fall 2008 6 Lecture 2SOP w/ 2-input gates INV AND2 OR2 tPD 8ps 15ps 18ps tCD 1ps 3ps 3ps Using the timing specs given to the left, what are tPD and tCD for this combinational circuit? Hint: to find overall tPD we need to find max tPD considering all paths from inputs to outputs. Previous example restricted to 2-input gates: 6.111 Fall 2008 7 Lecture 2More Building Blocks NAND (not AND) € = A ⋅ BNOR (not OR) € = A + BXOR (exclusive OR) € = A ⊕ BA B Z 0 0 0 0 1 1 1 0 1 1 1 0 CMOS gates are naturally inverting so we want to use NANDs and NORs in CMOS designs… XOR is very useful when implementing parity and arithmetic logic. Also used as a “programmable inverter”: if A=0, Z=B; if A=1, Z=~B Wide fan-in XORs can be created with chains or trees of 2-input XORs. A B Z 0 0 1 0 1 1 1 0 1 1 1 0 A B Z 0 0 1 0 1 0 1 0 0 1 1 0 6.111 Fall 2008 8 Lecture 2Universal Building Blocks NANDs and NORs are universal: Any logic function can be implemented using only NANDs (or, equivalently, NORs). Note that chaining/treeing technique doesn’t work directly for creating wide fan-in NAND or NOR gates. But wide fan-in gates can be created with trees involving both NANDs, NORs and inverters. = = = = = = 6.111 Fall 2008 9 Lecture 2SOP with NAND/NOR When designing with NANDs and NORs one often makes use of De Morgan’s laws: NAND form: NOR form: So the following “SOP” circuits are all equivalent (note the use of De Morgan-ized symbols to make the inversions less confusing): € A ⋅ B = A + B€ A + B = A ⋅ B= = AND/OR form NAND/NAND form NOR/NOR form All these “extra” inverters may seem less than ideal but often the buffering they provide will reduce the capacitive load on the inputs and increase the output drive. This will be handy in Lab 1 since you’ll be able to use just 7400’s to implement your circuit! De Morgan-ized NAND symbol De Morgan-ized NOR symbol De Morgan-ized Inverter 6.111 Fall 2008 10 Lecture 2Logic Simplification • Can we implement the same function with fewer gates? Before trying we’ll add a few more tricks in our bag. • BOOLEAN ALGEBRA: OR rules: AND rules: Commutative: Associative: Distributive: Complements: Absorption: De Morgan’s Law: Reduction: € € a + 1 = 1 a + 0 = a a + a = a€ a ⋅1 = 1 a ⋅ 0 = a a ⋅ a = a€ a + b = b + a a ⋅ b = b ⋅ a€ (a + b) + c = a + (b + c) (a ⋅ b) ⋅ c = a ⋅ (b ⋅ c)€ a ⋅ (b + c) = a ⋅ b + a ⋅ c a + b ⋅ c = (a + b) ⋅ (a + c)€ a + a = 1 a ⋅ a = 0€ a + a ⋅ b = a a + a ⋅ b = a + b a ⋅ (a + b) = a a ⋅ (a + b) = a ⋅ b€ a ⋅ b + a ⋅ b = b (a + b) ⋅ (a + b) = b€ a ⋅ b = a + b a + b = a ⋅ bKey to simplification: equations that match the pattern of the LHS (where “b” might be any expression) tell us that when “b” is true, the value of “a” doesn’t matter. So “a” can be eliminated from the equation, getting rid of two 2-input ANDs and one 2-input OR. 6.111 Fall 2008 11 Lecture 2Boolean Minimization: An Algebraic Approach Lets simplify the equation from slide #3: Using the identity ααα=+ AAFor any expression α and variable A: € Y = A ⋅ B ⋅ C + A ⋅ B ⋅ C + A ⋅ B ⋅ C + A ⋅ B ⋅ C€ Y = A ⋅ B ⋅ C + A ⋅ B ⋅ C + A ⋅ B ⋅ C + …


View Full Document

MIT 6 111 - Logic Synthesis

Documents in this Course
Verilog

Verilog

21 pages

Video

Video

28 pages

Bass Hero

Bass Hero

17 pages

Deep 3D

Deep 3D

12 pages

SERPENT

SERPENT

8 pages

Vertex

Vertex

92 pages

Vertex

Vertex

4 pages

Snapshot

Snapshot

15 pages

Memories

Memories

42 pages

Deep3D

Deep3D

60 pages

Design

Design

2 pages

Frogger

Frogger

11 pages

SkiFree

SkiFree

81 pages

Vertex

Vertex

10 pages

EXPRESS

EXPRESS

2 pages

Labyrinth

Labyrinth

81 pages

Load more
Download Logic Synthesis
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Logic Synthesis and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Logic Synthesis 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?