Densely packed decimal

Last updated

Densely packed decimal (DPD) is an efficient method for binary encoding decimal digits.

Contents

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:

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.

Densely packed decimal encoding rules [5]
DPD encoded valueDecimal digits
Code space
(1024 states)
b9b8b7b6b5b4b3b2b1b0d2d1d0Values encodedDescriptionOccurrences
(1000 states)
50.0%
(512 states)
abcdef0ghi0abc0def0ghi(0–7)(0–7)(0–7)3 small digits51.2%
(512 states)
37.5%
(384 states)
abcdef100i0abc0def100i(0–7)(0–7)(8–9)2 small digits,
1 large digit
38.4%
(384 states)
abcghf101i0abc100f0ghi(0–7)(8–9)(0–7)
ghcdef110i100c0def0ghi(8–9)(0–7)(0–7)
9.375%
(96 states)
ghc00f111i100c100f0ghi(8–9)(8–9)(0–7)1 small digit,
2 large digits
9.6%
(96 states)
dec01f111i100c0def100i(8–9)(0–7)(8–9)
abc10f111i0abc100f100i(0–7)(8–9)(8–9)
3.125%
(32 states, 8 used)
xxc11f111i100c100f100i(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):

DecimalBCDChen–HoDPD
0050000 0000 0101000 000 0101000 000 0101
0090000 0000 1001110 000 0001000 000 1001
0550000 0101 0101000 010 1101000 101 0101
0790000 0111 1001110 011 1001000 111 1001
0800000 1000 0000101 000 0000000 000 1010
0990000 1001 1001111 000 1001000 101 1111
5550101 0101 0101010 110 1101101 101 0101
9991001 1001 1001111 111 1001001 111 1111

See also

Related Research Articles

<span class="mw-page-title-main">Binary-coded decimal</span> System of digitally encoding numbers

In computing and electronic systems, binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each digit is represented by a fixed number of bits, usually four or eight. Sometimes, special bit patterns are used for a sign or other indications.

<span class="mw-page-title-main">Floating-point arithmetic</span> Computer approximation for real numbers

In computing, floating-point arithmetic (FP) is arithmetic that represents a subset of real numbers using an integer with a fixed precision, called the significand, scaled by an integer exponent of a fixed base. Numbers of this form are called floating-point numbers. For example, 12.345 is a floating-point number in a base-ten representation with five digits of precision:

In mathematics and computing, the hexadecimal numeral system is a positional numeral system that represents numbers using a radix (base) of sixteen. Unlike the decimal system representing numbers using ten symbols, hexadecimal uses sixteen distinct symbols, most often the symbols "0"–"9" to represent values 0 to 9, and "A"–"F" to represent values from ten to fifteen.

Double-precision floating-point format is a floating-point number format, usually occupying 64 bits in computer memory; it represents a wide dynamic range of numeric values by using a floating radix point.

A binary code represents text, computer processor instructions, or any other data using a two-symbol system. The two-symbol system used is often "0" and "1" from the binary number system. The binary code assigns a pattern of binary digits, also known as bits, to each character, instruction, etc. For example, a binary string of eight bits can represent any of 256 possible values and can, therefore, represent a wide variety of different items.

The IEEE Standard for Floating-Point Arithmetic is a technical standard for floating-point arithmetic established in 1985 by the Institute of Electrical and Electronics Engineers (IEEE). The standard addressed many problems found in the diverse floating-point implementations that made them difficult to use reliably and portably. Many hardware floating-point units use the IEEE 754 standard.

Hexadecimal floating point is a format for encoding floating-point numbers first introduced on the IBM System/360 computers, and supported on subsequent machines based on that architecture, as well as machines which were intended to be application-compatible with System/360.

<span class="mw-page-title-main">Mike Cowlishaw</span>

