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

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