Digital Circuits: Combinational Logic Design
The maximum number of marks for this assignment is 40. It will contribute towards 2% of your
assessment in this subject. For Question 4 you will design a decoder for the (7,4) Hamming
code. This is the circuit that you will implement and test in Workshop 3 with in-workshop
assessment worth 4% based on the successful demonstration and understanding of your design.
I suggest that you prioritise Question 4 for this reason.
Before we begin we will define some terminology and notation that will be used in the assignment.
An n-variable minterm is a product term with each of the n variables appearing exactly
once, in complemented or uncomplemented form. There are 2n
such product terms. Examples
of 4-variable minterms are WXY Z, W XY Z and W XY Z. The product term WX Z is not a
4-variable minterm since the term does not contain Y or Y .
When you move from a truth-table to a sum-of-products expression, you are actually expressing
the function as a sum-of-minterms. We will call the minterm associated with row i of the truthtable,
minterm i (assuming that we start at row 0). A compact way of representing a function
is simply to list the minterms corresponding to the rows of the truth-table that result in an
output of 1. We do this using the notation
F(X, Y, Z) = X,Y,Z(1, 2, 4, 7)
X Y Z + XY Z + XY Z + XY Z.
Another example of this notation is
G(W, X, Y, Z) = W,X,Y,Z(5, 11, 13, 14)
W XY Z + WXY Z + W XY Z + W XY Z.
If there are some inputs for which we dont care about the corresponding output, rows 3 and 5
for example, then we will write d(3, 5) to denote this.
1. 8 marks in total (Based on Wakerly, Problem 4.19)
Using Karnaugh maps, find a minimal sum-of-products expression for each of the following
logic functions.
(a) 2 marks Fa = W,X,Y,Z(0, 1, 3, 5, 14) + d(8, 15)
(b) 2 marks Fb = W,X,Y,Z(0, 1, 2, 8, 11) + d(3, 9, 15)
1
(c) 2 marks Fc = A,B,C,D(1, 5, 9, 14, 15) + d(11)
(d) 2 marks Fd = W,X,Y,Z(3, 5, 6, 7, 13) + d(1, 2, 4, 12, 15)
2. 8 marks in total
Two functions F and G are dependent on the four Boolean variables A, B, C and D.
The functions are defined by the following expressions:
F = A,B,C,D(0, 1, 2, 3, 5, 7)
G = A,B,C,D(5, 7, 12, 13, 14, 15)
(a) 2 marks Construct the K-map for F and derive a sum-of-products expression for
F that has the fewest possible product terms.
(b) 2 marks Construct the K-map for G and derive a sum-of-products expression for
G that has the fewest possible product terms.
(c) 4 marks Revisit the K-maps for F and G and see if you can produce an implementation
that requires fewer product terms in total (and thus fewer AND gates).
3. 8 marks in total
Programmable logic devices (PLDs) have an AND-OR array for easy implementation of
sum-of-products expressions. Most PLDs have a programmable inverter/buffer at the
output of the OR gate which can be programmed to invert or not. This means that to
implement a function F we can form a sum-of-products expression for F and not invert
the OR gate output. Alternatively, we can find a sum-of-products expression for the
complement of F (F) and then invert the OR gate output.
Consider the function F = W,X,Y,Z(2, 3, 4, 5, 6, 7, 11, 13, 15). Investigate the cost (in
terms of AND gates) of each of the strategies discussed above for implementing F. This
involves finding the minimal sum-of-products expressions for F and then F and comparing
the number of product terms required in each case