Encoders/Decoders

Decoders

We start off with designing a 3-8 decoder. First, we discuss the key features of the decoder. How many data inputs, control inputs, and outputs it has:

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.

x2x1x0 Operation
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.

Truth Table for 2-4 Decoder

The truth table for the 3-8 decoder is quite large, so we write the one for a 2-4 decoder.

x1 x0 z3 z2 z1 z0
0 0 0 0 0 1
0 1 0 0 1 0
1 0 0 1 0 0
1 0 1 0 0 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

Small Exercise

Suppose the output of a 3-8 decoder has z4 = 1. What must the input bits be? Since z4 = 1, we know that output 4 is active, and the rest of the outputs are 0. Thus, we write 4 in binary, using 3 bits (since there are 3 input bits), which is 100.

Thus, x2x1x0 = 100. That is, x2 = 1, x2 = 0, x0 = 0.

Decoder or DeMux

If you're thinking that a decoder looks a lot like a DeMUX, you're right. After all, they both seem to "select" an output. They aren't exactly the same. For example, 3-8 decoder has 3 data inputs. A 1-8 DeMUX has 3 control inputs, plus 1 more data input, for a total of 4 inputs.

In order to make the decoder and DeMUX essentially the same, we need to add an additional feature to the decoder.

2-4 Decoder with Enable

Remember when we talked about memory chips. There was a chip-enable. If this control input was active, then either a read or write was performed. If it was inactive, then neither read nor write is performed.

The enable control bit for the decoder acts somewhat like the chip enable.

Here's how the enable bit works:

Enable Operation
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.

x1 x0 z3 z2 z1 z0
0 0 0 0 0 e
0 1 0 0 e 0
1 0 0 e 0 0
1 0 e 0 0 0

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.

Encoder

The main difference between a MUX and a DeMUX is swapping the roles of inputs and outputs.

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
x0 0 0 0
x1 0 0 1
x2 0 1 0
x3 0 1 1
x4 1 0 0
x5 1 0 1
x6 1 1 0
x7 1 1 1

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 +
       \x0\x1\x2\x3\x4x5\x6\x7 +
       \x0\x1\x2\x3\x4x\5x6\x7 +
       \x0\x1\x2\x3\x4\x5\x6x7

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 = 1.

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.

Priority Encoder

Since we generally have no control over the inputs, it's not so realistic to expect exactly one input to be 1. We can make an encoder that relaxes this assumption.
Assumption A priority encoder assumes that at least one input is 1
This only excludes one possible input. The input where all bits are 0. We'll talk about what to do in that case.

Picking a Priority Scheme

With a priority encoder, we may have more than one input with a value of 1. How do we decide which input subscript to encode? This is where priority comes in. We need to assign a priority to each of the subscripts.

There are two common ways to do come up with a priority scheme.

You could imagine other ways of prioritizing the inputs.

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?

Modifying the Product Term

What does it mean to say, for example, that x4 has the highest priority? It means that x4 = 1, and x5 = 0, and x6 = 0, and x7 = 0. That is, every input with higher priority than x4 must be 0. We don't care what happens to inputs with lower priorities.

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:

 \x7\x6\x5x4
We negate all literals with higher priority than the input, and we leave out all literals with smaller priorities.

Priority Encoder Expressions

Thus, the modified Boolean expressions for priority encoders are:
  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

Simplifying Priority Encoders

The equations for the priority encoder can be simplified. For example, look at z1. Even though this Boolean expression is quite long, it still conveys the idea that if x7, x6, x3 or x2 is the highest priority, then z1 should be 1.

To discuss this more, let's rewrite z1 as:

  z1 = P7 + P6 + P3 + P2
where
  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\x2x1
Let'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.

An Exercise

Try to rewrite these expressions, but use the following priority scheme: let low subscripts have high priorities. The simplified expressions for priority encoders are not easy to understand, but with work and thought, they do make sense.

The All-Zero Case

What do we do if all the inputs are 0? We might encode 000 as output, but that creates a problem. In particular, we can't distinguish between all 0's as inputs as having x0 as 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.

Summary

Decoders are essentially DeMUXes. However, encoders are not essentially MUXes. Roughly speaking, decoders convert from binary to unary, while encoders convert from unary to binary. This isn't strictly accurate, but it gives you an approximate idea of what they do.

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.