Microsoft PowerPoint – Week 4 2021
Week 4
Outline
• Finish up Week 3:
• Recap memory
• Storing arrays
• Indirection
• Combinational Digital logic
• Boolean Algebra
• Expressions
• Simplification
• Truth Tables
• Logic Gates
• Simple Combinational Circuit analysis
Reminder. What is a memory
Address
Data out
• What is a cell?
• What is the total memory capacity?
• What is an address?
• What is the link between address and memory size?
• What two operations can a memory perform?
Reminder. What is a memory
decoder
0 n-1
Address
2 -1n
0
1 1 1 1
word[i] = 0011
word[j] = 1010
bit lines (normally pulled to 1 through
resistor – selectively connected to 0
by word line controlled switches)
j
i
word lines (only one
is active – decoder is
just right for this)
Address
Data out
Reminder. What is a memory
decoder
0 n-1
Address
2 -1n
0
1 1 1 1
word[i] = 0011
word[j] = 1010
bit lines (normally pulled to 1 through
resistor – selectively connected to 0
by word line controlled switches)
j
i
word lines (only one
is active – decoder is
just right for this)
Address
Data out
How do we store large objects in memory?
• A 32‐bit IEEE‐754 number in a 1MB memory where cells are 1 byte?
Activity 2/3
• Suppose you have two CPUs with a shared memory.
• If one assumes big endian architecture the other little endian, will it work?
How to store arrays
• Suppose it is an array of integers
• A[] = {10, 267, 39, 40}
• How many bits?
• Suppose you have a memory with 1 byte cells. What does it look like?
How to store arrays
• Memory has no notion of size
• It does not know how many bits are the integers
• It does not know they are storing integers
• If I know an array is stored in memory, how do I know its size?
How to store arrays
• Memory has no notion of size
• It does not know how many bits are the integers
• It does not know they are storing integers
• If I know an array is stored in memory, how do I know its size?
• Create a symbol to say end of array
• Typically used for strings (null character)
• Not great for integers (already have a 0)
• Store the size
• First put a number
• Do nothing…
• c
Activity 4
• Store in little endian
• Assume not storing size
Indirection
• Instead of storing/using a value stored in memory directly, use pass
the reference to the array
Why indirection
• Most commonly used for dynamic memory allocation/call‐by‐
reference or call by value
Why indirection is confusing…
• Multiple indirection. Why?
Digital Logic
What is digital logic?
• How 1’s and 0’s (and your encodings) are manipulated in silicon
Why digital logic?
• Fundamental building blocks of any digital circuit
• (Including computers)
• Two main types:
• Combinational
• Sequential
Why Boolean Algebra
• We want to design compact digital logic circuits
• Mathematicians already created way to play with 0’s and 1’s
Boolean Algebra vs elementary algebra
• Elementary algebra has many operations
• Add
• Subtract
• Multiply
• Divide
• …
• Boolean algebra simpler
• Conjunction
• Disjunction
• Negation
• Variables can only be 0 or 1
Conjunction
• If x and y are Boolean variables, conjunction denoted by:
• x.y
• x*y
• xy
• Rules:
• x, y can only be 0 or 1
• If x=1 and y=1, xy=1 otherwise xy=0
Disjunction
• If x and y are Boolean variables, disjunction denoted by:
• x+y
• Rules:
• x, y can only be 0 or 1
• If either x=1 or y=1, or both = 1, x+y=1 otherwise x+y=0
• (or only if both x=0 and y=0 does x+y=0)
Negation
• If x is a Boolean variable, negation denoted by:
• x’
• x ̄
• Rules:
• X can only be 0 or 1
• If x=1 or x ̄ =0
• If x=0 or x ̄ =1
How useful are these three operators?
• Imagine a general combinational logic circuit.
• What can it possibly do?
Evaluating Boolean expressions
• How to evaluate x+x’y?
• How many variables?
• How many different combinations of inputs?
Evaluating Boolean expressions
• How to evaluate x+x’y?
• How many variables?
• How many different combinations of inputs?
• Explore all options ‐ Truth Tables
Truth Tables
• Shows output for all input combinations
• Example: evaluate x+x’y
Activity 1
Canonical Boolean Expressions
• Is there other way to write x+x’y?
Canonical Boolean Expressions
• Is there other way to write x+x’y?
• Canonical expressions agree 1 way to represent all functions
• Most common types:
• SOP
• POS
SOP/POS example
• xz +x’y +yz+ xyz
Activity 2
Simplifying Boolean Expressions
• Is there any other way to write x+x’y?
• How do we show they are equivalent?
Why Boolean Algebra if truth tables work?
Why Boolean Algebra if truth tables work?
• Can take a long time to write truth tables…
Simplifying Boolean Expressions using
Boolean Algebra
• Need to make use of rules
Boolean algebra rules
Law Name Expression
Identity 1*x = x, 0 + x = x
Null 0*x = 0, 1 + x = 1
Idempotent x*x = x, x + x = x
Inverse x*x’ = 0, x + x’ = 1
Commutative x*y = y*x, x + y = y + x
Redundancy x + x’y = x + y, x(x’+y) = xy
Associative (xy)z = x(yz), (x+y) + z = x + (y+z)
Distributive x + yz = (x+y)(x+z), x(y+z) = xy + xz
Absorption x(x+y) = x, x + xy = x
De Morgan (xy)’ = x’ + y’, (x+y)’ = x’y’
Double Complement (x’)’ = x
Simplifying Compound expressions
• (a+b’)(c+d)’
Boolean algebra to silicon
• Logic gates key to any digital circuit
• Need to be able to implement all Boolean functions to manipulate 1’s
and 0’s
• Chip designers implement these logic circuits in silicon
Boolean algebra to silicon
Other common gates
Other common gates
Other common gates
• Do we need an xor gate?
• Is there any other way of
implementing it?
Other common gates
Other common gates
• Why? Easy in CMOS
Other common gates
How do gates work?
• Consider an AND gate with changing inputs.
How do gates work?
• Consider an AND gate
• How fast does it change?
How do gates work?
• Consider an AND gate
• How fast does it change?
• Which gates change fastest?
How do gates work?
• Consider an AND gate
• How fast does it change?
• Nanoseconds
• You can assume it is near instant
• Which gates change fastest?
How do we evaluate a circuit?
• Suppose we are given a random circuit: (Activity 3)
• How do we study its input and output behaviour
Reverse question
• Suppose we want to implement a (Boolean) function
• How do we turn this into a circuit
Activity 4
Can you use basic gates