Chapter 17 of 32

Decoders & Encoders

Every key you press on a keyboard has to be turned into a short binary code, and every binary address the processor sends out has to wake up exactly one memory chip. These two jobs are mirror images of each other. A decoder turns an n-bit code into "one line out of 2n is active". An encoder does the reverse: it looks at which one of many lines is active and produces its binary code.

A decoder is a combinational circuit with n inputs and up to 2n outputs, in which each input combination activates exactly one output. An encoder has 2n (or fewer) inputs, of which one is active, and n outputs giving the binary number of the active input.

In Demultiplexers we already met a decoder in disguise. In this chapter we study decoders properly (enable inputs, active-low outputs, expansion, implementing functions, the BCD-to-seven-segment decoder), then encoders and the far more useful priority encoder.


The Decoder

2-to-4 Decoder

A1

A0

D3

D2

D1

D0

0

0

0

0

0

1

0

1

0

0

1

0

1

0

0

1

0

0

1

1

1

0

0

0

D0 = A1′A0′    D1 = A1′A0    D2 = A1A0′    D3 = A1A0

Each output is one minterm of the inputs (see Canonical Forms: SOP & POS). This is the single most important fact about decoders:

Output Di of an n-to-2n decoder is the minterm mi of its n inputs.

An n-to-2n decoder built directly needs n NOT gates and 2n AND gates with n inputs each. A 3-to-8 decoder: 3 NOT + 8 three-input AND. A 4-to-16 decoder: 4 NOT + 16 four-input AND. A BCD-to-decimal decoder is a "4-to-10" decoder: it only uses the first ten minterms.

Enable Input

Most decoders have an enable E. When E = 0 all outputs are inactive; when E = 1 the decoder works normally. Each AND gate just gets one more input: Di = mi·E. As we saw in Demultiplexers, if you feed data into E, the decoder becomes a demultiplexer.

Active-Low Outputs and Enables

Commercial decoders are usually built with NAND gates, so the selected output goes to 0 and all others stay at 1. We call such outputs active-low and write them with a bar or prime: Di′ = (mi·E)′. Why low? Historically TTL gates could sink current (pull a line low) much better than source it, and a chip-select pin on a memory is normally active-low too, so the decoder output can drive it directly.

The 74HC138 / 74LS138 3-to-8 decoder is the textbook example:

  • Address inputs A2 A1 A0 (A0 least significant).

  • Three enables: G1 (active-high), G2A′ and G2B′ (both active-low). The chip is enabled only when G1 = 1, G2A′ = 0 and G2B′ = 0.

  • Outputs Y0′ ... Y7′, active-low: when enabled, the addressed output is 0 and the rest are 1; when disabled, all are 1.

Having enables of both polarities is a gift for expansion, as we will see next.


Building Larger Decoders

