Digital Circuits I
DAPA E.T.S.I. Informtica Universidad de Sevilla 10/2012
Jorge Juan <jjchico@dte.us.es> 2010, 2011, 2012 You are free to copy, distribute and communicate this work publicly and make derivative work provided you cite the source and respect the conditions of the Attribution-Share alike license from Creative Commons. You can read the complete license at: http://creativecommons.org/licenses/by-sa/3.0
Departamento de Tecnologa Electrnica Universidad de Sevilla
Contents
Logic functions
Logic operators Logic expressions Canonical forms Design approach
Boolean algebra Expression minimization Don't cares Functional analysis Timing analysis
Departamento de Tecnologa Electrnica Universidad de Sevilla
Logic functions
a b c
Formal specification (truth table) logic function
z
Verbal specification
Output a "1" if two or more inputs are equal to "1". Output "0" otherwise.
abc 000 001 010 011 100 101 110 111
z 0 0 0 1 0 1 1 1
Truth table: formal specification. Output value for every input combination (n inputs: 2n input values). Combinational (digital) circuits implement logic functions.
Departamento de Tecnologa Electrnica Universidad de Sevilla
Two-input logic functions
x y
xy 00 01 10 11
F0 0 0 0 0
F1 0 0 0 1
AND
F2 0 0 1 0
F3 0 0 1 1
F4 0 1 0 0
F5 0 1 0 1
F6 0 1 1 0
XOR
F7 0 1 1 1
OR
F8 1 0 0 0
F9 1 0 0 1
F10 1 0 1 0
F11 1 0 1 1
F12 1 1 0 0
F13 1 1 0 1
F14 1 1 1 0
NAND
F15 1 1 1 1
NOR XNOR
In general, there are 2(2^n) functions of n variables
Departamento de Tecnologa Electrnica Universidad de Sevilla
Logic operators and corresponding gates
x z 1 0
NOT
0 1
z=x
xy 00
z 0 0 0 1
AND
01 10 11
z=xy
x y
xy 00
z 0 1 1 1
OR
01 10 11
z=x+y
x y
Departamento de Tecnologa Electrnica Universidad de Sevilla
Logic operators and corresponding gates
xy 00 z 1 1 1 0 z 1 0 0 0 z 0 1 1 0 z 1 0 0 1
NAND
01 10 11 xy 00
z=xy
x y
NOR
01 10 11 xy 00
z=x+y
x y
XOR OR
01 10 11 xy 00
z = x y = xy + xy
x y
XNOR
01 10 11
z = x y = x y + xy
x y
Departamento de Tecnologa Electrnica Universidad de Sevilla
Logic expressions
a b c
logic function
An expression for a function can always be obtained by combining the NOT, AND and OR operators. Method: 1. For every "1" of the function, build a product term that is "1" for that input combination only. 2. Sum (OR) all the terms. The resulting expression is a sum-of-products (S-O-P) Terms containing all the literals are "minterms". The sum-of-minterms is known as "canonical form of minterms"
abc 000 001 010 011 100 101 110 111
z 0 0 0 1 0 1 1 1
z = abc + abc + abc + abc
Departamento de Tecnologa Electrnica Universidad de Sevilla
Logic expressions
a b c
logic function
An expression for a function can always be obtained by combining the NOT, AND and OR operators. Method: 1. For every "0" of the function, build a sum term that is "0" for that input combination only. 2. Multiply (AND) all the terms. The resulting expression is a product-of-sums (P-O-S) Terms containing all the literals are "maxterms". The sum-of-maxterms is known as "canonical form of maxterms"
abc 000 001 010 011 100 101 110 111
z 0 0 0 1 0 1 1 1
z = (a+b+c) (a+b+c) (a+b+c) (a+b+c)
Departamento de Tecnologa Electrnica Universidad de Sevilla
Canonical form notation
abc 000 001 010 011 100 101 110 111 abc 000 001 010 011 100 101 110 111 minterms abc abc abc abc abc abc abc abc maxterm a+b+c a+b+c a+b+c a+b+c a+b+c a+b+c a+b+c a+b+c m-notat. m0 m1 m2 m3 m4 m5 m6 m7 M-notation M0 M1 M2 M3 M4 M5 M6 M7
z = abc + abc + abc + abc z = m3 + m5 + m6 + m7 z = (3,5,6,7)
minterm: input combination for which the function is "1"
z = (a+b+c)(a+b+c)(a+b+c)(a+b+c) z = M0 M1 M2 M4 z = (0,1,2,4)
maxterm: input combination for which the function is "0"
Departamento de Tecnologa Electrnica Universidad de Sevilla
Logic design approach
z = abc + abc + abc + abc
S-O-P can be directly mapped to a digital circuits using three basic gates: - Inverters (complements) - AND (products) - OR (sum)
b z c
Is the result minimum?
Departamento de Tecnologa Electrnica Universidad de Sevilla
Contents
Logic functions Boolean algebra Expression minimization Don't cares Functional analysis Timing analysis
Departamento de Tecnologa Electrnica Universidad de Sevilla
Boolean algebra
{NOT, AND, OR} operators are a "Boolean algebra"
x+0 = x x+1 = 1 x+x = x x+x = 1 (x) = x x+y = y+x (x+y)+z = x+(y+z) x(y+z) = (xy)+(xz) (xy)+(xy) = x (x+y+...) = xy... x1=x x0=0 xx=x xx=0 xy = yx (xy)z = x(yz) x+(yz) = (x+y)(x+z) (x+y)(x+y) = x (xy...) = x+y+...
Elementary
George Boole (1815-1864)
Commutativity Associativity Distributivity Reduction De Morgan's
Duality: if an expression holds, the expression that results from interchanging + with and 0 with 1 also holds.
Departamento de Tecnologa Electrnica Universidad de Sevilla
Boolean algebra
Precedence of over +
x+(yz) = x+yz x+yz = x+yz
"" can be omitted
Departamento de Tecnologa Electrnica Universidad de Sevilla
Minimization
xy + xy = x
"x" can be any expression
z = abc + abc + abc + abc
0-term
z = bc
ac
ab
1-term
One term can be used more than once (we cannot simplify one term at a time).
Implicant of a function - Product term that can be part of a S-O-P expression of a function - Product term that "covers" some minterms of a function
Departamento de Tecnologa Electrnica Universidad de Sevilla
Minimization summary
Karnaugh maps (manual)
Tedious and error-prone for 5 or 6-input functions. Unfeasible for >6. Not feasible for a large number of inputs. Computational time increases exponentially with n. of inputs (32 inputs ~1015 prime implicants)
Quine-McCluskey
Alternative: Heuristic logic minimizers Implemented in logic synthesis tools
Departamento de Tecnologa Electrnica Universidad de Sevilla
Manual design process (summary)
Functional description (verbal?) Minimal S-O-P/P-O-S
Formalization No. of inputs and outputs Don't cares
Gate selection AND-OR or NAND-NAND? OR-AND or NOR-NOR? Single or dual rail?
Truth table/K-map Circuit Minimization "Only NAND" means SOP "Only NOR" means POS "Optimal" means try SOP&POS
a b c d
Departamento de Tecnologa Electrnica Universidad de Sevilla
Design example
Design a combinational circuit with four inputs (x3, x2, x1, x0) that represent the bits of a BCD digit X, and two outputs (c1, c0) that represents the bits of a magnitude C, where C is the quotient of the division X/3. E.g. if X=7 C=2, that is, (x3,x2,x1,x0)=(0,1,1,1) (c1,c0)=(1,0) Design the circuit using a minimum two-level structure of only NAND gates.
Departamento de Tecnologa Electrnica Universidad de Sevilla
Contents
Logic functions Boolean algebra Expression minimization Don't cares Functional analysis Timing analysis
Departamento de Tecnologa Electrnica Universidad de Sevilla
Functional analysis
x z y x xz z f(x,y,z) = x z + xyz xyz
Method. Starting at primary inputs:
For each gate with known inputs, calculate the equation at the gate's output. Repeat until the equations of all circuit outputs are known. Convert to a more useful representation: truth table, K-map, Give a verbal description of the operation (if possible).
Departamento de Tecnologa Electrnica Universidad de Sevilla
Timing analysis
x z y
y=1
I1 A1 I2 f(x,y,z) A2
I1 = x I2 = z A1 = I1 I2 A2 = x y z f = A1 + A2
Method:
y=1
I1 = x I2 = z A1 = I1 I2 A2 = x z f = A1 + A2
x z
I1 I2
A1 A2 f
0 10 20 30 40 50 60 70 80 90 100 t(ns)
For every gate: equations of the output as a function of the inputs. Substitute constant input values (DO NOT SUBSTITUTE ANYTHING ELSE) Draw node curves from primary inputs to the outputs. Delay every output transition by the gate's delay time (simple model: same delay for every gate: )
Departamento de Tecnologa Electrnica Universidad de Sevilla
