CS 2204: Digital Circuits
Lecture 1
Welcome!
About your
instructor
Siddharth Garg
Associate Professor, ECE
New York University
sg175@nyu.edu https://twitter.com/sg1753
https://www.instagram.com/siddharth.j.garg
mailto:sg175@nyu.edu
Tweets by sg1753
https://www.instagram.com/siddharth.j.garg
Teaching team
FPGA Lab Manager:
Chris Ng (cmn10@nyu.edu); Contact person for all IT issues related to remote login into lab machines and/or lab access.
mailto:cmn10@nyu.edu
Weekly Schedule
Monday Tuesday Wednesday Thursday Friday
Lab Help Hrs
Jayanth
10AM-Noon
TA Office Hrs
Dominique
8AM-10AM
Lecture
10AM-11:50AM
Lecture
10AM-11:50AM
TA Office Hrs
Rohan
2PM-4PM
TA Office Hrs
Dominique
2PM-4PM
Prof Office Hrs
Siddharth
2PM-4PM
Lab Help Hrs
Jayanth
7PM-9PM
TA Office Hrs
Rohan
4PM-6PM
Grading:
● Homeworks (15%): Assigned biweekly, to be
done individually
● Labs (25%): Assigned biweekly, to be done
in teams of 3 assigned by us. Remote +
asynchronous with the option of going in
● Midterm (25%): Wed Mar 17th
● Final (35%): As per university schedule
The basics: Boolean Logic
When you write C/C++/Python programs, you typically operate
on integer or floating point variables.
● But internally, chips operate on “simpler” Boolean
variables. A Boolean variable can take only two values.
Therefore it is called a Binary variable
Boolean algebra is named after George Boole,
an Irish mathematcian who first
conceptualized the idea of an algebra over
variables that were either “true” or “false”
https://en.wikipedia.org/wiki/George_Boole
https://en.wikipedia.org/wiki/George_Boole
A Simple Switch
Consider a “switch” that electrically connects two points
Variable x
represents
the “state”
of the
switch. In
this case,
either OFF
or ON.
Note that in the previous example, Boolean variable x could
take one of two two values, 0 or 1. But, you do NOT want to
interpret “0” and “1” as regular integers.
(In fact later we will see that the rules of integer
“addition” and “multiplication” don’t apply here.)
Values of x
SERIES combination of switches
Now imagine the switch is
connected to a battery and a
light
For what values of x1
and x2 is the Light ON?
“Truth” table
X1 (Switch 1) X2 (Switch 2) L (Light)
0 (OFF) 0 (OFF) 0
0 (OFF) 1 (ON) 0
1 (ON) 0 (OFF) 0
1 (ON) 1 (ON) 1
This is referred
to as a Boolean
AND function.
where ‘.’ is the
Boolean AND
operation
Parallel Combination
X1 (Switch 1) X2 (Switch 2) L (Light)
0 (OFF) 0 (OFF) 0
0 (OFF) 1 (ON) 1
1 (ON) 0 (OFF) 1
1 (ON) 1 (ON) 1
This is referred
to as a Boolean
OR function.
where ‘+’ is the
Boolean OR
operation
The “AND”operation is NOT multiplication
A note on Boolean functions
is also written as
The “OR”operation is NOT addition
is also written as
Note: Boolean functions are also called “logical” functions
Boolean Inversion (NOT)
x (Switch 1) L (Light)
0 (OFF) 1 (ON)
1 (ON) 0 (OFF)
This is referred
to as a Boolean
NOT function.
where ‘-’ is the
Boolean NOT
operation
Complex functions
0 0 1
0 1 0
1 0 0
1 1 0
Three (or multi) variable functions
Logic gates and networks
Boolean functions are physically implemented using
“logic gates.”
Logic gates and networks
Also called “INVERTER”
Complex networks
Arbitrarily complex Boolean logic
functions can be implemented using a
“network” of Boolean logic gates.
Operation of a Boolean logic network
What happens if the inputs change?
Operation of a
Boolean network
0 0 ?
0 1 ?
1 0 ?
1 0 ?
Timing diagram
Boolean Algebra
Boolean algebra allows us to manipulate equations and
formulas of Boolean variables. To do so, we will leverage
several “theorems”
See truth tables of . and + ops
Try
plugging in
both values
of x and
verifying
that these
theorems
hold…
Boolean Algebra = “regular” Algebra??
NOT !
Boolean algebra doesn’t follow the rules of algebra
over reals…
Boolean Algebra DUALITY
Dual of a statement:
1. Replace + with . (and vice-versa)
2. Replace 0 with 1 (and vice versa)
If a Boolean statement is true, it’s dual is true!
Two variable theorems
These look like
standard algebra
This one doesn’t. Hmmm…Duality
Two variable theorems
Now on to slightly more complex theorems
Worked out
proofs in class
Using Venn Diagrams to prove theorems
● Logic “0” is the empty set
● Logic “1” is the universal set
● x.y is interpreted as the intersection of sets x and y
● x+y is interpreted as the union of sets x and y
Proving theorems
x y x y
Proving theorems
x y x y
Proving theorems
x y x y