Excess-3 to BCD Converter
Excess-3 (XS-3) code was used in early decimal computers because it simplifies BCD subtraction: the 9's complement of any digit can be obtained simply by inverting all bits, eliminating the need for specialized complement hardware. IBM's early accounting machines and some telephone switching systems used XS-3 encoding. Converting between XS-3 and BCD is a practical code-conversion circuit that appears in digital design textbooks and interview questions at companies working with legacy number systems.
In Excess-3 code, each decimal digit d is represented as d + 3 in binary. For example, decimal 0 is 0011 in XS-3, decimal 5 is 1000, and decimal 9 is 1100. To convert XS-3 back to BCD (natural binary), subtract 3 (binary 0011) from the XS-3 code.
Your task is to take a 4-bit XS-3 input E = {E3, E2, E1, E0} and produce the corresponding 4-bit BCD output B = {B3, B2, B1, B0}. Valid XS-3 inputs range from 0011 (decimal 0) to 1100 (decimal 9). The output for each bit position is derived by computing E minus 0011 using half-adders and an inverter (subtracting 3 is equivalent to adding the 2's complement of 3, which is 1101, or equivalently: B = E + 1101 = E - 0011).
A clean implementation: B0 = NOT(E0). B1 = E1 XOR E0. B2 = E2 XOR (E1 AND E0). B3 = E3 XOR (E2 AND E1 AND E0) ... but this is complex. The simplest direct approach: subtract 3 in binary using a ripple-borrow subtractor. More elegantly: B = E + 13 (1101) mod 16, computed with two HAs and a NOT.
The direct derivation: since B = E + 13 (because E - 3 = E + 13 in 4-bit arithmetic), and 13 = 1101: B0 = E0 XOR 1 = NOT(E0). HA(E1, carry_from_b0) gives B1 and carry1. HA(E2, carry1) gives B2 and carry2. B3 = E3 XOR carry2.
| Signal | Direction | Width | Description | |--------|-----------|-------|-------------| | E3 | input | 1 | MSB of the XS-3 code | | E2 | input | 1 | Bit 2 of the XS-3 code | | E1 | input | 1 | Bit 1 of the XS-3 code | | E0 | input | 1 | LSB of the XS-3 code | | B3 | output | 1 | MSB of the BCD output | | B2 | output | 1 | Bit 2 of the BCD output | | B1 | output | 1 | Bit 1 of the BCD output | | B0 | output | 1 | LSB of the BCD output |
Constraints
- The circuit is purely combinational. No clock or state.
- Valid inputs are XS-3 codes 0011 through 1100 (representing BCD 0 through 9). Behavior for inputs 0000, 0001, 0010, 1101, 1110, 1111 is undefined — the circuit need not produce correct results for those inputs.
- The optimal solution uses 1 NOT, 2 HA, 1 XOR = 4 components (when implementing B = E + 1101 carry chain). Or equivalently 1 NOT + 2 HA + 1 XOR = 4 components.
- Output bit B0 is always NOT(E0) — the LSB of 13 (1101) is 1, so adding 1 to E0 simply inverts it with a carry.
Topics
Solve this problem
Place the gates, wire them up and watch the signals settle. Every submission runs on the same simulation engine that grades it.
This problem is part of Codiode Pro. The statement above is free to read.
The circuit builder and code editor need a desktop screen. On a phone, read the problem here and open it on a laptop to solve.