Decoders, encoders and comparators

Why it exists

A decoder turns a binary code into "one wire per value": it is how an address selects one memory row or one register, and how a control unit turns an opcode into an enable signal. An encoder does the opposite, turning "one wire per value" into a code (a keyboard scanner, an interrupt controller reporting which device interrupts). A comparator tells which of two numbers is larger. GATE asks for the output equations, the number of gates, how to build a big decoder from small ones, how to realise a function with a decoder, and how a priority encoder resolves several active inputs.

Prerequisites

You need combinational design and minterms from SOP, POS, minterms and maxterms.

Precise definitions

Decoder ($n$-to-$2^n$). Inputs $x_{n-1} \dots x_0$ and $2^n$ outputs $d_0, \dots, d_{2^n - 1}$. Exactly one output is 1, the one whose index equals the input value: $d_i = m_i(x)$. A decoder therefore generates all the minterms of its inputs. A 3-to-8 decoder is 8 three-input AND gates and 3 inverters. With an enable input $E$, $d_i = E \cdot m_i$ (all outputs 0 when $E = 0$). Some decoders are active-low: they are built from NAND gates and the selected output is 0 and the others are 1, $d_i' = (m_i)'$.

Larger decoders from smaller ones. Use the enable inputs: a 4-to-16 decoder is two 3-to-8 decoders; the top input bit drives the enables (enabling the first for 0 and the second for 1, via an inverter) and the other three bits go to both decoders. Equivalently it is five 2-to-4 decoders: one decodes the top two bits and enables one of four others that decode the lower two bits ($1 + 4 = 5$). In general an $n$-to-$2^n$ decoder from $k$-to-$2^k$ decoders (with $n \le 2k$) needs $1 + 2^{n-k}$ of them in two levels: one decodes the top $n - k$ bits and enables $2^{n-k}$ decoders for the remaining $k$ bits.

Implementing a function with a decoder. The function is the OR of the minterms where it is 1. Use a decoder and an OR gate on the corresponding outputs. If the decoder is active-low, use a NAND gate on those outputs instead. A circuit with several outputs shares one decoder: the full adder is a 3-to-8 decoder with two OR gates, $S = d_1 + d_2 + d_4 + d_7$ and $C_{out} = d_3 + d_5 + d_6 + d_7$. If a function has more 1s than 0s it is cheaper to OR the minterms where it is 0 and complement.

Encoder ($2^n$-to-$n$). Inputs $D_0, \dots, D_{2^n - 1}$, outputs a code. An octal-to-binary encoder has $A_2 = D_4 + D_5 + D_6 + D_7$, $A_1 = D_2 + D_3 + D_6 + D_7$, $A_0 = D_1 + D_3 + D_5 + D_7$. It assumes that at most one input is 1. Two limitations: if two inputs are 1 the output is the OR of their codes (wrong), and the code 000 is produced both by $D_0$ and by no input at all (so a valid output $V$ is needed).

Priority encoder. Resolves several active inputs by choosing the highest-priority one (the largest index by convention) and has an output $V$ that says whether any input is 1. For 4 inputs with $D_3$ the highest priority:

$A_1 = D_3 + D_2,\qquad A_0 = D_3 + D_2' D_1,\qquad V = D_3 + D_2 + D_1 + D_0 .$

$D_0$ does not appear in $A_1$ or $A_0$: the code for $D_0$ is 00, the same as "nothing", which is why $V$ is needed.

Magnitude comparator. For one bit: $A > B$ is $AB'$, $A = B$ is $A \odot B$ (XNOR), $A < B$ is $A'B$. For $n$ bits, let $x_i = A_i \odot B_i$ ($A_i$ equals $B_i$). Then

$(A = B) = x_3 x_2 x_1 x_0,\qquad (A > B) = A_3B_3' + x_3 A_2B_2' + x_3x_2 A_1B_1' + x_3x_2x_1 A_0B_0' ,$

and $A < B$ is the same with the roles of $A$ and $B$ swapped. The most significant bit that differs decides. Exactly one of the three outputs is 1. Larger comparators are cascaded: the result of the higher group is used and the lower group only matters when the higher group says equal.

How it works

The animation shows the sum bit of a full adder built from a 3-to-8 decoder and one OR gate. The columns are the decoder outputs $d_1, d_2, d_4, d_7$, their OR and the XOR of the inputs; each row has exactly one decoder output active, and the OR of the four matches the sum.

The priority encoder is easiest to understand from its table. For four inputs, step through all 16 rows: whichever inputs are active, the output is the code of the highest one, and the minimised equation for $A_0$ gives the same answer for every row.

Worked examples

#include <stdio.h>
 
/* 3-to-8 decoder: output i is 1 when the select value is i */
static int decoder(int a, int b, int c, int i) { return (4 * a + 2 * b + c) == i; }
 
