Logic Circuit Design and Implementation Techniques

Basic Logic Design Gate level circuit design Professor John Carelli Kutztown University Computer Science Department

Logical Expressions: Logical expressions can be implemented with simple gates ? ? + ? B + D ( ? + ?) * (B + D) ? Professor John Carelli Kutztown University Computer Science Department

Logical Completeness 1. AND combinations that yield a "1" in the truth table. 2. OR the results of the AND gates. Note: the bubble (inversion) on the inputs Can implement ANY truth table with AND, OR, NOT! Professor John Carelli Kutztown University Computer Science Department

DeMorgans Law A pair of logical propositions that say the following: ? ? = ? + ? ? + ? = ? * ? This allows us to convert between AND and OR operations Useful in circuit design Professor John Carelli Kutztown University Computer Science Department

DeMorgans: AND/OR conversion Consider this gate: Examine this truth table The last column is identical to an OR gate AND can be converted to OR by inverting all of its inputs and output reverse (OR to AND) is also true Professor John Carelli Kutztown University Computer Science Department

Implication: The previous results imply that any logical expression can be implemented with only NAND or NOR gates Because NAND s can be converted to NOR s and visa-versa And a NOT can be made from either a NAND or a NOR by tying the inputs together. Both of these are NOT s! Professor John Carelli Kutztown University Computer Science Department

Functional Design using Logic Gates Combinatorial Circuits Output only depends on current input values No memory of prior states Sequential Circuits Output depends on both current and past input values Requires circuit to store state information Combine current inputs with stored information to produce an output Both are required! We will start by looking at Combinatorial examples Professor John Carelli Kutztown University Computer Science Department

Simple Combinatorial Example Gates are implemented using transistor level circuits Input and output signals are voltage levels High voltage (~1V) represents a binary 1 or logical true Low voltage (0V) represents a binary 0 or logical false Z Z= ( ? + ?) * (B + D) Combinatorial: outputs only depend on inputs Professor John Carelli Kutztown University Computer Science Department

Binary Half Adder A gate level design for adding two 1-bit values A B Sum (S) Carry (C) 0 0 0 0 1 0 1 0 0 1 1 0 1 1 0 1 Upper gate is an Exclusive OR (XOR) Like an or , but output is zero when both inputs are one What is the problem with this? Professor John Carelli Kutztown University Computer Science Department

Binary Full Adder Includes a carry-in A B Cin S Cout 0 0 0 0 0 Cin=0 1 0 0 1 0 Cin=1 0 1 0 1 0 1 1 0 0 1 Cin=1 0 0 1 1 0 1 0 1 0 1 0 1 1 0 1 1 1 1 1 1 Note the following property of an XOR operation: Z= A B If B==0, then Z= A (output equals input) If B==1, then Z= !A (output equals input inverted) Professor John Carelli Kutztown University Computer Science Department

Four Bit Ripple Adder Use the full adder cell to construct a circuit for adding two 4-bit binary numbers Note inherent delay: sum becomes valid as the carry bits ripple their way from the LSB to The MSB Professor John Carelli Kutztown University Computer Science Department

Two bit decoder Only one output is 1 at a time Use to generate selection lines based on a binary number Convert an opcode or select a memory location Professor John Carelli Kutztown University Computer Science Department

Multiplexer (MUX) Select between two inputs If Select is 0, output=A If Select is 1, output=B Professor John Carelli Kutztown University Computer Science Department

4 to 1 Mux Use 2 bits to select one of 4 inputs S0 S1 Q Q S0 S1 Professor John Carelli Kutztown University Computer Science Department

4 to 1 MUX (another way) A B Use 2 to 1 MUX s S0 C S1 D S0 Professor John Carelli Kutztown University Computer Science Department

Logisim Circuit Software Build digital circuits Download: http://sourceforge.net/projects/circuit/ Installed in classroom 100% Free We will only use an extremely small subset of functionality available. Basic logic gates Inputs Others See Logisim PowerPoints for more info Professor John Carelli Kutztown University Computer Science Department

Sequential vs. Combinatorial Combinatorial Circuits Always get the same result for a given set of inputs Sequential Circuits Information is stored Output depends on both current inputs and internally stored state(s) A counter is a good example Current count is stored Next value depends on the current count Important for making memories and state machines Important for managing information flow Professor John Carelli Kutztown University Computer Science Department

Basic Latch A Latch is a circuit that stores one bit of information Inputs Data the value to store Enable (or Clock) data is stored when active Output the presently stored value Various types SR latch D latch JK latch Professor John Carelli Kutztown University Computer Science Department

