Microsoft Word – CSSE4010_2020_final_exam.docx
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 1 of 14
School of Information Technology and Electrical Engineering
EXAMINATION
Semester Two Final Examination, 2020
CSSE4010 Digital System Design
Examination information:
• This is an open-book non-invigilated online examination conducted as a timed Blackboard
submission
• You need to download this exam paper from the course Blackboard site, answer the
questions on the paper itself in the space provided (either electronically or writing on a printed
copy) and upload the answers (a scanned copy in case of handwritten answers) to the
submission link available on the course Blackboard site
• Duration of the exam is 2 hours and additional 30 minutes for any technical issues
• You must provide working of your answers and marks will be given not just for the final result
but also for the methods follow
• You must state any assumptions made during answering the questions
• This paper contains four questions each carrying 25 marks in 14 pages. You must answer all
questions
• Marks are as indicated for each question
• This final exam contributes towards 40% of the final course mark
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 2 of 14
Question 1 [25 marks]
1. Represent the following decimal numbers in the given formats [3 marks]
a. (-37) in fixed-point 8-bit 2’s complement with no fractional bits
b. (-15.125) in fixed-point 8-bit 2’s complement with 3 fractional bits
c. 875 in 16-bit binary coded decimal
2. Consider the following two Boolean functions expressed in terms of min-terms and don’t
care terms
𝒇 =#𝒎(𝟑, 𝟒, 𝟕, 𝟏𝟐, 𝟏𝟏) + 𝑫(𝟎, 𝟏𝟑, 𝟖, 𝟏𝟎)
𝒈 =#𝒎(𝟎, 𝟑, 𝟕, 𝟏𝟐, 𝟏𝟏, 𝟏𝟎) + 𝑫(𝟏, 𝟓, 𝟏𝟑, 𝟏𝟒, 𝟗)
a. Provide individually simplified minimal sum of product (SOP) expressions for each
function using K-maps and express the total gate cost as the sum of number of
AND gates, number of OR gates and number of wires used (you do not need to
count the NOT gates when computing the gate cost and you can assume that the
inverted version of the variables are available) [11 marks]
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 3 of 14
b. Considering any common terms between f and g that can be shared, obtain
simplified versions of f and g using K-maps considering both functions. Express
the total gate cost and compare with your answer in part (a). [11 marks]
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 4 of 14
Question 2 [25 marks]
1. Using Boolean algebra show that
𝐴𝐵𝐶̅ + 𝐵�̅�𝐷9 + 𝐵𝐶 + �̅�𝐷 = 𝐵 + �̅�𝐷 [3 marks]
2. Using DeMorgan’s law, express the Boolean function 𝐹 = 𝐴𝐵;𝐶 + �̅��̅� + 𝐴𝐵 with only OR and
NOT operations. [2 marks]
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 5 of 14
3. Using block diagrams, show how you can design an 8-bit signed comparator circuit based on
an 8-bit ripple carry adder/subtractor to perform the following signed comparisons. Your
circuit should have two 8-bit inputs A and B and separate outputs to show the result of the
following comparison operations: A>=B (greater than or equal), A=B (equal). [8 marks]
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 6 of 14
4. Using 4-bit carry look ahead (CLA) adders as building blocks, show how you can design an 8-
bit adder with saturation. You don’t need to show the internal details of the 4-bit CLA adders
and can use them as blocks. Your design should have two 8-bit inputs A and B and 8-bit sum
output S, which should be saturated if overflow occurs. The circuit should show how
saturation is implemented. [8 marks]
5. Show how the logic function 𝐹(𝐴, 𝐵, 𝐶, 𝐷) = ∑𝑚(0,1,3,4,8,9,15) be realised by using an 8
to 1 multiplexer. [4 marks]
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 7 of 14
Question 3 [25 marks]
1. Provide VHDL entity-architecture descriptions for the following basic blocks used in
sequential circuit design (use dataflow/behavioural abstractions only).
a. A gated D-latch with active high enable signal. [2 marks]
b. A positive edge triggered J-K flip flop with active low asynchronous clear
[2 marks]
c. A negative edge triggered T flip flop with active low asynchronous set
[2 marks]
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 8 of 14
2. Using block/gate diagrams and logic expressions show how you can convert from each
one of the following flip-flops to the given target flip-flop. You may use K-maps to obtain
simplified logic expression as needed.
a. D flip-flop to T flip-flop [2 marks]
b. T flip-flop to D flip-flop [2 marks]
c. D flip-flop to JK flip-flop [2 marks]
d. T flip-flop to JK flip-flop [2 marks]
3. Using the method of interacting finite state machines (FSMs) show how you can design a
bit sequence detector to detect the binary sequence 101101 with overlap detection. The
output should be held high for 3 clock cycles once the correct sequence is detected. An
example input and output would be:
Input: 010110101101110010
output: 000000111001110000 [11 marks]
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 9 of 14
Your solution should include state machines and suggested state encodings based on
heuristic rules for minimising logic. You do not need to provide flip-flop realisation of the
design and hence there is no need to obtain the logic expressions for any flip-flop inputs.
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 10 of 14
Question 4 [25 marks]
1. Briefly explain how pipelining and parallel processing can be used to improve the throughput
of a digital signal processing (DSP) system [2 marks]
2. Consider the finite impulse response (FIR) filter given by 𝑦(𝑛) = ∑ ℎ!𝑥(𝑛 − 𝑖)”!#$ . Provide
implementation structures for this filter according to the following specifications:
a. Standard direct-form structure with no-pipelining and no re-timing. [2 marks]
b. Data broadcast structure with no (additional) pipelining [2 marks]
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 11 of 14
c. Data broadcast structure with pipelining for maximum possible clock speed [2 marks]
d. If the coefficients of the above filter exhibit symmetry (i.e. ℎ! = ℎ”%!) a structure that
can achieve lower hardware complexity with maximum possible clock speed [2 marks]
e. Two-parallel version of the architecture in (d) [2 marks]
f. Compare the above designs (a)-(e) by tabulating their area complexity (number of
adders 𝑁&, multipliers 𝑁’ , and delay elements 𝑁() and time complexity (critical path
delay 𝑇)*( in terms of the propagation delay of adders 𝑇& and propagation delay of
multipliers 𝑇’ , and throughput 𝐹+&’*) [6 marks]
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 12 of 14
3. Consider a two-dimensional FIR filter (e.g. used in image processing) given by the
difference equation
𝑦(𝑛,, 𝑛-) =##ℎ!.𝑥(𝑛! − 𝑖, 𝑛- − 𝑗)
–
.#$
–
!#$
Having the following implementation architecture assuming that the 2-D input 𝑥(𝑛,, 𝑛-)
is raster scanned and fed into the architecture
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 13 of 14
a. If 𝑇& and 𝑇’ denotes the computation times of an adder and multiplier,
respectively, what is the critical path delay 𝑇)*( of the above 2-D filter
architecture [2 marks]
b.
c. Without using additional delays, use register re-timing to obtain an
implementation architecture with improved critical path delay, leading to better
sample throughput. What is the new 𝑇)*( after such re-timing? [5 marks]
Semester Two Final Examinations, 2020 CSSE4010 Digital System Design
Page 14 of 14
Space for any additional working and any assumptions made
END OF EXAMINATION