60.

[Top] [Next] [Prev]

Exercises

1. (PALs and PLAs) Our third word problem case study described a logical "function unit" that computed the eight combinational functions of the inputs A and B: constant 1, A OR B, A NAND B, A XOR B, A XNOR B, A AND B, A NOR B, and constant 0. Show how to implement this using a programmable logic array (with five inputs and one output). Draw the AND array and OR array, and indicate which connections must be made to implement the function. For each output from the AND array, indicate along the wire the product term it is implementing.

2. (PALs and PLAs) Show how to implement the BCD-to-seven--segment LED decoder using a PAL such as that in the P16H8 structure: 10 inputs, 8 OR gate outputs, and 7 product terms per OR gate. Use the shorthand notation developed in Section 4.1.

3. (Transmission Gates) A priority encoder circuit has inputs and outputs that are numbered from 1 to N. The operation of the -circuit is defined as follows. Determine the highest-numbered input that is asserted. Only the output with the same index as the highest-numbered input that is asserted should be asserted. If none of the inputs are asserted, all of the outputs read out a 0. A truth table for a two-input priority encoder circuit is shown in Figure Ex4.3.

Implement a two-input priority encoder circuit using discrete inverters and NAND gates only.
Implement the same function as in (a), except using CMOS transmission gates and inverters. Counting transistors, which implementation is more transistor efficient?
4. (Transmission Gates) Consider the description of the following circuit, often called a function generator. The circuit has two data inputs, A and B, four control inputs, G0, G1, G2, and G3, and one output F. F is defined as Describe how to "program" this function to implement the following 10 functions: A AND B, A OR B, A NAND B, A NOR B, 0, 1, A, B, A XOR B, and A XNOR B by placing the appropriate values on the Gi inputs.
Implement this function using CMOS transmission gates and inverters only. (Hint: Use the inputs A and B to control the transmission gates; consider how to route the appropriate Gi to the output F.)
5. (Switch Logic Implementation) Show how to implement a two-input by two-stack AND-OR-Invert gate with a minimum number of nMOS and pMOS transistors.

6. (Multiplexers vs. Demultiplexers)  Briefly define and differentiate between the following terms: decoder, demultiplexer, multiplexer. Mention the number of inputs, outputs, enable, and select bits, if any.
Using AND and OR gates, design a circuit to gate a single data input to one of four output lines, determined by the binary-encoded index on the two control lines. Which of the above parts did you design?
Repeat step (b) using a transistor "switching network" instead of AND and OR gates. Compare the discrete gate implementation versus the transmission gate implementation. Give one advantage and one disadvantage of each of the approaches.

7. (Multiplexer Implementation) The 2:1 multiplexer function has two data inputs A and B, a select control input S, and a single positive-logic output Z that operates as follows. When S is unasserted, input A is gated to the output. When S is asserted, input B is gated to the output Z. Draw schematics that implement the multiplexer function using only the following components:
Inverting tri-state buffers and conventional inverters.
Open-collector NAND gates, conventional inverters, and pull-up resistors.
Repeat parts (a) and (b) for a four-input multiplexer. S1, S0 = 00 gates A to Z; S1, S0 = 01 gates B to Z; S1, S0 = 10 gates C to Z; S1, S0 = 11 gates D to Z.
8. (Multiplexer Logic) Implement the function (A,B,C,D,E) = using a multiplexer and no other logic. The constants logic 1, logic 0, and the variables, but not their -complements, are available.

9.(Multiplexer Logic) Implement the 2-bit adder function (i.e., 2-bit binary number AB plus 2-bit binary number CD yields 3-bit result XYZ) using three 8:1 multiplexers. Show your truth table and how you derived the inputs to the multiplexers.

10.(Multiplexer Logic) Because 32:1 multiplexers do not exist in standard component catalogs, design a two-stage multiplexer network that realizes the six-variable function
(A,B,C,D,E,F) = S m(3,7,12,14,15,19,23,27,28,29,31,35,39, 44, 45,46,48,49,50,52,53,55,56,57,59) 
How many TTL packages are used?
How many TTL packages are required to implement this function using conventional inverters and NAND gates in a two-level -network?
11. (Multiplexer Logic) You are working for a company that produces clones of famous name computers. Your assignment is to copy the circuit shown in Figure Ex4.11, which is a component of the computer. Because of copyright laws, your boss is very emphatic that the new circuit not resemble the old one. Also, your boss's brother-in-law's electronics wholesale firm has a special deal on multiplexers. So the boss wants you to use only 4:1 multiplexers in your circuit.

