Circuits Circuits We will build circuits for addition,

Circuits Circuits We will build circuits for addition, multiplication and other arithmetic operations. This is actually used! Everywhere! From a truth table to a formula p q r output 0 0 0 1 0 0 1 0 0 1 0

0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1

1 1 1 From a truth table to a formula p q r output 0 0 0 1 0 0 1 0 0 1 0

0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1

1 1 Let us focus entirely on the rows that output 1! p q r output 0 0 0 1 0 0 1 0 0 1 0

0 0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1

1 1 Focusing on the 1st row p q r output 0 0 0 1 Write a formula that is 1 only on inputs p =0, q = 0, r = 0. p q r output 0 0 0

1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1

0 1 0 1 1 0 0 1 1 1 1 Focusing on the 1st row p q r output 0 0 0

1 Write a simple formula that is 1 only on inputs p =0, q = 0, r = 0. p q r output 0 0 0 1 0 0 1 0 0 1 0 0 0

1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1

1 Focusing on the 4th row p q r output 0 1 1 1 Same deal p q r output 0 0 0 1

0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0

1 0 1 1 0 0 1 1 1 1 Focusing on the 4th row p q r output 0 1 1 1

Same deal p q r output 0 0 0 1 0 0 1 0 0 1 0 0

0 1 1 1 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1

1 Focusing on the 5th row p q r output 1 0 0 1 p q r output 0 0 0 1

0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0

1 0 1 1 0 0 1 1 1 1 Focusing on the 8th row p q r output 1 1 1 1

How do we combine those simple formulae? How do we combine those simple formulae? ( ) ( ) ( ) ( ) p q r output 0 0 0 1

0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 1 1 0 1

0 1 1 0 0 1 1 1 1 Outputs 1 if and only if the truth table outputs 1! How do we combine those simple formulae? ( ) ( ) ( ) ( ) p q

r output 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1

0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 Outputs 1 if and only if the truth table outputs 1! We want to do this in hardware! Logical gates The smallest pieces of hardware that we will examine are called logical gates.

Every gate that we encounter will take bits as inputs and will emit one bit as output. 1 2 Gate Those gates can connect to each other in various different ways in order to create more complex circuits Our first gate 0 1 This gate is known as the inverter. It corresponds exactly to the negation operation in propositional logic! Where 1, set True. Where 0, set False 1 0 Our second gate 0 0

0 0 1 0 1 0 0 1 1 1 Corresponds to: Conjunction Disjunction Our second gate (AND gate) 0 0 0

0 1 0 1 0 0 1 1 1 Corresponds to: Conjunction Disjunction Our third gate (OR gate) Corresponds to logical disjunction (OR) 0 0 0

0 1 1 1 0 1 1 1 1 Exercises For the following logical circuits, vote on the Boolean functions of their inputs to which they correspond. ( ) ( ) ( ) ( ) Exercises For the following logical circuits, vote on the Boolean functions of

their inputs to which they correspond. ( ) ( ) ( ) ( ) Exercises ( ) ( ) ( ) ( ) Exercises ( ) ( ) ( ) ( ) Exercises

() () () () Exercises Watch out for De Morgans law! () The circuit above is equivalent to one where b and r are inverted before an AND gate! () () () Coming back to our original truth table ( ) ( ) ( ) ( )

Coming back to our original truth table ( ) ( ) ( ) ( ) For each small formula we have a circuit, and we will combine with a 4-input OR gate! Coming back to our original truth table ( ) ( ) ( ) ( ) For each small formula we have a circuit, and we will combine with a 4-input OR gate! Circuit 1 Circuit 2 Circuit 3 Circuit 4 Circuit 1 ( ) Circuit 2 ( )

Circuit 3 ( ) Circuit 4 ( ) Building Adder Circuits We want to build circuits that add arbitrarily large binary numbers. E.g 10011001 Inputs +00110011 Output 11001100 Half-Adder A half-adder is a circuit that adds two bits together! (Remember: is the carry bit.) Lets try to build a circuit that computes both S and C! Truth table X Y S

C 0 0 ? ? 0 1 ? ? 1 0 ? ? 1 1 ? ? Truth table X

Y S C 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1

Truth table X Y S C 0 0 0 0 0 1 1 0 1 0 1 0 1 1

0 1 X Y C S Truth table X Y S C 0 0 0 0 0 1 1 0

1 0 1 0 1 1 0 1 X Y X Y C S S XOR Gate (Exclusive OR) Half-Adder

Abstraction: We can now consider the half-adder as a black box that receives two inputs and emits two outputs. Abstraction! Half-Adder Full-Adder Now, lets consider the complete case, where we want to build a circuit that computes the sum of two 2-digit binary numbers: PQ +WX C S1 S2 To do this, we also need the ability to add 3 digits, because: C1 PQ +WX C S1 S2 Full-Adder Now, lets consider the complete case, where we want to build a circuit that computes the sum of two 2-digit binary numbers: PQ +WX C S1 S2 To do this, we also need the ability to add 3 digits, because: C1

PQ We will call a circuit that adds 3 digits a full +WX adder C S1 S2 PQ +WX C S1 S2 We could do the truth table. P Q W X 0 0 0 0 0 0 0 1 0

