Enter your keyword

post

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 (212) 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 (210) 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

Free Demo