Logic and Computer Design Fundamentals Chapter 4 Combinational Functions and Circuits
Functions of a single variable Can be used on inputs to functional blocks to implement other than block s intended function TABLE 4- Functions of One Variable F = F = F = F = V CC or V DD F5 F5 (c) F 5 F5 F5 F 5 (a) (b) (d) Chapter 4 2
Multi-bit Examples: A F 3 F 2 F A F (a) A A 2 3 4 A wide line is used to represent a bus which is a vector signal In (b) of the example, F = (F 3, F 2, F, F ) is a bus. The bus can be split into individual bits as shown in (b) (b) F (d) Sets of bits can be split from the bus as shown in (c) for bits 2 and of F. The sets of bits need not be continuous as shown in (d) for bits 3,, and of F. F 4 2 2: F F(2:) (c) 4 3,: 3 F(3), F(:) Chapter 4 3
F EN (a) EN F (b) Chapter 4 4
Decoding - conversion of an n-bit input code to an m-bit output code with n m 2 n such that each valid code word produces a unique output code Circuits that perform decoding are called decoders Here, functional blocks for decoding are called n-to-m line decoders, where m 2 n, and generate 2 n (or fewer) minterms for n input variables Chapter 4 5
-to-2-line Decoder 2-to-4-Line Decoder A D D A (a) A (b) D 5 A D 5 A A A D D D 2 D 3 A D 5 A A D 5 A A (a) Note that 2-4-line made up of 2 -to-2- line decoders and 4 AND gates. (b) D 2 5 A A D 3 5 A A Chapter 4 6
General procedure given in book for any decoder with n inputs and 2 n outputs. This procedure builds a decoder backward from outputs. The output AND gates are driven by two decoders with their numbers of inputs either equal or differing by. These decoders are then designed using same procedure until 2-to--line decoders are reached. Procedure can be modified to apply to decoders with the number of outputs 2 n Chapter 4 7
3-to-8-line decoder Number of output ANDs = 8 Number of inputs to decoders driving output ANDs = 3 Closest possible split to equal 2-to-4-line decoder -to-2-line decoder 2-to-4-line decoder Number of output ANDs = 4 Number of inputs to decoders driving output ANDs = 2 Closest possible split to equal Two -to-2-line decoders Chapter 4 8
Result 4 2-input ANDs 8 2-input ANDs A D D A D 2 2-to-4-Line decoder D 3 D 4 A 2 D 5 -to-2-line decoders D 6 D 7 3-to-8 Line decoder Chapter 4 9
7-to-28-line decoder Number of output ANDs = 28 Number of inputs to decoders driving output ANDs = 7 Closest possible split to equal 4-to-6-line decoder 3-to-8-line decoder 4-to-6-line decoder Number of output ANDs = 6 Number of inputs to decoders driving output ANDs = 2 Closest possible split to equal 2 2-to-4-line decoders Complete using known 3-8 and 2-to-4 line decoders Chapter 4
In general, attach m-enabling circuits to outputs See truth table below for function Note use of s to denote both and Combination containing two s represent four binary combinations Alternatively, can be viewed as distributing value of signal EN EN to of 4 outputs A In this case, called a demultiplexer A D EN A A D D D 2 D 3 D D 2 D 3 (a) (b) Chapter 4
Chapter 4 2
Chapter 4 3
Chapter 4 4
Chapter 4 5
Encoding - opposite of decoding - conversion of an m-bit input code to a n-bit output code with n m 2 n such that each valid code word produces a unique output code Circuits that perform encoding are called encoders An encoder has 2 n (or fewer) input lines and n output lines which generate binary code corresponding to input values Typically, an encoder converts a code containing exactly one bit that is to a binary code corresponding to position in which appears. Chapter 4 6
A decimal-to-bcd encoder Inputs: bits corresponding to decimal digits through 9, (D,, D 9 ) Outputs: 4 bits with BCD codes Function: If input bit D i is a, then output (A 3, A 2, A, A ) is BCD code for i, Truth table could be formed, but alternatively, equations for each of four outputs can be obtained directly. Chapter 4 7
Input D i is a term in equation A j if bit A j is in binary value for i. Equations: A 3 = D 8 + D 9 A 2 = D 4 + D 5 + D 6 + D 7 A = D 2 + D 3 + D 6 + D 7 A = D + D 3 + D 5 + D 7 + D 9 F = D 6 + D 7 can be extracted from A 2 and A Is there any cost saving? Chapter 4 8
If more than one input value is, then encoder just designed does not work. One encoder that can accept all possible combinations of input values and produce a meaningful result is a priority encoder. Among s that appear, it selects the most significant input position (or the least significant input position) containing a and responds with corresponding binary code for that position. Chapter 4 9
Priority encoder with 5 inputs (D 4, D 3, D 2, D, D ) - highest priority to most significant present - Code outputs A2, A, A and V where V indicates at least one present. No. of Minterms/Row D4 D3 Inputs D2 D D A2 Outputs A A V 2 4 8 6 s in input part of table represent or ; thus table entries correspond to product terms instead of minterms. The column on left shows that all 32 minterms are present in product terms in table Chapter 4 2
Could use a K-map to get equations, but can be read directly from table and manually optimized if careful: A 2 = D 4 A = D 4 D 3 + D 4 D 3 D 2 = D 4 F, F = (D 3 + D 2 ) A = D 4 D 3 + D 4 D 3 D 2 D = D 4 (D 3 + D 2 D) V = D 4 + F + D + D Chapter 4 2
Chapter 4 22
Chapter 4 23
Chapter 4 24
Chapter 4 25
Since 2 = 2, n = single selection variable S has two values: S = selects input I S = selects input I Logic equation: Y = SI + SI Decoder Enabling Circuits S I I Y Chapter 4 26
S Decoder S 4 3 2 AND-OR S S Decoder I I Y Y I 2 I 3 Chapter 4 27
Chapter 4 28
Chapter 4 29
Alternative implementation techniques: Decoders and OR gates Multiplexers (and inverter) ROMs PLAs PALs Lookup Tables Can be referred to as structured implementation methods since a specific underlying structure is assumed in each case Chapter 4 3
Implement m functions of n variables with: Sum-of-minterms expressions One n-to-2 n -line decoder m OR gates, one for each output Approach : Find the truth table for the functions Make a connection to the corresponding OR from the corresponding decoder output wherever a appears in the truth table Approach 2 Find the minterms for each output function OR the minterms together Chapter 4 3
Implement the following set of odd parity functions of (A 7, A 6, A 5, A 3 ) P = A 7 + A 5 + A 3 A 7 P 2 = A 7 + A 6 + A 3 A 6 P 4 = A 7 + A 6 + A 5 A 5 A 4 Finding sum of minterms expressions P = Σ m (,2,5,6,8,,2,5) P 2 = Σ m (,3,4,6,8,,3,5) P 4 = Σ m (2,3,4,5,8,9,4,5) Find circuit 4-to-6 decoder + ORs 2 3 4 5 6 7 8 9 2 3 4 5 P P 2 P 4 Chapter 4 32
Chapter 4 33
Chapter 4 34
Chapter 4 35
Equations: F = A B C + A B C + A B C + ABC F2 = AB + BC + AC F must be factored since four terms Factor out last two terms as W Product term 2 3 4 5 6 7 8 9 2 AND Inputs A B C D W Outputs W = A BC + ABC F = = A B C + AB C + W F2 = Y = AB + BC +AC Chapter 4 36
Product term AND gates inputs A A B B C C D D W W 2 W 3 A 4 All fuses intact (always 5 ) 5 F 6 B 7 8 F2 9 C 2 D A A B B C C D D W W Fuse intact Fuse blown Chapter 4 37
BC K-map A specification How can this be implemented A with four terms? Complete the programming table B C F 5 A BC + A B C + A B C F 5 AB + AC + BC + A B C BC A A PLA programming table B C F 2 5 AB + AC +BC F 2 5 AC + AB + BC Product term Inputs A B C Outputs ( ) F (T) F 2 AB AC BC 2 3 4 Chapter 4 38
A B C 2 Fuse intact Fuse blown 3 4 C C B B A A F F 2 Chapter 4 39
Lookup tables are used for implementing logic in Field-Programmable Gate Arrays (FPGAs) and Complex Logic Devices (CPLDs) Lookup tables are typically small, often with four inputs, one output, and 6 entries Since lookup tables store truth tables, it is possible to implement any 4-input function Thus, design problem is how to optimally decompose a set of given functions into a set of 4-input two- level functions. Chapter 4 4
Equations to be implemented: F (A,B,C,D,E) = A D E + B D E + C D E F 2 (A,B,D,E,F) = A D E + B D E + F D E Extract 4-input function: F 3 (A,B,D,E) = A D E + B D E F (C,D,E,F 3 ) = F 3 + C D E F 2 (D,E,F,F 3 ) = F 3 + F D E The cost of the solution is 3 lookup tables Chapter 4 4
Chapter 4 42
Chapter 4 43
Chapter 4 44
Chapter 4 45
- Chapter 4 46