Chapter 19 of 32

Code Converters

In Number Systems & Binary Codes we met several ways of writing the same number in bits: plain binary, Gray code, BCD, Excess-3. Each exists for a reason. Gray code stops a rotating shaft encoder from giving wild readings, BCD keeps decimal digits separate for displays and calculators, and Excess-3 made decimal subtraction easy in early machines. Different parts of a system often use different codes, so we need circuits that translate between them.

A code converter is a combinational circuit that takes a value represented in one binary code and outputs the same value represented in another code.

A code converter is designed like any other combinational circuit (see Combinational Circuit Design), with one extra opportunity: input codes that can never occur become don't-cares, which often shrink the logic dramatically. In this chapter we design binary ↔ Gray, BCD ↔ Excess-3 and binary → BCD converters.


The Design Procedure

  1. List every valid input code and the output code it should produce (the truth table).

  2. Mark input combinations that can never occur as don't-cares (x) for every output.

  3. Minimise each output bit separately with a K-map, using the don't-cares where they help.

  4. Look for shared sub-expressions between outputs and for XOR patterns, then draw the circuit.


Binary to Gray Code

In Gray code, consecutive values differ in exactly one bit. The conversion rule is short:

The MSB is copied: G3 = B3. Every other Gray bit is the XOR of the binary bit and the binary bit to its left: Gi = Bi+1 ⊕ Bi.

G3 = B3
G2 = B3 ⊕ B2
G1 = B2 ⊕ B1
G0 = B1 ⊕ B0

Why XOR? Plot G2 on a K-map with B3B2 on the rows: the rows 01 and 10 are all 1s and the rows 00 and 11 are all 0s. That pattern is B3′B2 + B3B2′ = B3 ⊕ B2, and the other two variables drop out completely. An n-bit converter needs only n − 1 XOR gates, all working in parallel, so the delay is one XOR gate whatever the width.

Example 1: Convert Binary 1011 to Gray

Binary:   B3=1   B2=0   B1=1   B0=1

G3 = B3       = 1
G2 = B3 ⊕ B2  = 1 ⊕ 0 = 1
G1 = B2 ⊕ B1  = 0 ⊕ 1 = 1
G0 = B1 ⊕ B0  = 1 ⊕ 1 = 0

Binary 1011 (11) → Gray 1110

Gray to Binary Code

Going back, each binary bit depends on the binary bit just computed to its left:

B3 = G3
B2 = B3 ⊕ G2 = G3 ⊕ G2
B1 = B2 ⊕ G1 = G3 ⊕ G2 ⊕ G1
B0 = B1 ⊕ G0 = G3 ⊕ G2 ⊕ G1 ⊕ G0

In words: each binary bit is the XOR of all Gray bits from the MSB down to that position, i.e. the parity of those Gray bits (a link we will use again in Parity Generators & Checkers). Built as a chain, it uses n − 1 XOR gates but the delay grows to n − 1 XOR delays, because B0 waits for B1, which waits for B2. If speed matters, each Bi can get its own XOR tree, using more gates.

Example 2: Convert Gray 1110 back to Binary

B3 = G3       = 1
B2 = B3 ⊕ G2  = 1 ⊕ 1 = 0
B1 = B2 ⊕ G1  = 0 ⊕ 1 = 1
B0 = B1 ⊕ G0  = 1 ⊕ 0 = 1

Gray 1110 → Binary 1011   (we got back the number from Example 1 ✓)

Verilog: Round Trip Binary → Gray → Binary

module bin2gray (input logic [3:0] b, output logic [3:0] g);
  assign g = b ^ (b >> 1);             // g3=b3, gi = b(i+1) ^ bi
endmodule

module gray2bin (input logic [3:0] g, output logic [3:0] b);
  assign b[3] = g[3];
  assign b[2] = b[3] ^ g[2];
  assign b[1] = b[2] ^ g[1];
  assign b[0] = b[1] ^ g[0];
endmodule

module tb;
  logic [3:0] bin, gray, back;
  bin2gray u1 (.b(bin), .g(gray));
  gray2bin u2 (.g(gray), .b(back));
  initial begin
    $display("Dec  Binary  Gray  Back");
    for (int i = 0; i < 16; i++) begin
      bin = i[3:0]; #1
      $display("%3d  %b    %b  %b", bin, bin, gray, back);
    end
  end
endmodule

Output (iverilog -g2012, vvp):

Dec  Binary  Gray  Back
  0  0000    0000  0000
  1  0001    0001  0001
  2  0010    0011  0010
  3  0011    0010  0011
  4  0100    0110  0100
  5  0101    0111  0101
  6  0110    0101  0110
  7  0111    0100  0111
  8  1000    1100  1000
  9  1001    1101  1001
 10  1010    1111  1010
 11  1011    1110  1011
 12  1100    1010  1100
 13  1101    1011  1101
 14  1110    1001  1110
 15  1111    1000  1111