/* 4-to-2 priority encoder, D3 highest: returns A1A0 and sets *valid */
static int priority(int d3, int d2, int d1, int d0, int *valid) {
    *valid = d3 || d2 || d1 || d0;
    int a1 = d3 || d2;
    int a0 = d3 || (!d2 && d1);
    (void)d0;
    return 2 * a1 + a0;
}
 
int main(void) {
    int bad = 0;
    for (int m = 0; m < 8; m++) {
        int a = (m >> 2) & 1, b = (m >> 1) & 1, c = m & 1;
        int sum = decoder(a, b, c, 1) || decoder(a, b, c, 2) || decoder(a, b, c, 4) || decoder(a, b, c, 7);
        int carry = decoder(a, b, c, 3) || decoder(a, b, c, 5) || decoder(a, b, c, 6) || decoder(a, b, c, 7);
        bad += sum != (a ^ b ^ c) || carry != (a + b + c >= 2);
    }
    printf("full adder from a decoder and two OR gates, wrong rows: %d\n", bad);
    printf("D3 D2 D1 D0 | A1 A0 V\n");
    for (int m = 0; m < 16; m++) {
        int d3 = (m >> 3) & 1, d2 = (m >> 2) & 1, d1 = (m >> 1) & 1, d0 = m & 1, v;
        int code = priority(d3, d2, d1, d0, &v);
        if (m == 0 || m == 1 || m == 2 || m == 3 || m == 4 || m == 6 || m == 8 || m == 15)
            printf(" %d  %d  %d  %d |  %d  %d  %d\n", d3, d2, d1, d0, code >> 1, code & 1, v);
    }
    int wrong = 0;
    for (int a = 0; a < 16; a++)
        for (int b = 0; b < 16; b++) {
            int x3 = !(((a >> 3) ^ (b >> 3)) & 1), x2 = !(((a >> 2) ^ (b >> 2)) & 1), x1 = !(((a >> 1) ^ (b >> 1)) & 1), x0 = !((a ^ b) & 1);
            int eq = x3 && x2 && x1 && x0;
            int gt = (((a >> 3) & 1) && !((b >> 3) & 1)) || (x3 && ((a >> 2) & 1) && !((b >> 2) & 1)) ||
                     (x3 && x2 && ((a >> 1) & 1) && !((b >> 1) & 1)) || (x3 && x2 && x1 && (a & 1) && !(b & 1));
            wrong += eq != (a == b) || gt != (a > b);
        }
    printf("4-bit comparator equations wrong on %d of 256 pairs\n", wrong);
    return 0;
}

full adder from a decoder and two OR gates, wrong rows: 0
D3 D2 D1 D0 | A1 A0 V
 0  0  0  0 |  0  0  0
 0  0  0  1 |  0  0  1
 0  0  1  0 |  0  1  1
 0  0  1  1 |  0  1  1
 0  1  0  0 |  1  0  1
 0  1  1  0 |  1  0  1
 1  0  0  0 |  1  1  1
 1  1  1  1 |  1  1  1
4-bit comparator equations wrong on 0 of 256 pairs

Cheat box

Traps and GATE patterns

Connections

A decoder with a data input on its enable is a demultiplexer, and a decoder followed by an OR gate does the same job as a multiplexer with fixed data (multiplexers and demultiplexers). A decoder driving OR gates is a ROM (an AND plane that is fixed and an OR plane that is programmed): see ROM, PLA and PAL. Comparators build on adders and subtractors (a comparator is a subtractor that discards the difference). In the CPU the control unit uses decoders for the opcode (ALU design).

PYQs

Consider the digital circuit shown below with two
input lines A and B, two select lines S0 and S1, and
an output line Y. The blocks Q and M represent an
active-high 2:4 decoder and a 4-to-1 multiplexer,
respectively.
Out
of
16
possible
input
combinations, the number of combinations that
produce Y = 1 is __________. (Answer in integer).

Consider a digital display system (DDS) shown in the
figure that displays the contents of register X. A 16-
bit code word is used to load a word in X, either from
S or from R. S is a 1024-word memory segment and
R is a 32-word register file. Based on the value of
mode bit M, T selects an input word to load in X. P
and Q interface with the corresponding bits in the
code word to choose the addressed word. Which one
of the following represents the functionality of P, Q,
and T?

DIGITAL LOGIC

If there are m input lines and n output lines for a
decoder that is used to uniquely address a byte
addressable 1 KB RAM, then the minimum value of
m + n is ____.

In the following truth table, V = 1 if and only if the
input is valid. In the following truth table,    V = 1 if
and only if the input is valid.

Inputs
D0
D1
D2
D3
0
0
0
0
1
0
0
0
x
1
0
0
x
x
1
0
x
x
x
1

Output
X0
X1
V
x
x
0
0
0
1
0
1
1
1
0
1
1
1
1

What function does the truth table represent?

Let k = 2n. A circuit is built by giving the output of
an n-bit binary counter as input to an n-to-2n bit
decoder. This circuit is equivalent to a ?

Self-check

Revision card

References