87.

[Top] [Next] [Prev]

Exercises

1. (Shift Register Design) Design the basic cell of a universal shift -register to the following specifications. The internal storage elements will be positive edge-triggered D flip-flops. Besides the clock, the shifter stage has two external control inputs, S0 and S1, and three external data inputs, SR, SL, and DI. SR is input data being shifted into the cell from the right, SL is data being shifted from the left, and DI is parallel load data. The current value of the flip-flop will be replaced according to the following settings of the control signals: S0 = S1 = 0: replace D with DI; S0 = 0, S1 = 1: replace D with SL; S0 = 1, S1 = 0: replace D with SR; S0 = S1 = 1: hold the current state. Draw a schematic for this basic shifter cell.

2. (Shift Register Design) Shifters are normally used to shift data in a circular pattern (the data that shifts out at one end of the shifter is shifted back into the other end), or as a logic shift (fill the shifted positions with 0's) or an arithmetic shift (propagate the high-order sign bit to the right or shift in 0's to the left). For example, if a 4-bit register contains the data 1110, the effects of the six kinds of shifts are the following:
Circular shift right: 1110 becomes 0111.
Circular shift left: 1110 becomes 1101.
Logical shift right: 1110 becomes 0111.
Logical shift left: 1110 becomes 1100.
Arithmetic shift right: 1110 becomes 1111.
Arithmetic shift left: 1110 becomes 1100.
Show how to wire up a 4-bit universal shift register (TTL component 74194) to perform the following kinds of shifts:

Circular shift right
Circular shift left
Logic shift right
Logic shift left
Arithmetic shift right
Arithmetic shift left
3. (Shift Register Design) Your task is to design a shift register -subsystem based on the TTL 74194 component that can implement the six kinds of shifts described in Exercise 7.2. The -subsystem has three control inputs, S2, S1, S0 that are interpreted as follows: S2, S1, S0 = 000 is hold; 001 is circular shift right; 010 is circular shift left; 011 is logic shift right; 100 is logic shift left; 101 is arithmetic shift right; 110 is arithmetic shift left; 111 is parallel load. Show the data path for the shifter subsystem. You may use multiplexers at the shift inputs to the 74194.
Show the combinational logic (equations or schematics) to decode the global S2, S1, S0 control inputs into the appropriate detailed control signals for the 74194 shifter and the external data path logic for handling the serial shift inputs.
4. (Register Design) A FIFO (first in, first out) queue is a special-purpose register file n words deep and m bits wide that operates as follows (see the block diagram in Figure Ex7.4(a)). When a PUSH_DATA control input is asserted, new data at the inputs at the right is read into the end of the queue. When a POP_DATA control input is asserted, existing data at the head of the queue becomes available at the outputs at the left. Since the FIFO has finite capacity, two status outputs indicate whether the FIFO is empty or full. PUSH_DATA is inhibited in a full FIFO, while POP_DATA is inhibited in an empty FIFO. On reset, the FIFO should be set to empty. A "flow-through" FIFO is the simplest form of this kind of device. The FIFO must fill up with data before any data can be removed. Furthermore, the FIFO must be completely -emptied before new data can be placed in it. Using only shift register components and combinational logic, design a flow-through 4 word by 4 bit FIFO. Consider carefully how to -represent the empty/full status of the FIFO. (Hint: Consider adding an (m + 1)st bit to the FIFO to indicate whether the FIFO word is valid.)


A more flexible version of the FIFO can be implemented with counter and register components. Two counters represent the Q_HEAD and Q_TAIL respectively. These can be used as an index to a register file or an array of registers for reading from the head of the FIFO or writing to its tail. (b) shows one way to implement the PUSH_DATA and -POP_DATA operations. POP_DATA delivers word2 to the -outputs and advances the Q_HEAD pointer. PUSH_DATA advances the tail pointer and writes the input to word0. Notice how the queue wraps around on itself. Your task is to implement a 4 word by 4 bit FIFO using two 2-bit counters for the Q_HEAD and Q_TAIL. Think carefully about how you determine whether the FIFO is empty or full. Don't forget to consider the starting configuration of the head and tail pointers on FIFO reset.

5. (Register Design) A LIFO (last in, first out) stack is similar in concept to the FIFO queue, except that the most recently pushed data is the first to be popped. The block diagram is identical to the FIFO, except that the data inputs and outputs are the same lines. Design a 4 word by 4 bit LIFO stack using shift registers and combinational logic only. Draw your schematic, indicating the components used. How do you distinguish between a full stack and an empty stack in this implementation?

