Densely packed decimal
Densely packed decimal (DPD) is an efficient method for binary encoding 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), even when using packed BCD. Densely packed decimal is a more efficient code that packs three digits into ten bits using a scheme that allows compression from, or expansion to, BCD with only two or three hardware gate delays.[1]
The densely packed decimal encoding is a refinement of Chen–Ho encoding; it gives the same compression and speed advantages, but the particular arrangement of bits used confers additional advantages:
- Compression of one or two digits (into the optimal four or seven bits respectively) is achieved as a subset of the three-digit encoding. This means that arbitrary numbers of decimal digits (not only multiples of three digits) can be encoded efficiently. For example, 38 = 12 × 3 + 2 decimal digits can be encoded in 12 × 10 + 7 = 127 bits – that is, 12 sets of three decimal digits can be encoded using 12 sets of ten binary bits and the remaining two decimal digits can be encoded using a further seven binary bits.
- The subset encoding mentioned above is simply the rightmost bits of the standard three-digit encoding; the encoded value can be widened simply by adding leading 0 bits.
- All seven-bit BCD numbers (0 through 79) are encoded identically by DPD. This makes conversions of common small numbers trivial. (This must break down at 80, because that requires eight bits for BCD, but the above property requires that the DPD encoding must fit into seven bits.)
- The low-order bit of each digit is copied unmodified. Thus, the non-trivial portion of the encoding can be considered a conversion from three base-5 digits to seven binary bits. Further, digit-wise logical values (in which each digit is either 0 or 1) can be manipulated directly without any encoding or decoding being necessary.
History
In 1969, Theodore M. Hertz, and in 1971, Tien Chi Chen (陳天機) with Irving Tze Ho (何宜慈) devised lossless prefix codes (referred to as Hertz and Chen–Ho encodings[2]) which packed three decimal digits into ten binary bits using a scheme which allowed compression from or expansion to BCD with only two or three gate delays in hardware. Densely packed decimal is a refinement of this, devised by Mike F. Cowlishaw in 2002,[1] which was incorporated into the IEEE 754-2008[3] and ISO/IEC/IEEE 60559:2011[4] standards for decimal floating point.
Encoding
Like Chen–Ho encoding, DPD encoding classifies each decimal digit into one of two ranges, depending on the most significant bit of the binary form: "small" digits have values 0 through 7 (binary 0000–0111), and "large" digits, 8 through 9 (binary 1000–1001). Once it is known or has been indicated that a digit is small, three more bits are still required to specify the value. If a large value has been indicated, only one bit is required to distinguish between the values 8 or 9.
When encoding, the most significant bits of each of the three digits to be encoded determine one of eight coding patterns for the remaining bits, according to the following table. The table shows how, on decoding, the ten bits of the coded form in columns b9 through b0 are copied into the three digits d2 through d0, and the remaining bits are filled in with constant zeros or ones.
| DPD encoded value | Decimal digits | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Code space (1024 states) |
b9 | b8 | b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 | d2 | d1 | d0 | Values encoded | Description | Occurrences (1000 states) | |
| 50.0% (512 states) |
a | b | c | d | e | f | 0 | g | h | i | 0abc | 0def | 0ghi | (0–7) (0–7) (0–7) | 3 small digits | 51.2% (512 states) | |
| 37.5% (384 states) |
a | b | c | d | e | f | 1 | 0 | 0 | i | 0abc | 0def | 100i | (0–7) (0–7) (8–9) | 2 small digits, 1 large digit |
38.4% (384 states) | |
| a | b | c | g | h | f | 1 | 0 | 1 | i | 0abc | 100f | 0ghi | (0–7) (8–9) (0–7) | ||||
| g | h | c | d | e | f | 1 | 1 | 0 | i | 100c | 0def | 0ghi | (8–9) (0–7) (0–7) | ||||
| 9.375% (96 states) |
g | h | c | 0 | 0 | f | 1 | 1 | 1 | i | 100c | 100f | 0ghi | (8–9) (8–9) (0–7) | 1 small digit, 2 large digits |
9.6% (96 states) | |
| d | e | c | 0 | 1 | f | 1 | 1 | 1 | i | 100c | 0def | 100i | (8–9) (0–7) (8–9) | ||||
| a | b | c | 1 | 0 | f | 1 | 1 | 1 | i | 0abc | 100f | 100i | (0–7) (8–9) (8–9) | ||||
| 3.125% (32 states, 8 used) |
x | x | c | 1 | 1 | f | 1 | 1 | 1 | i | 100c | 100f | 100i | (8–9) (8–9) (8–9) | 3 large digits, b9, b8: don't care |
0.8% (8 states) | |
Bits b7, b4 and b0 (c, f and i) are passed through the encoding unchanged, and do not affect the meaning of the other bits. The remaining seven bits can be considered a seven-bit encoding for three base-5 digits.
Bits b8 and b9 are not needed and ignored when decoding DPD groups with three large digits (marked as "x" in the last row of the table above), but are filled with zeros when encoding.
The eight decimal values whose digits are all 8s or 9s have four codings each. The bits marked x in the table above are ignored on input, but will always be 0 in computed results. (The 3 × 8 = 24 non-standard encodings fill in the gap between 103 = 1000 and 210 − 1 = 1023.)
Examples
This table shows some representative decimal numbers and their encodings in BCD, Chen–Ho, and densely packed decimal (DPD):
| Decimal | BCD | Chen–Ho | DPD |
|---|---|---|---|
| 005 | 0000 0000 0101 | 000 000 0101 | 000 000 0101 |
| 009 | 0000 0000 1001 | 110 000 0001 | 000 000 1001 |
| 055 | 0000 0101 0101 | 000 010 1101 | 000 101 0101 |
| 079 | 0000 0111 1001 | 110 011 1001 | 000 111 1001 |
| 080 | 0000 1000 0000 | 101 000 0000 | 000 000 1010 |
| 099 | 0000 1001 1001 | 111 000 1001 | 000 101 1111 |
| 555 | 0101 0101 0101 | 010 110 1101 | 101 101 0101 |
| 999 | 1001 1001 1001 | 111 111 1001 | 001 111 1111 |
See also
References
- Cowlishaw, Michael Frederic (2002-08-07) [May 2002]. "Densely Packed Decimal Encoding". IEE Proceedings - Computers and Digital Techniques. London, UK: Institution of Electrical Engineers. 149 (3): 102–104. doi:10.1049/ip-cdt:20020407. ISSN 1350-2387. Retrieved 2016-02-07.
- Cowlishaw, Michael Frederic (2014) [June 2000]. "A Summary of Chen-Ho Decimal Data encoding". IBM. Archived from the original on 2015-09-24. Retrieved 2016-02-07.
- IEEE Computer Society (2008-08-29). IEEE Standard for Floating-Point Arithmetic. IEEE. doi:10.1109/IEEESTD.2008.4610935. ISBN 978-0-7381-5753-5. IEEE Std 754-2008. Retrieved 2016-02-08.
- ISO/IEC/IEEE 60559:2011. 2011. Archived from the original on 2020-06-03. Retrieved 2016-02-08.
- Cowlishaw, Michael Frederic (2007-02-13) [2000-10-03]. "A Summary of Densely Packed Decimal encoding". IBM. Archived from the original on 2015-09-24. Retrieved 2016-02-07.
Further reading
- Cowlishaw, Michael Frederic (2003-02-25) [2002-05-20, 2001-01-27]. Written at Coventry, UK. "Decimal to binary coder/decoder" (US Patent). Armonk, New York, USA: International Business Machines Corporation (IBM). US6525679B1. Retrieved 2018-07-18 and Cowlishaw, Michael Frederic (2007-11-07) [2004-01-14, 2002-08-14, 2001-09-24, 2001-01-27]. Written at Winchester, Hampshire, UK. "Decimal to binary coder/decoder" (European Patent). Armonk, New York, USA: International Business Machines Corporation (IBM). EP1231716A2. Retrieved 2018-07-18. (NB. This patent is about DPD.)
- Bonten, Jo H. M. (2009-10-06) [2006-10-05]. "Packed Decimal Encoding IEEE-754-2008". Geldrop, Netherlands. Archived from the original on 2018-07-11. Retrieved 2018-07-11. (NB. An older version can be found here: Packed Decimal Encoding IEEE-754r.)
- Savard, John J. G. (2018) [2007]. "Chen–Ho Encoding and Densely Packed Decimal". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.