[Next] [Up] [Previous]

Decimal Representations

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.

If a computer only stored decimal digits, without any extra odd left-over bits to contain the sign of a number, would problems arise?

For integers, ten's complement encoding would allow numbers to range from -500..0 to +499...9, so no issue seems to arise.

But for floating-point numbers, ideally one would like the range of normalized mantissas (or significands, if you prefer) to be from .1000... to .9999... and not something else. One way to do that would be to require the last digit of the mantissa to be even, using the last bit instead to indicate the sign of the mantissa.

In 8421 encoding, the last bit is always 1 for odd numbers, so this is well suited to that case. But to have the sign bit for integers present as a single bit, one would want to use 5421 encoding instead.

It would certainly complicate multiplication circuitry to represent decimal numbers in alternating 5421/8421 notation, so that numbers with an even number of digits would always begin with a digit in 5421 representation and end with a digit in 8421 representation.

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.

[Next] [Up] [Previous]