5 multiple choice questions in quiz
Abstraction & Digital Logic: From Transistors to Gates Problem Transformation - levels of abstraction Natural Language Algorithm Program Machine Architecture Devices Micro-architecture Logic Circuits The desired behavior: the application The building blocks: electronic devices CSE12 Winter 2021 ‹#› Course Outline - What is Next? The building blocks of computers: logic gates How to represent information The basic algorithm: the von Neumann model RISC-V structure Programming the machine: assembly language CSE12 Winter 2021 ‹#› How do computers communicate? All creatures communicate in a particular language. A sentence in a language may be a specific arrangement of symbols “chirp squak” “ooh ooh aah aah” A digital computer, at its most basic level, speaks the binary language The binary language has only 2 symbols: 1 (ON), 0 (OFF) A certain string of 1s and 0s can be used to convey information in the binary language! Recall Permutation and Combinations from math classes! CSE12 Winter 2021 ‹#› How does birb communicate? Assume birb can utter only 2 distinct sounds: “chirp” and “squak” Further Assume birb can only use max 2 sounds to form a sentence “chirp squak” “ooh ooh aah aah” Question: What is the total possible number of ways birb can express himself through speech 6 ways! “chirp” “squak” “chirp squak” “Squak chirp” “squak squak” “chirp chirp” Question: If monke can only utter distinctly 2 soundss and form maximum 4 sounds in a sentence, what is the extent of his speech? CSE12 Winter 2021 ‹#› A joke you might appreciate more later into the course CSE12 Winter 2021 ‹#› Microprocessors contain many transistors 15-Core Xeon Ivy Bridge-EX (2014): 4310 million 10-Core Xeon Westmere-EX (2011): 2600 million Six-Core Core i7(2010): 1170 million AMD 6-core Opteron (2009): 904 million Intel Core i7 Quad (2008): 731 million Intel Core 2 Duo (2006): 291 million IBM/Apple PowerPC G5 (2003): 58 million Intel Pentium 4 (2000): 42 million IBM PowerPC 750FX (2002): 38 million Intel 4004 (1971): 2300 The Transistor: building block of computers CSE12 Winter 2021 ‹#› ‹#› Intel and Pentium are trademarks of Intel Corporation. IBM and PowerPC are trademarks of International Business Machines Corporation. Apple is a trademark of Apple Computer, Inc. What Is a Transistor? A switch, which can close between the source and the drain Changing the voltage of the gate lets you change the current flow between the source and drain (closing or opening the switch) CSE12 Winter 2021 ‹#› Logically, each transistor is used as a switch Combined to implement logic functions AND, OR, NOT Combined to build higher-level structures Adder, multiplexer, decoder, register, … Combined to build a processor ARM, Core 2 Duo, i7 9700k, etc What is a transistor? CSE12 Winter 2021 ‹#› ‹#› Truth Table (abbrvtd to T.T.) A truth table helps give tabular representation of the behavior of a logic gate A truth table with have columns for the inputs and for the output Truth table of an inverter/ NOT gate: InputOutput 10 01 input output CSE12 Winter 2021 ‹#› Logic Gates with >1 input signal Let us introduce the AND gate: An AND gate can have any number of input signals An AND gate will output a Logic High (1) ONLY when ALL of the inputs are at logic High(1) Else output is logic Low(0) CSE12 Winter 2021 ‹#› ‹#› AND gate Truth Table in1in2out 000 010 100 111 in1in2in3out 0000 0010 0100 0110 1000 1010 1100 1111 Goes through all 4 possible values for in1,in2 Goes through all 8 possible values for in1,in2 CSE12 Winter 2021 ‹#› Truth Table for n inputs If a Logic Gate has n number of inputs, then its truth table will have 2n number of rows. Corresponding to each such distinct pattern of inputs in a row, we will have a corresponding output value (1 or 0) Thus, if the AND gate had 4 inputs, it would have had 24 = 16 rows in its truth table Thus, if the AND gate had 17 inputs, it would have had 217 = 131072 rows in its truth table! When drawing a truth table for an n input logic gate, make sure each row has a unique pattern of 1s and 0s! Example, in a 4 input logic gate truth table, the input pattern 1011 must appear only once in your truth table! CSE12 Winter 2021 ‹#› The OR logic gate Let us introduce the OR gate: An OR gate can have any number of input signals An OR gate will output 0 ONLY when ALL of the inputs are 0 Else output is 1 CSE12 Winter 2021 ‹#› ‹#› OR gate Truth Table in1in2out 000 011 101 111 in1in2in3out 0000 0011 0101 0111 1001 1011 1101 1111 Goes through all 4 possible values for in1,in2 Goes through all 8 possible values for in1,in2 CSE12 Winter 2021 ‹#› NAND logic gate In a NAND logic gate, the output of an AND gate is simply connected to the input of a NOT gate! in1in2out 001 011 101 110 Truth Table of 2 input NAND gate in1in2in3out 0001 0011 0101 0111 1001 1011 1101 1110 Truth Table of 3 input NAND gate CSE12 Winter 2021 ‹#› NOR logic gate In a NOR logic gate, the output of an OR gate is simply connected to the input of a NOT gate! in1in2out 001 010 100 110 Truth Table of 2 input NOR gate in1in2in3out 0001 0010 0100 0110 1000 1010 1100 1110 Truth Table of 3 input NOR gate CSE12 Winter 2021 ‹#› 1. CMOS Logic Operation At its heart, a digital computer can understand only 1s (ON) and 0s (OFF). The computer is made up of CMOS switches which convey this information from one module to another CSE12 Winter 2021 ‹#› Task - Problem Statement Algorithm Program Instruction Set Architecture Microarchitecture Logic Gates Devices NMOS PMOS CSE12 Winter 2021 ‹#› Logic 1/0 NMOS PMOS Logic 1/0 CSE12 Winter 2021 ‹#› Test notes 1 1 CSE12 Winter 2021 ‹#› 0 0 CSE12 Winter 2021 ‹#› 1 1 CSE12 Winter 2021 ‹#› 0 0 CSE12 Winter 2021 ‹#› 0 0 Complementary MOS (CMOS) CSE12 Winter 2021 ‹#› “ Terminal” : term is affiliated with a network/circuit element, e.g. resistor, capacitor, transistor, inductor….. Quick reminder: Node vs Terminal CSE12 Winter 2021 ‹#› “ Node” : term is affiliated with a network, e.g. resistor, capacitor, transistor, inductor….. Quick reminder: Node vs Terminal CSE12 Winter 2021 ‹#› Quick reminder: Node vs Terminal CSE12 Winter 2021 ‹#› NOT gate (Inverter) Vdd V (Logic 1) 0 V (Logic 0) CSE12 Winter 2021 ‹#› 1 1 1 0 NAND gate CSE12 Winter 2021 ‹#› CSE12 Winter 2021 ‹#› ‹#› 1 0 0 0 CSE12 Winter 2021 ‹#› CSE12 Winter 2021 ‹#› CSE12 Winter 2021 ‹#› A general CMOS circuit Q. How to determine Out without solving for entire truth table??? Pull Up Network (PUN) Pull Down Network (PDN) A. Follow Output path through either the PUN (towards Vdd) or the PDN (towards gnd) PDN approach: Under what conditions does Out have a direct path to gnd?? Out = 0, (when A AND B ON) OR (when C AND D ON ) CSE12 Winter 2021 ‹#› CSE12 Winter 2021 ‹#› Digital Logic: Boolean Algebra and Gates Boolean Algebra Imagine a variable x. x can have only 1 out of 2 values: 0(low) or 1(high) With such a binary value on x, what type of possible math operations can we come up with? This is the basis of Boolean algebra. Boolean algebra is easily implemented by hardware. Two constants in Boolean Algebra: 1,0; Three fundamental operators: AND (&, . ), OR(+), NOT CSE12 Winter 2021 ‹#› Axioms of Boolean Algebra 0 · 0 = 0 1 + 1 = 1 1 · 1 = 1 0 + 0 = 0 0 · 1 = 1 · 0 = 0 1 + 0 = 0 + 1 = 1 if x = 0 then x’ = 1 if x = 1 then x’ = 0 Let’s have a closer look at what exactly those transistors were computing in the previous slides! Note: Here we are using the dot operator ‘.’ to signify AND CSE12 Winter 2021 ‹#› Single-Variable Theorems x · 0 = 0 x + 1 = 1 x · 1 = x x + 0 = x x · x = x x + x = x x · x’ = 0 x + x’ = 1 (x’)’ = x CSE12 Winter 2021 ‹#› Properties of Boolean Algebra Commutative x · y = y · x x + y = y + x Associative x · (y · z) = (x · y) · z x + (y + z) = (x + y) + z Distributive x · (y + z ) = x · y + x · z x + y · z = (x + y) · (x + z) CSE12 Winter 2021 ‹#› Properties of Boolean Algebra Absorption x + x · y = x x · (x + y) = x Combining x · y + x · y’ = x (x + y) · (x + y’) = x x Y(gulp!) CSE12 Winter 2021 ‹#› Properties of Boolean Algebra De Morgan’s Laws (x · y)’ = x’ + y’ (x + y)’ = x’y’ Other x + x’·y = x + y x · (x’ + y) = x · y CSE12 Winter 2021 ‹#› Basic Logic Gates XOR CSE12 Winter 2021 ‹#› ‹#› XOR gate XOR Output is a(XOR)b=a’b+ab’ (for 2 operands) In general, we say output is 1 if odd number of inputs are 1 0 if even number of inputs are 1 Output is a(XOR)b=a’b+ab’ (for 2 operands) In general, we say output is 1 if odd number of inputs are 1 0 if even number of inputs are 1 CSE12 Winter 2021 ‹#› XOR gate as a “programmable "inverter (NOT gate) Thus, we can “program” Z to either be inverse of B, or simply be equal to B, depending on the value of A Above is an alternative symbol for XOR gate as a programmable inverter. But in general, we will stick to the normal XOR gate symbol CSE12 Winter 2021 ‹#› Sagnik Nath () - Sum of Products (SOP) How do you get from a truth table to a logic expression? Sum of products is standard way of synthesizing simple circuits Procedure: Find the rows with the ‘1’ output Write the product-form expression for the inputs in that row (0=inverted, 1=normal) Combine the products in step 2 into a sum (OR the results of step 2) CSE12 Winter 2021 ‹#› ‹#› Sum of Products XOR Gate Find the rows with the ‘1’ output Write the product-form expression for the inputs in that row (0=inverted, 1=normal) Combine the products in step 2 into a sum (OR the results of step 2) ABY 00 01 10 11 CSE12 Winter 2021 ‹#› ‹#› Product of Sums Procedure: Find the rows with the ‘0’ output Write the sum-form expression for the inputs in that row (0=normal, 1=inverted) Combine the sums in step 2 into a product (AND the results of step 2) Note: we treat 0 and 1 reverse than for SoP CSE12 Winter 2021 ‹#› ‹#› Product of Sums XOR Gate ABY 000 011 101 110 CSE12 Winter 2021 ‹#› Examples of SoP and PoS ABCD 0000 0010 0101 0110 1000