Set-Reset (SR) Latch Truth Table (Active High) ? is set to 1 when S=1 and R=0 ( ? == 0) ?is reset to 0 when S=0 and R=1 ( ? == 1) Previous state is retained when S == 0 and R == 0 S ==1 and R == 1 is invalid (both ? and ? == 0) Professor John Carelli Kutztown University Computer Science Department

D Latch When EN is one: D gets latched (stored) Value of D appears at output (Q) When CLK is zero: Stored value is retained Q equals stored value Changing D has no effect _ SR Latch _ SR Latch EN Invalid because Q == Q EN EN EN Professor John Carelli Kutztown University Computer Science Department

Master Slave Flip Flop Two D-Latches in series When CLK=0, D is stored in the Master D-Latch When CLK=1, output of Master is transferred to the Slave Net effect: D appears at Q on 0->1 transition of CLK Master Slave Professor John Carelli Kutztown University Computer Science Department

Flip-Flop timing diagram Data is captured in Master when CLK is low It is transferred to the Slave latch when CLK goes high Q changes when CLK changes from 0 to 1 on the rising or positive edge edge-triggered logic Professor John Carelli Kutztown University Computer Science Department

Registers A register is a device for storing multiple bits simultaneously Used in computers to represent data (i.e. numbers, characters, etc) The multiple bits are labeled using brackets 32 bit examples: A[0:31] or A[31:0] Either way is ok, but must be consistent! Individual bits accessed with the same notation, ex: A[0] Registers can be made from either Latches or Flip-Flops Each bit in the register shares a common enable or clock bit Professor John Carelli Kutztown University Computer Science Department

Example Register This example uses D-Latches with a common enable pin WE ( write-Enable ) to store 4 bits simultaneously The 4 bits D[3:0] are all stored when WE becomes active D[3] D[2] D[1] D[0] Q[3] Q[2] Q[1] Q[0] Note: can also construct a register using Flip-flops In that case, the bits would be loaded on a (common) clock edge Professor John Carelli Kutztown University Computer Science Department

Memory Like registers, but 2-dimensional Stores an array of multi-bit data values Address Space: number of locations (usually a power of 2) k = 2n locations Addressability: number of bits per location (e.g., byte-addressable) m bits Based on content from MacGraw-Hill Professor John Carelli Kutztown University Computer Science Department

Typical Memory Interface Address Bus Selects which word to access in the memory Data Bus* On write: provides the data to store in the memory On read: gets loaded with the addressed word contents Write Enable When asserted, write data on Data Bus to the memory Otherwise, read from the memory Clock When active, perform the selected operation * Note: may have separate read and write Data Busses (see next slide) Professor John Carelli Kutztown University Computer Science Department

22x3 Memory word select word select word WE word WE input input bits bits address address write write enable enable address address decoder decoder output bits output bits Based on content from MacGraw-Hill Professor John Carelli Kutztown University Computer Science Department

Register Transfer Logic Register Transfer Logic (RTL) is used to implement computational circuits like microprocessors Parallel bits, representing data, are transferred from register to register Between the registers is combinatorial logic Data gets modified as it passes through the logic implementing a desired function The multi-bit connection between registers is referred to as a bus The number of bits in the bus depends on the architecture (64, 32, 16, ) Professor John Carelli Kutztown University Computer Science Department

RTL Example A[0:3] D Q Z[0:3] 0:3 CK Cloud of Logic (combinatorial) D Q 0:3 CK B[0:3] D Q 0:3 CK CLK Registers (4 bit edge-triggered) CLK CLK is free running On each clock edge, data gets stored in the registers Data transferred via 4-bit buses (note the labeling [0:3] ) inputs get loaded into A and B on one CLK edge Result of combinatorial logic appears at Z on the next CLK edge Cloud of Logic can be any useful function (add, compare, ) Professor John Carelli Kutztown University Computer Science Department

Basic Microcomputer Design clock synchronizes CPU operations control unit (CU) coordinates sequence of execution steps ALU performs arithmetic and bitwise processing data bus registers I/O I/O Memory Storage Unit Central Processor Unit (CPU) Device #1 Device #2 ALU CU clock control bus address bus buses carry multi-bit words representing memory addresses, data, or control information typically 64 bits wide, 32 bits in older machines 30 Irvine, Kip R. Assembly Language for x86 Processors 7/e, 2015. Modified, John Carelli

Clock Synchronizes all CPU and BUS operations Machine cycle (or clock cycle) measures time of a single operation Clock is used to trigger events Continuously running (normally) Generated with a motherboard-mounted quartz crystal Typically over 1Ghz (1 billion cycles per second) one cycle 1 0 31 Irvine, Kip R. Assembly Language for x86 Processors 7/e, 2015. Modified, John Carelli