COCO Review Problems for Test 2 Fall 2000
Review Problems for Test 2
1. Tri-state gates: Fill up the truth table for the tri-state gate shown below.
A / B / C / Y0 / 0 / 0
0 / 0 / 1
0 / 1 / 0
0 / 1 / 1
1 / 0 / 0
1 / 0 / 1
1 / 1 / 0
1 / 1 / 1
2. OC-gates: Write out the logic function for the following circuit with open-collector gates. Also fill up the truth table given
/ A / B / C / D / Y0 / 0 / 0 / 0
0 / 0 / 0 / 1
0 / 0 / 1 / 0
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
1 / 1 / 0 / 1
1 / 1 / 1 / 0
1 / 1 / 1 / 1
Logic Function: Y =
3. ROMs
We wish to extend the BCD-to-seven-segment display converter to handle hexadecimal digits (see Figure Ex4.27 in your Textbook). The input bits are denoted . We wish to build this circuit using the ROM discussed in class. /Write down the ROM address, and the stored content for the following display characters:
Display Character / ROM Address / ROM Contents
“1”
“7”
“3”
“5”
“2”
4. Adders
a) Given the truth table for the half-adder, show that the composition of two half-adders and an OR gate as in section 1.3.6 yields the same truth table as the full adder.
Table P1.25. Half-Adder and Full -Adder truth tables.
Half-Adder / Full-AdderA / B / C’ / S / A / B / C / C’ / S
0 / 0 / 0 / 0 / 0 / 0 / 0 / 0 / 0
0 / 1 / 0 / 1 / 0 / 0 / 1 / 0 / 1
1 / 0 / 0 / 1 / 0 / 1 / 0 / 0 / 1
1 / 1 / 1 / 0 / 0 / 1 / 1 / 1 / 0
1 / 0 / 0 / 0 / 1
1 / 0 / 1 / 1 / 0
1 / 1 / 0 / 1 / 0
1 / 1 / 1 / 1 / 1
Figure 1.25. Block diagram of the composition of the two half-adders and an OR gate to yield the behavior of a full-adder
b) Assuming the internal diagram for the carry out and sum (half adder) are the following, compute the gate delays when the full-adder sum and carry out will be available.
c) Given Gi = AiBi and Pi = Ai Å Bi using Boolean algebra show how Si+1 = Pi Å Ci and Ci+1 = Gi + Ci Pi
d) Explain how this carry lookahead procedure leads to a faster implementation of the 4-bit adder.
5. Twos Complement Arithmetic:
a) Negate the signed 8-bit number represented by $9C.
b) Add the following twos complement numbers. Put an X next to the answer if the result is wrong (i.e. there has been an overflow).
carry0 / 0 / 1 / 1 / 0 / 1
+ / 1 / 1 / 0 / 1 / 0 / 1
sum
c) Subtract the following twos complement numbers. Put an X next to the answer if the result is wrong (i.e. there has been an overflow).
carry1 / 0 / 1 / 1 / 0 / 1
– / 0 / 1 / 0 / 1 / 0 / 1
difference
6. Multiplexors/Demultiplexors:
a) You are working for a company that produces clones of famous name computers. Your assignment is to copy the circuit shown in the figure, which is a component of the computer. Because of copyright laws, your boss is very emphatic that the new circuit does 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 1:4 multiplexers in your circuit.
b) Implement the function: with an 1-to-8 demux/decoder.
7. Hazards/Glitches:
Consider the minimized function
Map this function on the K-map and indicate the groupings corresponding to the function terms. Does this function have a static 1-hazard ? If so, use the K-map to identify terms you need to add to the function to remove the hazard. Write the SOP form of the revised function below.
8. Flip-flops/Simple State Diagrams:
a) Consider a J-K flip flop. Given the following state diagram template, draw the transitions corresponding to a sequence of inputs (J,K) = (0,1), (1,0), (1,1), (1,1), (0,0). Assume that the flip flop is initially reset (i.e. Q=0).
b) Consider a negative edge-triggered D-flip-flop. Assume D was initially 0. The clock is initially 0; it transitions to 1 at time 1; and transitions back to 0 at time 2, and to 1 at time 3. D changes to 1 at time 1. Plot a timing diagram to capture the output from time 0 to 4. Assume that gate delays are negligible.
c) A NAND latch is constructed as shown. Each gate has a unit delay.
Suppose m = n = y = 1 for a long time. Determine the steady-state value of z.
d) Given input waveforms m and n, determine the waveforms for y and z.
Computer Components and Operations Page 10 of 14
e) Realize the functionality of a Toggle flip flop by designing an appropriate excitation network for a D flip flop. Fill in the next state and excitation table entries.
T / Q / Q+ / D0 / 0
0 / 1
1 / 0
1 / 1
f) Obtain a minimum expression for the input D.
g) Draw the schematic for the network inside the dotted outer box below.
Computer Components and Operations Page 10 of 14
h) A negative-edge triggered JK Flip Flop with Set and Clear has a minimum Setup Time of 20 ns and a minimum Hold Time of 10 ns. Mark the minimum Setup-Hold Window about the appropriate Clocking Event.
9. Registers:
Study the 74194 bi-directional universal shift register. Assume this chip is initially cleared, and S1=1, S0=1, with inputs DCBA = 0101 and positive edge trigger applied. What are the expected outputs?
Now, if S1, S0 = 01, SL = 0, SR = 1; what are the outputs ?
10. Counters:
Consider the 2-bit zig-zag counter, (00 ® 10 ® 01 ® 11 ® 00 ® ...).
a) Sketch the state diagram for this counter.
b) Denote the bit on the left as B, and the bit on the right as A. Using this notation, construct the next-state and excitation tables for this counter using the template below. We have to implement this using T-flip flops
Current State / Next State / Flip-Flop Inputs0 / 0
0 / 1
1 / 0
1 / 1
c) Sketch the circuit diagram for the 2-bit zig-zag code counter using the template below. Is the counter self-starting ?
Computer Components and Operations Page 10 of 14
Computer Components and Operations Page 10 of 14
11. Complex counters
Synthesize a 3-bit binary counter that skips all the even numbers, i.e. follows the sequence:
1 ® 3 ® 5 ® 7 ® 1 ® ...
a. Sketch the state diagram below. Comment on any notable patterns among the states. Try to take advantage of it in part (b) if you can.
b. Fill in the state transition table as well as the remapped next state functions for a J-K flip-flop implementation. (Note: there may be extra rows/columns in the table. Leave them blank)
A / B / C / A+ / B+ / C+ / JA / KA / JB / KB / JC / KC12. UP/DOWN counters (similar to latest studio)
c. Given below is an incomplete state transition table for a 2-bit up/down counter using D flip-flops. Fill in the missing next states, the DA & DB columns, and find the minimal logic equations for the DA and DB inputs.
M (down/up) / A / B / A+ / B+ / DA / DB0 / 0 / 0 / 0 / 1
0 / 0 / 1 / 1 / 0
0 / 1 / 0
0 / 1 / 1
1 / 0 / 0 / 1 / 1
1 / 0 / 1 / 0 / 0
1 / 1 / 0
1 / 1 / 1
Answer: DA = DB =
13. Moore vs Mealy machines
This part is about a sequential machine designed to be a serial adder. There are two inputs x1 and x0 and one output z. The inputs represent two binary numbers, inputted bit-by-bit, with the least significant bits presented first. The output is their sum, calculated bit-by-bit, including carry, as each pair of input bits is seen. For example,
ECSE-2610 Computer Components & Operations, Fall 2000 Page 14 of 14
x1 / 011010x0 / 110110
z / 100011
Here is the state diagram, with ½ of the arrows filled in.
a. Is this a Moore machine or a Mealy machine? Circle one.
b. Fill in the rest of the arrows, with their labels.
ECSE-2610 Computer Components & Operations, Fall 2000 Page 14 of 14
c. Here are 4 rows of the truth table. Please fill them in.
y1 / y0 / x1 / x0 / y1+ / y0+ / z0 / 0 / 0 / 0
0 / 0 / 1 / 0
0 / 1 / 1 / 1
1 / 1 / 1 / 1
d. Study the machine, figure out what the two state bits must mean, and describe each in 5 words or less.
y1:
y0:
e. Now, we will implement the sequential adder with the other type of machine. Here is the state diagram, but with only half of the arrows. Please add the rest (with their complete labels).
f. What does the state mean (in 5 words or less)?
14. More FSMs:
a) Consider the communicating state machines with initial inputs: X=0, Y=0, Z = 0 entering into states A and C respectively. Sketch the timing diagram for outputs X ,Y and Z in the template given
b) Consider the vending machine similar to the one discussed in class in which the user has only one type of coin Nickels or Dimes, but not both. It opens when 10c or more is deposited. Draw the minimized state diagram, fill up the symbolic and encoded state tables. Assuming a D-flip flop implementation, minimize the K-maps and write the functions for D0, D1 and Open.
ECSE-2610 Computer Components & Operations, Fall 2000 Page 14 of 14