CS 2204: Digital Circuits
Lecture 7
ECE/CS trivia
Harvard Mark II (Note: Not the
sketchy social media founder)
Grace Hopper (Legendary programmer)
4-variable k-map
Cubes of size 2, 4, and 8
are possible. Any cube can
be expressed as the product
of the variables that are
common across all the
minterms in the cube
Example 4
1
1 1 1
1 1
1
1
1
1
From sop to pos
We can also write f in “product-of-sum”
form as follows
Each entry of a
truth-table is also
associated with a
“max-term.” E.g.
A Boolean function f can
be written as the
“product” of maxterms
over rows for which f=0
Example pos form
Example pos form
Implementation using and/or gates
Implementation using NAND and NOR GATES
On real silicon chips we can only implement NAND (NOT-AND)
and NOR (NOT-OR) gates, along with NOT gates. We would
implement AND gates using NAND followed by NOT. Likewise, we
would implement OR gates using NOR followed by NOT.
Transitioning between gates
FRom and-or to NAND-NOR Boolean logic netlists
Another example (with POS form)
Not gates can be designing using Nands or Nors
exercise
Implement using ONLY NOR gates
Base-n representations
Base 2 (Binary) Representation
Base 8 (Octal) Representation
Numbers in range 0,1,2,…7
Example:
Base 16 (Hex) Representation
Numbers in range 0,1..9,A,B..F
Example:
Hex used as shorthand for binary
Computers used binary representations. For examples, “ints”
in C are 32-bit binary numbers.
But writing down 32-bits is tedious, so we often use a
hexadecimal representation instead.
Q: How many hexadecimal numbers needed to represent a 32-bit
binary value? Hint: how many binary numbers do you need for
a single hex number?
Example
Convert the following binary value to hexadecimal.
Strategy: group into sets of 4 bits each. Convert each set
of 4 bits into hex equivalent.
Adding binary values
Binary additions are very similar to the way we perform
decimal additions!
+1 +1 +1
1 1 0 1 = 13
+ 0 1 0 1 =+ 5
———————–
1 0 0 1 0 = 18
Adding binary values
Binary additions are very similar to the way we perform
decimal additions!
+1 +1 +1
1 1 0 1 = 13
+ 1 1 0 1 =+13
———————–
1 1 0 1 0 = 26
A “full” Adder
Takes a “carry-in” bit, two inputs bits x and y, and outputs
a sum bit and a “carry out” bit
0
0
Carry out bit K-mapSum bit K-map
A small detour: xor gates
We will show that:
Sum bit using xors
Circuit diagram of a full adder
A full adder is essentially a
single-bit adder
N-bit adder
+1 +1 +1
1 1 0 1
+ 0 1 0 1
———————–
1 0 0 1 0