Last (family) name:



Last (family) name: ____SOLUTION__________

First (given) name: _________________________

Student I.D. #: _____________________________

Circle section: Saluja Ramanathan

Department of Electrical and Computer Engineering

University of Wisconsin - Madison

ECE/CS 352 Digital System Fundamentals

Final Examination

Tuesday, December 16, 2003, 12:25 – 2:25 PM

Instructions:

1. Closed book examination.

2. No calculator, hand-held computer or portable computer allowed.

3. You must show your complete work. Points will be awarded only based on what appears in your answer book.

4. Five points penalty if you fail to enter name, ID#, or instructor selection.

5. No one shall leave the room during the last 5 minutes of the examination.

6. Upon announcement of the end of the exam, stop writing on the exam paper immediately. Pass the exam to aisles to be picked up by a TA. The instructor will announce when to leave the room.

7. Failure to follow instructions may result in forfeiture of your exam and will be handled according to UWS 14 Academic misconduct procedures.

|Problem |Points |Score |

|1 |18 | |

|2 |15 | |

|3 |13 | |

|4 |15 | |

|5 |15 | |

|6 |8 | |

|7 |8 | |

|8 |8 | |

|Total |100 | |

1. (18 points) Truth table, canonical forms, minimization

a) (5 points) Represent function realized by the logic circuit given below in Sum of Minterms canonical form.

[pic]

[pic]

b) (4 points) Draw a realization of the function below in two level NAND/NAND form. Assume that inputs are available only in uncomplimented forms.

[pic]

[pic]

c) (4 points) Represent F(A,B,C,D) in the equation above (Problem 1b) in Product of Maxterm canonical form.

[pic]

d) (5 points) A combinational circuit F depends on three inputs A, B, and C. The input-output behavior of the circuit is shown in the following waveforms. Write the function F in minimum two level SOP form. You must show all your work. No points will be awarded for just writing the final answer.

[pic]

Answer: [pic]

2. (15 points) Minimization – Quine-McClusky method (Tabular method) Prime implicant generation

Let: G(w,x,y,z) = m(0, 4, 5, 6, 7, 9, 10, 12, 13, 15)

