Densely packed decimal

Densely packed decimal

Densely packed decimal (DPD) is a 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). Densely Packed Decimal is a more efficient code that packs three digits into 10 bits using a scheme that allows compression from, or expansion to, BCD with only two or three gate delays in hardware.[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 3-digit encoding. This means that arbitrary numbers of decimal digits (not just 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.
  • The subset encoding mentioned above is simply the rightmost bits of the standard 3-digit encoding; the encoded value can be widened simply by adding leading 0 bits.
  • All 7-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 8 bits for BCD, but the above property requires that the DPD encoding must fit into 7 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 3 base-5 digits to 7 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.

Contents

History

In 1971, Tien Chi Chen and Dr. Irving T. Ho devised a lossless prefix code (now known as Chen-Ho encoding) which packed three decimal digits into 10 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, by Mike Cowlishaw, which was incorporated into the IEEE 754-2008 standard 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 bit of each of the three digits to be encoded select one of 8 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.

Densely packed decimal encoding rules[2]
b9 b8 b7 b6 b5 b4 b3 b2 b1 b0 d2 d1 d0 Values encoded Digit pattern
a b c d e f 0 g h i 0abc 0def 0ghi (0–7) (0–7) (0–7) Three small digits
a b c d e f 1 0 0 i 0abc 0def 100i (0–7) (0–7) (8–9) Two small digits,
one large
a b c d e f 1 0 1 i 0abc 100f 0dei (0–7) (8–9) (0–7)
a b c d e f 1 1 0 i 100c 0def 0abi (8–9) (0–7) (0–7)
a b c 1 0 f 1 1 1 i 0abc 100f 100i (0–7) (8–9) (8–9) One small digit,
two large
a b c 0 1 f 1 1 1 i 100c 0abf 100i (8–9) (0–7) (8–9)
a b c 0 0 f 1 1 1 i 100c 100f 0abi (8–9) (8–9) (0–7)
x x c 1 1 f 1 1 1 i 100c 100f 100i (8–9) (8–9) (8–9) Three large digits

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 7 bits can be considered a 7-bit encoding for 3 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.

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

  1. ^ *Cowlishaw, M. F. (May 2002). "Densely packed decimal encoding". IEE Proceedings – Computers and Digital Techniques (Institution of Electrical Engineers) 149 (3): 102–104. doi:10.1049/ip-cdt:20020407. ISSN 1350-2387. 
  2. ^ Cowlishaw, M. F. (2000-10-03). "Summary of Densely Packed Decimal encoding". http://speleotrove.com/decimal/DPDecimal.html. Retrieved 2008-09-10. 

Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Densely Packed Decimal — (DPD) is a 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… …   Wikipedia

  • Decimal computer — Decimal computers, computers which have a decimal architecture, represent numbers and/or addresses in decimal, and provide instructions to operate on those numbers and/or addresses directly; examples of encoding used are BCD, Excess 3, two out of …   Wikipedia

  • Decimal floating point — Floating point precisions IEEE 754: 16 bit: Half (binary16) 32 bit: Single (binary32), decimal32 64 bit: Double (binary64), decimal64 128 bit: Quadruple (binary128), decimal128 Other: Minifloat · Extended precision Arbitrary precision… …   Wikipedia

  • Binary-coded decimal — In computing and electronic systems, binary coded decimal (BCD) is a digital encoding method for numbers using decimal notation, with each decimal digit represented by its own binary sequence. In BCD, a numeral is usually represented by four bits …   Wikipedia

  • Decimal128 floating-point format — Floating point precisions IEEE 754: 16 bit: Half (binary16) 32 bit: Single (binary32), decimal32 64 bit: Double (binary64), decimal64 128 bit: Quadruple (binary128), decimal128 Other: Minifloat · Extended precision Arbitrary precision In com …   Wikipedia

  • Decimal32 floating-point format — Floating point precisions IEEE 754: 16 bit: Half (binary16) 32 bit: Single (binary32), decimal32 64 bit: Double (binary64), decimal64 128 bit: Quadruple (binary128), decimal128 Other: Minifloat · Extended precision Arbitrary precision In com …   Wikipedia

  • Decimal64 floating-point format — Floating point precisions IEEE 754: 16 bit: Half (binary16) 32 bit: Single (binary32), decimal32 64 bit: Double (binary64), decimal64 128 bit: Quadruple (binary128), decimal128 Other: Minifloat · Extended precision Arbitrary precision In com …   Wikipedia

  • IEEE 754 revision — This article describes the revision process of the IEEE 754 standard, 2000 2008, and the changes included in the revision. For a description of the standard itself, see IEEE 754 2008. IEEE 754 2008 (previously known as IEEE 754r ) was published… …   Wikipedia

  • Mike Cowlishaw — Michael F. Cowlishaw Born …   Wikipedia

  • Chen–Ho encoding — 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… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”