Midterm Exam — Spring 2024

CS-173 Fundamentals of Digital Systems

22nd April 2024

Mirjana Stojilović
Parallel Systems Architecture Lab (PARSA)
Midterm Exam — Spring 2024 Exercise 1
CS-173 Fundamentals of Digital Systems Multiple Choice Questions

Part I: Multiple Choice Questions

[Question 1] 4 points

What is the 8-bit two’s complement representation of the decimal number (−40)10 ?

a) 00101000
b) 11011000
c) 10101000
d) 11010111

2 of 24 Version 1.0 of 22nd April 2024, EPFL ©2024

Solution 1 Midterm Exam — Spring 2024
Multiple Choice Questions CS-173 Fundamentals of Digital Systems

[Solution 1]

To compute the two’s complement of (−40)10 , follow the below steps:

1. Compute the binary representation of (40)10 :

4010 = 001010002

2. To get the two’s complement form from the binary representation of (40)10 , invert
all the bits and add one to it:
110101112
+000000012
110110002

3. Thus, the 8-bit two’s complement representation of (−40)10 is:

110110002

As a result, the correct option is (b).

Version 1.0 of 22nd April 2024, EPFL ©2024 3 of 24

Midterm Exam — Spring 2024 Exercise 2
CS-173 Fundamentals of Digital Systems Multiple Choice Questions

[Question 2] 8 points

Consider a decimal number x = (−114)10 . Let y be the 8-bit two’s complement repre-
sentation of x. If we perform arithmetic shift right of the binary vector y by two bits,
we obtain an integer z, also an 8-bit vector in two’s complement format. What is the
value of z?

a) (E3)16

b) (38)16

c) (−61)10

d) (23)16

4 of 24 Version 1.0 of 22nd April 2024, EPFL ©2024

Solution 2 Midterm Exam — Spring 2024
Multiple Choice Questions CS-173 Fundamentals of Digital Systems

[Solution 2]

To compute z follow the below steps:

1. Compute the two’s complement representation of (−114)10 :

−11410 = 100011102

Thus, y = 100011102 .

2. Perform an arithmetic right shift of y by two bits:

100011102 → Shift right by two bits → 111000112

Note that the MSB is replicated during arithmetic right shift.

3. As a result, z = 111000112 , which is equal to (E3)16 .

Therefore, the correct option is (a).

Version 1.0 of 22nd April 2024, EPFL ©2024 5 of 24

Midterm Exam — Spring 2024 Exercise 3
CS-173 Fundamentals of Digital Systems Multiple Choice Questions

[Question 3] 4 points

Consider two fixed-point representations in two’s complement, Fx1 and Fx2, having m
bits for the integer part and f bits for the fractional part. Specifically:

• Fx1: m = 4, f = 4 and

• Fx2: m = 5, f = 3.

If DR() stands for dynamic range, which of the following statements is true?

a) DR(Fx1) = DR(Fx2)
b) DR(Fx1) = DR(Fx2) × 2
c) DR(Fx1) = DR(Fx2) / 2
d) None of the above

6 of 24 Version 1.0 of 22nd April 2024, EPFL ©2024

Solution 3 Midterm Exam — Spring 2024
Multiple Choice Questions CS-173 Fundamentals of Digital Systems

[Solution 3]

Given a fixed-point number in two’s complement form with m integer bits and f frac-
tional bits, the dynamic range (DR) is given by:

2m−1
DR = = 2m−1+f
2−f

For both Fx1 and Fx2, m + f is same and equal to eight, therefore,

DR(Fx1) = DR(Fx2).

As a result, the answer is option (a).

Version 1.0 of 22nd April 2024, EPFL ©2024 7 of 24

Midterm Exam — Spring 2024 Exercise 4
CS-173 Fundamentals of Digital Systems Multiple Choice Questions

[Question 4] 8 points

Consider the truth table for a 3-input, 1-output logic function f . Which of the following
logic functions is equivalent to f ?

a b c f
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 0

a) ac + b b) ab + bc + ac
c) ab + ab + abc + abc + abc d) a + b + c

8 of 24 Version 1.0 of 22nd April 2024, EPFL ©2024

Solution 4 Midterm Exam — Spring 2024
Multiple Choice Questions CS-173 Fundamentals of Digital Systems

[Solution 4]

Only the first truth table matches the truth table given in the question, so the correct
answer is option (a).

a b c f a b c f
0 0 0 1 0 0 0 0
0 0 1 1 0 0 1 1
0 1 0 0 0 1 0 0
a) 0 1 1 0 b) 0 1 1 1
1 0 0 1 1 0 0 0
1 0 1 1 1 0 1 0
1 1 0 1 1 1 0 1
1 1 1 0 1 1 1 1