Execute the Quine-McCloskey algorithm to find all the Prime Implicants of the function The algorithm has been started for you below (minterms are listed in increasing 1's count order). Complete the algorithm and CIRCLE the PRIME IMPLICANTS. You will be penalized severely if any of the implicant or prime implicant generated by is not an implicant or prime implicant.

|mi |Index Order |( |1-Cubes |( |2-Cubes |

|0 |0000 |( |0 0 - 0 | |0 1 - - |

|4 |0100 |( |0 1 0 - |( |- 1 0 - |

|5 |0101 |( |0 1 - 0 |( |-1 - 1 |

|6 |0110 |( |- 1 0 0 |( | |

|9 |1001 |( |0 1 – 1 |( | |

|10 |1010 | |- 1 0 1 |( | |

|12 |1100 |( |0 1 - 1 |( | |

|7 |0111 |( |1 – 0 1 | | |

|13 |1101 |( |1 1 0 - |( | |

|15 |1111 |( |- 1 1 1 |( | |

| | | |1 1 - 1 |( | |

| | | | | | |

| | | | | | |

| | | | | | |

Answer: The prime implicants are:

3. (13 points) Finite state machine – Excitation map

a) (12 points) A single input six state (Sa, Sb, Sc, Sd, Se, Sf) finite state machine is realized using 3 flip-flops. A D type FF is used to realize the variable Q1, a T FF is used to realize the variable Q2, and a JK type FF is used to realize the variable Q3. Partially completed exitation map and the next states are listed in the table below. Complete all entries in the table. Note that two combinations of state encodings are not used and these are Q1 Q2 Q3 = 010 and 111.

| |State Code | | | | |

|State | | | | | |

| |Present State |Input |Next State |Output |Flip-Flop inputs |

| |Q1 |Q2 |Q3 |I |Q1(t+1) |Q2(t+1) |Q3(t+1) |Y |D1 |

|R0 ( R1 + R2 |

a) (4 points) Registers R1 and R2 have the values shown in the table below. Fill in the VALUE of Register R0 AFTER the instruction executes. Also fill in the C, Z, N, and V bits that change based on the operations. NOTE: all representations are in 2’s complement format and arithmetic operations take place using 2’s complement arithmetic.

|Operation |R0(t+1) |R1(t) |R2(t) |C |V |Z |N |

|R0 ( R1 + R2 |0 0 0 0 0 0 0 0 |11111111 |00000001 |1 |0 |1 |0 |

11111111

+ 00000000

1 00000000

11111111

+ 11111111

1 11111110

6. (8 points) ASM realization

Consider the ASM given below. Implement this using one flip-flop per state approach. Some of the components needed for the implementation are drawn below. You may require additional gates to implement the logic. Use as few gates as possible. Excessive use of additional gates will be penalized.

[pic]

7. (8 points) RAM

Design and all the relevant information for a memory module is given in the figure below.

[pic]

Answer the following:

(a) (1 points) What is the size of module M1: Where K = 210

(b)(1 points) What is the size of this memory: Where K = 210

(c) (2 points) If an address (54A3)16 and a read command is issued which memory module will place date on the data bus.

Module M2

(d) (2 points) What is the maximum address of any bit in M2. Write your answer in Hex.

(e) (2 points) What is the minimum address of any bit in M3. Write your answer in Hex.

8. (8 points) ROM and PLDs

(a) (4 points) An 8X2 bit ROM given below is to be used to realize a full adder. Program this ROM.

|A |B |C |S |C |

|0 |0 |0 |0 |0 |

|0 |0 |1 |1 |0 |

|0 |1 |0 |1 |0 |

|0 |1 |1 |0 |1 |

|1 |0 |0 |1 |0 |

|1 |0 |1 |0 |1 |

|1 |1 |0 |0 |1 |

|1 |1 |1 |1 |1 |

(b) (4 points) Realize the three variable function [pic] using the PLD (attahced figure if a PAL) provided. Note that I have already marked the inputs to the PAL as well as the pin at which the function F should be produced.

[pic]

[pic]

Basic Identities of Boolean Algebra

|1. X + 0 = X |2. X( 1 = X |Existence of 0 and 1 |

|3. X + 1 = 1 |4. X( 0 = 0 |Existence of 0 and 1 |

|5. X + X = X |6. X ( X = X |Idempotence |

|7. X + [pic]=1 |8. X([pic]= 0 |Complement |

|9. [pic]=X | |Involution |

|10. X + Y = Y + X |11. X ( Y = Y ( X |Commutative Law |

|12. X + (Y + Z) = (X + Y) + Z |13. X (YZ) = (XY) Z |Associative Law |

|14. X(Y + Z) = XY + XZ |15. X + YZ = (X + Y)(X + Z) |Distributive Law |

|16. [pic] |17. [pic] |DeMorgan’s Law |

Useful Boolean Identities

|X + XY = X | |[pic] |

|[pic] | |[pic] |

|[pic] | |[pic] |

Flip-Flop Characteristics Tables

|JK Flip Flop | |SR Flip-Flop |

|J |K |Q(t+1) | |S |R |Q(t+1) |

|0 |0 |Q(t) | |0 |0 |Q(t) |

|0 |1 |0 | |0 |1 |0 |

|1 |0 |1 | |1 |0 |1 |

|1 |1 |[pic] | |1 |1 |Indetminate |

|D Flip-Flop | |T Flip-Flop |

|D |Q(t+1) | |T |Q(t+1) |

|0 |0 | |0 |Q(t) |

|1 |1 | |1 |[pic] |

-----------------------

[pic]

[pic]

[pic]

[pic]

1 0 1 0 0 – 0 0 1 – 0 1

0 1 - - - 1 0 - - 1 - 1

F(A,B,C,.D) = " ( 3, 5 )

g(A,B,C,.D) = " ( 8, 10, 11 )

8000

7FFF

64 ∏ ( 3, 5 )

g(A,B,C,.D) = ∑ ( 8, 10, 11 )

8000

7FFF

64 Kb Kb

16 Kb

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download