Two things to notice: in the Gray column every line differs from the next in exactly one bit (including 15 → 0: 1000 → 0000), and the "Back" column always equals the binary input, so the two converters are exact inverses. The neat one-liner b ^ (b >> 1) is the same formula Gi = Bi+1 ⊕ Bi applied to all bits at once.


BCD to Excess-3

Excess-3 (XS-3) represents a decimal digit d as the 4-bit binary value of d + 3. It is self-complementing: the 9's complement of a digit is obtained by inverting all four bits (for example 2 = 0101, 7 = 1010).

Inputs A B C D (BCD, A = 8s bit), outputs W X Y Z (Excess-3):

Decimal

BCD: A B C D

Excess-3: W X Y Z

0

0 0 0 0

0 0 1 1

1

0 0 0 1

0 1 0 0

2

0 0 1 0

0 1 0 1

3

0 0 1 1

0 1 1 0

4

0 1 0 0

0 1 1 1

5

0 1 0 1

1 0 0 0

6

0 1 1 0

1 0 0 1

7

0 1 1 1

1 0 1 0

8

1 0 0 0

1 0 1 1

9

1 0 0 1

1 1 0 0

-

1010 to 1111

x x x x (don't care)

Only 10 of the 16 input combinations are valid, so six rows (10 to 15) are don't-cares. Without them the logic would be noticeably bigger.

K-Maps

X = Σm(1, 2, 3, 4, 9) + d(10..15)          W = Σm(5, 6, 7, 8, 9) + d(10..15)

                CD                                        CD
           00   01   11   10                         00   01   11   10
AB  00  |  0    1    1    1               AB  00  |  0    0    0    0
    01  |  1    0    0    0                   01  |  0    1    1    1
    11  |  x    x    x    x                   11  |  x    x    x    x
    10  |  0    1    x    x                   10  |  1    1    x    x

X: B′C  (rows 00,10 × cols 11,10)          W: A   (rows 11,10, octet)
   B′D  (rows 00,10 × cols 01,11)             BC  (rows 01,11 × cols 11,10)
   BC′D′ (rows 01,11 × col 00)                BD  (rows 01,11 × cols 01,11)

Doing the same for Y and Z gives the complete converter:

W = A + BC + BD        = A + B(C + D)
X = B′C + B′D + BC′D′  = B ⊕ (C + D)
Y = CD + C′D′          = (C ⊕ D)′
Z = D′

The factored forms on the right are what you actually build: the term (C + D) is computed once and shared by W and X. The whole converter is one OR gate, one AND gate, one more OR gate (for W), one XOR (for X), one XNOR (for Y) and one inverter (for Z). The factored forms agree with the SOPs on all ten valid inputs (they may differ on the don't-care inputs, which is allowed).

Example 3: BCD 0111 (7)

A=0 B=1 C=1 D=1      C + D = 1
W = 0 + 1·1 = 1
X = 1 ⊕ 1  = 0
Y = (1 ⊕ 1)′ = 1
Z = 1′ = 0
Output WXYZ = 1010 = 10 = 7 + 3 ✓

Excess-3 to BCD

Now the inputs are W X Y Z and the valid codes are 0011 to 1100 (3 to 12), so the don't-cares are 0, 1, 2, 13, 14 and 15. Minimising each output:

A = WX + WYZ
B = X′Y′ + X′Z′ + XYZ
C = Y ⊕ Z
D = Z′

Check with XS-3 1100 (decimal 9): W=1, X=1, Y=0, Z=0. A = 1·1 = 1; B = 0 + 0 + 0 = 0; C = 0 ⊕ 0 = 0; D = 1. Output 1001 = 9 ✓.

Notice that the least significant two bits are the same in both directions: the bottom bit is always inverted (adding or subtracting 3, an odd number, flips the parity), and bit 1 is an XOR or XNOR of the two lowest input bits.


Binary to BCD

A 4-bit binary number (0 to 15) needs two BCD digits: a tens digit that is either 0 or 1, and a units digit. Call the binary input A B C D (A = 8s bit) and the outputs T (tens) and U3U2U1U0 (units). All 16 inputs are valid, so there are no don't-cares here.

T  = AB + AC         (value ≥ 10: 8 plus 2 or 4)
U3 = AB′C′           (value is 8 or 9)
U2 = A′B + BC
U1 = A′C + ABC′
U0 = D               (subtracting 10, an even number, never changes the last bit)

Check with 1101 (13): T = 1·1 = 1; U3 = 0; U2 = 0 + 1·0 = 0; U1 = 0 + 1·1·1 = 1; U0 = 1. Output 1 | 0011, i.e. "1" "3" ✓.

For wider numbers a single K-map is hopeless, so designers use the double-dabble (shift-and-add-3) algorithm: shift the binary number left into a BCD register one bit at a time, and before each shift add 3 to every BCD digit that is 5 or more. Adding 3 before the doubling is the same as adding 6 after it, which is the familiar "+6" correction used in BCD arithmetic.


Other Common Converters

Converter

Key idea

Where covered

Binary → Gray

Gi = Bi+1 ⊕ Bi, n − 1 parallel XORs

This chapter

Gray → Binary

Bi = Bi+1 ⊕ Gi, XOR chain

This chapter

BCD ↔ Excess-3

Add or subtract 3; don't-cares for unused codes

This chapter

Binary → BCD

Subtract 10 when ≥ 10; double-dabble for wide inputs

This chapter

BCD → seven-segment

7 outputs, don't-cares 10 to 15

Decoders & Encoders

Any code → any code (many bits)

Store the table in a ROM: address = input code, data = output code

Later, in Memory & Programmable Logic Devices (ROM, PLA, PAL)


Common Mistakes

  • Gray → binary using Gi+1 ⊕ Gi. That is the binary → Gray formula. Going back you must use the binary bit already computed: Bi = Bi+1 ⊕ Gi.

  • Ignoring don't-cares in BCD-based converters. You get a correct but much bigger circuit, and lose marks for "minimal".

  • Using the wrong don't-care set for Excess-3 → BCD. The invalid inputs are 0000, 0001, 0010, 1101, 1110, 1111, not 1010 to 1111.

  • Assuming the factored form equals the SOP everywhere. They only need to agree on valid inputs; on don't-care inputs they may differ.

  • Forgetting the MSB rule. In both directions the most significant bit is copied unchanged: Gn−1 = Bn−1.


Interview and GATE Questions

Q1. Convert binary 10110 to Gray code.

G4 = 1, G3 = 1 ⊕ 0 = 1, G2 = 0 ⊕ 1 = 1, G1 = 1 ⊕ 1 = 0, G0 = 1 ⊕ 0 = 1. Gray = 11101.

Q2. Convert Gray 0111 to binary.

B3 = 0, B2 = 0 ⊕ 1 = 1, B1 = 1 ⊕ 1 = 0, B0 = 0 ⊕ 1 = 1. Binary = 0101 (5).

Q3. How many XOR gates does an 8-bit binary-to-Gray converter need, and what is its delay?

7 XOR gates (n − 1), and all work in parallel, so the delay is one XOR gate delay.

Q4. In a BCD-to-Excess-3 converter, which input combinations are don't-cares, and what is the simplest expression for the LSB of the output?

Inputs 1010 to 1111 (10 to 15) are don't-cares. The output LSB is Z = D′.

Q5. Show that X = B′C + B′D + BC′D′ equals B ⊕ (C + D) for valid BCD inputs.

If B = 0: X = C + D, and B ⊕ (C + D) = C + D. If B = 1: X = C′D′ = (C + D)′ by De Morgan, and 1 ⊕ (C + D) = (C + D)′. Equal in both cases. (A is not involved at all.)

Q6. Why is Excess-3 called self-complementing?

The 9's complement of a digit d, i.e. 9 − d, has XS-3 code (9 − d) + 3 = 15 − (d + 3), which is the bitwise inverse of the XS-3 code of d (because 15 = 1111). So complementing the bits gives the 9's complement directly.

Q7. In a 4-bit binary-to-BCD converter, why is U0 = D?

The units digit is either the number itself (0 to 9) or the number minus 10 (10 to 15). Subtracting 10, an even number, does not change whether a number is odd, so the last bit passes straight through.


Summary

  • A code converter translates a value between codes; it is designed with a truth table and K-maps, using unused input codes as don't-cares.

  • Binary → Gray: Gn−1 = Bn−1, Gi = Bi+1 ⊕ Bi (n − 1 parallel XORs).

  • Gray → Binary: Bn−1 = Gn−1, Bi = Bi+1 ⊕ Gi (an XOR chain).

  • BCD → XS-3: W = A + B(C + D), X = B ⊕ (C + D), Y = (C ⊕ D)′, Z = D′.

  • XS-3 → BCD: A = WX + WYZ, B = X′Y′ + X′Z′ + XYZ, C = Y ⊕ Z, D = Z′ (don't-cares 0, 1, 2, 13, 14, 15).

  • Binary → BCD: small widths by K-map, wide numbers by double-dabble; large arbitrary converters go into a ROM.

  • Next, Parity Generators & Checkers uses the same XOR building block for error detection.