Baixe o app para aproveitar ainda mais
Prévia do material em texto
249 Chapter 12 Exercise 12.1: The controller has 6 states, and we are going to use the one- ip- op per state appoach for the design. The inputs are: Input condition GO A DIST > 10 B (DIST � 10) and (COUNT = 3) C (DIST � 10) and (COUNT 6= 3) Calling the inputs of the ip ops for each state as NS i , we generate the following expressions: NS 0 = S 0 :GO 0 NS 1 = S 0 :GO + S 3 NS 2 = S 1 :C NS 3 = S 2 + S 4 NS 4 = S 1 :A NS 5 = S 1 :B + S 5 These expressions are implemented in a PSA as shown in Figure 12.1. Exercise 12.2: A modulo-11 counter is expressed by the following state transition and output function table: PS Input y 3 y 2 y 1 y 0 x = 0 x = 1 0000 0000,0 0001,0 0001 0001,0 0010,0 0010 0010,0 0011,0 0011 0011,0 0100,0 0100 0100,0 0101,0 0101 0101,0 0110,0 0110 0110,0 0111,0 0111 0111,0 1000,0 1000 1000,0 1001,0 1001 1001,0 1010,0 1010 1010,0 0000,1 NS(Y 3 Y 2 Y 1 Y 0 ), output From this table, using Kmaps we obtain the following minimal expressions for the next state bits and the output (terminal count - TC): Y 3 = y 3 x 0 + (y 3 y 0 1 + y 2 y 1 y 0 )x = y 3 x 0 + y 3 y 0 1 x+ y 2 y 1 y 0 x Y 2 = y 2 x 0 + (y 2 y 0 1 + y 2 y 0 0 + y 0 2 y 1 y 0 )x = y 2 x 0 + y 2 y 0 1 x+ y 2 y 0 0 x+ y 0 2 y 1 y 0 x Y 1 = y 1 x 0 + (y 0 1 y 0 + y 0 3 y 1 y 0 )x = y 1 x 0 + y 0 1 y 0 x+ y 0 3 y 1 y 0 x Y 0 = y 0 x 0 + (y 0 1 y 0 0 + y 0 3 y 0 0 )x = y 0 x 0 + y 0 1 y 0 0 x+ y 0 3 y 0 0 x TC = y 3 y 1 x 250 Solutions Manual - Introduction to Digital Design - August 2, 1999 AND Array OR Array -- programmable connection 1 2 6 -- connection made 3 4 5 9 7 8 State RegisterCK S0 S1 S2 S3 S4 S5 NS0 NS1 NS2 NS3 NS4 NS5 S0 S1 S2 S3 S4 S5 GO A B C Figure 12.1: PSA implementation of a controller - Exercise 12.1 The implementation of these equations using a PSA is shown in Figure 12.2. Exercise 12.3: The number of address lines should be 4, since a BCD digit is the single input. The maximum value to be stored in the ROM is 9 2 = 81, which requires dlog 2 81e = 7 bits to be represented in binary. Thus, at least a 16 � 7 ROM is required to implement the function. Exercise 12.4: The system that converts from BCD to Excess-3 is shown in Figure 12.3. It implements the following table: Solutions Manual - Introduction to Digital Design - August 2, 1999 251 OR Array 1 2 6 3 4 5 7 8 y2 y1 y0 xy3 AND Array -- programmable connection -- connection made State RegisterCK y3 y2 y1 y0 Y3 Y2 Y1 Y0 TC 9 10 11 12 13 14 Figure 12.2: Modulo-11 counter - Exercise 12.2 BCD Excess 3 b 3 b 2 b 1 b 0 q 3 q 2 q 1 q 0 0000 0011 0001 0100 0010 0101 0011 0110 0100 0111 0101 1000 0110 1001 0111 1010 1000 1011 1001 1100 Exercise 12.5: For this implementation we need a 2 12 � 6 ROM. Twelve address lines receive the input bits from a, b, and c 2 f0; 1; :::; 15g. Six bits are required to represent 0 � s � 45. The block diagram of the component is shown in Figure 12.4. 252 Solutions Manual - Introduction to Digital Design - August 2, 1999 decoder 0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ROM q1q3 q2 q0 b0 b1 b2 b3 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 - - - - - - - - - - - - - - - - - - - - - - - - Figure 12.3: BCD to Excess-3 converter - Exercise 12.4 Exercise 12.6: The high-level speci�cation of the single-digit decimal adder is: Input: A,B 2 f0; 1; 2; :::; 9g and c in 2 f0; 1g Output: S 2 f0; 1; 2; :::; 9g and c out 2 f0; 1g Function: S = ( A+B + c in if A+B + c in < 10 A+B + c in � 10 if A+B + c in � 10 c out = ( 0 if A+B + c in < 10 1 if A+B + c in � 10 Calling a, b and s the integers obtained from the Excess-3 representation we get: a = A+ 3 b = B + 3 s = S + 3 Substituting these expressions on the equations above, we obtain: s = ( a+ b+ c in � 3 if a+ b+ c in � 6 < 10 a+ b+ c in � 13 if a+ b+ c in � 6 � 10 c out = ( 0 if a+ b+ c in � 6 < 10 1 if a+ b+ c in � 6 � 10 Solutions Manual - Introduction to Digital Design - August 2, 1999 253 de co de r 0 1 2 3 4 5 6 7 8 9 10 11 0 1 2 3 4095 ROM 0 0 0 0 0 0 0 0 0 0 0 1 1 0 1 1 0 1 s1s3 s2 s0 a3 a2 a1 a0 b3 b2 b1 b0 c3 c2 c1 c0 0 0 0 0 1 0 0 0 0 0 1 1 s5 s4 Figure 12.4: ROM implementation - 3-input 4-bit adder - Exercise 12.5 The ROM implementation of a single digit Excess-3 adder requires 9 addressing lines (512 words). Four bits are used by each Excess-3 digit a or b (represented by a and b), and one bit is used for carry input (c in ). Each word needs to have 5 bits: four bits for the output digit in Excess-3 (s) and one bit for carry output (c out ). We de�ne the address vector as x = (a; b; c in ), which is the binary representation of x = 32a + 2b + c in and the contents of each word as w = (c out ; s), which corresponds to w = 16c out + s. The value in each word position x of the ROM is given as: w = ( a+ b+ c in � 3 if a+ b+ c in < 16 a+ b+ c in + 3 if a+ b+ c in � 16 A block diagram for the ROM showing some words' contents is presented in Figure 12.5. Address 102, for example, corresponds to the addition of A = 0 and B = 0 in Excess-3 (a = b = 3), and c in = 0. Exercise 12.7: Part (a) - using one decoder and ROM modules of eight 4-bit words. Figure 12.6 COST = 4� (ROM) +DEC = 4� (ROM) + 4� (AND-2) + 2� (NOT) #interconnections = 13 delay = �(ROM) + �(AND-2) + �(NOT) where � represents the component delay. Part (b) - using ROM modules and a multiplexer. Figure 12.7. COST = 4� (ROM) +MUX = 4� (ROM) + 16� (AND-3) + 4� (OR-4) + 2� (NOT) #interconnections = 29 254 Solutions Manual - Introduction to Digital Design - August 2, 1999 de co de r 0 1 2 3 4 5 6 7 8 0 1 2 3 102 103 104 105 106 107 408 409 511 ROM - - - - - - - - - - - - - - - - - - - - 1 1 1 1 1 c out s1s3 s2 s0 c in a0 a1 a2 a3 b0 b1 b2 b3 0 0 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 0 1 0 0 1 0 1 0 0 1 1 0 1 1 0 1 1 1 1 1 0 0 Figure 12.5: ROM implementation of an Excess-3 digit adder - Exercise 12.6 delay = �(ROM) + �(MUX) = �(ROM) + �(AND-3) + �(OR-4) Thus, the �rst design is better than the second one in all aspects. Exercise 12.8: Since the number of products used by each output is not known, we need to assume the worst case situation, when most of them are used by a single output, and 1 (or none) is used by the other outputs. The PLA provides only 128 product terms, thus, we need to use two PLAs to obtain 256 product terms, combining their outputs with OR gates. The number of inputs is also larger than the number of inputs in each PLA device, thus, a binary decoder is used to select among 4di�erent PLA banks, each bank consisting of a pair of PLAs with ORed outputs. The design is shown in Figure 12.8. Exercise 12.9: For the ROM implementation of the function we need 2 6 words of 2 bits. Thus, a complete switching function table should be implemented, with 64 entries. For the PLA implementation, it is important to notice that z 1 = 1 when a = b, and z 0 = 1 when a = (b� 1) mod 8. The minterms used to generate z 1 are shown in the following table: Solutions Manual - Introduction to Digital Design - August 2, 1999 255 a b f0 f1 f2 f3 0001 0010 0000 0100 0001 0010 1000 0000 E decoder 0 1 2 3 1 0 0110 1000 0000 0100 1000 1000 0001 0000 E c d e c d e 1000 0010 0000 0001 0010 0010 1000 0100 E c d e 0001 0010 1000 0000 0000 0100 1010 0000 E c d e 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 2 1 0 2 1 0 2 1 0 2 1 0 ROM ROM ROM ROM Figure 12.6: Implementation of switching function using one decoder and ROM- Ex. 12.7 a 2 a 1 a 0 b 2 b 1 b 0 product terms to generate z 1 000 000 a 0 2 a 0 1 a 0 0 b 0 2 b 0 1 b 0 0 001 001 a 0 2 a 0 1 a 0 b 0 2 b 0 1 b 0 010 010 a 0 2 a 1 a 0 0 b 0 2 b 1 b 0 0 011 011 a 0 2 a 1 a 0 b 0 2 b 1 b 0 100 100 a 2 a 0 1 a 0 0 b 2 b 0 1 b 0 0 101 101 a 2 a 0 1 a 0 b 2 b 0 1 b 0 110 110 a 2 a 1 a 0 0 b 2 b 1 b 0 0 111 111 a 2 a 1 a 0 b 2 b 1 b 0 For PLAs what matters is the number of product terms. It is not possible to reduce the number of product terms shown in the table since both a and b change one bit from one row to another. Thus, two literals are di�erent from one minterm to another, making impossible the combination of two minterms. The number of product terms is already minimal. Similarly, for z 0 (the case a = (b� 1) mod 8): a 2 a 1 a 0 b 2 b 1 b 0 product terms to generate z 0 000 111 a 0 2 a 0 1 a 0 0 b 2 b 1 b 0 001 000 a 0 2 a 0 1 a 0 b 0 2 b 0 1 b 0 0 010 001 a 0 2 a 1 a 0 0 b 0 2 b 0 1 b 0 011 010 a 0 2 a 1 a 0 b 0 2 b 1 b 0 0 100 011 a 2 a 0 1 a 0 0 b 0 2 b 1 b 0 101 100 a 2 a 0 1 a 0 b 2 b 0 1 b 0 0 110 101 a 2 a 1 a 0 0 b 2 b 0 1 b 0 111 110 a 2 a 1 a 0 b 2 b 1 b 0 0 where again the number of product terms is minimal. 256 Solutions Manual - Introduction to Digital Design - August 2, 1999 1 0 a b 0123 0123 0123 0123 4x4-input MUX f0 f1 f2 f3 0110 1000 0000 0100 1000 1000 0001 0000 E 1 c d e 2 1 0 0 1 2 3 4 5 6 7 0001 0010 0000 0100 0001 0010 1000 0000 E 1 c d e 2 1 0 0 1 2 3 4 5 6 7 1000 0010 0000 0001 0010 0010 1000 0100 E 1 c d e 2 1 0 0 1 2 3 4 5 6 7 c d e 2 1 0 0 1 2 3 4 5 6 7 0001 0010 1000 0000 0000 0100 1010 0000 E 1 ROM ROM ROM ROM Figure 12.7: Implementation of switching function using ROM and MUX - Ex. 12.7 Thus, the PLA would need to have 16 products, 6 inputs, and 2 outputs. Exercise 12.10: The design of the BCD counter can be done with the ROM module, 4-bit register and AND gate, as shown in Figure 12.9. No need for the adder. The ROM module receives the Present State of the counter (stored in the 4-bit register) as address bits. Each word contains the value of the next state. Using the LOAD input of the register the circuit will load the next state only when CNT = 1. The state is kept the same when CNT = 0. The terminal count output is generated by the AND gate, as TC = Q 3 Q 0 . PLA PLA PLA bank En Input En Input outputs outputs PLA Bank 0 PLA Bank 1 PLA Bank 2 PLA Bank 3 binary dec 0 1 0 1 2 3 x12 x13 E 1 (x11,x10,...,x1,x0) z0 z1 z2 z3 Figure 12.8: Design using PLAs - Exercise 12.8 Solutions Manual - Introduction to Digital Design - August 2, 1999 257 ROM de co de r0 1 2 3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 00010 00100 00110 01000 01010 01100 01110 10000 10010 00001 ----- ----- ----- ----- ----- ----- LD Register CNT CK TC Q3 Q2 Q1 Q0 Figure 12.9: BCD counter - Exercise 12.10 Exercise 12.11: Size of state register and ROM for: (a) Moore sequential system with 512 states, 3 inputs and 2 outputs. For 512 states, a minimum of 9 bits are required to represent each state. The ROM needs to have as many address lines as the number of state bits plus the number of inputs, which corresponds to a total of 12 bits. Since this is a Moore machine the total number of ROM bits is reduced by using separate ROMs to generate the next state and to generate the outputs. The ROM for the next state will have 2 12 � 9 bits. The ROM to generate the output will be a 2 9 � 2 bits ROM. Thus, the implementation will require a 2 12 � 9 ROM, a 2 9 � 9 ROM, a and a 9-bit register. Of course, the implementation can use only one ROM, resulting the same as for the Mealy case. (b) For a Mealy model, the system will have only a single 2 12 � 11 ROM, and a 9-bit register. This time the output values are stored with the next state bits. (c) When the state transition depends only on one input, a multiplexer (in this case a network of multiplexer would be required, since the number of inputs is quite large). The multiplier is used to select the correct input among the possible system inputs, depending on the present state of the system. The output of the multiplexer is used as an address line for the ROM 258 Solutions Manual - Introduction to Digital Design - August 2, 1999 which will have a size of 2 10 � 9 bits, and generates the next state bits. Since this is a Moore machine, another ROM is used to generate the outputs. Same way as done in part (a), a 2 9 � 2 ROM is required for the outputs. A 9-bit register is used to store the state values. A block diagram of the system is shown in Figure 12.10. MUX Present State system inputs active in each state ROM ROM a dd re ss a dd re ssCLK outputs Figure 12.10: Block diagram for Exercise 12.11(c) (d) For a Mealy system, with the same conditions of the one considered in part (c), a 2 10 � 11 ROM, a network of muxes to select the input (same as in part (c)), and a 9-bit register are used. The ROM stores both the next state bits and the output values. (e) Since the system in part (c) is implemented as a Moore machine, the output doesn't depend on the input values, and for this reason, this question doesn't make sense. If we apply this idea to the system in part (d), then the output should be generated by a separate ROM with 11 addressing lines and 2-bit words. The generation of the next state would be done by a 2 10 � 9 ROM. The network of muxes to select the inputs would be used, and a 9-bit register would store the state bits. Exercise 12.12: From Figure 12.18 of the text we obtain the following statetransition and output table: PS Input z y 2 y 1 y 0 x = 0 x = 1 000 000 100 1 001 010 110 0 010 000 100 0 011 011 111 0 100 001 101 1 101 000 100 0 110 011 111 0 111 001 101 1 NS Using the name S i for state i we obtain the following high level description of the sequential system: Solutions Manual - Introduction to Digital Design - August 2, 1999 259 Input: x 2 f0; 1g Output: z 2 f0; 1g States: S i , with 0 � i � 7 State transition and output function table: PS Input z y 2 y 1 y 0 x = 0 x = 1 S 0 S 1 S 4 1 S 1 S 2 S 6 0 S 2 S 0 S 4 0 S 3 S 3 S 7 0 S 4 S 1 S 5 1 S 5 S 0 S 4 0 S 6 S 3 S 7 0 S 7 S 1 S 5 1 NS The state diagram for the system is shown in Figure 12.11. S0/1 S1/0 S2/0 S3/0 S4/1S5/0S6/0S7/1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 Figure 12.11: State diagram for system in Exercise 12.12. Exercise 12.13: Observe that each state has transitions to another state based on only one input among 3 possible inputs 2 fa; b; cg. A multiplexer can be used to select the desired input, and the diagram can be modi�ed to have only one input, let's call it x. The new transition table would be: PS Inputs x = 0 x = 1 S0 S3/10 S1/01 S1 S1/00 S2/01 S2 S3/00 S4/01 S3 S1/00 S0/00 S4 S4/00 S3/11 NS,z 1 z 0 260 Solutions Manual - Introduction to Digital Design - August 2, 1999 Assume that the state S i is represented by the vector i = (y 2 ; y 1 ; y 0 ). The network that imple- ments the state diagram is given in Figure 12.12. 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ROM MUX 0 1 2 3 4 5 6 7 2 1 0 01110 00100 01100 00100 10000 xxxxx xxxxx xxxxx 00101 01001 10001 00000 01111 xxxxx xxxxx xxxxx x Reg CK a c a b b y2 y1 y0 y2 y1 y0 Y2Y1Y0 (next State) (present state) z0 z1 Y2 Y1 Y0 y2 y1 y0 Next state Present State 3 2 1 0 E 1 E 1 Figure 12.12: Network for Exercise 12.13 Solutions Manual - Introduction to Digital Design - August 2, 1999 261 Exercise 12.14: Part (a): Based on the information that the ROM word contains: � the next state bits (3 bits are required for a sequence of 8 clock cycles), � the output bits for T 1 , T 2 , and T 3 , and � one bit L that controls the load of the register that stores the sequence number s. we conclude that each ROM word requires 7 bits. Since 16 di�erent sequences are generated by the system, 16� 8 = 128 words are required. Thus, a 128� 7 ROM is used. Part (b): The system diagram is shown in Figure 12.13. COMMENT: the s value is loaded at the last clock cycle of the sequence, not the one before the last. T1 T2 T3 s CK ce D Q4s most significant address bits Q2Q1Q0 8 words ROM s=0 s=1 s=2 s=3 s=4 s=5 s=15 L CK 3 3Q2Q1Q0 T1T2T3 L Q2Q1Q0 T1T2T3 L 0 0 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 1 1 1 0 1 0 0 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 1 1 0 0 1 0 0 0 0 0 0 0 1 System 3 4 Figure 12.13: System implementation for Exercise 12.14 Part (c): The contents of the ROM for the case s = 5 is the following: Address Next State T 1 T 2 T 3 L 101000 001 011 0 101001 010 110 0 101010 011 111 0 101011 100 100 0 101100 101 101 0 101101 110 000 0 101110 111 001 0 101111 000 000 1 262 Solutions Manual - Introduction to Digital Design - August 2, 1999 Exercise 12.15: For this design we use a ROM that receives as input lines the values of the present state, and 2 input bits. In fact, there are 3 conditions that are used as inputs, but making use the the multiplexer we are able to select among two inputs: GO and DIST > 10. The third input is inserted directly as an address signal to the ROM. The ROM contains the information on the next state and the outputs (CLEAR,CHECK,TURNLEFT90,COUNTUP ,MOVE,STOP ). Thus 9 bits are required per ROM word. The design is shown in Figure 12.14. 0 000100000 1 000100000 2 001100000 3 001100000 4 010010000 5 101010000 6 100010000 7 100010000 8 011001000 9 011001000 10 -------- 11 -------- 12 001000100 13 001000100 14 -------- 15 -------- 16 011000010 17 011000010 18 -------- 19 -------- 20 101000001 21 101000001 22 -------- 23 -------- 24 -------- 25 -------- 26 -------- 27 -------- 28 -------- 29 -------- 30 -------- 31 -------- 0 1 2 3 4 de co de r ROM Reg. CK COUNT=3 MUX 0 1 2 3 4 5 6 7 2 1 0 GO DIST>10 0 0 0 0 0 0 STOP MOVE COUNTUP TURNLEFT90 CHECK CLEAR Figure 12.14: Circuit for Exercise 12.15 Exercise 12.16: The ROM used to design this counter should have 2 8 words of 8 bits each. We consider the design of an autonomous counter. The block diagram for the circuit is shown in Figure 12.15. The contents of the ROM would be too lengthy to describe using a table with all entries. It is easier to consider the following tabular description that uses ranges of values. ROM addresses or word contents are represented by a pair (x; y), with x; y 2 f0; 1; 2; :::15g. As an example, the range speci�ed as (1; 10)� (1; 15) represents the ordered sequence of values: (1; 10); (1; 11); (1; 12); (1; 13); (1; 14); and (1; 15). Solutions Manual - Introduction to Digital Design - August 2, 1999 263 ROM ad dr es s TC CLK Figure 12.15: ROM implementation of Decimal Counter - Exercise 12.16 Address Contents (0,0)-(0,9) (0,1)-(0,9),(1,0) (0,10)-(0,15) d.c. (1,0)-(1,9) (1,1)-(1,9),(2,0) (1,10)-(1,15) d.c. (2,0)-(2,9) (2,1)-(2,9),(3,0) (2,10)-(2,15) d.c. (3,0)-(3,9) (3,1)-(3,9),(4,0) (3,10)-(3,15) d.c. (4,0)-(4,9) (4,1)-(4,9),(5,0) (4,10)-(4,15) d.c. (5,0)-(5,9) (5,1)-(5,9),(6,0) (5,10)-(5,15) d.c. (6,0)-(6,9) (6,1)-(6,9),(7,0) (6,10)-(6,15) d.c. (7,0)-(7,9) (7,1)-(7,9),(8,0) (7,10)-(7,15) d.c. (8,0)-(8,9) (8,1)-(8,9),(9,0) (8,10)-(8,15) d.c. (9,0)-(9,9) (9,1)-(9,9),(0,0) (9,10)-(15,15) d.c. The ROM address receives the present state bits and the contents of a ROM word provides the next state value. A content of D.C. means that ANY value can be used. A Terminal Count signal is generated when the next state is (0; 0). Exercise 12.17: The ROM implementation of the system is shown in Figure 12.16. The complete contents of the ROM that generates (z 22 ; z 21 ; z 20 ) (using decimal notation) is given in the next table: 264 Solutions Manual - Introduction to Digital Design - August 2, 1999 0 1 2 3 4 5 x x x y y y 20 21 22 20 21 22 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 40 63 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - - - - - - - - - 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 - - - - - - - - - - - - - - - 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 1 2 3 x x y y 10 11 10 11 z z z22 21 20 0 0 0 0 0 0 - - 0 0 0 1 1 0 - - 0 0 1 0 0 1 - - - - - - - - - - z z11 10 0 1 0 1 2 3 0 0 0 1 x y 00 z 00 00 Figure 12.16: ROM implementation of Exercise 12.17 y 2 x 2 z 2 y 2 x 2 z 2 y 2 x 2 z 2 y 2 x 2 z 2 0 0 0 2 0 0 4 0 0 6 0 dc 0 1 0 2 1 2 4 1 4 6 1 dc0 2 0 2 2 4 4 2 3 6 2 dc 0 3 0 2 3 1 4 3 2 6 3 dc 0 4 0 2 4 3 4 4 1 6 4 dc 0 5 dc 2 5 dc 4 5 dc 6 5 dc 0 6 dc 2 6 dc 4 6 dc 6 6 dc 0 7 dc 2 7 dc 4 7 dc 6 7 dc 1 0 0 3 0 0 5 0 dc 7 0 dc 1 1 1 3 1 3 5 1 dc 7 1 dc 1 2 2 3 2 1 5 2 dc 7 2 dc 1 3 3 3 3 4 5 3 dc 7 3 dc 1 4 4 3 4 2 5 4 dc 7 4 dc 1 5 dc 3 5 dc 5 5 dc 7 5 dc 1 6 dc 3 6 dc 5 6 dc 7 6 dc 1 7 dc 3 7 dc 5 7 dc 7 7 dc The PLA implementation of the system needs the representation of the output functions as a sum of product terms. The switching expressions in sum-of-products form for the various outputs are: z 22 (y 22 ; y 21 ; y 20 ; x 22 ; x 21 ; x 20 ) = m 2 (12; 18; 27; 33) z 21 (y 22 ; y 21 ; y 20 ; x 22 ; x 21 ; x 20 ) = m 2 (10; 11; 17; 20; 25; 28; 34; 35) z 20 (y 22 ; y 21 ; y 20 ; x 22 ; x 21 ; x 20 ) = m 2 (9; 11; 19; 20; 25; 26; 34; 36) Solutions Manual - Introduction to Digital Design - August 2, 1999 265 z 11 (y 11 ; y 10 ; x 11 ; x 10 ) = m 1 (6; 9) z 10 (y 11 ; y 10 ; x 11 ; x 10 ) = m 1 (5; 10) z 00 (y 00 ; x 00 ) = x 00 y 00 = m 0 (3) Since the outputs z 2i depend on the same set of inputs, they should be mapped to the same PLA. If more inputs and products are available in the component, functions z 1i and z 00 could also be implemented in the same PLA. A total of 21 products were listed in the expressions above, however, it is possible to reduce this number of products to 20. Using ESPRESSO we were able to reduce the number of products to generate z 2 from 16 to 15 (the others cannot be reduced). One possible solution is to combine m 2 (9) and m 2 (25) on the generation of z 20 and obtain the single product term y 0 22 y 20 x 0 22 x 0 21 x 20 . ESPRESSO also reduces the number of literals in each product term, however, this feature is not important for PLA implementation. Exercise 12.18: Number of Con�gurable Logic Blocks for � an 8-to-1 multiplexer. Since a CLB can implement a 2-input multiplexer, and the 8-to-1 multiplexer can be designed with a tree of 7 2-input multiplexers, the total number of CLBs required for this case is 7. � a 4-bit right/left shift register with parallel load. For this implementation, a 4-input multi- plexer is required for each register bit. A 4-input multiplexer uses 3 CLBs (tree organization), thus a total of 12 CLBs are needed. The ip- ops to store the register state are available in the CLBs used to implement the multiplexers. � a modulo-9 counter with parallel load and TC. A canonical design of an autonomous modulo- 9 counter (no control input, only the sequence of states changing with the clock input) would generate the following expressions for the next state bits: Y 3 = Q 2 Q 1 Q 0 Y 2 = Q 2 Q 0 1 +Q 0 2 Q 1 Q 0 +Q 2 Q 0 0 Y 1 = Q 1 Q 0 0 +Q 0 1 Q 0 Y 0 = Q 0 3 Q 0 0 A pair of these functions can be implemented by a CLB (two 3-input functions). When we add the inputs CNT, LD, and parallel input, to the variable Y i (in order to generate the actual value that is loaded as each state bit), we get a function of 4 inputs, that requires 1 CLB for each state bit. Thus the total number of CLBs is 6. The required ip ops are available on the CLBs used for combinational logic. � an 8-bit two's complement adder. A Carry Ripple adder will require 8 Full Adders. Each CLB can implement 1 FA, thus, the total number of CLBs in this implementation is 8. � a 4 � 2 multiplier (positive integers). To generate the partial products 4 CLBs are used (2 product bits per CLB). These bits are summed in a 5-bit adder, which, based on the result given in the previous item, will require 5 CLBs. Thus, the total number of CLBs required to implement the multiplier is 9. The reader may also try to reduce this number by creating a optmized mapping of the the product generation and addition funtions for the least signi�cant bits.
Compartilhar