Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof (resit) / 1

Take

w, x, y, z

as the four input bits, of weights

8, 4, 2, 1

, and let 1 light a segment of the seven-segment display. The required truth table is

value   wxyz   abcdefg
 0      0000   1111110
 1      0001   0110000
 2      0010   1101101
 3      0011   1111001
 4      0100   0110011
 5      0101   1011011
 6      0110   1011111
 7      0111   1110000
 8      1000   1111111
 9      1001   1111011
10      1010   0000000
11      1011   0000000
12      1100   0000000
13      1101   0000000
14      1110   0000000
15      1111   0000000

Here binary-coded decimal represents one decimal digit per group of four bits. The six unused codes must be zeros in every output for this part; they are not don't-care conditions.

Solution

 0  0

Use Karnaugh maps with rows

w x

and columns

yz

, both in Gray code order

00, 01, 11, 10

. Juxtaposition means Boolean conjunction,

+

means Boolean disjunction, and a bar means Boolean negation. The minimal sum of products forms are

c = \overset{w}{ˉ} x + \overset{w}{ˉ} z + \overset{x}{ˉ} \overset{y}{ˉ},

(1)

and

d = w \overset{x}{ˉ} \overset{y}{ˉ} + \overset{w}{ˉ} \overset{x}{ˉ} y + \overset{w}{ˉ} y \overset{z}{ˉ} + \overset{w}{ˉ} \overset{x}{ˉ} \overset{z}{ˉ} + \overset{w}{ˉ} x \overset{y}{ˉ} z .

(2)

For

c

, the groups are

{4, 5, 6, 7}

{1, 3, 5, 7}

and

{0, 1, 8, 9}

. For

d

, take

{8, 9}

{2, 3}

{2, 6}

{0, 2}

and the isolated minterm

{5}

. Every group contains only required ones. The last

c

group wraps between the top and bottom map rows.

These covers are minimal:

c

needs its three essential groups, forced by inputs 6, 3 and 8. For

d

, input 5 is isolated, while 9, 3 and 6 each force their respective pair; input 0 still needs a further group. These five groups also attain the minimum literal count of 16.

Solution

 0  0

Use

w, x, y

as the three select bits of the 8-to-1 multiplexer, so address

i = 4 w + 2 x + y

selects data input

D_{i}

. Connect

(D_{0}, D_{1}, D_{2}, D_{3}, D_{4}, D_{5}, D_{6}, D_{7}) = (\overset{z}{ˉ}, 1, z, \overset{z}{ˉ}, 1, 0, 0, 0) .

(1)

A single NOT gate produces

\overset{z}{ˉ}

, shared by

D_{0}

and

D_{3}

; the other connections are wires and constant logic levels. For each fixed select address the data input reproduces the corresponding two rows of the truth table, including zeros for all invalid codes.

d

 0  0

Solution

 0  0

Only now may the invalid codes 10–15 be marked as don't-care conditions. The

f

Karnaugh map gives

f = w + x \overset{y}{ˉ} + x \overset{z}{ˉ} + \overset{y}{ˉ} \overset{z}{ˉ} .

(1)

The groups are

{8, \dots, 15}

{4, 5, 12, 13}

{4, 6, 12, 14}

and

{0, 4, 8, 12}

. They cover all required ones, avoid valid-digit zeros, and may assign either output to invalid codes. The valid inputs 0, 5, 6 and 9 cannot share a valid implicant with each other, so at least four product terms are necessary. The displayed four-term cover uses only seven literals.

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof (resit) / 1

a

Solution

b

Solution

c

Solution

d

Solution

 Ancestors (10)

 Discussion (0) New discussion

 Articles by others on the same topic (0)

Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Digital systems, linear algebra, introduction to formal proof (resit) / 1

 Discussion (0)  Subscribe (1) New discussion

 Discussion (0) New discussion