a b c f a b c f
0 0 0 0 0 0 0 0
0 0 1 1 0 0 1 1
0 1 0 1 0 1 0 1
c) 0 1 1 1 d) 0 1 1 1
1 0 0 0 1 0 0 1
1 0 1 1 1 0 1 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1

Version 1.0 of 22nd April 2024, EPFL ©2024 9 of 24

Midterm Exam — Spring 2024 Exercise 5
CS-173 Fundamentals of Digital Systems Multiple Choice Questions

[Question 5] 6 points

Consider the following circuits:

(a) (b) (c)

The capacitance of the input of the inverter is 1 fF. The capacitance of an input of a
two-input AND gate is 2 fF. Let us call ta the delay of the inverter NOT1 in circuit (a),
tb the delay of the inverter NOT1 in circuit (b), and tc the delay of the inverter NOT1
in circuit (c). Which of the following is true?

a) tb > tc > ta b) tc > tb ≥ ta

c) tc > tb > ta d) tc > ta > tb

10 of 24 Version 1.0 of 22nd April 2024, EPFL ©2024

Solution 5 Midterm Exam — Spring 2024
Multiple Choice Questions CS-173 Fundamentals of Digital Systems

[Solution 5]

The output capacitance of the inverter in circuit (a) is 1 fF, the output capacitance of the
inverter in circuit (b) is 3 fF, and the output capacitance of the inverter in circuit (c) is
2 fF. The delay of an inverter is proportional to the output capacitance. Therefore, the
correct choice is a) tb > tc > ta .

Version 1.0 of 22nd April 2024, EPFL ©2024 11 of 24

Midterm Exam — Spring 2024 Solution 6
CS-173 Fundamentals of Digital Systems Detailed Answer Type Questions

Part II: Detailed Answer Type Ques-

tions

[Question 6] 8 points

Consider the floating-point representation

X = (S Em−1 Em−2 · · · E1 E0 Mn−1 Mn−2 · · · M0 )

with the following properties:

• (n + 1)-bit significand in sign-and-magnitude format, normalized, with a hidden

bit;

• m-bit exponent, in biased format, where the bias equals B = 2m−1 − 1.

Assume n = 4 and m = 6. Given a binary digit vector X = (110 0011 1111), find the
corresponding decimal value.

Note: Show the intermediate steps of the computation.

12 of 24 Version 1.0 of 22nd April 2024, EPFL ©2024

Solution 6 Midterm Exam — Spring 2024
Detailed Answer Type Questions CS-173 Fundamentals of Digital Systems

[Solution 6]

The decimal number can be calculated in the following way:

1. The sign bit is 1, the number is negative.

2. For the mantissa:

• Given n = 4, the binary representation of the mantissa without the hidden

bit consists of the last 4 bits of X, which is 1111.
• With the hidden bit, the normalized mantissa is 1.1111.
• In the decimal form, the value of the normalized mantissa is:

(1.1111)2 = 1 + 2−1 + 2−2 + 2−3 + 2−4 10 = (1.9375)10

3. Bias of the exponent is:

26−1 − 1 = 31

4. For the calculation of exponent:

• Given m = 6, the binary representation of the exponent consists of the 6 bits

immediately after the sign-bit. Thus, the exponent in binary form is 100011.
• Thus, exponent without the bias in decimal form is:

20 + 21 + 25 = 35

• Therefore, the biased exponent can be calculated by subtracting bias from

the exponent:

20 + 21 + 25 − 31 = 4

Therefore, the number in decimal format can be given as:

(−1) × 1 + 2−1 + 2−2 + 2−3 + 2−4 × 24

= − (16 + 8 + 4 + 2 + 1)
= − 31.0

Version 1.0 of 22nd April 2024, EPFL ©2024 13 of 24

Midterm Exam — Spring 2024 Exercise 7
CS-173 Fundamentals of Digital Systems Detailed Answer Type Questions

[Question 7] 10 points

Simplify the following logic function f = ab + c · (bc + a) using the Boolean algebra
transformations. If implemented as a logic circuit, your final, simplified expression
should contain only one AND gate and one NOT gate. You are not required to draw
the logic circuit.

Note: Show the intermediate steps and clearly specify the transformations applied.

14 of 24 Version 1.0 of 22nd April 2024, EPFL ©2024

Solution 7 Midterm Exam — Spring 2024
Detailed Answer Type Questions CS-173 Fundamentals of Digital Systems

[Solution 7]

