Combinational Logic PDF

Chapter 5: Combinational Logic SkillsArray Digital Logic Introduction Logic circuits for digital systems may be; 1. Combinational  Consists of input variables, logic gates, and output variables.  Outputs at any time determined from only the present comb...

Chapter 5: Combinational Logic SkillsArray Digital Logic Introduction Logic circuits for digital systems may be; 1. Combinational  Consists of input variables, logic gates, and output variables.  Outputs at any time determined from only the present combination of inputs. 2. Sequential  Employ storage elements in addition to logic gates.  Outputs are a function of present inputs, past inputs,  They are the building blocks of digital systems SkillsArray Digital Logic 2  For n input variables, there are 2n possible combinations of the binary inputs. The diagram of a combinational circuit has logic gates with no feedback paths or memory elements. SkillsArray Digital Logic 3  Combinational vs. Sequential Circuits n-inputs Combinational m-outputs Circuit (Depend only on inputs) Combinational Circuit n-inputs m-outputs Combinational Circuit Storage Next Elements Present state state Sequential Circuit SkillsArray Digital Logic 4 Functional Blocks Fundamental circuits that are the base building blocks of most larger digital circuits They are reusable and are common to many systems. Examples of functional logic circuits i. Code converters ii. Adders iii. Decoders iv. Encoders v. Multiplexers SkillsArray Digital Logic 5 Where they are used Multiplexers  Selectors for routing data to the processor, memory, I/O  Multiplexers route the data to the correct bus or port. Decoders  Used for selecting things like a bank of memory and then the address within the bank.  This is also the function needed to ‘decode’ the instruction to determine the operation to perform. Encoders  Used in various components such as keyboards. SkillsArray Digital Logic 6 Analysis To obtain the output Boolean functions from a logic diagram: 1. Label all gate outputs that are a function of input variables with arbitrary symbols. Determine the Boolean functions for each gate output. 2. Label the gates that are a function of input variables and previously labeled gates with other arbitrary symbols. Find the Boolean functions for these gates. 3. Repeat the step 2 until the outputs of the circuit are obtained. 4. By repeated substitution of previously defined functions, obtain the output Boolean functions in terms of input variables. SkillsArray Digital Logic 7 Example SkillsArray Digital Logic 8  The Boolean functions derived from the input variables are; F2 = AB + AC + BC T1 = A + B + C T2 = ABC Outputs of gates that are a function of already defined symbols T3 = F’2T1 F1 = T3 + T2 F1 = T3 + T2 = F’2T1 + ABC = (AB + AC + BC)’(A + B + C) + ABC = (A’ + B’)(A’ + C’)(B’ + C’)(A + B + C) + ABC = (A’ + B’C’)(AB’ + AC’ + BC’ + B’C) + ABC = A’BC’ + A’B’C + AB’C’ + ABC SkillsArray Digital Logic 9  The truth table for the previous example is given as; SkillsArray Digital Logic 10 Design Procedure Steps i. Specifications: determine the required number of inputs and outputs and assign a symbol to each. ii. Formulation: i. Derive the truth table that defines the required relationship between inputs and outputs. ii. Obtain the simplified Boolean functions for each output as a function of the input variables. iii. Optimization: Draw the logic diagram and verify the correctness of the design (manually or by simulation). iv. Technology Mapping: Map the logic diagram to the implementation technology selected v. Evaluation: Evaluate the timing and power SkillsArray Digital Logic 11 1&2. Specification & Formulation A conversion circuit –  Inserted between the two systems each using different codes for the same information.  Makes the two systems compatible BCD to Excess-3 code converter BCD code words for digits 0 through 9: 4-bit patterns 0000 to 1001, respectively Excess-3 code words for digits 0 through 9: 4-bit patterns consisting of 3 (binary 0011) added to each BCD code word SkillsArray Digital Logic 12 3. Optimization For each symbol of the Excess-3 code, we use 1’s to draw the map for simplifying Boolean function. SkillsArray Digital Logic 13 z = D’ 4. Mapping y = CD + C’D’ = CD + (C + D)’ x = B’C + B’D + BC’D’ = B’(C + D) + BC’D’ = B’(C + D) + B(C + D)’ w = A + BC + BD = A + B(C + D) SkillsArray Digital Logic 14 4. Mapping Cont… A W B X C Y D Z SkillsArray Digital Logic 15 Binary Adder SkillsArray Digital Logic 16 Half Adder A combinational circuit that performs the addition of two bits is called a half adder. The truth table for the half adder is listed below: S: Sum C: Carry S = x’y + xy’ C = xy SkillsArray Digital Logic 17 SkillsArray Digital Logic 18 Full-Adder A combinational circuit that performs the addition of three bits(two significant bits and a previous carry) is a full adder. It has three inputs and two outputs, whereas half adder has only two inputs and two outputs. The first two inputs are A and B and the third input is an input carry as C-IN. SkillsArray Digital Logic 19 Full-Adder Function S = x’y’z + x’yz’ + xy’z’ + xyz C = xy + xz + yz SkillsArray Digital Logic 20 Simplified Expressions SkillsArray Digital Logic 21 Full adder implemented in SOP SkillsArray Digital Logic 22  Full-adder can also implemented with two half adders and one OR gate (Carry Look-Ahead adder). S = z ⊕ (x ⊕ y) = z’(xy’ + x’y) + z(xy’ + x’y)’ = xy’z’ + x’yz’ + xyz + x’y’z C = z(xy’ + x’y) + xy = xy’z + x’yz + xy SkillsArray Digital Logic 23 Half Adder Vs Full Adder SkillsArray Digital Logic 24 Full Adder Circuit Diagram SkillsArray Digital Logic 25  In a computer, for a multi-bit operation, each bit must be represented by a full adder and must be added simultaneously.  To add two 8-bit numbers, you will need 8 full adders which can be formed by cascading two of the 4-bit blocks. SkillsArray Digital Logic 26 Example: Binary Adder Also called Ripple Carry Adder, because of the construction with full adders are connected in cascade. Consider the two binary numbers A = 1011 & B = 0011 Their sum S = 1110 is formed with the four-bit adder as follows: SkillsArray Digital Logic 27 Carry Propagation Because the propagation delay will affect the output signals on different time, signals are given enough time to get the precise and stable outputs. For an n -bit adder, there are 2n gate levels for the carry to propagate from input to output. Since all other arithmetic operations are implemented by successive additions, the time consumed during the addition process is critical. Solutions  Use faster gates with reduced delays. However, physical circuits have a limit to their capability.  Increase the complexity of the equipment in such a way that the carry delay time is reduced.  The most widely used technique employs the principle of carry look- ahead to improve the speed of the algorithm. SkillsArray Digital Logic 28 Cont… SkillsArray Digital Logic 29 Boolean Functions Pi = Ai ⊕ Bi steady state value Gi = AiBi steady state value Output: sum and carry Si = Pi ⊕ Ci Ci+1 = Gi + PiCi Gi : carry generate Pi : carry propagate C0 = input carry C1 = G0 + P0C0 C2 = G1 + P1C1 = G1 + P1G0 + P1P0C0 C3 = G2 + P2C2 = G2 + P2G1 + P2P1G0 + P2P1P0C0 C3 does not have to wait for C2 and C1 to propagate. SkillsArray Digital Logic 30 Logic diagram of carry look-ahead generator C3 is propagated at the same time as C2 and C1. SkillsArray Digital Logic 31 4-bit Adder with Carry Lookahead Delay time of n-bit CLAA = XOR + (AND + OR) + XOR SkillsArray Digital Logic 32 Binary Subtractor The number from which other number is to be deducted is called as minuend and the number subtracted from the minuend is called subtrahend. SkillsArray Digital Logic 33 Half-Subtractor SkillsArray Digital Logic 34 Full-Subtractor It has three input terminals in which two terminals corresponds to the two bits to be subtracted (minuend A and subtrahend B), and a borrow bit Bi corresponds to the borrow operation. There are two outputs, one corresponds to the difference D output and other borrow output Bo SkillsArray Digital Logic 35 SkillsArray Digital Logic 36 Parallel Binary Subtractors This can be designed in several ways, including combination of half and full subtractors, all full subtractors, all full adders with subtrahend complement input, etc. SkillsArray Digital Logic 37 Using Full- Subtractors Using Full- Adders with an Inverter SkillsArray Digital Logic 38 Parallel Adder / Subtractor Computers need only one common hardware circuit to handle both types of arithmetic. M = 1subtractor ; M = 0adder The exclusive- OR with output V is for detecting an overflow. SkillsArray Digital Logic 39 Applications of Full Subtractor Employed for ALU (Arithmetic logic unit) in computers to subtract at CPU & GPU for the applications of graphics to decrease the circuit difficulty. Performing arithmetical functions like subtraction, in electronic calculators as well as digital devices. Applicable for different microcontrollers for arithmetic subtraction, timers, and program counter (PC) Used in processors to compute tables, address, etc. It is also useful for DSP and networking based systems. SkillsArray Digital Logic 40 Overflow Binary numbers in the signed-complement system in binary subtractor are added and subtracted by the same basic addition and subtraction rules as unsigned numbers. Overflow is a problem in digital computers because the number of bits that hold the number is finite and a result that contains n+1 bits cannot be accommodated. SkillsArray Digital Logic 41 Overflow on signed and unsigned When two unsigned numbers are added,  an overflow is detected from the end carry out of the MSB position. When two signed numbers are added,  the leftmost bit always represents the sign  the sign bit is treated as part of the number and the end carry does not indicate an overflow. An overflow cannot occur after an addition if one number is positive and the other is negative. An overflow may occur if the two numbers added are both positive or both negative. SkillsArray Digital Logic 42 Example Two signed binary numbers, ±70 and ± 80, are stored in two eight-bit registers. The range of numbers that each register can accommodate is from binary +127 to binary -128. Since the sum of the two numbers is ± 150, it exceeds the capacity of an eight-bit register. SkillsArray Digital Logic 43 Decimal adder SkillsArray Digital Logic 44  BCD Adder BCD adder can’t exceed 9 on each input digit. K is the carry. SkillsArray Digital Logic 45  When the binary sum is greater than 1001, we obtain a non-valid BCD representation. The addition of binary 6(0110) to the binary sum converts it to the correct BCD representation and also produces an output carry as required. To distinguish them from binary 1000 and 1001, which also have a 1 in position Z8, we specify further that either Z4 or Z2 must have a 1. C = K + Z8Z4 + Z8Z2 SkillsArray Digital Logic 46  A decimal parallel adder that adds n decimal digits needs n BCD adder stages. The output carry from one stage must be connected to the input carry of the next higher- order stage. SkillsArray Digital Logic 47 Binary Multiplier SkillsArray Digital Logic 48 Two-bit by Two-bit Binary Multiplier Usually there are more bits in the partial products and it is necessary to use full adders to produce the sum of the partial products. And SkillsArray Digital Logic 49 Four-bit by Three- bit Binary Multiplier For J multiplier bits and K multiplicand bits we need (J X K) AND gates and (J − 1) K-bit adders to produce a product of J+K bits. K=4 and J=3, we need 12 AND gates and two 4-bit adders. SkillsArray Digital Logic 50 Magnitude Comparator A magnitude comparator is a combinational circuit that compares two numbers A and B and determines their relative magnitudes. The outcome of the comparison is specified by three binary variables that indicate whether A>B A=B A