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
List every valid input code and the output code it should produce (the truth table).
Mark input combinations that can never occur as don't-cares (x) for every output.
Minimise each output bit separately with a K-map, using the don't-cares where they help.
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.