f = ab + c · (bc + a)
f = ab + c · ((bc) · a) (De Morgan’s Theorem)
f = ab + c · ((b + c) · a) (De Morgan’s Theorem)
f = ab + c · (ab + ac) (Distributive Property)
f = ab + abc + acc (Distributive Property)
f = ab + abc (xx = 0)
f = ab (x + xy = x)

Version 1.0 of 22nd April 2024, EPFL ©2024 15 of 24

 Midterm Exam — Spring 2024 Exercise 8
CS-173 Fundamentals of Digital Systems Detailed Answer Type Questions

[Question 8] 12 points

Consider the following Verilog module. It defines a Verilog module named

cont_assign taking a 4-bit vector a as input, and giving a 2-bit vector f as output.

Listing 2.1: A behavioral Verilog model using continuous assignments.

1 module cont_assign (
2 input [3:0] a,
3 output [1:0] f
4 );
5

6 wire b, c;
7

8 assign b = (a[0] & a[2]) | ( a[1] & a[3]);

9 assign c = (a[0] | ~ a[2]) & ( ~ a[1] | a[3]);
10 assign f = {c, b};
11

12 endmodule

(a) Draw the equivalent logic circuit by using the basic logic gates AND, OR, and NOT.

(b) What are the values of b, c, f[0], and f[1] when a is 4'b0111?

Note: Show the intermediate steps of computation.

16 of 24 Version 1.0 of 22nd April 2024, EPFL ©2024

Solution 8 Midterm Exam — Spring 2024
Detailed Answer Type Questions CS-173 Fundamentals of Digital Systems

[Solution 8]

a) Figure 1 shows the equivalent logic circuit corresponding to Listing 2.1. Inputs a0
through a3 represent the individual bits of input a, from least to most significant,
respectively. Outputs f0 and f1 similarly represent the least and most significant bit,
respectively, of output f. The output of gates b and c in Figure 1 correspond to the
eponymous wire variables in Listing 2.1.

Figure 1: Logic circuit described by Listing 2.1.

Version 1.0 of 22nd April 2024, EPFL ©2024 17 of 24

Midterm Exam — Spring 2024 Solution 8
CS-173 Fundamentals of Digital Systems Detailed Answer Type Questions

b) When input a is 4'b0111, wire b takes on the value 1, wire c the value 0, and
output f the value 2'b01.

Listing 2.2 works through and lists the intermediate values in more detail.

Listing 2.2: Intermediate working for Listing 2.1.

// The given input vector:
a = 4'b0111
// corresponds to the individual bits:
a[0] = 1
a[1] = 1
a[2] = 1
a[3] = 0

// Substitute bits in intermediate wire expressions:

b = (1 & 1) | ( 1 & 0) = 1 | 0 = 1
c = (1 | ~ 1) & ( ~ 1 | 0) = (1 | 0) & (0 | 0) = 1 & 0 = 0

// Concatenate wire bits into output vector:

f = {0, 1} = 2'b01
// which corresponds to the individual bits:
f[0] = 1
f[1] = 0

18 of 24 Version 1.0 of 22nd April 2024, EPFL ©2024

Exercise 9 Midterm Exam — Spring 2024
Detailed Answer Type Questions CS-173 Fundamentals of Digital Systems

[Question 9] 10 points

Consider the logic circuit:

Write the Verilog module describing the given circuit. Use only structural (i.e., gate-
level) modeling and do not use Verilog bitwise operators. You are not required to write
a testbench.

Version 1.0 of 22nd April 2024, EPFL ©2024 19 of 24

 Midterm Exam — Spring 2024 Solution 9
CS-173 Fundamentals of Digital Systems Detailed Answer Type Questions

[Solution 9]

Listing 2.3 shows one way of describing the circuit. Overall we need six Verilog gates:
three OR gates, one AND gate, and one NOT gate, as well as a second NOT gate for the
negated input to the AND gate. In addition, three internal wire variables are needed
to connect intermediate gates.

Listing 2.3: Verilog structural model of the given circuit.

1 module priority_enc (
2 input a, b, c, d,
3 output x, y, z
4 );
5

6 wire not_c, h, i;
7

8 not (not_c, c);

9 not (x, i);
10 or (y, d, h);
11 and (h, not_c, b);
12 or (i, d, c);
13 or (z, i, b, a);
14

15 endmodule

20 of 24 Version 1.0 of 22nd April 2024, EPFL ©2024

Exercise 10 Midterm Exam — Spring 2024
Detailed Answer Type Questions CS-173 Fundamentals of Digital Systems

[Question 10] 30 points

Consider the logic circuit:

