Intro. to Digital Systems - TEST #3 - November 15, 2002

PLEDGE: I have not violated the Honor Code in completing this test. ________________________________
READ THESE NOTES:
Sign the pledge above and initial each sheet. Show all of your work.
You may omit any ONE question but you must indicate which one you want omitted by writing OMIT next to it and circling the question number.
Do not spend an excessive amount of time on any one question. All questions count the same.
If you have trouble with a question, skip it and come back to it later.
You may explain your answers if you choose to.
  1. Refer to the logic diagram in the text for a positive logic S-R latch implemented with NOR gates. If the S line is high and the R line is low and both are held in that state then the Q output is high and the Q' output is low. Suppose that the R line is brought high while the S line is high and both are then held high. By tracing signals through the logic diagram, determine and describe what happens to the output (Q and Q').






  2. Give the VHDL code for a positive edge-triggered J-K flip-flop with reset.










  3. Two 4-bit numbers are each stored in 4-bit bidirectional shift registers (A and B) with parallel load. Create a circuit for a device that will implement the assembly language instruction TEST A, B.
    TEST A, B sets a flag to 1 if A is less than B and resets the flag to 0 if A is greater than or equal to B.
    A and B remain unchanged after the TEST instruction is executed.
    Your circuit will set output line X to 1 if A is less than B and reset X to 0 otherwise.
    You may use whatever devices you like to implement the circuit, however, your grade for this problem will depend upon how "inexpensive" your design is (of course it must "work" as well). The "cost" of your circuit will be measured in number of NAND gates.
    Examples For the cost of other devices refer to your text to see how they are implemented with NAND gates. You may not use transmission gates in this problem.











    In the next few problems you will design a circuit using J-K flip flops that displays prime numbers between 0 and 7 inclusive (let's call it a Prime-counter). I.e., on successive clock ticks the circuit will move from state 2 to state 3 to state 5 to state 7 and back to state 2. The positive output from each flip-flop is wired to a light to display the prime numbers.
    The circuit will have one input, X (actually the clock) and one output, Y, which will become 1 when the counter transitions from 7 to 2. Otherwise Y = 0. A zero input will do nothing. I.e., it will not change the output or the state of the machine.

  4. A) Draw the state transition diagram for the circuit. Number the states 010, 011, 101 and 111.









    B)Complete the state table below for the Prime-counter. 
             A    B    C    X    A+   B+   C+   Y   Ja   Ka   Jb   Kb   Jc   Kc
           |    |    |    |    |    |    |    |    |    |    |    |    |
           |    |    |    |    |    |    |    |    |    |    |    |    |
           |    |    |    |    |    |    |    |    |    |    |    |    |
           |    |    |    |    |    |    |    |    |    |    |    |    |
           |    |    |    |    |    |    |    |    |    |    |    |    |
           |    |    |    |    |    |    |    |    |    |    |    |    |
           |    |    |    |    |    |    |    |    |    |    |    |    |
           |    |    |    |    |    |    |    |    |    |    |    |    |
  5. A) Determine the flip-flop input functions and the function defining output Y. Don't forget the "don't cares".







    B) Draw the circuit for the Prime-counter.









    C) Using the flip-flop input equations determine what happens if the circuit erroneously enters the unused state A=0, B=0, C=0. Expand the state transition diagram to include this state and its transitions. (Do not modify the circuit design - simply illustrate what happens after state [0,0,0] is exited).






    A clocked flip-flop (which we shall call the clocked L-M flip-flop) has the following properties. If L = M = 0 then Q+ = 0
    If L = M = 1 then Q+ = Q' (i.e. the state changes).
    If L = M' (i.e. L and M are not equal) then Q+ = Q (i.e. no change).
  6. Give the excitation table for the L-M flip-flop. (The excitation table describes how the flip-flop inputs generate changes in the flip-flop outputs.)
    CAUTION: This one may be unusual in some respect.




  7. Implement the Prime-counter using L-M flip-flops.
    You MUST show
    1. the state transition table,
    2. the Karnaugh maps,
    3. the flip-flop input equations
    4. the final circuit















    Consider the following Moore sequential network. 
    
             A'     A         B'     B
             |      |---Z1    |      |---Z2
             |      |         |      |
          --------------    --------------
          |            |    |            |
          | K       J  |    | K       J  |
          --------------    --------------
	    |   |   |         |   |   |
	    X   C   |         X   C   |
	        L   |             L   |
	        K   |             K   |
                   AND               AND
                  -----             -----
                   |  |              |  |
                   X  B'             X  A
  8. Create a state transition table for the above circuit. From the state table create a state transition graph.








    The LCCS code is a 4-bit code that can be used to encode the digits 0 through 9. LCCS has the property that every valid bit pattern has exactly 1 or 2 ones.
  9. A) Design and draw a state transition diagram for an LCCS code error detector using the minimum possible number of states. The detector should act similarly to the BCD error detector that we designed in class. I.e., your error detector will examine a stream of LCCS 4-bit codes. When an error is detected it should output a one and enter an error state in which it stays. For valid LCCS codes your error detector should output a zero.
    HINT: Use the fact that all valid LCCS codes have exactly 1 or 2 ones.









    B) What is the minimum number of flip-flops requried to implement your design? ____

  10. A 4-bit multiplier can be built primarily from an 8-bit adder, an octal 2-1 mux and three 8-bit bidirectional shift registers (A, B and C) with parallel load similar to the 4-bit shift register on page 260 in the text. Show how this may be done.
    Your multiplier should implement the instruction, A = B * C.
    HINTS: Consider that two numbers (B and C) can be multiplied together by shifting the first number, B, and adding the result into an accumulator (register A) according the bit pattern of the second number, C. I.e., every clock tick shifts the first number. The second number controls whether the shifted B register or all zeros are added to the first number. You may use the octal 2 to 1 mux for this. (See the quad 2 to 1 mux on page 121 of your text. This algoirithm mimics the way we multiply numbers by hand. Another method using identical hardware is based upon a version of Hoerner's polynomial multiplication algorithm.
    If b = b3b2b1b0 and c = c3c2c1c0 are two 4-bit binary numbers then
    b*c = 2*(2*(2*(b*c3)+b*c2)+b*c1)+b*c0
    Each multiply by 2 is simply a shift of the accumulator.
    Note also that a clever implementation using the load line for the A register means that the octal 2-1 mux may be eliminated in either method.













Top of this page   Top of page      Home page   Home page