6. (Register Design) Repeat Exercise 7.5, this time using registers and counters. Draw the schematic. How do you distinguish between a full stack and an empty stack? What is the initial condition of the pointers at reset? (Register Design) One way to compute the twos complement of a number is examine the number bit by bit from the lowest-order bit to the highest-order bit. In scanning from right to left, find the first bit that is one. All bits to the left of this should now be complemented to form the twos complement number. For example, the twos complement of 0010 is formed as follows:


Your task is to draw a schematic for a 4-bit register with parallel inputs and outputs and the synchronous control signals HOLD, CLEAR, LOAD, and COMPLEMENT. When the complement signal is asserted, the register's contents will be replaced by its twos complement.

7. (Shifter Application) Figure 7.9 shows the partial imple-mentation of a bit-serial transmission subsystem. This -subsystem is unidirectional: it can transmit only from the left shift registers to the right. Extend this data path implementation to make it bidirectional. Under external control, include logic (such as multiplexers) thatComposition 2 allows the subsystem to transmit from right to left as well as left to right.

The subsystem also needs a counter that can raise a signal after 8 bits have been transmitted. Show how a counter such as the TTL 74163 synchronous up-counter can be used to perform this function.


8. (Shifter Application) In this exercise, you will generate control logic for use with the data path you developed in Exercise 7.6. You are given the control signals DIRECTION (0 = left to right, 1 = right to left), LOAD (load parallel data), XMIT (transmit bits in the indicated direction). External logic first sets the DIRECTION, then asserts LOAD to load parallel data, and finally asserts XMIT to begin the data transfer. Your logic will use these inputs to (a) parallel load the appropriate shifter registers, (b) shift 8 bits in the correct direction, and (c) place the receiving registers in the hold state when the transfer is complete. State all assumptions, and show your equations or logic schematics.

9. (Counter Design) Design a 2-bit counter that behaves according to the two control inputs I0 and I1 as follows: I0, I1 = 0, 0: stop counting; I0, I1 = 0, 1: count up by one; I0, I1 = 1, 0: count down by one; I0, I1 = 1, 1: count by two. Draw the state diagram and state transition table.

Implement the counter using T flip-flops, D flip-flops, and J-K flip-flops.
Which choice of flip-flops leads to the minimum gate count? Assume that only two-input NAND, NOR, XOR, and XNOR gates are available. Draw the schematic for your minimum gate count implementation.
Which choice of flip-flops leads to the minimum wire count?
The same kinds of gates are available as in part (c). Draw the schematic for your minimum wire count implementation. Indicate how you have counted the interconnections.

10. (Counter Design) Design a three flip-flop counter that counts in the following sequence: 000, 010, 111, 100, 110, 011, 001, and repeat. Design the counter using toggle flip-flops. Verify that your implementation is self-starting.

11. (Counter Design) Consider the design of a 4-bit BCD counter that counts in the following sequence: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, and then back to 0000,
0001, etc.
Draw the state diagram and next-state table.
Implement the counter using D flip-flops, toggle flip-flops, S-R flip-flops, and J-K flip-flops.
Implement the counter making it self-starting just for the D flip-flop case.

12. (Counter Design) Consider the design of a 4-bit Gray code counter (that is, only one of the state bits changes for each -transition) that counts in the following sequence: 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000, and then back to 0000, 0001, 0011, etc.
Draw a state diagram and next-state table.
Implement the counter using D flip-flops, toggle flip-flops, R-S flip-flops, and J-K flip-flops.
Do you have to worry about self-starting? Why or why not?

13. (Counter Design) The 4-bit Johnson counter advances through the sequence 0000, 1000, 1100, 1110, 1111, 0111, 0011, 0001, and repeat. Using the standard counter design process, show how to implement this count sequence using (a) D flip-flops and (b) T flip-flops. How does your solution compare with the J-K implementation of Figure 7.10, in terms of gates and wiring -complexity?

14. (Self-Starting Counters) Analyze your solutions to Exercise 7.12(a) and (b) to check whether or not they are self-starting. Draw complete state diagrams and show all states and transitions implied by your implementation.

15. (Reverse Engineering) What is the counter state diagram implied by the flip-flop implementation of Figure Ex7.14?

16. (Reverse Engineering) Consider a counter implemented with three toggle flip-flops, labeled C, B, A from highest-order bit to lowest. The next-state function is implemented by the logic in Figure Ex7.15. Assuming the counter can be reset to state 000, what is the state diagram for this counter?

17. (Ripple Counters) Figure 7.37 shows a 3-bit ripple up-counter. What simple change can you make to this circuit to convert it to a down-counter? Show your logic circuit and associated timing diagram. Explain why your circuit operates correctly.

