COMP2300/6300
Computer Organisation and Program Execution
Digital Logic
Dr Charles 1, 2022
Copyright By PowCoder代写 加微信 powcoder
Week 1: Boolean algebra
It starts with a thought
An Investigation of the Laws of Thought on Which are Founded the Mathematical Theories of Logic and Probabilities by , 1854
You can still buy it from Amazon
Booleʼs big idea: true & false are all you need
What is Boolean algebra?
Algebra is the study of mathematical symbols and the rules for manipulating these symbols; itʼs about variables like a and b and operators like ∧ (binary and), ∨ (binary or), ¬ (unary not, sometimes represented with an overline e.g. ).
Boolean means that all variables & expressions can take one of two values. We can call them true and false, 1 and 0, or Mary and Mengyuan; it doesnʼt matter.
Boolean algebra builds expressions with these basic building blocks, e.g. ¬(a∧b)∨c
this is all revision from MATH1005, so weʼre gonna speed through
Truth tables
Truth tables are just a convenient way of enumerating all the of the possible values our variables can take. If youʼve got variables, you need rows in your truth table (why?)
Hereʼs an example with 2 variables:
a b a∧b TTT TFF FTF FFF
Other handy Boolean operators
a→b=(¬a∨b) aimpliesb (a≡b)=(a∧b)∨(¬a∧¬b) aequivalenttob (a⊕b)=(a∧¬b)∨(¬a∧b) aexclusiveor/xorb
¬(a∧b)=(¬a∨¬b) anotand/nandb ¬(a∨b)=(¬a∧¬b) anotor/norb
You can reduce any Boolean expression to only NAND or only NOR operators (try it and see!).
Logic functions
You know about functions from maths, e.g. hereʼs a two-argument function of
We can have functions of Boolean variables and as well:
… = )𝑏 ,𝑎(𝑔
)𝑦(𝑛𝑖𝑠 𝑥 = )𝑦 ,𝑥(𝑓
Can you think of anything we can do with the Boolean function that we canʼt do with the real-valued function ?
… = )𝑏 ,𝑎(𝑔
… = )𝑦,𝑥(𝑓
Full binary operator truth table
What does this have to do with my microbit?
Logic gates
How does your computer add 1+1?
How would a 5yo do it?
Number representations
Remember that an integer can be represented in a di erent “base” (or “radix”), e.g. binary (base-2), octal (base-8), hexadecimal (base-16) or the familiar decimal (base-10).
Binary 0b 0000 0000 0000 0000 0000 0000 0000 0000
Note: hex & binary padded to 32-bit, negative numbers represented with 32-bit twoʼs complement
0x 0000 0000
Combinational logic
Letʼs start simple: 1+1
Consider the Boolean function (the s is short for sum). How would we put this in a (pseudo) truth table?
abs 000 011 101 112
𝑏 + 𝑎 = )𝑏 ,𝑎(𝑠
Not quite…
This doesnʼt really work because we canʼt have three distinct values (0, 1 and 2) in Boolean algebra. But what if we just consider one “column” of the addition?
110 (carry the 1)
Add a c (carry) column
absc 0000 0110
bit == binary digit
But what is ?
The truth table is a complete spec for the function that weʼre interested in, but it
doesnʼt tell us how to express
using the rules we looked at earlier. c minterms
absc 0000 0 1 1 0 1 0 1 0 1101
s minterms ¬a∧b
s=(a∧¬b)∨(¬a∧b)=a⊕b c=a∧b
So far… Combinational Logic:
lets us make a Boolean expressions for any truth-table
Boolean Algebra:
lets us simplify Boolean expressions to something manageable
Half-adder
s=a⊕b c=a∧b
DLS: Digital Logic Simulator
DLS is a time-driven event-based multi-delay 3-value digital logic simulator.
Thereʼs both desktop (cheap) & web (free) versions.
DLS isnʼt compulsory for the course, but itʼs a nice way for me to demo things.
Demo: Half-adder
Full-Adder
What about carry in?
Whatʼs missing with the half-adder? Carry in (ci) as well as carry out (co).
a b ci s co
00000 01010 10010 11001 00110 01101 10101 11111
s=(a∧¬b∧¬ci)∨(¬a∧b∧¬ci)∨(¬a∧¬b∧ci)∨(a∧b∧ci) =(((a∧¬b)∨(¬a∧b))∧¬ci)∨(((¬a∧¬b)∨(a∧b))∧ci) =((a⊕b)∧¬ci)∨((a=b)∧ci)
Full-adder
cout=(a∧b)∨((a⊕b)∧cin) (trustme!)
Demo: Full-adder
Ripple-carry adder
We can join them together like so:
1. how many bits can be added together? 2. how long does it take?
3. where does the final carry bit go?
What about subtraction?
Weʼve got two options:
1. do some more minterms stu (boo!)
2. trick the full adder into subtracting things instead
show of hands?
Twos complement representation
The basic idea: can we define (binary) negative numbers such that our adder still works?
Twos complement representation
The twos complement “circle”
Quiz: negative or positive?
0b011011101110101010010
0b1011000000000011101111111111101010010000000001010101
itʼs all in your mind
Simple ALU
A simple ALU (Arithmetic & Logic Unit) which can ADD, XOR, AND, OR two arguments.
Sequential logic
What does it mean for a computer to have memory? Can the combinational logic functions weʼve looked at so far remember things?
no! we need feedback
Sequential == state-oriented
This makes intuitive sense—the feedback loop allows the current output to be fed back in (as input).
Sequential logic circuits can no longer be treated as “pure” input-output black boxes—they carry “state” (i.e. the sequence of inputs matters).
S (set), R (reset)
stackexchange asks: “Why is the output of stateful elements o en named Q?”
There are four possible input combinations:
¬s ¬r e ect
1 1 keep current state q
0 1 setq(to1)
1 0 resetq(to0)
0 0 forbidden (q and ¬q both set to 1)
Demo: SR latch
Problems with the SR latch
1. the forbidden thing (this is obviously bad)
2. there are some tricky timing issues (because physics: remember, there are real electrons flying around)
3. have to keep changing inputs…
Gated D latch
The gated D latch uses an enable input, so that the latch is set only when you want it to be.
JK master-slave flip-flop
Better again, set/reset on a clock: no timing problems, no forbidden inputs, toggle operation (although itʼs a more complex circuit)
This video is private
Store multiple bits, can serve as general-purpose fast on-CPU storage, or hold state for peripherals, etc. Note the shared clock line
Feeling lost?
These are all physical components in your computer.
Thereʼs no magic (!), just these billion of these little mathematical machines.
Further reading
Plantz: Introduction to Computer Organization chapters 5-7
Patterson & HennessyAppendix A “The Basics of Logic Design” EEVblog Intro to Digital Logic (YouTube)
: Logic Gates, SR Latch, D Latch, D Flip-Flop, JK Flip Flop
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com