12. (Decoder Implementation) Demonstrate how to implement a 6:64 decoder using generic 2:4 and 4:16 decoders.

13. (Decoder Implementation) We have seen how to implement decoders using AND gates and NOR gates. Show how to implement the truth table of the 74138 4:16 decoder, including the three-input enable logic, G1, , , using only NAND gates and inverters.

14.(Decoder Implementation) A decoder together with an OR gate connected to its output terminals can be used in the synthesis of combinational networks.

Implement the function (A,B,C,D) = (not necessarily in minimized form) using one 4:16 decoder and a very large -fan-in OR gate.
Compare the resulting number of ICs with a solution using discrete gates only.
15. (Implementation Methods) Given the following function in sum of products form (not necessarily minimized):
Implement the function F using
An 8:1 multiplexer.
A 4:16 decoder with a 16-input OR gate.
A 16-word ROM.
A PLA-like structure using the notation of Section 4.1.
(Implementation Methods) Given a four-input Boolean function, (A,B,C,D) = S m(0,3,5,7,11,12,13,15) Implement the function using a 16:1 multiplexer.
Implement using an 8:1 multiplexer (use D, as MUX data inputs and A, B, C as MUX control inputs).
Implement the function using a 4:1 multiplexer. (Hint: Place A and B on the select inputs. Assume , are available and use an OR gate to form one of the inputs to the multiplexer.)
Implement the function using a 4:16 decoder and an OR gate.
16.(Implementation Methods) Given the function (A,B,C,D) = ( + B) ( + C + D) (A + + D) in minimized product of sums form and the don't-care set D = {M0,M2,M9,M10}, do the -following: Write in canonical product of sums form.
Write in canonical sum of products form.
Write in minimized sum of products form.
Show how to implement with a single three-stack by three-input AND-OR-Invert gate.
Show how to implement with an 8:1 multiplexer.
(Implementation Methods) Given the three functions X, Y,
and Z, defined by X(A,B,C,D) = S m(1,2,3,5,7,9,11,13,15), Y(A,B,C,D) = P M(2,3,4,5,6,7,8,10,12,14), and Z(A,B,C,D) = S m(0,1,2,3,5,7), Find the minimum sum of products form for each of these functions. How many unique product terms are there in your answer?
Find an alternative sum of products form for X, Y, and Z that minimizes the number of unique product terms to implement all three functions simultaneously. How many unique product terms do you find in this implementation?
Show how to implement your solution to part (b) in a PLA -structure.
17. (Implementation Methods) Consider the implementation of a circuit with four data inputs, A, B, C, D, two outputs, F and G, and two control inputs and . The block diagram and functional truth table are shown in Figure Ex4.19.

Assume that , , , and are available. Implement F and G using AND and OR gates only.
Assume that , , , and are available. Draw the schematic implementing the functions using NAND gates and noninverting tri-state buffers with active low enables. (Your solution should not be a simple restatement of your answer for part (a).)
Assume that , , , and are available. Draw the -schematics that implement F and G using open-collector NAND gates and conventional inverters only.
Implement F and G using transmission gates only.
18. (ROM-based Implementation) Design a schematic for a read-only memory subsystem of size 65536 words by 8 bits wide, using 2764 8K by 8-bit ROMs.
Use a single 3:8 decoder and inverters.
Use a single 2:4 decoder and inverters. Is there a clever way to make use of the output enable inputs to the ROM as well as the chip select lines?