18. (Asynchronous Inputs) Can you think of any cases in which an asynchronous load or reset signal is acceptable in a digital design?

19. (Offset Counters) Figure 7.41 shows a possible implementation for a counter with a beginning offset. The counter will eventually enter the correct sequence, but in some applications this may not be acceptable. How might you add a reset signal that will force the counter into a valid state when it is asserted? What assumptions must be made about the duration of the reset signal?

20. (Offset Counters) Use two cascaded synchronous up-counters (for example, a TTL 74163 component) to implement a 6-bit -offset counter that counts from 000010 to 110011 and repeats. Make sure the counter begins in state 000010 when the external reset signal is asserted.

21. (Self-Starting Counters) Determine whether the counter implementation shown in the K-maps of Figure 7.34 is self-starting. Show the complete state diagram including the illegal states.

22. (Self-Starting Counters) Determine whether the counter implementation indicated by the logic schematic of Figure 7.36 is self-starting. Show the complete state diagram including the invalid states. How does it compare with the complete state diagram of Exercise 7.20?

23. (Counter/Register Applications) Consider the design of a bit-serial adder. This circuit uses a single full adder to add two binary numbers presented in serial fashion, 1 bit at a time. Draw the schematic for a 4-bit version of this circuit. Two
4-bit shift registers are loaded with the data to be added in parallel. These are shifted out a bit at a time, starting with
the lowest-order bit, into the A and B inputs of the full adder. The partial sum is shifted into a third register.

How should the carry out be handled between subsequent bits?
Define your control signals for the bit-serial adder subsystem. Draw a timing diagram that illustrates the sequencing of these signals to implement the 4-bit addition. What happens on reset?
24. (Counter/Register Applications) Flip-flops, registers, and counters can be used to implement a variety of useful clocking functions. Design a system that will generate a single clock pulse one period long each time a push-button is pressed (you may assume that an external reference clock is available).

Design a system using an MSI counter that will assert a signal for exactly 13 clock pulses each time a push-button is pressed (once again, an external reference clock is available).
In many applications, it is desirable to single step the clock as well as to halt a free-running clock signal and later restart it. Design a circuit that will generate a single clock pulse each time a STEP push-button is pressed. Provide a separate -circuit, independent of STEP, that will cleanly turn the clock on when a RUN switch is in the ON position and off when RUN is in its off position. No marginal/partial clock outputs are allowed.
25. (Counter/Register Applications) Design a 2-bit binary up-counter to the following specification. The counter has five inputs (not including the clock) and three outputs. The inputs are CLR, LOAD, COUNT, LB, and LA. CLR takes precedence over LOAD, which in turn takes precedence over COUNT. The outputs are B, A, and RCO. When CLR is asserted, the flip-flops of the counter in Exercise 7.24 are reset to 0. If LOAD is asserted (when CLR is not asserted), the flip-flops' contents are replaced by the LB and LA inputs. If COUNT is asserted (when CLR and LOAD are not asserted), the flip-flops' contents are incremented: 00 becomes 01, 01 becomes 10, 10 becomes 11, and 11 becomes 00. When the counter is in state 11, RCO is asserted.
Implement the counter in Exercise 7.24 using D flip-flops and as few logic components as possible. Hint: Use 4-to-1 multiplexers to implement your next-state function. You may also use XOR gates, as well as standard AND, OR, and NOT gates.
26. (Random-Access Memories) A microprocessor with an 8-bit-wide data bus uses RAM chips of 4096 by 1-bit capacity. How many chips are needed and how should their address lines be connected to provide a memory capacity of 16 Kbytes (1 byte = 8 bits).

27. (Random-Access Memories) Consider a 1-megabit dynamic memory component. The memory is organized into 512 rows of 2048 bits each. Assume that every bit must be refreshed within 4 ms. How frequently should a row refresh operation be scheduled? If the memory has an 80 ns access time, approximately what fraction of memory accesses must be dedicated for refresh?

28. (Random-Access Memories) Consider the memory controller design described in Section 7.6.5. Show an alternative implementation of the control signals INC_ADR, , and that leads to a different detailed sequencing of the signals that is still logically correct.

29. (Random-Access Memories) Consider the read and write timing of the 2114 memory component in Figures 7.55 and 7.56. What is the minimum clock width for the overlapping clocks generated by the memory controller that will still meet the memory's timing specification? Justify your answer.

[Top] [Next] [Prev]

This file last updated on 07/14/96 at 16:36:05.
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