Problem 6 - Digital Design

Answer the following questions concerning 8-input priority encoder.

1.

Design it in a sum-of-product form using AND, OR, NOT gates.

2.

Using 8-input prority encoders, design a 32-input priority encoder.

1.

A 8-input priority encoder establishes an input priority to ensure that only the highest-priority input line is encoded. We choose to give priority to an input line that represent a bit from a given weight over one with a weight which is less significant. If both $D_2$ and $D_5$ are logic-1 simultaneously, the output will be 101 ($5=(101)_2$) because $D_5$ has a higher priority over $D_2$. Therefore, the truth table of such an encoder will be:

Inputs								Outputs
$D_7$	$D_6$	$D_5$	$D_4$	$D_3$	$D_2$	$D_1$	$D_0$	$a$	$z$	$y$	$x$
0	0	0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	0	1	0	0	0	0
0	0	0	0	0	0	1	X	0	0	0	1
0	0	0	0	0	1	X	X	0	0	1	0
0	0	0	0	1	X	X	X	0	0	1	1
0	0	0	1	X	X	X	X	0	1	0	0
0	0	1	X	X	X	X	X	0	1	0	1
0	1	X	X	X	X	X	X	0	1	1	0
1	X	X	X	X	X	X	X	0	1	1	1

If $D_7$ is logic-1, then $x$,$y$, and $z$ will be logic-1. If $D_6$ is logic-1, then $z$ and $y$ will be logic-1 iff $D_7$ is logic-0. This verification is done thanks to an AND foor. $a$ is one when all the inputs are logic-0. This output will be used later.

2.

For the 32-bit pritority encoder, we use four 8-bit priority encoders and two combinational circuits. We keep the same notation as above but add a subscript to figure out which one of the four encoder we are talking about. The output will be the five lines called $Z$,$Y$,$X$,$W$, and $V$. Here follows the sequence of the binary numbers from 31 to 0.

$$\begin{tabular}{cc\vert cc\vert rc\vert cc} 31 & 11111 & 23 & 101... ...& 00001 \\ 24 & 11000 & 16 & 10000 & 8 & 01000 & 0 & 00000 \\ \end{tabular}$$

According to the previous table, $Z$ and $Y$ can de determined by the knowledge of all the $a_i$. We also determine $A$, which is the equivalent for our neew circuit of the previous $a_i$. The truth table determining the first of our two combinational circuits follows.

Inputs				Outputs
$a_3$	$a_2$	$a_1$	$a_0$	$A$	$Z$	$Y$
0	0	0	0	0	1	1
0	0	0	1	0	1	1
0	0	1	0	0	1	1
0	0	1	1	0	1	1
0	1	0	0	0	1	1
0	1	0	1	0	1	1
0	1	1	0	0	1	1
0	1	1	1	0	1	1
1	0	0	0	0	1	0
1	0	0	1	0	1	0
1	0	1	0	0	1	0
1	0	1	1	0	1	0
1	1	0	0	0	0	1
1	1	0	1	0	0	1
1	1	1	0	0	0	0
1	1	1	1	1	0	0

$p_i$ is a variable telling us which encoder we should take the output from. Indeed, the value of the sequence $X$,$W$, and $V$ is exactly the value of the sequence $z_i$, $y_i$, and $x_i$, respecitvely, where $i$ can be determined from the knowledge of $Z$ and $Y$. Once $p_i$ is calculated, all the $p_i$'s are ANDed with the output of the correspondent encoders. As the outputs of the encoders are directly linked to $X$,$W$, and $V$, the latters will be reached by the right value only. This corresponds to the use of a multiplexer using $Z$ and $Y$ as select lines and the outputs of the encoders as a multiple input.

Inputs		Outputs
$Z$	$Y$	$p_3$	$p_2$	$p_1$	$p_0$
0	0	0	0	0	1
0	1	0	0	1	0
1	0	0	1	0	0
1	1	1	0	0	0

The last logic diagram uses a lot of intuitive notations. In particular, $z_ip_i$, for instance, shows that the $z_i$ and $p_i$ have been ANDed before reaching that point. Because of the feed back, the path from the outputs of the encoders to $X$,$W$, and $V$ should be lengthened by the use of non-inverter for example. This is not shown on the diagram.