L04 [Digital Logic I]

Transitor Comparison

Know some degree how to build it, but you don't have to straight up memorize how to build a NAND gate

• You should know what a P-type and N-type transitor do
• When you trace through it you should be able to understand

For n-type transitors:

• With the supply voltage applied to the device the transistor acts like a closed or connected switch

For p-type transitors:

• With the supply voltage applied to the device the transistor acts like a open or disconnected switch

Problem with discrete transitors still

• Big
• Take a lot of material to build
• Need a lot of individual connections, which are prone to failure

Solution: make integrated circuits

Conte Bubble Theorem

Combinational Logic

• A combination of AND, OR, NOT (plus NAND and NOR)
• Same inputs will always produce same outputs

Decoder

If you have a decoder with n input/selector bits, the most outputs the decoder could have is 2^n

Multiplexor

We have a problem: You have m signals and you want to select the logical value on one of them, determined by a set of n control wires

Solution: the multiplexor!

• The basic multiplexor has 1 output, n control lines, and 2^n inputs

Adders

Simple Adder For a single bit, it's just A ^ B

A	B	A + B
0	0	0
0	1	1
1	0	1
1	1	0

Half Adder The carry for a single bit is just A & B

A	B	A + B	Carry Out
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Truth in Adding

A	B	Carry In	Out	Carry Out
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Full Adder

Boolean Simplification

Useful rules for boolean simplification

A + AB = A
A + A'B = A + B
(A + B)(A + C) = A + BC

Recitation Notes 9/8

Transitors

Transitors must be closed for a current/value to be able to propagate through

Connect n-type to pass 0, connect p-type to pass 1

• p is connected to Power
  • p also has a circle
• n is connected to grouNd (or Not power)

PMOS uses p-type, NMOS uses n-type, and Complementary MOS (CMOS) uses both

Conte Bubble Theorem

Basically just flip all the bubbles

Decoders

• Sets exactly one output based on which of the input bits are set
• Looks like an isosceles trapezoid flipped on its side
• If there are n input bits, there are 2^n outputs

Multiplexer (mux)

• Selects between inputs using a selector
• If there are 2^n inputs, there are n selector bits
• Looks like decoder but reflected across vertical axis
• There is always only one output

Demultiplexer (demux)

• Sends the input across exactly one of the output lines
• Other outputs remain zero
• If there are 2^n outputs, then there are n selector bits
• Always only one input

Karnaugh Maps (KMaps)

• Ordering is in gray code
  • Only have to toggle one bit at a time

00
01
11
10

For two bit gray code, just copy the bottom

000
001
---
011
010
---
110
111
101
100

Distrubtion of variables according to gray code. This is our input, and we want to create a circuit to get this output.

a	b	c	Func(A,B,C)
0	0	0	X
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	0
1	1	1	1

	AB	AB'	A'B'	A'B
C	1	1	0	1
C'	0	1	X (Don't Care)	0

Rules of K-map grouping:

1. Groups can only contain 1's or X's
2. All the 1's have to be contained
3. Each group has to be a power of 2
4. Groups must be rectangular but can wrap around edges
5. Groups can overlap =)

Now, we can write the simplified expression

(ABC + A’BC) + (AB’C + AB’C’)

This simplifies to

BC + AB'

Practice for kMaps

Trick: you can just pull out the common letters

You can technically do all groups of one, but you want to maximize the groups

From the small group, you get A'C and from the large group you get B