0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1

0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0

1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1

C S1 S2 PQ +WX C S1 S2 We could do the truth table. P Q W X 0 0 0 0 0 0 0 1 0

0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0

0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0

1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 C

S1 S2 But its time consuming and we are all busy people Constructing a Full-Adder in another way We need to build a circuit that computes the sum of 3 digits, e.g P + Q +R P + Q Step 1: Compute C1S1 with a half-adder: Half-Adder 1 1 Constructing a Full Adder 1 Half-Adder S1 Step 2: Compute + R C2S

Step 3: Combine and with an OR gate to yield the final carry bit . Think: Why did we choose an OR gate? Constructing a full-adder 1 Half-Adder 2 1 Half-Adder Step 3: Combine and with an OR gate to yield the final carry bit . Think: Why did we choose an OR gate? Abstraction time! Full Adder Black Box 3 inputs, 2 outputs

Full Adder 2-bit adder However, we still have not solved our original problem, which is to construct a circuit that adds 2-bit numbers! PQ +WX C S1 S2 So, we need a circuit that takes 4 inputs and emits 3 outputs: 2-bit adder 1 2 Constructing a 2-bit adder Step 1: Take care of the right-most column with a half-adder: C1 PQ +WX C S1 S2 2 Half-Adder

1 Constructing a 2-bit adder Step 1: Take care of the right-most column with a half-adder: C1 PQ +WX C S1 S2 2 Half-Adder 1 Full-Adder 1 Step 2 (and final): Connect Half-Adder and new inputs to Full-adder appropriately to produce final circuit. Constructing a 2-bit adder Step 1: Take care of the right-most column with a half-adder: C1 PQ +WX C S1 S2

2 Full-Adder 2 1 3 Constructing a 3-bit adder (neat) C2 C1 APQ + BWX C3 S1S2 S3 3 2-bit adder 2 Full-Adder 2 1 3 Constructing an n-bit adder (messy) 1 1

HA 1 2 2 FA 1 1 1 2 2 1 FA 1 full adders half-adders

FA Constructing an n-bit adder (neat) 1 1 1 2 2 2 (n-1)-bit adder 1 1 1 FA

Other numeric functions Addition (have done) Multiplication Division Primality test (test whether a number is prime) There are circuits for all of these! Computers actually work this way at the base level: they consist of gates. Fun exercise Input: number in binary Output: number in unary (!) 0 0 1 1 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 1 Circuit

0 0 1 1 1 1 2 1 0 0 1 1 1 1 1 First micro-circuit 0 0 1 1 1 1 0 1 0 0 1 1 0 0 0 0

1 1 0 0 1 1 1 1 0 1 1 1 1 1 = Second micro-circuit 0 0 1 1 1 1 0 1 0 0 1 1

0 0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 Second micro-circuit 0 0 1 1 1 1 0 1 0 0 1 1

0 0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 (from distributive law of conjunction over disjunction!) Third micro-circuit 0 0 1 1 1 1 0 1

0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 Third micro-circuit 0 0 1 1 1 1 0 1 0

0 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1 Final circuit 0 0 1 1 1

1 0 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 1 0 1 1 1 1 1

Final circuit 0 0 1 1 1 1 0 1 0 0 1 1 2-to-3 binary to unary decoder! 0 0 0 0 1 1 0 0 1 1

1 1 0 1 1 1 1 1

Recently Viewed Presentations

• We just live in their world." —Danny Hillis, Thinking Machines (Wired 01.2011) "It is not the strongest of the species that survives, nor the most intelligent, but the one most responsive to change." —Charles Darwin "You must be the change...
• He invited Mussolini to join a coalition government with Giolitti. 1925 Mussolini seized dictatorial powers during a political crisis [Black Shirts murdered one of Mussolini's chief Socialist critics, Giacomo Matteotti].
• Introducing Technology Into The Paving Process. ALABAMA ASPHALT PAVEMENT ASSOCIATION. March 08-09, 2016. ... Circuit Of The Americas (COTA) F1 Track in Austin TX with Austin Bridge & Road (2012) 3D Milling and 3D Paving. ... Introducing Technology Into The...
• Certification Four levels Assistant race officer Club race officer National race officer Senior National race officer Certification as Asst Race Officer attend this course no prerequisite required Basic principles * Safety no more "human against the sea" sailing is a...
• * Shed Roof A shed roof is similar to a flat roof but has more pitch. It is frequently used for additions or with other roof styles. * Mansard Roof The mansard roof is a French design and is more...
• Eligibility. Student's financial aid file must be complete. All requested documents must have been submitted and verification of data completed prior to receipt of FWS Request Form.
• Les Adams, President & CEO. Project Manager/Author for 120+ Public Safety Studies/Master . Plans/Reports on Police, Fire, EMS, Communications, Emergency Preparedness
• DC-8 In Situ Water Vapor And Aerosol Measurements Bruce Anderson, Gao Chen, Eddie Winstead, NASA LaRC In Situ Aerosol Sensors Dry Size, Optical Properties, Number Density, Volatility