Digital Logic Computer Architecture CS 215 Boolean Algebra AND OR NOT NAND NOR Exclusive OR XOR Exclusive NOR XNOR Truth Tables George Boole AND OR A B F AB F A B F A B F 0 0 0 0 0 0 0 1 0 0 1 1 1 0 0 1 0 1 1 1 1 1 1 1 NOT A F A F 0 1 1 0 NAND NOR A B F AB F A B F A B F 0 0 1 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 0 Exclusive OR XOR Exclusive NOR XNOR A B F A xnor B F A B F A B F 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 0 1 1 0 1 1 1 Types of Logic Combinational Logic Sequential Logic Combinational Logic Logical decisions based only on combinations of inputs Maps inputs to outputs No feedback Inputs outputs have two states High generally 5 Volts Low 0 Volts Combinational Logic Analog Continuum of values Digital Optical Circuits Use phase or polarization Multi valued circuits More than two states Logic Gates Boolean operations can also be represented as Boolean logic functions AND AB OR A B Compliment A Logic Gates OR AND A B A F B Inverter Buffer A F F A F Logic Gates NOR NAND A B A F Exclusive OR XOR A F B B F Exclusive NOR XNOR A B F Transistors Control strong electrical signal with a weak signal Support the process of amplification Threshold Only voltages within the low and high ranges will work Forbidden Zone Electronics Inverter VCC VCC 5 V A RL A Vin Vout Collector Emitter GND 0 V Schematic symbol Transistor circuit Properties of Boolean Algebra Commutative AB BA A B B A Distributive A B C AB AC A BC A B A C Identity 1A A 0 A A Properties of Boolean Algebra Compliment Logical inverse Associative A BC AB C A B C A B C Idempotence AA A A A A Multimedia Logic Try this Draw logic diagrams for the following A B C F ABC F AB C F A B C F A B C F A B A C B C F Create a truth table a circuit diagram for each of the previous equations Implement your diagrams and test them DeMorgan s Laws A B A B AB A B Try drawing truth tables to prove this is true Standard Circuits Multiplexer Demultiplexer Encoder Decoder Full adder Multiplexer Demultiplexer Multiplexer 2n inputs share a communication channel using n control bits Demultiplexer Single input connects to one of 2n outputs using n control bits Try this Create a truth table for a 2 input multiplexer Use this truth table to create a corresponding circuit Encoder Decoder Encoder 2n inputs n outputs Output is binary code for which input had a 1 Decoder n inputs 2n outputs Output that gets 1 determined by inputs all others get 0 Try this Create a truth table for a 4x2 encoder Use this truth table to create a corresponding circuit Full adder Adds three one bit binary numbers C A B and outputs two onebit binary numbers a sum S and a carry C1 Usually a component in a cascade of adders The carry in for one full adder circuit is from the carry out from the previous circuit 1 1 1 1 0 1 1 0 0 Try this Create a truth table for a Full Adder Use this truth table to create a corresponding circuit Does it look like this Sequential Logic Decisions based on combinations of current inputs as well as past history of outputs S R Flip Flop What would the truth table look like for this Is Q an input What s the purpose of this circuit S Q R Q Reduction Algebraic Method K Map Method Tabular Method Algebraic Method F AB A A B 1 property A 1 A distributive identity identity Algebraic Method F ABC ABC ABC ABC How would you reduce this Give it a try Did you get F BC AC AB How did you get it Algebraic Method Try these F A B C AB F A B C B A C C A B Try this Create a circuit diagram based on the following 4 inputs 1 output Output is 1 whenever exactly two of the inputs are 1 K Map Method F ABC ABC ABC ABC AB C 0 1 0 0 0 1 1 1 1 1 0 1 1 1 Try this AB CD 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 And this AB CD 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 And this AB CD 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 1 1 1 1 1 And this AB CD 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 Don t Care s AB CD 0 0 0 1 1 1 1 0 0 0 1 d Can be 0 or 1 0 1 1 1 1 0 d 1 1 1 1 Try this AB CD 0 0 0 1 1 1 1 0 0 0 0 1 1 1 d 1 1 1 1 d 1 1 0 d Try this Design a circuit with three inputs and two outputs such that the outputs represent the binary encoding of the three inputs added together Tabular Method Quine McClusky A A B C D F A B C D 0 0 0 0 d 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 1 0 0 1 1 1 0 1 0 1 0 1 0 0 0 0 1 1 0 0 1 0 1 1 1 0 1 0 0 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 0 0 0 1 1 0 1 1 0 0 1 0 1 1 1 1 1 0 1 0 1 1 0 1 1 d 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 d B Note how the above rows are ordered A Start with a truth table that lists all input combinations and their outputs B Eliminate rows that have a 0 output Note a d output is interpreted as 1 Tabular Method Quine McClusky A B C D A B C D 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 0 0 1 1 …