a) Assume that the gates have no propagation delay. Given the input signal wave-
forms shown below, draw the corresponding timing waveforms for the remaining sig-
nals p1, p2, p3, p4, p5, p6, f, and g.

b) Assume that the logic gates have the following propagation delays:

• two-input AND: tAND2 = 3 ns,

• two-input OR: tOR2 = 2 ns,
• three-input OR: tOR3 = 3 ns, and
• tNOT = 1 ns.

List all input-to-output paths in this circuit. To describe such a path, simply write a
sequence (inputname, Gi, Gj, ..., outputname). For example, for one of the paths that
starts at input a and terminates at output f, you should write (a, G5, G7, f), where G5
and G7 are the labels of the AND gates on that path.

For each of the listed paths, compute the path delay.

Version 1.0 of 22nd April 2024, EPFL ©2024 21 of 24

Midterm Exam — Spring 2024 Exercise 10
CS-173 Fundamentals of Digital Systems Detailed Answer Type Questions

What is the worst case delay of the circuit? Which path is the critical path? If there are
multiple paths with the same worst case delay, specify them all.

Note: Show the intermediate delay computation steps.

22 of 24 Version 1.0 of 22nd April 2024, EPFL ©2024

Solution 10 Midterm Exam — Spring 2024
Detailed Answer Type Questions CS-173 Fundamentals of Digital Systems

[Solution 10]

a)

b)

(a, G5, G7, f): There are two 2-input AND gates gates on this path, so the delay of
this path is 2 × tAN D2 = 2 × 3 = 6 ns.

(a, G4, G6, G7, f): There are two 2-input AND gates and one 2-input OR gate on
this path, so the delay of this path is 2 × tAN D2 + tOR2 = 2 × 3 + 2 = 8 ns.

(a, G4, G6, G8, g): There are one 2-input AND gate, one 2-input OR gate and one
3-input OR gate on this path, so the delay of this path is tAN D2 +tOR2 +tOR3 = 3+2+3 =
8 ns.

(a, G4, G8, g): There are one 2-input OR gate, and one 3-input OR gate on this
path, so the delay of this path is tOR2 + tOR3 = 2 + 3 = 5 ns.

(b, G1, G5, G7, f): There are two 2-input AND gates and one NOT gate on this
path, so the delay of this path is 2 × tAN D2 + tN OT = 2 × 3 + 1 = 7 ns.

(b, G1, G8, g): There are one 3-input OR gate and one NOT gate on this path, so
the delay of this path is tOR3 + tN OT = 3 + 1 = 4 ns.

Version 1.0 of 22nd April 2024, EPFL ©2024 23 of 24

Midterm Exam — Spring 2024 Solution 10
CS-173 Fundamentals of Digital Systems Detailed Answer Type Questions

(b, G3, G6, G7, f): There are two 2-input AND gates and one 2-input OR gate on
this path, so the delay of this path is 2 × tAN D2 + tOR2 = 2 × 3 + 2 = 8 ns.

(b, G3, G6, G8, g): There are one 2-input AND gate, one 2-input OR gate and one
3-input OR gate on this path, so the delay of this path is tAN D2 +tOR2 +tOR3 = 3+2+3 =
8 ns.

(c, G3, G6, G7, f): There are two 2-input AND gates and one 2-input OR gate on
this path, so the delay of this path is 2 × tAN D2 + tOR2 = 2 × 3 + 2 = 8 ns.

(c, G3, G6, G8, g): There are one 2-input AND gate, one 2-input OR gate and one
3-input OR gate on this path, so the delay of this path is tAN D2 +tOR2 +tOR3 = 3+2+3 =
8 ns.

(c, G2, G4, G6, G7, f): There are two 2-input AND gates, one 2-input OR gate and
one NOT gate on this path, so the delay of this path is 2 × tAN D2 + tOR2 + tN OT =
2 × 3 + 2 + 1 = 9 ns.

(c, G2, G4, G6, G8, g): There are one 2-input AND gate, one 2-input OR gate, one
3-input OR gate and one NOT gate on this path, so the delay of this path is tAN D2 +
tOR2 + tOR3 + tN OT = 3 + 2 + 3 + 1 = 9 ns.

(c, G2, G4, G8, g): There are one 2-input OR gate, one 3-input OR gate and one
NOT gate on this path, so the delay of this path is tOR2 + tOR3 + tN OT = 2 + 3 + 1 = 6 ns.

Therefore, the critical paths are (c, G2, G4, G6, G7, f) and (c, G2, G4, G6, G8, g)
with a delay of 9 ns. The circuit diagram for the critical paths is shown below.

24 of 24 Version 1.0 of 22nd April 2024, EPFL ©2024