Mike Cowlishaw is a visiting professor at the Department of Computer Science at the University of Warwick, and a Fellow of the Royal Academy of Engineering. He is a retired IBM Fellow, and was a Fellow of the Institute of Engineering and Technology, and the British Computer Society. He was educated at Monkton Combe School and the University of Birmingham.

Chen–Ho encoding is a memory-efficient alternate system of binary encoding for decimal digits.

Decimal floating-point (DFP) arithmetic refers to both a representation and operations on decimal floating-point numbers. Working directly with decimal (base-10) fractions can avoid the rounding errors that otherwise typically occur when converting between decimal fractions and binary (base-2) fractions.

<span class="mw-page-title-main">Decimal computer</span> Computer operating on base-10 numbers

Decimal computers are computers which can represent numbers and addresses in decimal as well as providing instructions to operate on those numbers and addresses directly in decimal, without conversion to a pure binary representation. Some also had a variable wordlength, which enabled operations on numbers with a large number of digits.

The IEEE 754-2008 standard includes decimal floating-point number formats in which the significand and the exponent can be encoded in two ways, referred to as binary encoding and decimal encoding.

IEEE 754-2008 was published in August 2008 and is a significant revision to, and replaces, the IEEE 754-1985 floating-point standard, while in 2019 it was updated with a minor revision IEEE 754-2019. The 2008 revision extended the previous standard where it was necessary, added decimal arithmetic and formats, tightened up certain areas of the original standard which were left undefined, and merged in IEEE 854.

Offset binary, also referred to as excess-K, excess-N, excess-e, excess code or biased representation, is a method for signed number representation where a signed number n is represented by the bit pattern corresponding to the unsigned number n+K, K being the biasing value or offset. There is no standard for offset binary, but most often the K for an n-bit binary word is K = 2n−1 (for example, the offset for a four-digit binary number would be 23=8). This has the consequence that the minimal negative value is represented by all-zeros, the "zero" value is represented by a 1 in the most significant bit and zero in all other bits, and the maximal positive value is represented by all-ones (conveniently, this is the same as using two's complement but with the most significant bit inverted). It also has the consequence that in a logical comparison operation, one gets the same result as with a true form numerical comparison operation, whereas, in two's complement notation a logical comparison will agree with true form numerical comparison operation if and only if the numbers being compared have the same sign. Otherwise the sense of the comparison will be inverted, with all negative values being taken as being larger than all positive values.

Single-precision floating-point format is a computer number format, usually occupying 32 bits in computer memory; it represents a wide dynamic range of numeric values by using a floating radix point.

In computing, decimal32 is a decimal floating-point computer numbering format that occupies 4 bytes (32 bits) in computer memory. It is intended for applications where it is necessary to emulate decimal rounding exactly, such as financial and tax computations. Like the binary16 format, it is intended for memory saving storage.

In computing, decimal64 is a decimal floating-point computer numbering format that occupies 8 bytes in computer memory. It is intended for applications where it is necessary to emulate decimal rounding exactly, such as financial and tax computations.

decimal128 is a decimal floating-point computer number format that occupies 128 bits in computer memory. Formally introduced in IEEE 754-2008, it is intended for applications where it is necessary to emulate decimal rounding exactly, such as financial and tax computations.

BCD, also called alphanumeric BCD, alphameric BCD, BCD Interchange Code, or BCDIC, is a family of representations of numerals, uppercase Latin letters, and some special and control characters as six-bit character codes.

SQUOZE is a memory-efficient representation of a combined source and relocatable object program file with a symbol table on punched cards which was introduced in 1958 with the SCAT assembler on the SHARE Operating System (SOS) for the IBM 709. A program in this format was called a SQUOZE deck. It was also used on later machines including the IBM 7090 and 7094.

References

  1. 1 2 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.
  2. 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.
  3. 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.
  4. ISO/IEC/IEEE 60559:2011. 2011. Archived from the original on 2020-06-03. Retrieved 2016-02-08.
  5. 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