Name (Please Print)______________________________________________

Please write your Student ID#:____________________________

Instructions/Please Read Carefully!

In taking this examination, you agree that all work recorded herein is your own. A student caught in the act of cheating will be given a grade of F on this examination and a letter will be written to his or her file.

Read the questions carefully. If something appears ambiguous, raise your hand and ask, the exam may have bugs. Points have been assigned according to the formula such that 1 point = 1 exam minute, so pace yourself accordingly. There are 120 points on this test and you have 120 minutes to complete the exam.

Be sure to answer all questions.

All work is to be done on the attached sheets and under no circumstances are blue books or loose sheets to be used. Write your name at the top and do not proceed until you are told to do so.

Short Answer (10 points) Circle T if the statement is true, otherwise circle F for false.

1. Any Sequential Boolean function can
be generated using demultiplexors. T F final1a.html

2. A master/slave flipflop samples its inputs on one edge of the clock while it changes its output on the other edge. T F (ans: T, the clock goes through an invertor).

3. Synchronous control inputs are sampled only on a clock edge. T F (ans:false, you may have a level edge sample as well as a rising or falling edge sample).

4. The difference between a programmable logic array (PLA) and a programmed array logic (PAL) is that the former has an OR array that cannot be personalized while the latter does. T F (ans: false, check page 165 of Katz, Devices with this generality are called programmable logic arrays).

5. A read-only memory (ROM) can be viewed as a programmable AND/OR array in which the AND plane is programmed as a full decoder. T F (ans: this is true)

6. A Moore Machine usually has less states that an equivalent Mealy Machine.
T F

7. The problem with a standard Mealy Machine is that its output changes are not synchronized to the changes in the clock. T F

8. A synchronous digital systems contains a single reference signal, the clock, such that all state memory changes are made with respect to the clock signal. T F (ans: true)

Fill in the blank with the correct answer:

9. The canonical POS form of an expression results in a ____3______level circuit. Assume that inverters do count.

10. If you built a 128:1 multiplexer from 4:1 muxes, how many 4:1 muxes would you need?____128/4 = 32 + 32/4 = 8 + 8/4 = 2 + 1, i.e., 32 + 8 + 2 + 1 = 43______

11. Reverse Engineering (20 points)

Given the following implementation of a three-bit counter implemented with toggle flip-flops, derive the state transition diagram through the process of reverse engineering. Show all calculations to receive full credit!

Reverse Engineering Calculations:
TA= TB= TC=

Ta=A+BxorC

Tb=A+B

Tc=A+(BxorC)'

The answer is below:

ABC	TATBTC	A+B+C+
000	001	001
001	100	101
010	110	100
011	011	000
100	111	011
101	111	010
110	111	001
111	111	000

The sequence is 0,1,5,2,4,3,0 also, 7,0 and 6,1,5,2 this is a self-starting counter.

Fill-in the State Transition Table:

Add the transitions to complete the State Diagram:

12. (10 points)

A. For the following pairs of numbers, if the sum of the numbers results in a valid result in the given number system, write the equivalent base 10 result in the space provided. Otherwise, write "overflow" .Twos Complements:

Ones Complements:

B. For fill out the following truth table:

 X   Y   Z   F   
 0   0   0       
 0   0   1       
 0   1   0       
 0   1   1       
 1   0   0       
 1   0   1       
 1   1   0       
 1   1   1       
 
 

Convert f to canonical SOP form:

13. (20 points) A MOORE sequential network has one input and one output. The output should be 1 if the total number of 0's received at the input is ODD and the total number of 1's received is an EVEN number greater than 0. This machine can be implemented in exactly six states. Complete the state diagram below :

Give a brief description of the partial strings recognized in each state

S0:

S1:

S2:

S3:

S4:

S5: Odd # of Zeros, Even # (>0) of Ones

14. (5 points) In a carry lookahead adder, the correct equation for the carry input to the second stage (C2) is:

(a) C2=G1+P1C0
(b) C2=G0+P1C1
(c) C2=G1+P1G0+P1P0C1
(d) C2=G1+P1G0+P1P0C0

15. (5 points) Match the circuit below with the phrase that best describes it from the list

(a) clocked R-S latch
(b) clocked D latch
(c) master/slave R-S flip-flop
(d) master/slave T flip-flop

16. (5 Points) Find the dual and complement of the following expression. (Do not simplify.)

F = ((([1 + (a + b')c + d'e'])))[f' + (gh')(i + j)] + k*0

17 (5 points) Given that ,
Find the minterm expansion for F. 18. (10 Points) Your task is to implement a finite state machine with TOGGLE flipflops given the following state diagram. The FSM is a complex GRAY code counter with two control inputs, I1 and I0, which determine the next state. Complete the state transition table (on the left), including the necessary inputs to the toggle flipflops, T1 and T0, which will hole the state of the counter. Q1 and Q0 are the output of these two flipflops. Then fill in the next state k-maps. Finally draw the implementation schemeatic making use of a minumum number of AND OR and Inverter gates.

19. (10 points) Implement the following truth table, with inputs ABCD and with output X, using an 8:1 multiplexer. Assume that inputs ABC are to be used for selection. Please show work.

20. (10 points) The following transistion table represents a sequential machine. It is to be realized with combinational logic and two J/K flip-flops. There is a single input, x, and a single output, Z. Determine the minimal boolean expressions for the inputs of the flip-flops and for the output.

J1=

K1=

J2=

K2=

Z=

21. (10 points) Implement a Combinational Logic Design

Implement a combinational logic circuit that converts a 4 bit sign plus magnitude number to the corresponding 4 bit 2's complement number.

First, complete the following truth table, Then fill in the following k-maps and write down the output functions in minimized sum of products form:

Please check over your work, if you have extra time. Points are not awarded for tests handed in early. Good luck with your finals and have a nice break!