Chen–Ho encoding

From Wikipedia, the free encyclopedia
  (Redirected from Chen-Ho encoding)
Jump to: navigation, search

Chen–Ho encoding is an alternate system of binary encoding for decimal digits.

The traditional system of binary encoding for decimal digits, known as Binary-coded decimal (BCD), uses four bits to encode each digit, resulting in significant wastage of binary data bandwidth (since four bits can store 16 states and are being used to store only 10).

The concepts behind Chen–Ho encoding were first introduced in a memo from Tien Chi Chen to Dr. Irving T. Ho in 1971. Both men were working for IBM at the time, although in different locations. Tien Chi Chen also consulted with Dr. Frank Tung to verify the results of his theories independently.

Tien Chi Chen noted that the digits zero through seven were simply encoded using three binary digits. He also postulated that one could use a flag to identify a different encoding for the digits eight and nine, which would be encoded using a single bit.

Application[edit]

In practice, a series of boolean transformations are applied to the stream of input bits, compressing BCD encoded digits from 12 bits per three digits to 10 bits per three digits. Reversed transformations are used to decode the resulting coded stream to BCD. Equivalent results can also be achieved by the use of a look-up table.

The final version of Chen–Ho encoding was published in 1975 in the journal Communications of the Association for Computing Machinery (CACM). This version included several refinements, primarily related to the application of the encoding system.

Chen–Ho encoding is limited to encoding of sets of three decimal digits. One prominent application uses a 128-bit register to store 33 decimal digits with a three digit exponent.

Chen-Ho decimal data encoding
Binary encoding Decimal digits
b9 b8 b7 b6 b5 b4 b3 b2 b1 b0 d2 d1 d0 Values encoded Description
0 a b c d e f g h i 0abc 0def 0ghi (0–7) (0–7) (0–7) Three small digits
1 0 0 c d e f g h i 100c 0def 0ghi (8–9) (0–7) (0–7) Two small digits,
one large
1 0 1 c a b f g h i 0abc 100f 0ghi (0–7) (8–9) (0–7)
1 1 0 c d e f a b i 0abc 0def 100i (0–7) (0–7) (8–9)
1 1 1 c 0 0 f a b i 0abc 100f 100i (0–7) (8–9) (8–9) One small digit,
two large
1 1 1 c 0 1 f d e i 100c 0def 100i (8–9) (0–7) (8–9)
1 1 1 c 1 0 f g h i 100c 100f 0ghi (8–9) (8–9) (0–7)
1 1 1 c 1 1 f 0 0 i 100c 100f 100i (8–9) (8–9) (8–9) Three large digits

Related Systems of Encoding[edit]

In 2002, Mike Cowlishaw published a further refinement of Chen–Ho encoding known as Densely Packed Decimal encoding in IEE Proceedings – Computers and Digital Techniques, which is summarized here. Densely Packed Decimal is the decimal encoding used in the IEEE 754 standard.

See also[edit]

References[edit]