In general, you have a k-ceil(lg(k)) decoder.
What does a 3-8 decoder do? A decoder assumes the inputs x2x1x0 represent a 3-bit bitstring represented in UB. Thus, if x2x1x0 = 011, then the number 3 is input into the decoder, since 011 in UB has a value of 310.
For each of the 8 possible inputs, exactly one of the outputs is set to 1. The rest have a value of 0. Thus, if x2x1x0 = 011, then z3 = 1 while all other outputs are 0.
Here's a table describing the behavior of an 8-3 decoder.
|000||z0 = 1|
|001||z1 = 1|
|010||z2 = 1|
|011||z3 = 1|
|100||z4 = 1|
|101||z5 = 1|
|110||z6 = 1|
|111||z7 = 1|
To see what this is doing, let's look at one of the rows of the table above. In particular, look at the last row. When x2x1x0 = 111 (that is, x2 = 1, x1 = 1, and x0 = 1), then we know 111 is UB for 710.
Thus, we make z7 = 1. All other outputs are set to 0.
We can write the Boolean expression for each of the outputs. Since
this is a conventional truth table, we can write sum-of-products for
each output. Since each output only has one row with an output of
1, this results in a minterm.
z3 = x1x0
z2 = x1\x0
z1 = \x1x0
z0 = \x1\x0
Thus, x2x1x0 = 100. That is, x2 = 1, x2 = 0, x0 = 0.
In order to make the decoder and DeMUX essentially the same, we need to add an additional feature to the decoder.
The enable control bit for the decoder acts somewhat like the chip enable.
Here's how the enable bit works:
|e = 0||All outputs are 0|
|e = 1||Acts like regular decoder without enable|
If the enable is active, it behaves as a regular decoder. If it's not active, then all outputs are 0.
This is equivalent to the following condensed truth table.
There is now a direct correspondence between a 1-8 DeMUX and a 3-8 decoder with enable.
In other words, the only difference is that interpretation of what is a control bit and what is a data bit. The two circuits are identical.
It stands to reason that this is the difference between an encoder and a decoder. For example, a 3-8 decoder has 8 outputs, of which exactly one output is 1.
If we convert the output to input, we get 8 inputs, where exactly one input is 1. This is the constraint of a regular encoder.
Assumption A regular encoder assumes that exactly one input is 1 (while all other inputs are 0).Consider this assumption. Normally, we have 8 inputs, which means we have 28 or 256 rows. Only 8 rows satisify the the assumption (i.e., xi = 1 for i ranging from 0 to 7). The remaining rows either have too many 1's or no 1's at all.
With the 3-8 decoder, the inputs were a 3 bit UB bitstring which told us which output to set high. So, now that inputs are outputs, the output of an 8-3 decoder has 3 bits as output. This should indicate which input was set to 1, and output the binary representation (in UB) of the input. THus, if x5 = 1 (and all other inputs are 0), then the output is z2z1z0 = 101, since 101 is interpreted as 5 in UB.
Thus, we can write a simplified truth table with only those 8 rows.
|Input Variable Has Value 1||z2||z1||z0|
Thus, if x3 = 1, then the 3 output bits, z2z1z0 = 011, since 011 is maps to value 3 in UB.
Suppose we wanted to write the Boolean expression for z2. As before, we identify the rows with 1's as outputs, and create a minterm.
If we do this, we will have very large minterms.
z2 = \x0\x1\x2\x3x4\x5\x6\x7 +
The terms need not be this large. We've assumed that exactly one
input is a 1. This is a strong assumption that allows us to
simply the expression greatly.
z2 = x4 + x5 + x6 + x7
z1 = x2 + x3 + x6 + x7
z0 = x1 + x3 + x5 + x7
Let's see how this works. Suppose we know that x3 =
1. Then, z2 = 0, since x3
does not appear in the Boolean expression (thus, all other literals
are 0). x3 do appear in z1 and
z0, so x1 = 1 and x0
Therefore, x2x1x0 = 011, which is UB for 3, so that's what we expected. Again, this Boolean expression can be simplified because we assume exactly one input is 1.
Assumption A priority encoder assumes that at least one input is 1This only excludes one possible input. The input where all bits are 0. We'll talk about what to do in that case.
There are two common ways to do come up with a priority scheme.
For now, let's assume that larger subscripts have higher priorities.
The Boolean expressions we came up with for the regular encoder
are no longer valid.
z2 = x7 + x6 + x5 + x4
z1 = x7 + x6 + x3 + x2
z0 = x7 + x5 + x3 + x1
To make it a little easier to modify, I've written the expressions
with the highest priority input variable first.
So why doesn't this work? Suppose x4 = 1, and x3 = 1. The higher priority is 4, so we should have an output of 100.
However, if we plug into the Boolean expressions, we get an output of 111, which is clearly incorrect. The problem? Our assumption that exactly one input is 1 no longer holds.
For example, x4 appears in the Boolean expression for z2. We assumed, for a regular encoder, that if x4 = 1, then no other input was 1. However, we can no longer assume this.
How can we modify these formulas so that we know that, say, x4 has the highest priority?
How can we come up with a Boolean expression to convey this? This
looks very much like creating a minterm, except we don't use all input
variables. In fact, that's what it is:
We negate all literals with higher priority than the input, and
we leave out all literals with smaller priorities.
z2 = x7 + \x7x6 + \x7\x6x5 + \x7\x6\x5x4 z1 = x7 + \x7x6 + \x7\x6\x5\x4x3 + \x7\x6\x5\x4\x3x2 z0 = x7 + \x7\x6x5 + \x7\x6\x5\x4x3 + \x7\x6\x5\x4\x3\x2x1
To discuss this more, let's rewrite z1 as:
z1 = P7 + P6 + P3 + P2
P7 = x7
P6 = \x7x6
P3 = \x7\x6\x5\x4x3
P2 = \x7\x6\x5\x4\x3x2
This is the same Boolean expression as before, but it makes it
easier to identify the product terms.
When we rewrite the Boolean expression this way, we expect the following to happen. If x7 has the highest priority, then P7 = 1, while P6, P3, and P2 are all 0. If x6 has the highest priority, then P6 = 1, while P7, P3, and P2 are all 0.
In particular, if one of the four priorities (7, 6, 3, 2) are the highest priority, then the corresponding Pi is 1, while the other priorities are 0.
Let's look at P6 more closely. P6 = \x7x6. Do we really need to have \x7 in P6. Could we simplify P6 to be simply x6?
We can analyze this by cases. Either x7 = 1, or x7 = 0. In either case, we also assume x6 = 1.
Suppose x7 = 1. That means that x6 is not the highest priority, but x7 is. This would normally cause problems because P7 will have value 1. That is, when x6 is 1, two product terms are 1: P7 and P6. This is not really a problem, because P7 would have already made z1 = 1, so it doesn't matter that P6 also makes it 1 as well.
The other case is when x7 = 0. That means that x6 has the highest priority, so P7 = 0, but that's OK, because P6 = 1, and z1 is 1, as it should be.
This leads us to the following strategy. If there is already a product term handling a higher priority, we can leave the negated literal out. For example, look at \x7\x6x5 in the Boolean expression for z2. We don't need to keep either \x7 nor \x6, since priority 7 and 6 are already handled by other product terms in the expression.
Strategy To simplify the product terms in the Boolean expressions for a priority encoder, leave out any negated literal that has higher priority than the term, and is already taken care of by a different term.This leads to the following simplified expression:
z2 = x7 + x6 + x5 + x4 z1 = x7 + x6 + \x5\x4x3 + \x5\x4x2 z0 = x7 + \x6x5 + \x6\x4x3 + \x6\x4\x2x1Let's look at one term more closely. Let's look at \x5\x4x3 from z1. We didn't need to keep \x7 nor \x6 since there were terms to handle priority 7 and 6 (which both have higher priority than 3).
We had to keep \x4 and \x3 since there were no terms to handle those cases. In particular, if either 4 or 5 were the highest priority, the output of z1 must be 0. Thus, we need these negated literals to force \x5\x4x3 to be 0 when priority 4 or 5 are the highest priority.
One way to solve this problem is to create a status bit. This bit is an output. We could say that this bit is 1 if the input is valid, and 0 if not. Thus, this bit is only 0 when all inputs are 0. Other hardware devices could look at the status bit to determine whether a proper encoding was performed.
Priority encoders allow us to encode values based on a priority scheme. Of all the combinational logic devices, understanding priority encoders is perhaps the most challenging. Even encoders take a little time to fully comprehend.