COPE-01 Digital Logic.indd
1
Digital Logic
Uwe R. Zimmer – The Australian National University
Computer Organisation & Program Execution 2021
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 9 of 481 (chapter 1: “Digital Logic” up to page 96)
References for this chapter
[Patterson17]
David A. Patterson & John L. Hennessy
Computer Organization and Design – The Hardware/Software Interface
Appendix A “The Basics of Logic Design”
ARM edition, Morgan Kaufmann 2017
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 10 of 481 (chapter 1: “Digital Logic” up to page 96)
It starts with a thought …
An Investigation of the Laws of Thought
on Which are Founded the Mathematical
Theories of Logic and Probabilities
by George Boole, 1854
George Bool, 1815-1864
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 11 of 481 (chapter 1: “Digital Logic” up to page 96)
Boolean Values & Operators
There are two values:
e.g. True and False. (aka “1” and “0”)
Two binary operators on expressions a, b:
a b0 (aka a b+ or “a OR b” or SUM)
a b/ (aka a b$ or “a AND b” or PRODUCT)
One unary operator on an expression a:
a (aka aJ or alor “NOT a”)
Truth tables:
a b a b0 a b/ a
False False False False True
True False True False False
False True True False
True True True True
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 12 of 481 (chapter 1: “Digital Logic” up to page 96)
Axiomatic Boolean Algebra (Whitehead 1898)
0-Laws /-Laws
a a0 = a a a/ = a (redundant)
a b0 = b a0 a b/ = b a/ (commutative)
a b c0 0^ h = a b c0 0^ h a b c/ /^ h = a b c/ /^ h (associative)
a a b0 /^ h = a (absorption)
a b c/ 0^ h = a b a c/ 0 /^ ^h h (distribution)
Truea / = a (identity)
(constant)
a a0 = True a a/ = False (inverse)
DeMorgan
(double not)
N ti l U i it
Algebras allow for easier
reasoning than truth tables.
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 13 of 481 (chapter 1: “Digital Logic” up to page 96)
Axiomatic Boolean Algebra (Huntington 1904)
0-Laws /-Laws
(redundant)
a b0 = b a0 a b/ = b a/ (commutative)
(associative)
(absorption)
a b c0 /^ h = a b a c0 / 0^ ^h h a b c/ 0^ h = a b a c/ 0 /^ ^h h (distribution)
a False0 = a Truea / = a (identity)
(constant)
a a0 = True a a/ = False (inverse)
DeMorgan
(double not)
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 14 of 481 (chapter 1: “Digital Logic” up to page 96)
Axiomatic Boolean Algebra
… many other axiomatic formulations of Boolean algebra exist.
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 15 of 481 (chapter 1: “Digital Logic” up to page 96)
Redundant Boolean Algebra
0-Laws /-Laws
a a0 = a a a/ = a (redundant)
a b0 = b a0 a b/ = b a/ (commutative)
a b c0 0^ h = a b c0 0^ h a b c/ /^ h = a b c/ /^ h (associative)
a a b0 /^ h = a a a b/ 0^ h = a (absorption)
a b c0 /^ h = a b a c0 / 0^ ^h h a b c/ 0^ h = a b a c/ 0 /^ ^h h (distribution)
a False0 = a Truea / = a (identity)
a True0 = True a False/ = False (constant)
a a0 = True a a/ = False (inverse)
a b0 = a b/ a b/ = a b0 DeMorgan
a = a
(double not)
(redundant)( d d t)
… second nature for a
computer scientist!
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 16 of 481 (chapter 1: “Digital Logic” up to page 96)
Common Boolean operators
Commonly used operators on expressions a, b to defi ne boolean algebras:
a b0 (aka a b+ or “a OR b” or SUM)
a b/ (aka a b$ or “a AND b” or PRODUCT)
a (aka aJ or alor “not a”)
Other handy operators:
a b” = a b0^ h (aka “a IMPLIES b”)
a b=^ h = a b a b/ 0 /^ ^h h (aka “a EQUALS b”)
a b5 = a b a b/ 0 /^ ^h h (aka “a EXCLUSIVE-OR b” or “a XOR b”)
a b/ = a b0^ h (aka “a NOT-AND b”or “a NAND b”)
a b0 = a b/^ h (aka “a NOT-OR b”or “a NOR b”)
NAND and NOR are the only sole suffi cient boolean operators,
i.e. you can reduce any boolean expression to only NAND or only NOR operators.
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 17 of 481 (chapter 1: “Digital Logic” up to page 96)
All binary Boolean operators
Inputs a, b Function Name Sum of products NAND Don’t cares
a F F T T build
, , x/ 0b F T F T
q
F F F F False Constant FALSE a, b
F F F T a b/ AND a b a b/ / /
F F T F a b” NOT-IMPLICATION a b/^ h
F F T T a IDENTITY a b
F T F F b a” NOT-IMPLICATION a b/^ h
F T F T b IDENTITY b a
F T T F a b5 EXCLUSIVE-OR, XOR a b a b/ 0 /^ ^h h
F T T T a b0 OR a a b b/ / /
T F F F a b0 NOT-OR, NOR a b/^ h
T F F T a b= EQUALITY, EQ a a bb 0 //^ ^h h
T F T F b INVERSE b a
T F T T b a” IMPLICATION ba 0
T T F F a INVERSE a a a/ b
T T F T a b” IMPLICATION a b0
T T T F a b/ NOT-AND, NAND a b0
T T T T True Constant True a, b
Output q
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 18 of 481 (chapter 1: “Digital Logic” up to page 96)
Combinational Logic Functions
Logic is reducible/equivalent to pure functions: there are no states!
IF the function is combinational then there is only one output for any combination of inputs,
e.g. the function can be written out as a truth table:
a b c Output q
F F F F
F F T F
F T F T
F T T F
T F F T
T F T T
T T F T
T T T F
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 19 of 481 (chapter 1: “Digital Logic” up to page 96)
Combinational Logic Functions
Logic is reducible/equivalent to pure functions: there are no states!
IF the function is combinational then there is only one output for any combination of inputs,
e.g. the function can be written out as a truth table:
a b c Output q minterms
F F F F
F F T F
F T F T a b c/ /
F T T F
T F F T a b c/ /
T F T T a b c/ /
T T F T a b c/ /
T T T F
Sum of minterms: q = a b c a b c a b c a b c/ / / / / / / /0 0 0^ ^ ^ ^h h h h
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 20 of 481 (chapter 1: “Digital Logic” up to page 96)
Combinational Logic Functions
Logic is reducible/equivalent to pure functions: there are no states!
IF the function is combinational then there is only one output for any combination of inputs,
e.g. the function can be written out as a truth table:
a b c Output q minterms Simplifi ed minterms
F F F F
F F T F
F T F T a b c/ /
b c/
F T T F
T F F T a b c/ /
a b/
T F T T a b c/ /
T T F T a b c/ /
T T T F
Sum of minterms: q = a b c a b c a b c a b c/ / / / / / / /0 0 0^ ^ ^ ^h h h h
Sum of simplifi ed minterms: q = a b b c/ 0 /^ ^h h
Simplifi cations can be done by (automated) algebraic transformations, Karnaugh maps or others
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 21 of 481 (chapter 1: “Digital Logic” up to page 96)
Combinational Logic Functions
Logic is reducible/equivalent to pure functions: there are no states!
IF the function is combinational then there is only one output for any combination of inputs,
e.g. the function can be written out as a truth table:
a b c Output q minterms Simplifi ed minterms
F F F F
F F T F
F T F T a b c/ /
b c/
F T T F
T F F T a b c/ /
a b/
T F T T a b c/ /
T T F T a b c/ /
T T T F
Sum of minterms: q = a b c a b c a b c a b c/ / / / / / / /0 0 0^ ^ ^ ^h h h h
Sum of simplifi ed minterms: q = a b b c/ 0 /^ ^h h
Simplifi cations can be done by (automated) algebraic transformations, Karnaugh maps or others
Every combinational function can
be written as a sum of products!
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 22 of 481 (chapter 1: “Digital Logic” up to page 96)
Combinational Logic Functions
Logic is reducible/equivalent to pure functions: there are no states!
IF the function is combinational then there is only one output for any combination of inputs,
e.g. the function can be written out as a truth table:
a b c Output q
F F F F
F F T F
F T F T
F T T F
T F F T
T F T T
T T F T
T T T F
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 23 of 481 (chapter 1: “Digital Logic” up to page 96)
Combinational Logic Functions
Logic is reducible/equivalent to pure functions: there are no states!
IF the function is combinational then there is only one output for any combination of inputs,
e.g. the function can be written out as a truth table:
a b c Output q maxterms
F F F F a b c0 0
F F T F a b c0 0
F T F T
F T T F a b c0 0
T F F T
T F T T
T T F T
T T T F a b c0 0
maxterms product q = a b c a b c a b c a b c0 0 / 0 0 / 0 0 / 0 0^ ^ ^ ^h h h h
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 24 of 481 (chapter 1: “Digital Logic” up to page 96)
Combinational Logic Functions
Logic is reducible/equivalent to pure functions: there are no states!
IF the function is combinational then there is only one output for any combination of inputs,
e.g. the function can be written out as a truth table:
a b c Output q maxterms Simplifi ed maxterms
F F F F a b c0 0
a b0
F F T F a b c0 0
F T F T
F T T F a b c0 0
b c0
T F F T
T F T T
T T F T
T T T F a b c0 0
maxterms product q = a b c a b c a b c a b c0 0 / 0 0 / 0 0 / 0 0^ ^ ^ ^h h h h
simplifi ed maxterms product q = a b b c0 / 0^ ^h h
Simplifi cations can be done by (automated) algebraic transformations, Karnaugh maps or others
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 25 of 481 (chapter 1: “Digital Logic” up to page 96)
Combinational Logic Functions
Logic is reducible/equivalent to pure functions: there are no states!
IF the function is combinational then there is only one output for any combination of inputs,
e.g. the function can be written out as a truth table:
a b c Output q maxterms Simplifi ed maxterms
F F F F a b c0 0
a b0
F F T F a b c0 0
F T F T
F T T F a b c0 0
b c0
T F F T
T F T T
T T F T
T T T F a b c0 0
maxterms product q = a b c a b c a b c a b c0 0 / 0 0 / 0 0 / 0 0^ ^ ^ ^h h h h
simplifi ed maxterms product q = a b b c0 / 0^ ^h h
Simplifi cations can be done by (automated) algebraic transformations, Karnaugh maps or others
Every combinational function can
be written as a product of sums!
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 26 of 481 (chapter 1: “Digital Logic” up to page 96)
Digital Electronics
Symbolic: Q A B/= Elementary logic gate symbols:
Diagram:
Technology:
≡
NAND
A
B
Q
A
B
Q
PMOS
NMOS
NAND
NAND NAND
A Q
NAND
NAND
NAND
Q
Q
A
B
A
B
NAND
NAND
NAND
NAND
A
B
Q
NOTA Q
OR Q
A
B
Q
A
B
AND
XOR
A
B
Q
≡
≡
≡
≡
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 27 of 481 (chapter 1: “Digital Logic” up to page 96)
Combinational Logic Functions
The logic equivalent to pure functions: there are no states!
IF the function is combinational then there is only one output for any combination of inputs,
e.g. the function can be written out as a truth table:
a b c Output q Minterms Simplifi ed minterms
F F F F
F F T F
F T F T a b c/ /
b c/
F T T F
T F F T a b c/ /
a b/
T F T T a b c/ /
T T F T a b c/ /
T T T F
Sum of minterms: q = a b c a b c a b c a b c/ / / / / / / /0 0 0^ ^ ^ ^h h h h
Sum of simplifi ed minterms: q = a b b c/ 0 /^ ^h h
Simplifi cations can be done by (automated) algebraic transformations, Karnaugh maps or others
b/b h
a
b
c
q
ORs
ANDs
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 28 of 481 (chapter 1: “Digital Logic” up to page 96)
Combinational Logic Functions
The logic equivalent to pure functions: there are no states!
IF the function is combinational then there is only one output for any combination of inputs,
e.g. the function can be written out as a truth table:
a b c Output q Minterms Simplifi ed minterms
F F F F
F F T F
F T F T a b c/ /
b c/
F T T F
T F F T a b c/ /
a b/
T F T T a b c/ /
T T F T a b c/ /
T T T F
Sum of minterms: q = a b c a b c a b c a b c/ / / / / / / /0 0 0^ ^ ^ ^h h h h
Sum of simplifi ed minterms: q = a b b c/ 0 /^ ^h h
Simplifi cations can be done by (automated) algebraic transformations, Karnaugh maps or others
b/b h
a
b
c
ORs
q
ANDs
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 29 of 481 (chapter 1: “Digital Logic” up to page 96)
Combinational Logic Functions
The logic equivalent to pure functions: there are no states!
IF the function is combinational then there is only one output for any combination of inputs,
e.g. the function can be written out as a truth table:
a b c Output q Minterms Simplifi ed minterms
F F F F
F F T F
F T F T a b c/ /
b c/
F T T F
T F F T a b c/ /
a b/
T F T T a b c/ /
T T F T a b c/ /
T T T F
Sum of minterms: q = a b c a b c a b c a b c/ / / / / / / /0 0 0^ ^ ^ ^h h h h
Sum of simplifi ed minterms: q = a b b c/ /0^ ^h h
Simplifi cations can be done by (automated) algebraic transformations, Karnaugh maps or others
b/b h
a
b
c
ORs
q
ANDs
combination of inputs,The number of terms
(“fan-in” for the gates)
infl uences the total delay
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 30 of 481 (chapter 1: “Digital Logic” up to page 96)
Processing Data
Encrypting a bit vector
(whatever it represents)
with a secret key:
Assuming the key is random
and not used for anything else:
This is surprisingly secure
… and extremely fast!
D0
XOR
K0
E0
Encryption
XOR
Decryption
D0
D1
XOR
K1
E1
XOR D1
D2
XOR
K2
E2
XOR D2
D3
XOR
K3
E3
XOR D3
D4
XOR
K4
E4
XOR D4
D5
XOR
K5
E5
XOR D5
D6
XOR
K6
E6
XOR D6
D7
XOR
K7
E7
XOR D7
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 31 of 481 (chapter 1: “Digital Logic” up to page 96)
Bit Vectors
Groups of bits could represent:
States, enumeration values, arrays of Booleans, numbers, etc. pp.
… or any grouping or combination of the above Algebraic Types
The form of encoding could be chosen to optimize for:
• Performance e.g. minimal decoding effort
• Redundancy / error detection e.g. large Hamming distance
• Safe transitions e.g. Gray codes
• Physical mapping e.g. maps on existing hardware interfaces
• Compactness e.g. holds the maximal number of values per memory cell
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 32 of 481 (chapter 1: “Digital Logic” up to page 96)
Encoding
Assuming a type can have 7 different values, many forms of encoding are possible:
Enumeration type
Encoding
1-bit error
detecting
1-bit error correcting
Index Value Single bit
Gray
code
Even
parity
Hamming
(7,4)
Hamming
(3,1)
Binary
1 Secured 0000001 000 0000 0000000 000000000 000
2 Taxi 0000010 001 0011 1110000 000000111 001
3 Take-off 0000100 011 0101 1001100 000111000 010
4 Cruising 0001000 010 0110 0111100 000111111 011
5 Gliding 0010000 110 1001 0101010 111000000 100
6 Approach 0100000 111 1010 1011010 111000111 101
7 Landing 1000000 101 1100 1100110 111111000 110
VHDL or Verilog gives you full control over the encoding.
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 33 of 481 (chapter 1: “Digital Logic” up to page 96)
Binary encoding
Encoding of choice if compactness is essential or you need to add values.
0 0 1 0 1 0 1 0
*20*21*22*23*24*25*26*27
32 8 2+ + = 42
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 34 of 481 (chapter 1: “Digital Logic” up to page 96)
Binary encoding
Encoding of choice if compactness is essential or you need to add values.
0 0 1 0 1 0 1 0
*20*21*22*23*24*25*26*27
32 8 2+ + = 42
0 0 0 0 0=
0 0 0 1 1=
0 0 1 0 2=
0 0 1 1 3=
0 1 0 0 4=
0 1 0 1 5=
0 1 1 0 6=
0 1 1 1 7=
1 0 0 0 8=
1 0 0 1 9=
1 0 1 0 A=
1 0 1 1 B=
1 1 0 0 C=
1 1 0 1 D=
1 1 1 0 E=
1 1 1 1 F=
Binary HexadecimalDecimal
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 35 of 481 (chapter 1: “Digital Logic” up to page 96)
Binary encoding
Encoding of choice if compactness is essential or you need to add values.
0 0 1 0 1 0 1 0
*20*21*22*23*24*25*26*27
32 8 2+ + = 42
0 0 0 0 0=
0 0 0 1 1=
0 0 1 0 2=
0 0 1 1 3=
0 1 0 0 4=
0 1 0 1 5=
0 1 1 0 6=
0 1 1 1 7=
1 0 0 0 8=
1 0 0 1 9=
1 0 1 0 A=
1 0 1 1 B=
1 1 0 0 C=
1 1 0 1 D=
1 1 1 0 E=
1 1 1 1 F=
Binary HexadecimalDecimal
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
=
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
2 A
*160
32 10+ = 42
*161
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 36 of 481 (chapter 1: “Digital Logic” up to page 96)
Half Adder
A B S C S minterms C minterms
0 0 0 0
0 1 1 0 A B/
1 0 1 0 A B/
1 1 0 1 A B/
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 37 of 481 (chapter 1: “Digital Logic” up to page 96)
Half Adder
A B S C S minterms C minterms
0 0 0 0
0 1 1 0 A B/
1 0 1 0 A B/
1 1 0 1 A B/
S = A B A B/ 0 /^ ^h h
C = A B/
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 38 of 481 (chapter 1: “Digital Logic” up to page 96)
Half Adder
A B S C S minterms C minterms
0 0 0 0
0 1 1 0 A B/
1 0 1 0 A B/
1 1 0 1 A B/
S = A B A B/ 0 /^ ^h h = A B5
C = A B/
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 39 of 481 (chapter 1: “Digital Logic” up to page 96)
Half Adder
A B S C S minterms C minterms
0 0 0 0
0 1 1 0 A B/
1 0 1 0 A B/
1 1 0 1 A B/
S = A B A B/ 0 /^ ^h h = A B5
C = A B/ A XOR
ANDB
S
C
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 40 of 481 (chapter 1: “Digital Logic” up to page 96)
Full Adder
Ai Bi C i 1- Si C i
0 0 0 0 0
0 1 0 1 0
1 0 0 1 0
1 1 0 0 1
0 0 1 1 0
0 1 1 0 1
1 0 1 0 1
1 1 1 1 1
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 41 of 481 (chapter 1: “Digital Logic” up to page 96)
Full Adder
Ai Bi C i 1- Si C i Si minterms C i minterms
0 0 0 0 0
0 1 0 1 0 A B Ci i i 1/ / –
1 0 0 1 0 A B Ci i i 1/ / –
1 1 0 0 1 A B Ci i i 1/ / –
0 0 1 1 0 A B Ci i i 1/ / –
0 1 1 0 1 A B Ci i i 1/ / –
1 0 1 0 1 A B Ci i i 1/ / –
1 1 1 1 1 A B Ci i i 1/ / – A B Ci i i 1/ / –
Si = A B C A B C A B C A B Ci i i i i i i i i i i i1 1 1 1/ / 0 / / 0 / / 0 / /- – – -_ _ _ ^i i i h
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 42 of 481 (chapter 1: “Digital Logic” up to page 96)
Full Adder
Ai Bi C i 1- Si C i Si minterms C i minterms
0 0 0 0 0
0 1 0 1 0 A B Ci i i 1/ / –
1 0 0 1 0 A B Ci i i 1/ / –
1 1 0 0 1 A B Ci i i 1/ / –
0 0 1 1 0 A B Ci i i 1/ / –
0 1 1 0 1 A B Ci i i 1/ / –
1 0 1 0 1 A B Ci i i 1/ / –
1 1 1 1 1 A B Ci i i 1/ / – A B Ci i i 1/ / –
Si = A B C A B C A B C A B Ci i i i i i i i i i i i1 1 1 1/ / 0 / / 0 / / 0 / /- – – -_ _ _ ^i i i h
= A B A B C A B A B Ci i i i i i i i i i1 1/ / / 0 / / /0 0- -__^ _ ___ ^h ii i i hi i
= A B C A B Ci i i i i i1 15 / 0 /=- -_^ ^^h i h h = A B C A B Ci i i i i i1 15 / 0 /5- -_^ __h i i i
= A B Ci i i 15 5 -^ h
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 43 of 481 (chapter 1: “Digital Logic” up to page 96)
Full Adder
Ai Bi C i 1- Si C i Si minterms C i minterms
0 0 0 0 0
0 1 0 1 0 A B Ci i i 1/ / –
1 0 0 1 0 A B Ci i i 1/ / –
1 1 0 0 1 A B Ci i i 1/ / –
0 0 1 1 0 A B Ci i i 1/ / –
0 1 1 0 1 A B Ci i i 1/ / –
1 0 1 0 1 A B Ci i i 1/ / –
1 1 1 1 1 A B Ci i i 1/ / – A B Ci i i 1/ / –
Si = A B Ci i i 15 5 -^ h
C i = A B C A B C A B C A B Ci i i i i i i i i i i i1 1 1 1/ / 0 / / 0 / / 0 / /- – – -_ _ ^ ^i i h h
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 44 of 481 (chapter 1: “Digital Logic” up to page 96)
Full Adder
Ai Bi C i 1- Si C i Si minterms C i minterms
0 0 0 0 0
0 1 0 1 0 A B Ci i i 1/ / –
1 0 0 1 0 A B Ci i i 1/ / –
1 1 0 0 1 A B Ci i i 1/ / –
0 0 1 1 0 A B Ci i i 1/ / –
0 1 1 0 1 A B Ci i i 1/ / –
1 0 1 0 1 A B Ci i i 1/ / –
1 1 1 1 1 A B Ci i i 1/ / – A B Ci i i 1/ / –
Si = A B Ci i i 15 5 -^ h
C i = A B C A B C A B C A B Ci i i i i i i i i i i i1 1 1 1/ / 0 / / 0 / / 0 / /- – – -_ _ ^ ^i i h h
= A B C A B C A B C A B Ci i i i i i i i i i i i1 1 1 1/ / / / 0 / / 0 / /0- – – -_ ^ _ ^i h i h
= A B A B A B Ci i i i i i i 1/ 0 / / /0 -^ ___ ^h i hi i
= A B A B Ci i i i i 1/ 0 5 / -^ ^^h h h
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 45 of 481 (chapter 1: “Digital Logic” up to page 96)
Full Adder
Ai Bi C i 1- Si C i Si minterms C i minterms
0 0 0 0 0
0 1 0 1 0 A B Ci i i 1/ / –
1 0 0 1 0 A B Ci i i 1/ / –
1 1 0 0 1 A B Ci i i 1/ / –
0 0 1 1 0 A B Ci i i 1/ / –
0 1 1 0 1 A B Ci i i 1/ / –
1 0 1 0 1 A B Ci i i 1/ / –
1 1 1 1 1 A B Ci i i 1/ / – A B Ci i i 1/ / –
Si = A B Ci i i 15 5 -^ h
C i = A B A B Ci i i i i 1/ 0 5 / -^ ^^h h h
Ai
XOR
AND
Bi
XOR
AND
OR
Si
Ci-1 Ci
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 46 of 481 (chapter 1: “Digital Logic” up to page 96)
Ripple Carry Adder
2 + 2 = 4 ?
A1
XOR
AND
B1
XOR
AND
OR
S1 A2
XOR
AND
B2
XOR
AND
OR
S2
C1 C2
A0
XOR
AND
B0 S0
C0
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 47 of 481 (chapter 1: “Digital Logic” up to page 96)
Ripple Carry Adder
2 + 2 = 4 !
A1
XOR
AND
B1
XOR
AND
OR
S1 A2
XOR
AND
B2
XOR
AND
OR
S2
C1 C2
A0
XOR
AND
B0 S0
C0
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 48 of 481 (chapter 1: “Digital Logic” up to page 96)
Ripple Carry Adder
2 – 1 = 1 ?
A1
XOR
AND
B1
XOR
AND
OR
S1 A2
XOR
AND
B2
XOR
AND
OR
S2
C1 C2
A0
XOR
AND
B0 S0
C0
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 49 of 481 (chapter 1: “Digital Logic” up to page 96)
Radix complements
Can we defi ne negative numbers such that our adder still works?
x x 0- =
Or: what can you add to 42 in an 8 bit binary representation
such that the result will be 28 (and hence 0 in 8 bits)?
0 0 1 0 1 0 1 0
? ? ? ? ? ? ? ?
+
=
0 0 0 0 0 0 0 01
42
-42
256
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 50 of 481 (chapter 1: “Digital Logic” up to page 96)
Radix complements
Can we defi ne negative numbers such that our adder still works?
x x 0- =
Or: what can you add to 42 in an 8 bit binary representation
such that the result will be 28 (and hence 0 in 8 bits)?
0 0 1 0 1 0 1 0
1 1 0 1 0 1 1 0
+
=
0 0 0 0 0 0 0 01
42
-42
256
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 51 of 481 (chapter 1: “Digital Logic” up to page 96)
Radix complements
Can we defi ne negative numbers such that our adder still works?
x x 0- =
Or: what can you add to 42 in an 8 bit binary representation
such that the result will be 28 (and hence 0 in 8 bits)?
0 0 1 0 1 0 1 0
1 1 0 1 0 1 1 0
+
=
0 0 0 0 0 0 0 01
42
-42
256
“Invert all bits
and add 1”
2’s-complement
(as the
radix/base is 2)
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 52 of 481 (chapter 1: “Digital Logic” up to page 96)
2’s complements
The 2’s complement encoding interprets
the natural binary range 2n 1- … 2 1n –
as negative numbers 2n 1- – … 1-
0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0……0000 00000000 1111 00000000 1111 00000000 1111 0000 ……0000 1111… 1111 00000000 1111 00000000 1111 1111 000000000 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0
0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0…
2n-1-1
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0
0 0 1 0 1 0 1 0 …1 0 0 0 0 0 0 0
-2n-1
Natural binary numbers
2’s complement binary numbers
2n-1
…
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 53 of 481 (chapter 1: “Digital Logic” up to page 96)
2’s complements
The 2’s complement encoding interprets
the natural binary range 2n 1- … 2 1n –
as negative numbers 2n 1- – … 1-
0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0……0000 00000000 1111 00000000 1111 00000000 1111 0000 ……0000 1111… 1111 00000000 1111 00000000 1111 1111 000000000 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0
0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0…
2n-1-1
0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1
0
0 0 1 0 1 0 1 0 …1 0 0 0 0 0 0 0
-2n-1
Natural binary numbers
2’s complement binary numbers
2n-1
…
It’s all in your mind!
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 54 of 481 (chapter 1: “Digital Logic” up to page 96)
Ripple Carry Adder
2 – 1 = 1 ?
A1
XOR
AND
B1
XOR
AND
OR
S1 A2
XOR
AND
B2
XOR
AND
OR
S2
C1 C2
A0
XOR
AND
B0 S0
C0
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 55 of 481 (chapter 1: “Digital Logic” up to page 96)
Ripple Carry Adder
2 – 1 = 1 !
… with an overall carry-fl ag indicated.
A1
XOR
AND
B1
XOR
AND
OR
S1 A2
XOR
AND
B2
XOR
AND
OR
S2
C1 C2
A0
XOR
AND
B0 S0
C0
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 56 of 481 (chapter 1: “Digital Logic” up to page 96)
Ripple Carry Adder
How long does it take until the
last carry fl ag stabilizes ?
A1
XOR
AND
B1
XOR
AND
OR
S1 A2
XOR
AND
B2
XOR
AND
OR
S2
C1 C2
A0
XOR
AND
B0 S0
C0
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 57 of 481 (chapter 1: “Digital Logic” up to page 96)
Ripple Carry Adder
What distinguishes the red from the green gates ?
A1
XOR
AND
B1
XOR
AND
OR
S1 A2
XOR
AND
B2
XOR
AND
OR
S2
C1 C2
A0
XOR
AND
B0 S0
C0
Carry-lookahead circuitry
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 58 of 481 (chapter 1: “Digital Logic” up to page 96)
Arithmetic Logic Unit (ALU)
Ai
XOR
AND
Bi
XOR
AND
OR
Si
Ci-1 Ci
AND
AND
AND
AND
OR
OR
OP1-4 Resulti
AND
AND
AND
AND
OP1 (ADD)
OP2 (XOR)
OP3 (AND)
OP4 (OR)
INSTR
ALU Slice i
ALU
Instruction
Decoder
A simple ALU which can ADD, XOR, AND, OR two arguments.
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 59 of 481 (chapter 1: “Digital Logic” up to page 96)
Towards States
(everything up to here was combinational logic)
How do we make operations depends on:
… an overfl ow in the previous operation?
… the state of the CPU?
… a counter having reached zero?
… two arguments having been equal?
… etc. pp.
We need to hold on to some states!
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 60 of 481 (chapter 1: “Digital Logic” up to page 96)
States
≡
Q
Q
NAND Q
NAND Q
S
R
S
R
S R Q Q
0 0 ? ?
0 1 ? ?
1 0 ? ?
1 1 ? ?
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 61 of 481 (chapter 1: “Digital Logic” up to page 96)
States
≡
Q
Q
NAND Q
NAND Q
S
R
S
R
S R Q Q
0 0 ? ?
0 1 ? ?
1 0 ? ?
1 1 Q Q
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 62 of 481 (chapter 1: “Digital Logic” up to page 96)
States
≡
Q
Q
NAND Q
NAND Q
S
R
S
R
S R Q Q
0 0 ? ?
0 1 ? ?
1 0 ? ?
1 1 Q Q
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 63 of 481 (chapter 1: “Digital Logic” up to page 96)
States
≡
Q
Q
NAND Q
NAND Q
S
R
S
R
S R Q Q
0 0 ? ?
0 1 1 0
1 0 ? ?
1 1 Q Q
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 64 of 481 (chapter 1: “Digital Logic” up to page 96)
States
≡
Q
Q
NAND Q
NAND Q
S
R
S
R
S R Q Q
0 0 ? ?
0 1 1 0
1 0 0 1
1 1 Q Q
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 65 of 481 (chapter 1: “Digital Logic” up to page 96)
States
NAND
NAND
≡
Q
Q
NAND
NAND
NAND Q
NAND Q
S
R
S
R
NAND
NAND
S R Q Q
0 0 ½ ½
0 1 1 0
1 0 0 1
1 1 Q Q
Assuming Q as well as Q
to be active simultaneously
may lead to instability.
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 66 of 481 (chapter 1: “Digital Logic” up to page 96)
States
≡
Q
Q
NAND Q
NAND Q
S
R
S
R
S R Q Q
0 0 Forbidden
0 1 1 0
1 0 0 1
1 1 Q Q
“S-R Flip-Flop”
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 67 of 481 (chapter 1: “Digital Logic” up to page 96)
Deriving SR Flip Flops
S R Q Q
0 0 0 *
0 0 1 *
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 68 of 481 (chapter 1: “Digital Logic” up to page 96)
Deriving SR Flip Flops
S R Q Q Q minterms
0 0 0 * S R Q/ /
0 0 1 * S QR/ /
0 1 0 1 S R Q/ /
0 1 1 1 S R Q/ /
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1 S R Q/ /
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 69 of 481 (chapter 1: “Digital Logic” up to page 96)
Deriving SR Flip Flops
S R Q Q Q minterms Simplifi ed
0 0 0 * S R Q/ /
S
0 0 1 * S QR/ /
0 1 0 1 S R Q/ /
0 1 1 1 S R Q/ /
R Q/
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1 S R Q/ /
Q = S R Q0 /^ h
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 70 of 481 (chapter 1: “Digital Logic” up to page 96)
Deriving SR Flip Flops
S R Q Q Q minterms Simplifi ed
0 0 0 * S R Q/ /
S
0 0 1 * S QR/ /
0 1 0 1 S R Q/ /
0 1 1 1 S R Q/ /
R Q/
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1 S R Q/ /
Q = S R Q0 /^ h = S R Q/ /
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 71 of 481 (chapter 1: “Digital Logic” up to page 96)
Deriving SR Flip Flops
S R Q Q Q minterms Simplifi ed
0 0 0 * S R Q/ /
S
0 0 1 * S QR/ /
0 1 0 1 S R Q/ /
0 1 1 1 S R Q/ /
R Q/
1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1 S R Q/ /
Q = S R Q0 /^ h = S R Q/ /
≡
Q
Q
NAND Q
NAND Q
S
R
S
R
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 72 of 481 (chapter 1: “Digital Logic” up to page 96)
D Flip-Flop
D Q
Q
≡
NAND
NAND
NAND
NAND
NAND
NAND
D
C
Q
Q
C
S
R
Set pre-latch
Reset pre-latch
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 73 of 481 (chapter 1: “Digital Logic” up to page 96)
D Flip-Flop
D Q
Q
≡
NAND
NAND
NAND
NAND
NAND
NAND
D
C
Q
Q
C
S
R
Set pre-latch
Reset pre-latch
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 74 of 481 (chapter 1: “Digital Logic” up to page 96)
D Flip-Flop
D Q
Q
≡
NAND
NAND
NAND
NAND
NAND
NAND
D
C
Q
Q
C
S
R
Set pre-latch
Reset pre-latch
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 75 of 481 (chapter 1: “Digital Logic” up to page 96)
D Flip-Flop
D Q
Q
≡
NAND
NAND
NAND
NAND
NAND
NAND
D
C
Q
Q
C
S
R
Set pre-latch
Reset pre-latch
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 76 of 481 (chapter 1: “Digital Logic” up to page 96)
D Flip-Flop
D Q
Q
≡
NAND
NAND
NAND
NAND
NAND
NAND
D
C
Q
Q
C
S
R
Set pre-latch
Reset pre-latch
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 77 of 481 (chapter 1: “Digital Logic” up to page 96)
D Flip-Flop
D Q
Q
≡
NAND
NAND
NAND
NAND
NAND
NAND
D
C
Q
Q
C
S
R
Set pre-latch
Reset pre-latch
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 78 of 481 (chapter 1: “Digital Logic” up to page 96)
D Flip-Flop
D Q
Q
≡
NAND
NAND
NAND
NAND
NAND
NAND
D
C
Q
Q
C
S
R
Set pre-latch
Reset pre-latch
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 79 of 481 (chapter 1: “Digital Logic” up to page 96)
D Flip-Flop
D Q
Q
≡
NAND
NAND
NAND
NAND
NAND
NAND
D
C
Q
Q
C
S
R
Set pre-latch
Reset pre-latch
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 80 of 481 (chapter 1: “Digital Logic” up to page 96)
Master-Slave JK Flip-Flop
Master SlaveSlaMMasMas
NAND
NAND
Q
Q
NAND
NAND
NAND
NAND
NAND
NAND
NOT
S
R
J
K
C
J
K
Q
Q
S
R
≡C
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 81 of 481 (chapter 1: “Digital Logic” up to page 96)
Master-Slave JK Flip-Flop
Master SlaveSlaMMasMas
NAND
NAND
Q
Q
NAND
NAND
NAND
NAND
NAND
NAND
NOT
S
R
J
K
C
J
K
Q
Q
S
R
≡C
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 82 of 481 (chapter 1: “Digital Logic” up to page 96)
Master-Slave JK Flip-Flop
Master SlaveSlaMMasMas
NAND
NAND
Q
Q
NAND
NAND
NAND
NAND
NAND
NAND
NOT
S
R
J
K
C
J
K
Q
Q
S
R
≡C
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 83 of 481 (chapter 1: “Digital Logic” up to page 96)
Master-Slave JK Flip-Flop
Master SlaveSlaMMasMas
NAND
NAND
Q
Q
NAND
NAND
NAND
NAND
NAND
NAND
NOT
S
R
J
K
C
J
K
Q
Q
S
R
≡C
Master is reset on the rising clock edge
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 84 of 481 (chapter 1: “Digital Logic” up to page 96)
Master-Slave JK Flip-Flop
Master SlaveSlaMMasMas
NAND
NAND
Q
Q
NAND
NAND
NAND
NAND
NAND
NAND
NOT
S
R
J
K
C
J
K
Q
Q
S
R
≡C
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 85 of 481 (chapter 1: “Digital Logic” up to page 96)
Master-Slave JK Flip-Flop
Master SlaveSlaMMasMas
NAND
NAND
Q
Q
NAND
NAND
NAND
NAND
NAND
NAND
NOT
S
R
J
K
C
J
K
Q
Q
S
R
≡C
Slave follows on the falling clock edge
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 86 of 481 (chapter 1: “Digital Logic” up to page 96)
Master-Slave JK Flip-Flop
Master SlaveSlaMMasMas
NAND
NAND
Q
Q
NAND
NAND
NAND
NAND
NAND
NAND
NOT
S
R
J
K
C
J
K
Q
Q
S
R
≡C
Slave follows on the falling clock edgeSlave fSl
The decoupling between
the two stages makes this
fl ip-fl op race free – even
in JK-toggle mode.
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 87 of 481 (chapter 1: “Digital Logic” up to page 96)
Register
D0
Q0
D
C
D1
Q1
D
D2
Q2
D
D3
Q3
D
D4
Q4
D
D5
Q5
D
D6
Q6
D
D7
Q7
D
Could serve as a generic, fast storage inside the CPU (general register)
Or to hold internal states (e.g. ALU overfl ow) of the CPU
which are used by e.g. branching instructions.
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 88 of 481 (chapter 1: “Digital Logic” up to page 96)
Toggle Flip-Flop
Q
Q
D Q
Q
≡S
R
J
K
Q
Q
S
R
≡
S
R
J
K
Q
Q
S
R
D
C
T Q
Q
≡
J
K
Q
Q
S
R
T
C
T Q
Q
≡
D Q
Q
XORT
C
J Q
Q
≡
D Q
QCK
AND
OR
AND
J
K
S
R
S
R
Toggle Flip-Flops change state with every clock cycle.
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 89 of 481 (chapter 1: “Digital Logic” up to page 96)
Counter
T S
R
T S
R
T S
R
T S
R
T S
R
T S
R
T S
R
T S
R
1
C
S0 S1 S2 S3 S4 S5 S6 S7
R
Q0 Q1 Q2 Q3 Q4 Q5 Q6 Q7
1 1 1 1 1 1 1
Your controller has many counters which can
e.g. be used to delay operations without the
need to execute instructions.
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 90 of 481 (chapter 1: “Digital Logic” up to page 96)
Simple CPU Architecture
You can already build most of the
components of a CPU by now.
(The most essential missing component is the
sequencer which is a specialized state-machine.)
We will come back to the CPU architectures
towards the end of the course.
The next chapter will be about
programming a CPU at machine level.
ALU
M
em
o
ry
Sequencer
Decoder
Code management
Registers
IP
SP
Flags
Data management
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 91 of 481 (chapter 1: “Digital Logic” up to page 96)
STM32L476 Discovery
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 92 of 481 (chapter 1: “Digital Logic” up to page 96)
STM32L476 Discovery
Main MCU
Debugger MCU
Display MCU
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 93 of 481 (chapter 1: “Digital Logic” up to page 96)
STM32L476 Discovery
LCD
Joystick
Reset
OTG LEDs
Power
Debugger
state
User LEDs
Over current
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 94 of 481 (chapter 1: “Digital Logic” up to page 96)
STM32L476 Discovery
Current meter to MCU
60 nA … 50 mA
U R Zi Th
Headphone jack
USB OTG
Multiplexed 24 bit
RD-DAConverter with
stereo power amp
Microphone
“9 axis” motion sensor
(underneath display):
3 axis accelerometer
3 axis gyroscope
3 axis magnetometer
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 95 of 481 (chapter 1: “Digital Logic” up to page 96)
STM32L476 Discovery
There is a lot more hardware
here than you could possibly
master in one semester …
… and you will master a lot
more about CPUs at the end the
course than you think now.
Digital Logic
© 2021 Uwe R. Zimmer, The Australian National University page 96 of 481 (chapter 1: “Digital Logic” up to page 96)
Digital Logic
• Boolean Algebra
• Truth tables and Boolean operations
• Minterms and simplifying expressions
• Combinational Logic
• Logic gates
• Numbers
• Adders, ALU
• State-oriented Logic
• Flip-Flops, registers and counters
• CPU Architecture
Summary