The following table shows some of the many ways in which decimal digits have been represented on computers. As can be seen, quite a variety of representations have been used.

At the present time, virtually the only method for directly representing single decimal digits in binary form which is still in use is the Natural Binary Coded Decimal, or 8421, code which is the first one described in the table below.

Later, we will encounter ways of representing groups of two or three decimal
digits in seven or ten binary bits respectively, of the general form known as
*Chen-Ho encoding*, which allows the efficiency of decimal data storage to
rival that of binary.

Natural Reflected LARC Binary Binary Coded Excess-3 2 out Bi-quinary Reversed Excess-11 Decimal Modified of 5 Bi-quinary * __ __ Gray 8421 2421 8421 5421 6321 Code 50 43210 86420 1 0 0000 0011 0000 0000 0000 0000/0111 0000 00011 01 00001 0000 00001 0 01011 1 0001 0100 0001 0111 0001 0110 0001 00101 01 00010 0001 00001 1 01100 2 0010 0101 0010 0110 0010 0101 0011 00110 01 00100 0011 00010 0 01101 3 0011 0110 0011 0101 0011 0100/1011 0010 01001 01 01000 0111 00010 1 01110 4 0100 0111 0100 0100 0100 1010 0110 01010 01 10000 0110 00100 0 01111 5 0101 1000 1011 1011 1000 1001 1110 01100 10 00001 1000 00100 1 10000 6 0110 1001 1100 1010 1001 1000/1111 1010 10001 10 00010 1001 01000 0 10001 7 0111 1010 1101 1001 1010 1110 1011 10010 10 00100 1011 01000 1 10010 8 1000 1011 1110 1000 1011 1101 1001 10100 10 01000 1111 10000 0 10011 9 1001 1100 1111 1111 1100 1100 1000 11000 10 10000 1110 10000 1 10100

The Excess-3 code has the property that one can add two decimal numbers using a binary adder, and then correct each digit position individually based on whether or not there has been a carry out of that digit position. This means that a little extra hardware, to latch carries out of every four-bit expanse within a binary number, is still needed, of course. When there was no carry, the digit is now in an excess-6 form, and thus three must be subtracted from it; when there was a carry, since the carry represented, in binary, the value 16 rather than 10, the digit is now in natural BCD form, and so three must be added to produce an excess-3 result.

As it happens, 10 + 11 + 11 equals 32. If we represent each decimal digit by five binary bits in excess-11 code, then all we need is to chop the sum into five-bit groups and add them together, since there is no overlap between the values 0 to 9 and the values 22 to 31, unlike the values from 0 to 9 and the values from 6 to 15. So excess-11 code lends itself to a software-only implementation of decimal arithmetic. Since some architectures can handle the translation of eight-bit characters more easily than five-bit characters, one could also represent a decimal digit by eight binary bits in excess-123 code.

The bi-quinary code denotes numerical value by bit position, and is not unlike how numbers are represented on an abacus, particularly if one thinks of the 0 bits instead of the 1 bits as the beads. Representing a value by the position of a single bit in a string of ten bits is also possible, and the ENIAC is a computer that represented decimal digits in this fashion. The punched card code also used that principle as well.

The 2* 4 2 1 and 8 4 -2 -1 codes have the property that, if all the digits from 0 to 9 are equal in frequency, then the bits 0 and 1 will be equal in frequency. Of course, if balance is highly important, one could alternate between 2 of 5 code and complemented 2 of 5 code; the result would also be self-clocking. A decimal computer might store decimal numbers in that way on disk, in Chen-Ho encoding or Densely Packed Decimal in main memory, and in packed BCD in cache, so that 6 digits would occupy 30 bit positions on disk, 20 bits in main memory, and 24 bits in cache.

A 1977 paper by C. K. Yuen described a code which used a mix of negative and positive radixes that could only represent digits up to 9, thus simplifying generating the carry from decimal addition. While such a code could represent digits below zero, which are also invalid, they will not result from adding two decimal digits.

I haven't yet seen his paper, but one column in the table above depicts a 6 3 -2 -1 code, which may have the desirable properties sought by this means.

6 is twice 3, and -2 is twice -1, so these parts of the code can be added by two-bit binary adders. A carry out of the last two bits would need to be handled by some extra circuits to decrement the first two digits, and put the appropriate value in the last two.

That would lead to the second of the two codes for 0, 3, and 6 shown in the column for that code above. The first code for 0 clearly is to be preferred, since it wouldn't change anything as input to the two two-bit adders, but presumably the logic for a carry at what would otherwise be the 10 to 11 transition is also simpler than the usual decimal carry logic.

The Gray Code, as shown here, in order to retain the property
that makes the conventional Gray Code for binary numbers useful for
shaft encoders, uses combinations that correspond to the binary
values in the 2*421 code. When a shaft encoder is used to read
a multi-digit number, a reflected *decimal* code has to be
applied to the number as a whole so that there is only one
transition between each adjacent pair of positions.

Chen-Ho encoding, an ingenious scheme of encoding three decimal digits (1000 possible values) in ten binary bits (1024 possible values) without peforming a conventional radix conversion, which would require multiplications, is now dealt with in the following page.

- Chen-Ho Encoding and Densely Packed Decimal
- The Proposed Decimal Floating Point Standard
- Quasilogarithmic Floating Point

[Next] [Up] [Previous]