3-to-8 from Two 2-to-4 Decoders

               A1 A0 (to both)
                  │
  A2 ──>[NOT]──> E  [2-to-4 #1] ──> D0 D1 D2 D3     (active when A2 = 0)
  A2 ───────────> E  [2-to-4 #2] ──> D4 D5 D6 D7     (active when A2 = 1)

The most significant input picks which decoder is enabled; the lower bits pick the output inside it.

4-to-16 from Two 74138s (No Extra Gates)

Feed A2A1A0 to both chips. Connect A3 to G2A′ of chip 1 (so it is enabled when A3 = 0) and to G1 of chip 2 (enabled when A3 = 1). Tie the unused enables to their active levels. Chip 1 now produces outputs 0 to 7 and chip 2 produces 8 to 15, and no inverter is needed because the two enables have opposite polarities.

4-to-16 from 2-to-4 Decoders

Four 2-to-4 decoders driven by A1A0 produce the 16 outputs, and a fifth 2-to-4 decoder driven by A3A2 enables one of them. Total 5. In general you count level by level from the output side, just like the trees in Multiplexers and Demultiplexers.

Target

Built from

Count

4-to-16

3-to-8 with enable

2 (plus one inverter, or none with a 74138)

4-to-16

2-to-4 with enable

4 + 1 = 5

5-to-32

3-to-8 with enable

4 + one 2-to-4 to enable them

6-to-64

3-to-8 with enable

8 + 1 = 9

This is exactly how memory address decoding works: the high address bits go through a decoder whose outputs drive the chip-select pins of the memory chips, while the low address bits go to every chip and select a word inside it.


Implementing Functions with a Decoder

Because a decoder outputs every minterm, any function written as Σm is an OR of the right outputs.

Example 1: Full Adder with a 3-to-8 Decoder

Connect A, B, Cin to A2, A1, A0. From Half & Full Adders:

S    = Σm(1, 2, 4, 7)   →  S    = D1 + D2 + D4 + D7
Cout = Σm(3, 5, 6, 7)   →  Cout = D3 + D5 + D6 + D7

Hardware: one 3-to-8 decoder + two 4-input OR gates

Three practical rules:

  • Active-low outputs → use NAND. With a 74138, S = (D1′·D2′·D4′·D7′)′, a 4-input NAND.

  • Many 1s → use the complement. If F has 6 minterms out of 8, F′ has only 2, so take F = NOR of the two outputs of F′ (with active-high outputs) to save gate inputs.

  • One decoder, many functions. All outputs share the same decoder, so a decoder is attractive when several functions of the same inputs are needed (as with S and Cout).


BCD-to-Seven-Segment Decoder

The digits on a calculator, a microwave or a lift display are drawn with seven LED segments named a to g:

     ─a─
    f   b
     ─g─
    e   c
     ─d─

A BCD-to-seven-segment decoder takes a BCD digit ABCD (A is the 8s bit) and produces seven outputs, one per segment. Strictly it is a code converter (it has 7 outputs, not 10), but it is traditionally called a decoder. Inputs 1010 to 1111 never occur in BCD, so they are don't-cares (see K-Maps with Don't-Care Conditions). In this table 1 means "segment on", and 6 and 9 are drawn with their tails (segment a on for 6, segment d on for 9):

Digit

A B C D

a

b

c

d

e

f

g

0

0 0 0 0

1

1

1

1

1

1

0

1

0 0 0 1

0

1

1

0

0

0

0

2

0 0 1 0

1

1

0

1

1

0

1

3

0 0 1 1

1

1

1

1

0

0

1

4

0 1 0 0

0

1

1

0

0

1

1

5

0 1 0 1

1

0

1

1

0

1

1

6

0 1 1 0

1

0

1

1

1

1

1

7

0 1 1 1

1

1

1

0

0

0

0

8

1 0 0 0

1

1

1

1

1

1

1

9

1 0 0 1

1

1

1

1

0

1

1

10-15

1010-1111

x

x

x

x

x

x

x

Minimising each column with a 4-variable K-map using the don't-cares gives (one minimal form each; some segments have more than one equally small answer):

a = A + C + BD + B′D′
b = B′ + CD + C′D′
c = B + C′ + D
d = A + B′D′ + B′C + CD′ + BC′D
e = B′D′ + CD′
f = A + C′D′ + BC′ + BD′
g = A + B′C + BC′ + CD′

Check one: digit 4 = 0100 (A = 0, B = 1, C = 0, D = 0). Segment e = B′D′ + CD′ = 0 + 0 = 0, so e is off; segment f = C′D′ = 1, so f is on. Looking at a "4", the lower-left segment e is indeed off and the upper-left f is on.

Two practical points. First, displays come as common-cathode (a segment lights when driven HIGH) or common-anode (lights when driven LOW). The 7447 / 74LS47 decoder-driver has active-low outputs for common-anode displays; the 7448 / 74LS48 has active-high outputs. Second, fonts differ: the 7447 family draws 6 and 9 without tails (segment a off for 6, segment d off for 9), while the 74247 family draws them with tails. Always state your font in an exam answer, because it changes the a and d equations.


The Encoder

An encoder assumes exactly one input is active and outputs its index in binary.

4-to-2 Encoder

Active input

Y1

Y0

D0

0

0

D1

0

1

D2

1

0

D3

1

1

Y1 = D2 + D3        Y0 = D1 + D3

The rule: output bit k is the OR of all inputs whose index has bit k = 1. Notice D0 does not appear at all.

8-to-3 (Octal-to-Binary) and Decimal-to-BCD Encoders

8-to-3:            Y2 = D4 + D5 + D6 + D7
                   Y1 = D2 + D3 + D6 + D7
                   Y0 = D1 + D3 + D5 + D7

Decimal-to-BCD:    Y3 = D8 + D9
(10-to-4)          Y2 = D4 + D5 + D6 + D7
                   Y1 = D2 + D3 + D6 + D7
                   Y0 = D1 + D3 + D5 + D7 + D9

An 8-to-3 encoder is just three 4-input OR gates. That simplicity hides two serious problems:

  1. Two inputs active at once. If D3 and D5 are both 1, then Y = 011 OR 101 = 111, which claims D7 is active. Garbage.

  2. No input active. The output is 000, which is indistinguishable from "D0 is active".


The Priority Encoder

A priority encoder outputs the index of the highest-priority active input (usually the highest-numbered one) and has an extra valid output V that is 1 when at least one input is active.

4-to-2 Priority Encoder (D3 Highest)

D3

D2

D1

D0

Y1

Y0

V

0

0

0

0

x

x

0

0

0

0

1

0

0

1

0

0

1

x

0

1

1

0

1

x

x

1

0

1

1

x

x

x

1

1

1

An x in an input column means "0 or 1, it does not matter", so this 5-row table stands for all 16 input combinations. The x in the first row's outputs is a true don't-care: when V = 0 nobody looks at Y.

Deriving the Equations with K-Maps

Put D3D2 on the rows and D1D0 on the columns (Gray order):

Y1:                 D1D0               Y0:                 D1D0
           00   01   11   10                      00   01   11   10
D3D2 00 |  x    0    0    0                 00 |  x    0    1    1
     01 |  1    1    1    1                 01 |  0    0    0    0
     11 |  1    1    1    1                 11 |  1    1    1    1
     10 |  1    1    1    1                 10 |  1    1    1    1

Y1: one octet (rows 01, 11) → D2, one octet (rows 11, 10) → D3
    Y1 = D3 + D2

Y0: octet (rows 11, 10) → D3; quad (row 00 cols 11, 10 + row 10 cols 11, 10) → D2′D1
    Y0 = D3 + D2′D1

V  = D3 + D2 + D1 + D0

Read Y0 = D3 + D2′D1 in words: "the answer is odd (3 or 1) if D3 is active, or if D1 is active and the higher D2 is not there to override it." The D2′ factor is the priority logic.

8-to-3 Priority Encoder

The same reasoning (a higher input blocks lower ones only when it would change that output bit) gives:

Y2 = D7 + D6 + D5 + D4
Y1 = D7 + D6 + D5′D4′D3 + D5′D4′D2
Y0 = D7 + D6′D5 + D6′D4′D3 + D6′D4′D2′D1
V  = D7 + D6 + D5 + D4 + D3 + D2 + D1 + D0

These were checked against "index of the highest 1" for all 255 non-zero inputs. Example: D = 0100 1111 (D6, D3, D2, D1, D0 active). Y2 = 1 (D6), Y1 = 1 (D6), Y0: D7 = 0, and every other term contains D6′ = 0, so Y0 = 0. Output 110 = 6. Correct.

In the chip world, the 74148 is an 8-to-3 priority encoder with active-low inputs and outputs, an enable input EI′, a "group select" output GS′ (low when the chip is enabled and some input is active, playing the role of V) and an enable output EO′ (low when the chip is enabled but no input is active), which lets two chips be cascaded into a 16-to-4 priority encoder. The 74147 is a 10-to-4 (decimal-to-BCD) priority encoder, the circuit behind simple keypads.

Where Priority Encoders Are Used

  • Interrupt controllers: several devices request service; the encoder reports the most urgent one.

  • Keyboards and keypads: if two keys are pressed, one well-defined code still comes out.

  • Leading-one detection in floating-point normalisation and in "count leading zeros" instructions.

  • Bus arbitration: granting a shared bus to the highest-priority requester.


Verilog Model

A behavioural 3-to-8 decoder and an 8-to-3 priority encoder. The casez statement with ? wildcards is a direct copy of the priority table: the first matching line wins.

// 3-to-8 decoder with active-high enable
module decoder3to8 (input logic en, input logic [2:0] a, output logic [7:0] y);
  assign y = en ? (8'b0000_0001 << a) : 8'b0000_0000;
endmodule

// 8-to-3 priority encoder: highest-numbered active input wins
module prio_enc8to3 (input logic [7:0] d, output logic [2:0] y, output logic v);
  always_comb begin
    v = |d;
    casez (d)
      8'b1???????: y = 3'd7;
      8'b01??????: y = 3'd6;
      8'b001?????: y = 3'd5;
      8'b0001????: y = 3'd4;
      8'b00001???: y = 3'd3;
      8'b000001??: y = 3'd2;
      8'b0000001?: y = 3'd1;
      default:     y = 3'd0;
    endcase
  end
endmodule

module tb;
  logic en; logic [2:0] a; logic [7:0] y;
  logic [7:0] d; logic [2:0] code; logic v;
  decoder3to8  dec (.en(en), .a(a), .y(y));
  prio_enc8to3 enc (.d(d), .y(code), .v(v));
  initial begin
    $display("Decoder:  EN A   | Y7..Y0");
    en = 0; a = 3'd5; #1 $display("          %b  %b | %b", en, a, y);
    en = 1;
    for (int i = 0; i < 8; i++) begin
      a = i[2:0]; #1 $display("          %b  %b | %b", en, a, y);
    end
    $display("Priority encoder:  D7..D0   | Y   V");
    show(8'b0000_0000);
    show(8'b0000_0001);
    show(8'b0001_0100);
    show(8'b0100_1111);
    show(8'b1000_0001);
  end
  task show(input logic [7:0] val);
    d = val; #1 $display("                   %b | %b %b", d, code, v);
  endtask
endmodule

Output (iverilog -g2012, vvp):

Decoder:  EN A   | Y7..Y0
          0  101 | 00000000
          1  000 | 00000001
          1  001 | 00000010
          1  010 | 00000100
          1  011 | 00001000
          1  100 | 00010000
          1  101 | 00100000
          1  110 | 01000000
          1  111 | 10000000
Priority encoder:  D7..D0   | Y   V
                   00000000 | 000 0
                   00000001 | 000 1
                   00010100 | 100 1
                   01001111 | 110 1
                   10000001 | 111 1

Look at the first two encoder lines: input 0000 0000 and input 0000 0001 both give Y = 000, and only V tells them apart. That is exactly why the valid bit exists.


Decoder vs Encoder at a Glance

Point

Decoder

Encoder

Priority encoder

Inputs → outputs

n → 2n

2n → n

2n → n + V

Assumption on inputs

Any combination

Exactly one active

Any combination

Each output is

A minterm (AND)

An OR of inputs

OR of AND terms with priority factors

Typical chip

74138, 74139, 7447

-

74148, 74147

Typical use

Address and instruction decoding, displays

Simple switch encoding

Interrupts, keypads, leading-one detection


Common Mistakes

  • Using OR gates with active-low decoder outputs. Use NAND gates (De Morgan).

  • Forgetting the extra decoder that drives the enables when expanding: 4-to-16 from 2-to-4 needs 5, not 4.

  • Including D0 in an encoder's equations. Index 0 has no 1 bits, so D0 appears in none of them (only in V).

  • Assuming an ordinary encoder handles two active inputs. It ORs their codes; use a priority encoder.

  • Forgetting the valid output, so "no input" and "input 0" look the same.

  • Ignoring the 6 and 9 font in seven-segment questions, or ignoring the don't-cares 10 to 15, which give much smaller equations.


Interview and GATE Questions

Q1. How many 3-to-8 decoders with enable are needed to build a 6-to-64 decoder?

Eight decoders driven by the low three bits produce the 64 outputs; one more, driven by the high three bits, enables one of the eight. Total 9.

Q2. Implement F(A, B, C) = Σm(0, 1, 2, 4, 5, 6) with a 3-to-8 decoder and the fewest gate inputs.

F has six minterms, F′ = Σm(3, 7) has two. Take F = (D3 + D7)′, a single 2-input NOR on the decoder outputs. (Algebraically F = (BC)′ = B′ + C′, which confirms the answer.)

Q3. An 8-to-3 priority encoder (D7 highest) receives D7...D0 = 0010 1100. What are Y and V?

The highest active input is D5, so Y = 101 and V = 1.

Q4. An ordinary (non-priority) 8-to-3 encoder receives D2 = D4 = 1. What does it output?

010 OR 100 = 110, i.e. it wrongly reports input 6.

Q5. Derive Y0 of a 4-to-2 priority encoder with D3 highest.

Y0 = 1 when the winner is 3 or 1. Winner 3: D3. Winner 1: D3′D2′D1. So Y0 = D3 + D3′D2′D1 = D3 + D2′D1 (absorption: X + X′Y = X + Y).

Q6. How many AND gates, and of what fan-in, does a 4-to-16 decoder with enable need?

16 AND gates with 5 inputs each (4 address literals + enable), plus 4 inverters.

Q7. In a seven-segment decoder, why are inputs 1010 to 1111 treated as don't-cares?

A BCD digit is only 0 to 9, so those codes never occur. Marking them x lets the K-map form larger groups, for example segment c becomes just B + C′ + D.


Summary

  • An n-to-2n decoder outputs all minterms; output i is mi. With an enable it doubles as a demultiplexer.

  • Commercial decoders (74138) have active-low outputs and several enables; combine their outputs with NAND gates.

  • Large decoders are built hierarchically; the high address bits choose which small decoder is enabled.

  • Decoder + OR gates implements any set of functions in Σm form.

  • The BCD-to-seven-segment decoder uses don't-cares 10 to 15; mind the display type and the 6/9 font.

  • An encoder ORs inputs into a binary index but fails with zero or multiple active inputs.

  • A priority encoder outputs the highest active index plus a valid bit; 4-to-2: Y1 = D3 + D2, Y0 = D3 + D2′D1.

  • Next, Magnitude Comparators builds circuits that decide whether A > B, A = B or A < B.