19. (Word Problems) A logic network has four inputs (Input0, Input1, Input2, Input3) and two outputs (Output0, Output1). At least one of the inputs is always asserted high. If a given input line has a logic 1 applied to it, the output signals will encode its index in binary. For example, if Input2 is asserted, the output reads Output1 = 1, Output0 = 0. If two or more inputs are at logic 1, the output will be set according to which input has the highest index (Input3 > Input2 > Input1 > Input0).
Fill in the truth table for this function.
Fill in K-maps for Output1 and Output0, and find the Boolean expression for the minimum sum of products implementation.
20.(Word Problems) You are to implement a combinational multiplier. It has two 2-bit inputs and a 4-bit output. The first 2-bit input is represented by the variables A, B; the second 2-bit input is represented by C, D. The outputs are W, X, Y, Z, from the most significant bit to the least.
Complete a truth table that describes the functional behavior of the multiplier.
Find the minimum sum of products forms for the outputs using the K-map method.
21. (Word Problems) An n-input majority function asserts its output whenever more than half of its inputs are asserted. You are to implement a seven-input majority function, which will assert its output whenever four or more of its inputs are asserted. Don't panic just because this is a seven-variable function. Build it up as a multilevel function whose subfunctions each have less than six variables. As a block diagram, it looks like Figure Ex4.23.

Circuits #1 and #2 tally the number of their inputs that are asserted, providing the count in binary on the outputs (V, Y are the most significant bits; W, Z are the least significant bits). Based on these second-level inputs, Q determines if more than four or more of the original inputs are 1.

Find the minimized sum of products form for circuit #1 (circuit #2 is identical). The functions V and W should look familiar. What do they implement?
Complete a five-variable truth table for circuit #3.
Find the minimum sum of products form for Q using the K-map method.
Find the minimum product of sums form for Q using the K-map method.
22. (Word Problems) You are to design a converter that maps a 4-bit binary code into a 4-bit Gray code. The 4-bit Gray code sequence is defined as follows: 0000, 0001, 0011, 0010, 0110, 0111, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000. Give the truth table, and show how to implement this code converter as a ROM circuit and as a PLA circuit.

23.(Case Studies) How close can the rods be placed on the conveyor belt without invalidating the solution to Case Study 1?

24. (Case Studies) Verify that the misII equations for the BCD-to-seven-segment LED decoder really do map onto the same on-set as the espresso equations. This can be accomplished by expanding the equations into two-level sum of products form and filling in four-variable K-maps from the equations thus derived. How do the K-maps compare with those of Figure 4.70?

25. (Case Studies) We wish to extend the BCD-to-seven-segment LED display decoder to become a hexadecimal LED display decoder. The LED representations of the hex digits 0, 1, 2, 3, 4, 5, 6, 7, 8, and 9 are exactly the same as for the equivalent BCD digits. Figure Ex4.27 shows how the segment displays should be illuminated to denote the hex digits A (1010), B (1011), C (1100), D (1101), E (1110), and F (1111). Obtain the minimized sum of products implementations for the display inputs.


Show how to implement the logic for the extended design as a PLA with four inputs and seven outputs. Draw the AND array and OR array, and indicate which connections must be made to implement the function. For each output from the AND array, indicate along the wire the product term it is implementing.

26. (Case Studies) Design to the gate level an arithmetic and logic function unit based on the circuit of Case Study 3. The modifications to the specification are as follows. We add one additional input Cin and one extra output Cout. When the control inputs C0C1C2 = 000, F generates the function A plus B plus Cin and Cout is the carry-out result from the binary addition. The rest of the control signal settings generate the same functions as before. (Cout is a don't care for these.)
27. (Case Studies) In the function table for the barrel shifter (Figure 4.81), the input data rotates from right to left. How does the implementation change if the data are rotated from left to right instead? Your answer should consider both the logic gate and transmission gate implementation styles.
28. (Tally Circuit) Examine the truth table for the two-input Tally function (Figure 4.23) very carefully. Is there a way to implement the three outputs without using an XOR gate? (Hint: Think of a way to implement the One output in terms of the Zero and Two functions.) How does this revised gate-level implementation compare with the switch implementation?

[Top] [Next] [Prev]


This file last updated on 07/13/96 at 21:42:49.
randy@cs.Berkeley.edu;


What is Sarbanes-Oxley[q]
What is Sarbanes-Oxley[q]
ISBN: 71437967
EAN: N/A
Year: 2006
Pages: 101

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net