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:

- Data inputs: 3 (labeled x2, x1, x0)
- Control inputs: 0
- Outputs: 8 (labeled z7, ..., z0)

In general, you have a k-ceil(lg(k)) decoder.

- Data inputs:: ceil( lg k ) (labeled
**xceil(lg k), ..., x0**) - Control inputs: 0
- Outputs: k (labeled zk-1, ..., z0)

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 / Operation000 / 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 / z00 / 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 / Operatione = 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 / z00 / 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.

- The data inputs of a decoder correspond to the control bits of a DeMUX.
- The enable input of a decoder correspond to the data bit of a DeMUX.

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 / z0x0 / 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.

- Larger subscripts have higher priorities. Thus, 0 has the lowest priority, and 7 has the highest.
- Smaller subscripts have higher priorities. Thus, 7 has the lowest priority, and 0 has the highest.

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, thenz1 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, whileP7, 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.