BECE102L-Digital Systems Design Module 3 PDF

BECE102L-DIGITAL SYSTEMS DESIGN MOD-3 DESIGN OF COMBINATIONAL LOGIC CIRCUITS by Dr. Penchalaiah Palla Department of Micro and Nanoelectronics School of Elect...

BECE102L-DIGITAL SYSTEMS DESIGN MOD-3 DESIGN OF COMBINATIONAL LOGIC CIRCUITS by Dr. Penchalaiah Palla Department of Micro and Nanoelectronics School of Electronics Engineering Vellore Institute of Technology Vellore, TN Combinational Logic design 1 WEEK TOPICS 1 MODELSIM DEMO, GATE LEVEL HDL FOR LOGIC GATES 2 HALF ADDER, FULL ADDER, HALF SUBTRACTOR, FULL SUBTRACTOR 3 TASK 1 – SIMPLIFICATION OF SOP/POS AND DESIGN USING NAND/NOR GATES – 10M 4 CONCEPT OF MUX, DEMUX, DECODER, ENCODER 5 TASK 2 – MUX/DEMUX BASED APPLICATIONS – 10M BEFORE CAT - 1 6 FLIP-FLOPS/LATCH – BEHAVIORAL MODELLING 7 CONCEPTS OF COUNTERS, SHIFT REGISTERS 8 TASK 3 – SEQUENTIAL CIRCUITS -10M 9 H/W DATA PATH CIRCUITS 10 TASK 4 – IMPLEMENTATION OF DATA PATHS – 15M BEFORE CAT - 2 11 CONCEPT OF FSM – MEALY 12 CONCEPT OF FSM – MOORE 13 TASK 5 – FSM – 15M 14 PRACTICE 15 FAT Remember.. Inputs. Network. Outputs.. ◆ Combinational The outputs depend only on the current input values It uses only logic gates ◆ Sequential The outputs depend on the current and past input values It uses logic gates and storage elements 5 Notes ◆ If there are n input variables, there are 2^n input combinations ◆ For each input combination, there is one output value ◆ Truth tables are used to list all possible combinations of inputs and corresponding output values 6 Basic Combinational Circuits ◆ Code Converters ◆ Adders ◆ Subtractors ◆ Decoders ◆ Encoders ◆ Multiplexers ◆ Demultiplexers 7 Combinational Logic 8 Combinational Logic 9 Combinational Logic 10 Combinational Logic 11 Combinational Logic 12 Combinational Logic 13 Combinational Logic 14 Combinational Logic 15 Combinational Logic 16 Combinational Logic 17  Conversion from Gray to Binary Combinational Logic 18 Part-1-Design Procedure ◆ Determine the inputs and outputs ◆ Assign a symbol for each ◆ Derive the truth table ◆ Get the simplified boolean expression for each output ◆ Draw the network diagram 19  Example ◆ Conversion from BCD to excess-5 Combinational Logic 20  Example (Cont.) W = A + B + CD Combinational Logic 21  Example (Cont.) X = A + B' D'+ B' C'+ BCD Combinational Logic 22  Example (Cont.) Find Y and Z Draw the network diagram For more details read the text Book Combinational Logic 23  Boolean functions Combinational Logic 24  Binary to Gray Code Converter Boolean functions Combinational Logic 25  Adders ◆ Essential part of every CPU ◆ Half adder (Ignore the carry-in bit) It performs the addition of two bits ◆ Full adder It performs the addition of three bits Combinational Logic 26  Functional Blocks: Addition ▪ Binary addition used frequently ▪ Addition Development: Half-Adder (HA), a 2-input bit-wise addition functional block, Full-Adder (FA), a 3-input bit-wise addition functional block, Ripple Carry Adder, an iterative array to perform binary addition, and Carry-Look-Ahead Adder (CLA), a hierarchical structure to improve performance. © Pearson Education, Inc.  Half Adder Functional Block: Half-Adder ▪ A 2-input, 1-bit width binary adder that performs the following computations: X 0 0 1 1 +Y +0 +1 +0 +1 CS 00 01 01 10 ▪ A half adder adds two bits to produce a two-bit sum ▪ The sum is expressed as a X Y C S sum bit , S and a carry bit, C 0 0 0 0 ▪ The half adder can be specified 0 1 0 1 as a truth table for S and C  1 0 0 1 1 1 1 0 © Pearson Education, Inc.  Half Adder Logic Simplification: Half-Adder ▪ The K-Map for S, C is: S Y C Y ▪ This is a pretty trivial map! By inspection: 0 11 0 1 X 12 X 13 S = X ×Y + X ×Y = X  Y 3 2 S = ( X + Y ) ×( X + Y ) ▪ and C = X ×Y C = ( ( X×Y ) ) ▪ These equations lead to several implementations. © Pearson Education, Inc.  Half Adder Five Implementations: Half-Adder ▪ We can derive following sets of equations for a half- adder: ( a ) S = X ×Y + X ×Y ( d ) S = ( X + Y ) ×C C = X ×Y C = ( X + Y) ( b ) S = ( X + Y ) ×( X + Y ) ( e ) S = X  Y C = X ×Y C = X ×Y ( c ) S = ( C+ X×Y) C = X ×Y ▪ (a), (b), and (e) are SOP, POS, and XOR implementations for S. ▪ In (c), the C function is used as a term in the AND- NOR implementation of S, and in (d), the C function is used in a POS term for S. © Pearson Education, Inc.  Half Adder Implementations: Half-Adder ▪ The most common half adder implementation is: X (e) Y S S = XY C C = X ×Y ▪ A NAND only implementation is: C S = (X +Y)C X = X C +Y C S = ( X  C )  (Y  C ) Y C = X Y © Pearson Education, Inc.  Full Adder Functional Block: Full-Adder ▪ A full adder is similar to a half adder, but includes a carry-in bit from lower stages. Like the half-adder, it computes a sum bit, S and a carry bit, C. For a carry-in (Z) of Z 0 0 0 0 0, it is the same as X 0 0 1 1 the half-adder: +Y +0 +1 +0 +1 CS 00 01 01 10 For a carry- in (Z) of 1: Z 1 1 1 1 X 0 0 1 1 +Y +0 +1 +0 +1 CS 01 10 10 11 © Pearson Education, Inc.  Full Adder Logic Optimization: Full-Adder ▪ Full-Adder Truth Table: X Y Z C S 0 0 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 ▪ Full-Adder K-Map: 1 1 0 1 0 1 1 1 1 1 S Y C Y 1 1 1 0 1 3 2 0 1 3 2 X 1 1 X 1 1 1 4 5 7 6 4 5 7 6 Z Z © Pearson Education, Inc.  Full Adder Equations: Full-Adder ▪ From the K-Map, we get: S = XYZ+ XY Z+ XYZ+ XYZ C = XY+XZ+YZ ▪ The S function is the three-bit XOR function (Odd Function): S = XYZ ▪ The Carry bit C is 1 if both X and Y are 1 (the sum is 2), or if the sum is 1 and a carry-in (Z) occurs. Thus C can be re-written as: C = X Y + (X  Y) Z ▪ The term X·Y is carry generate. ▪ The term XY is carry propagate. © Pearson Education, Inc.  Logic diagram of full adder S = XYZ C = X Y + (X  Y) Z © Pearson Education, Inc.  Full Adder Another Implementation of full adder ▪ Full Adder Schematic Ai Bi Gi ▪ Here X, Y, and Z, and C (from the previous pages) are Ai, Bi, Ci and Ci+1, respectively. Also, G = generate and Pi Ci P = propagate. ▪ Note: This is really a combination of a 3-bit odd function (for S)) and Carry logic (for Ci+1): Ci+1 Si (G = Generate) OR (P =Propagate AND Ci = Carry In) Ci+1 = G + P · Ci © Pearson Education, Inc.  BINARY SUBTRACTION Example: Subtract binary number 101 from 1011 (borrow) 01 1 0 1 1 - 1 0 1 0 1 1 0  TEST Subtract binary number 11 from 1010 01 0 10 1 0 1 1 0 1 0 - 1 1 0 1 1 1  HALF SUBTRACTOR Subtracts LSD column in binary subtraction Input Output Logic A Di (difference) Symbol: Half Subtractor B B0 (borrow out) Logic Diagram:  FULL SUBTRACTOR Used for subtracting binary place values other than the 1s place Input Output Logic Bin Di (difference) Symbol: Full A Subtractor B B0 (borrow out) Logic Bin H. S. Di Diagram: A H. S. B0 B  2s COMPLEMENT NOTATION 2s complement representation - widely used in microprocessors. Represents sign and magnitude MSB LSB Sign bit (0 = + ; 1 = -) Decimal: +7 +4 +1 0 -1 -4 -7 2s Complement: 0111 0100 0001 0000 1111 1100 1001  2s COMPLEMENT - CONVERSIONS Converting positive numbers to 2s complement: Same as converting to binary Converting negative numbers to 2s complement: Decimal to 2s 2s Complement to Complement Binary - 4 (decimal) 1 1 0 0 (2s C) Convert decimal 1s to binary 0100 complement 1s 0011 complement 1011 Add 1 Add 1 - 4 = 1 1 0 0 (2s Complement) 0 1 0 0 (Binary)  ADDING/SUBTRACTING IN 2s COMPLEMENT 2s complement notation makes it possible to add and subtract signed numbers (Decimal) 2s Complement (- 1) 1111 + (- 2) + 1110 (- 3) 1 11 0 1 2s complement Discard (+1) 0001 + (- 3) + 1101 (- 2) 11 1 0 2s complement  TEST Add the following 2s complement numbers: (+5) 0 1 0 1 + (- 4) + 1 1 0 0 (+1) 1 0 0 0 1 Discard © Pearson Education, Inc.  Binary Subtractor ◆ Remember You need to take 2’s complement to represent negative numbers A-B ✓ Take 2’s complement of B and add it to A First take 1’s complement and add 1 Combinational Logic 46  3-11 Binary Adder-Subtraction Signed Integers ▪ Positive numbers and zero can be represented by unsigned n-digit, radix r numbers. We need a representation for negative numbers. ▪ To represent a sign (+ or –) we need exactly one more bit of information (1 binary digit gives 21 = 2 elements which is exactly what is needed). ▪ Since computers use binary numbers, by convention, the most significant bit is interpreted as a sign bit: s an–2  a2a1a0 where: s = 0 for Positive numbers s = 1 for Negative numbers and ai = 0 or 1 represent the magnitude in some form. © Pearson Education, Inc.  Signed Binary Numbers Signed Integer Representations ▪Signed-Magnitude – here the n – 1 digits are interpreted as a positive magnitude. ▪Signed-Complement – here the digits are interpreted as the rest of the complement of the number. There are two possibilities here: Signed 1's Complement ▪ Uses 1's Complement Arithmetic Signed 2's Complement ▪ Uses 2's Complement Arithmetic © Pearson Education, Inc.  Signed Binary Numbers Signed Integer Representation Example ▪ r =2, n=3 Number Sign -Mag. 1's Comp. 2's Comp. +3 011 011 011 +2 010 010 010 +1 001 001 001 +0 000 000 000 –0 100 111 — –1 101 110 111 –2 110 101 110 –3 111 100 101 –4 — — 100 © Pearson Education, Inc.  Signed Integer Representation © Pearson Education, Inc.  Signed Binary Addition and Subtraction Signed-Magnitude Arithmetic ▪ If the parity of the two signs is 0: 1. Add the magnitudes. 2. Check for overflow (a carry out of the MSB) 3. The sign of the result is the same as the sign of the first operand. ▪ If the parity of the two signs is 1: 1. Subtract the second magnitude from the first. 2. If a borrow occurs: take the two’s complement of result and make the result sign the complement of the sign of the first operand. 3. Overflow will never occur. © Pearson Education, Inc.  Signed Binary Addition and Subtraction Sign-Magnitude Arithmetic Examples ▪ Example 1: 0010 +0101 ▪ Example 2: 0010 +1101 ▪ Example 3: 1010 - 0101 © Pearson Education, Inc.  Signed Binary Addition and Subtraction Signed-Complement Arithmetic ▪ Addition: 1. Add the numbers including the sign bits, discarding a carry out of the sign bits (2's Complement), or using an end-around carry (1's Complement). 2. If the sign bits were the same for both numbers and the sign of the result is different, an overflow has occurred. 3. The sign of the result is computed in step 1. ▪ Subtraction: Form the complement of the number you are subtracting and follow the rules for addition. © Pearson Education, Inc.  Signed Binary Addition and Subtraction Signed 2’s Complement Examples ▪ Example 1: 1101 +0011 ▪ Example 2: 1101 -0011 © Pearson Education, Inc.  Signed Binary Addition © Pearson Education, Inc.  Signed Binary Subtraction © Pearson Education, Inc. 57 58 Combinational Logic 59 60 61  Decoder ◆ n by 2^n decoder Converts information from n input lines into 2^n output lines ◆ Example -2x4 Decoder, 3x8 Decoder, 4x16 Decoder 2x4 Decoder Internal Structure of 2x4 Decoder 62 Another View 63 64 65 66 67 68  From course text book 4x16 Decoder 69 70 71 72 73 3x8 Decoder From course text book 74 Example 75 Full Adder with Decoder Si = Ai  Bi  Ci Ci +1 = Ai Bi ' Ci + Ai ' Bi Ci + Ai Bi 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93  What is a Multiplexer (MUX)? A MUX is a digital switch that Multiplexer has multiple inputs (sources) Block Diagram and a single output (destination). The select lines determine 2N 1 MUX Inputs Output which input is connected to (sources) (destination) the output. MUX Types N → 2-to-1 (1 select line) Select → 4-to-1 (2 select lines) Lines → 8-to-1 (3 select lines) → 16-to-1 (4 select lines) 94 Multiplexer(contd..)  Typical Application of a MUX Multiple Sources Selector Single Destination MP3 Player Docking Station D0 Laptop MUX D1 Sound Card Y D2 D3 Surround Sound System Digital B A Selected Source Satellite 0 0 MP3 0 1 Laptop 1 0 Satellite Digital 1 1 Cable TV Cable TV 96 4-to-1 Multiplexer (MUX) D0 MUX D1 Y D2 D3 B A B A Y 0 0 D0 0 1 D1 1 0 D2 1 1 D3 97  4-to-1 Multiplexer Waveforms D0 D1 Input Data D2 D3 A Select Line B Output Y Data D0 D1 D2 D3 D0 D1 D2 D3 98  Medium Scale Integration MUX 4-to-1 MUX 8-to-1 MUX 16-to-1 MUX Inputs Output (Y) (and inverted output) Select Enable 99 Realization of 4-to-1 line multiplexer Symbol Logic Diagram Truth Table Realization of 4-to-1 line multiplexer USING a CASE statement TESTBENCH Building a Large Multiplexer  Multiplexers One of the primary applications of multiplexers is to provide for the transmission of information from several sources over a single path. This process is known as multiplexing. Demultiplexer = decoder with an enable input. Multiplexer/Demultiplexer for information transmission Logic Design with Multiplexers 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Logic Design with Multiplexers Logic Design with Multiplexers 8-to-1 MUX  Example: 8-to-1 0 0 0 MUX 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Logic Design with Multiplexers Logic Design with Multiplexers  Example 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Boolean Function Implementation 120 Example How do you implement it with 8x1 MUX? 121 Example How do you implement it with 4x1 MUX? 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Logic Design with Multiplexers and K- maps K-map representation  Example 0 0 0 0 0 1 1 0 1 1 0 1 0 0 1 1 0 1 0 0 1 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 0 1 0 0  Realization 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Alternative Structures Note that order of variables on input lines matters! 8-to-1-line multiplexers and 4-variable Boolean functions Can do the same thing, three variables are placed on select lines, inputs to the data lines are single-variable functions. Example: Can we do better? K-map Structure Example: Example  Example Multiplexer Tree What is a Demultiplexer (DEMUX)? A DEMUX is a digital switch Demultiplexer with a single input (source) Block Diagram and a multiple outputs (destinations). DEMUX The select lines determine Input 1 2N Outputs which output the input is (source) (destinations) connected to. DEMUX Types N → 1-to-2 (1 select line) Select → 1-to-4 (2 select lines) Lines → 1-to-8 (3 select lines) → 1-to-16 (4 select lines) 134 Typical Application of a DEMUX Single Source Selector Multiple Destinations B/W Laser Printer Fax Machine D0 DEMUX X D1 D2 Color Inkjet Printer D3 B A Selected Destination 0 0 B/W Laser Printer Pen Plotter 0 1 Fax Machine 1 0 Color Inkjet Printer 1 1 Pen Plotter 135 1-to-4 De-Multiplexer (DEMUX) D0 DEMUX D1 X D2 D3 B A B A D0 D1 D2 D3 0 0 X 0 0 0 0 1 0 X 0 0 1 0 0 0 X 0 1 1 0 0 0 X 1-to-4 De-Multiplexer Waveforms X Input Data S0 Select Line S1 D0 D1 Output Data D2 D3 137  Medium Scale Integration DEMUX 1-to-4 DEMUX 1-to-8 DEMUX 1-to-16 DEMUX Select Outputs (inverted) Input (inverted) Note : Most Medium Scale Integrated (MSI) DEMUXs , like the three shown, have outputs that are inverted. This is done because it requires few logic gates to implement DEMUXs with inverted outputs rather than no-inverted outputs. 138 Study Problem ◆ Course Book Chapter – 4 Problems 4 – 31 ✓ Construct a 16x1 multiplexer with two 8x1 and one 2x1 multiplexer. Use block diagrams 139 Study Problem ◆ Course Book Chapter – 4 Problems 4 – 34 An 8x1 multiplexe r has inputs A, B, and C connected to the selection inputs S2 , S1 , and S0 respectively. The data inputs I1 = I 2 = I 7 = 0; I 3 = I 5 = 1; I 0 = I 4 = D; I 6 = D' Determine the Boolean function t hat the multiplexe r implements 140  Parity Generator and Parity Checker Even Parity Generator Let us assume that a 3-bit message is to be transmitted with an even parity bit. The total number of 1s must be even, to generate the even parity bit P. truth table of even parity generator Combinational Logic 141 Combinational Logic 142 Combinational Logic 143  VERILOG CODE: module evenparity( input x,y,z, output result); xor (result,x,y,z); endmodule Combinational Logic 144  TEST BENCH: // Wait 100 ns for global reset to finish module tb_evenparity; reg x,y,z; #100; evenparity evnparity0 (result, x,y,z); initial begin x = 0; // Initialize Inputs x = 0; y = 1; y = 0; z = 0; z = 0; // Wait 100 ns for global reset to finish #100; // Wait 100 ns for global reset to finish // Add stimulus here #100; x = 0; x = 0; y = 0; y = 1; z = 1; z = 1; Combinational Logic 145  // Wait 100 ns for global reset to finish // Wait 100 ns for global reset to finish #100; #100; x = 1; x = 1; y = 0; y = 1; z = 0; z = 1; // Wait 100 ns for global reset to finish // Wait 100 ns for global reset to finish #100; #100; x = 1; end y = 0; endmodule z = 1; // Wait 100 ns for global reset to finish #100; x = 1; y = 1; z = 0; Combinational Logic 146 Combinational Logic 147  Odd Parity Generator The total number of bits must be odd in order to generate the odd parity bit. 1 is placed in the parity bit in order to make the total number of bits odd when the total number of 1s in the truth table is even. Combinational Logic 148 Combinational Logic 149  Parity Check It is a logic circuit that checks for possible errors in the transmission Even Parity Checker The output of the parity checker is denoted by PEC (parity error check). The below table shows the truth table for the even parity checker in which PEC = 1 if the error occurs, i.e., the four bits received have odd number of 1s and PEC = 0 if no error occurs, i.e., if the 4-bit message has even number of 1s. Combinational Logic 150  Truth Table Combinational Logic 151 Combinational Logic 152  The above logic expression for the even parity checker can be implemented by using three Ex-OR gates Combinational Logic 153  Odd Parity Checker where PEC =1 if the 4-bit message received consists of even number of 1s (hence the error occurred) and PEC= 0 if the message contains odd number of 1s (that means no error). Combinational Logic 154 Combinational Logic 155