What is DENSELY PACKED DECIMAL?
As we are all aware, computing binary-coded decimal (BCD) is a class of binary encodings of decimal numbers where each decimal digit is represented by a fixed number of four bits. So a combination of 12 bits can represent 1000 (000-999) different numbers whereas in binary representation 12 bits can represent 4096 (2^{12}) distinct numbers. These figures show a packing density about 24.41 % which is very poor. The reason for poor density is that we don’t use 6 codes per decimal digit (1010, 1011, 1100, 1101, 1110, 1111). To enhance the package density Cowlinshaw in 2002, proposed a new compression scheme called Densely Packed Decimal. This was latterly used as decimal encoding scheme in IEEE 754:2008 standard. So the motive of this article is to study about Densely Packed Decimal coding.
In this technique, 3 decimal digits are processed at a time and a compressed code of 10 bits is generated. So 10 bits can represent 1000 (000-999) numbers in DPD whereas in binary number system, a combination of 10 bits can represent 1024 (2^{10}) distinct numbers. As per calculations the packing efficiency is about 97.65 %. The compression enhances the efficiency from 24.41 % to 97.65 %. This compression method shows a brilliant ingenuity.
Digit | BCD Bit-pattern |
0 | 0000 |
1 | 0001 |
2 | 0010 |
3 | 0011 |
4 | 0100 |
5 | 0101 |
6 | 0110 |
7 | 0111 |
8 | 1000 |
9 | 1001 |
Table 1: Binary Coded Decimal
The compression system heavily relies on the structure of the bit patterns ubiquitously used to store a decimal digit into four bits (BCD code). Table 1 shows BCD codes for first 10 decimal digits.
Let us look more closely at all the ten bit patterns. The patterns can be split into a group of left three bits and a single right bit. The right bit is changing in every new number that is 0 or 1. So this bit cannot be compressed. Therefore it must be copied directly and unchanged into the compressed code.
When the right bit is removed from every digit new 3-bits mini-digits remain:
Digit | Bit-pattern | Digit Type |
0 | 000 | Small |
1 | 001 | Small |
2 | 010 | Small |
3 | 011 | Small |
4 | 100 | Large |
Table 2: Mini Digits
The mini-digits shows there are four of them with the left bit zero (called the small digits) and one with bit one (called the large digit). This division is the basis of the DPD compression scheme.
The left bit of each digit will not be copied directly. Only the middle and right bit of the small digits are copied directly. Those of the large digit also are not.
The 3 decimal digits in BCD are represented as a combination of 12 bits (a, b, c, d, e, f, g, h, i, j, k, l). As shown in table 3 with BCD code of 697.
6 | 9 | 7 | |||||||||
0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 1 |
a | b | c | d | e | f | g | h | i | j | k | l |
Table 3: 697 BCD Representations
The value of bits ‘a’, ‘e’ and ‘i’ decide whether the digits are large or small. In DPD, ten bits are used to represent the compression result as given in table 4.
p | q | r | s | t | u | v | w | x | y |
Table 4: Format of DPD Coding
Where, ‘r’ =‘d’, ‘u’ = ‘h’ and ‘y’ = ‘l’. One out of the compressed bits, v, always becomes a bit with a value ‘invented’ by the encoding system. The value of v could be ‘0’ or ‘1’ depending upon the combination of ‘aei’ bits. The value of ‘v’ will be ‘0’ for ‘aei’ = ‘000’ and ‘1’ for all other combinations. The table 5 summarizes all possible combination of ‘aei’ and the possible values for bit ‘v’.
‘aei’ | v | Types of BCD Digits | ‘pq’ | ‘st’ | ‘wx’ |
000 | 0 | All digits are small | ‘bc’ | ‘fg’ | ‘jk’ |
001 | 1 | Only right digit is large | ‘bc’ | ‘fg’ | 00 |
010 | 1 | Only middle digit is large | ‘bc’ | ‘jk’ | 01 |
011 | 1 | Only left digit is small | ‘bc’ | 10 | 11 |
100 | 1 | Only left digit is large | ‘jk’ | ‘fg’ | 10 |
101 | 1 | Only middle digit is small | ‘fg’ | 01 | 11 |
110 | 1 | Only right digit is small | ‘jk’ | 00 | 11 |
111 | 1 | All digits are large | 00 | 11 | 11 |
Table 5: DPD mapping table
In case of all small digits ‘pq’ represents ‘bc’, ‘st’ represents ‘fg’ and ‘wk’ represent ‘jk’. In other cases, the combination of ‘wx’ bits represents the position of large digit in the combination of 3 digits, if large digits are more than one then the value is ‘11’. In case of single large digit the combination of ‘st’ represents ‘fg’, if middle digit is large and all digits are small then ‘st’ represent ‘jk’ and ‘fg’ respectively. In case of single small digit ‘st’ represent the position of the small digit from right side. In case of all large digits the value of ‘st’ should be ‘11’. In case of all digit small, right digit is large, middle digit is large or left digit is small the combination of ‘pq’ holds value of ‘bc’. In case of left digit is large, middle digit is small, right digit is small and All digits are large the combination of ‘pq’ represents ‘jk’, ‘fg’, ‘jk’ and ‘00’ value respectively. The table 6 summarizes the whole of the compression scheme.
‘aei’ | Types of BCD Digits | ‘pqr’ | ‘stu’ | v | ‘wxy’ |
000 | All digits are small | ‘bcd’ | ‘fgh’ | 0 | ‘jkl’ |
001 | Only right digit is large | ‘bcd’ | ‘fgh’ | 1 | ‘00l’ |
010 | Only middle digit is large | ‘bcd’ | ‘jkh’ | 1 | ‘01l’ |
011 | Only left digit is small | ‘bcd’ | ‘10h’ | 1 | ‘11l’ |
100 | Only left digit is large | ‘jkd’ | ‘fgh’ | 1 | ‘10l’ |
101 | Only middle digit is small | ‘fgd’ | ‘01h’ | 1 | ‘11l’ |
110 | Only right digit is small | ‘jkd’ | ‘00h’ | 1 | ‘11l’ |
111 | All digits are large | ‘00d’ | ‘11h’ | 1 | ‘11l’ |
Table 6: DPD mapping table
Author: Manjesh
M.Tech (Electronics and Communication Engineering)
Academic Counselor (IGNOU)
IT- faculty at PC Training Institute Ltd