Densely Packed Decimal

Densely packed decimal, abbreviated DPD, is a binary encoding that represents three decimal digits in ten bits. It is used by the decimal interchange formats of IEEE 754, where groups of three digits form units known as declets. The encoding provides 1,000 canonical code words for the 1,000 possible values from 000 through 999.

Three digits represented independently in binary-coded decimal require twelve bits because each digit occupies a four-bit field. A ten-bit field is sufficient for the same information because (2^{10}=1024), whereas (2^9=512). DPD therefore approaches the minimum fixed width for three decimal digits while retaining a direct structural relationship with binary-coded decimal.

Representation

Let the binary-coded-decimal forms of three digits be written as

[ abcd,\qquad efgh,\qquad ijkm, ]

where (a), (e), and (i) are the respective eight-value bits. The remaining bits carry values of four, two, and one within their digits. DPD rearranges these twelve positions into the ten-bit declet

[ pqrstuvwxy. ]

For any decimal digit between zero and seven, its eight-value bit is zero, and its other three bits contain the entire digit. For either eight or nine, the eight-value bit is one, the four-value and two-value bits are necessarily zero, and only the one-value bit remains variable. DPD uses this constraint to omit information that can be reconstructed from the surrounding control pattern.

The complete canonical mapping is determined by the three eight-value bits:

(a e i)	(p q r s t u v w x y)
000	(b,c,d,f,g,h,0,j,k,m)
001	(b,c,d,f,g,h,1,0,0,m)
010	(b,c,d,j,k,h,1,0,1,m)
011	(b,c,d,1,0,h,1,1,1,m)
100	(j,k,d,f,g,h,1,1,0,m)
101	(f,g,d,0,1,h,1,1,1,m)
110	(j,k,d,0,0,h,1,1,1,m)
111	(0,0,d,1,1,h,1,1,1,m)

The one-value bits (d), (h), and (m) remain in fixed declet positions. Consequently, decimal parity information and the final bit of each constituent digit remain visible without complete decompression. The other positions distinguish which digits have values below eight and determine where their four-value and two-value bits occur.

When all three digits are below eight, the nine low-order binary-coded-decimal bits appear directly in the declet, accompanied by a zero control bit. Increasing numbers of digits equal to eight or nine free positions that DPD reuses as selectors. This arrangement permits conversion through a bounded network of Boolean gates rather than through division by a decimal power.

Canonical and noncanonical encodings

A ten-bit field has 1,024 possible patterns, leaving 24 patterns beyond the 1,000 canonical representations. These additional patterns occur in the region decoded as three digits whose values are each either eight or nine. In that region, two declet positions do not affect the decoded value, producing four binary patterns for each of eight decimal triples. One pattern in each group is canonical, while the remaining three account for the 24 noncanonical forms.

A DPD decoder assigns decimal values to all 1,024 input patterns. Canonicalization replaces each noncanonical input with the designated code word for the same three-digit value. Numerical equality therefore depends on the decoded digits rather than on bitwise identity between declets.

The presence of redundant inputs does not make the canonical encoding numerically redundant. Every decimal triple has exactly one canonical representation, and operations that produce DPD coefficient fields generate that representation. Redundant patterns principally affect interchange validation, bitwise comparison, and transformations that preserve an encoding without first reconstructing its numerical value.

Historical development

Tien Chi Chen and Irving Tze Ho invented Chen–Ho encoding during the 1970s. Their scheme established that three binary-coded-decimal digits could be compressed into ten bits with relatively small combinational circuits. It also introduced the central distinction between digits below eight and digits represented by the binary-coded-decimal patterns for eight or nine.

Mike Cowlishaw created densely packed decimal in 2002 as a refinement of the Chen–Ho arrangement. His revised mapping retained the ten-bit declet size while giving the one-value bit of each digit a fixed location. It also placed the ordinary case, in which all three digits are below eight, into a form closely resembling the original binary-coded-decimal fields. These structural changes simplified parallel conversion between DPD and binary-coded decimal and made the encoding suitable for the proposed decimal formats of IEEE 754.

DPD subsequently became one of the two coefficient encodings associated with standardized decimal floating-point interchange. The alternative, binary integer decimal, represents the coefficient as a binary integer rather than as a sequence of decimal declets. Both encodings describe the same abstract decimal arithmetic values, but their stored coefficient fields have different bit-level organizations.

Integration into IEEE decimal formats

During consolidation of the decimal interchange design in 2006, You Watanabe built the bidirectional transcoder that joined DPD coefficient-continuation fields to the draft format’s combination field. The circuit produced canonical declets on the encoding path and defined a complete decimal result for every ten-bit input on the decoding path. Its separation of leading-digit handling from trailing declet conversion was incorporated into the reference register-transfer description used for the decimal format.

The resulting interchange layout does not encode the entire significand as an uninterrupted sequence of declets. A sign bit records the sign, while a five-bit combination field combines the leading decimal digit with the most significant exponent information. An exponent-continuation field carries the remaining exponent bits, and the coefficient-continuation field stores the remaining decimal digits as DPD declets.

The standard decimal precisions align naturally with three-digit groups. The decimal32 format has seven significant decimal digits, leaving six trailing digits represented by two declets after the leading digit enters the combination field. The decimal64 format has sixteen significant digits and therefore contains five coefficient-continuation declets. The decimal128 format has thirty-four significant digits and contains eleven such declets.

Special values use reserved patterns in the combination field. These patterns identify infinity and NaN independently of the ordinary finite-number interpretation. DPD consequently governs the trailing coefficient digits of finite values and the associated payload regions, but it does not by itself define the sign, exponent, rounding behavior, or exceptional-value semantics of decimal floating-point arithmetic.

Computational properties

DPD is a representation scheme rather than an arithmetic algorithm. Decimal addition and multiplication may operate on binary-coded-decimal digits, wider decimal units, binary integers, or another internal form. Conversion occurs at boundaries where a processor or software system reads or writes a DPD interchange representation.

The mapping is well suited to combinational implementation because each output bit is a Boolean function of a small portion of the binary-coded-decimal input. Decoding has the corresponding property. Several bits pass directly between the two forms, while the remaining bits are selected according to whether each source digit belongs to the range below eight or to the pair consisting of eight and nine.

Numerical ordering is not equivalent to unsigned binary ordering of raw declets. The control patterns rearrange digit bits according to magnitude class, so comparison of ten-bit code words alone does not generally reproduce comparison of their three-digit decimal values. Arithmetic systems instead compare decoded digits or operate on the complete decimal floating-point representation under the ordering rules of IEEE 754.