Densely packed decimal

Densely packed decimal (DPD)は、二進化十進表現の一種で、情報量と計算量の両方で効率的な手法として提案されたものである。

十進法の1桁を二進法4ビットで表現する伝統的な方法であるBCDは、4ビットで表現可能な16個の状態の内10個のみしか使っておらず、無駄が多い。DPDは3桁（1000状態）を10ビット（1024状態の表現が可能）に押し込めるためより効率的であり、またこの圧縮にかかるハードウェアのコストはわずか2、3ゲートの遅延のみである*。

DPDはを洗練させたものである。圧縮率と速度の利点はそのままに、加えて特徴的なビットの配置により以下の利点がある。
 1桁や2桁からの変換も同じ符号化方式のサブセットで可能（それぞれ4ビットと7ビット）。これはすなわち3の倍数桁でない任意の桁数の十進表現を効率的に符号化できるということである。
 上で述べたサブセットの符号化は単純に下位ビットを取り出すだけである。逆に言えば符号化された値の上位に0を埋めるだけで標準的な10ビットの符号に変換できる。
 7ビットの二進化十進数(0-79)はDPDでも同一のビットパターンになる。これは頻出する小さな値の変換を簡単にする。（これは80で破綻する。なぜなら上記の性質のために十進で2桁の数は7ビットに収める必要があるためである）
 各桁の最下位ビットは無変換で常に同一の位置へコピーされ、他のビットへの影響もない。つまりこの符号化は3桁の5進数から7桁の2進数への変換と解釈できる。
 各桁の最上位ビット以外は、無変換でコピーされるか、消える。このため複雑な演算は必要ない。

 歴史 
1971年、陳天機(Tien Chi Chen)とIrving T. Hoが現在Chen-Ho符号化として知られる手法を考案した。これは3桁の10進数を10ビットに無劣化でパックする接頭符号表現であり、わずか2、3ゲートのハードウェア遅延でBCDとの間の変換が可能であった。DPDはこれを洗練させたものであり、(Mike Cowlishaw)により考案された。DPDは浮動小数点表現の標準のIEEE 754-2008の、十進浮動小数点に取り入れられた。

 符号化方式 
Chen-Ho符号と同様、DPD符号は、各桁の数字を最上位ビットに応じて2種類に分類する。0から7(2進0000-0111)の「小さい」数字と、8および9(2進1000, 1001)の「大きい」数字である。ある数字が小さいことがわかっていれば、追加の3ビットでその数字を指定できる。ある数字が大きければ、追加のビットは1ビットのみで済む。
符号化において、対象の3つの数字それぞれの最上位ビットにより、残りのビットをエンコードするパターンが8つのうちから選択される。下表にそのパターンを示す。

+Densely packed decimal 符号化規約 DPD符号 10進数字 b9  b8  b7  b6  b5 b4  b3  b2  b1  b0 d2  d1  d0 符号化元の値 説明abcdef0ghi0abc0def0ghi(0–7) (0–7) (0–7)  全て小さい数字abcdef100i0abc0def100i(0–7) (0–7) (8–9)  小2つ、大1つabcghf101i0abc100f0ghi(0–7) (8–9) (0–7)ghcdef110i100c0def0ghi(8–9) (0–7) (0–7)abc10f111i0abc100f100i(0–7) (8–9) (8–9)  小1つ、大2つdec01f111i100c0def100i(8–9) (0–7) (8–9)ghc00f111i100c100f0ghi(8–9) (8–9) (0–7)xxc11f111i100c100f100i(8–9) (8–9) (8–9)  全て大きい数字

 b3が0ならば、全ての数字が小さいパターンである。(1行目)
 残りの9ビットを使って3つの小さい数字をエンコードする。
 b3が1かつb2,b1がともに1でないならば、小さい数字2つと大きい数字1つのパターンである。(2-4行目)
 b2,b1で数字の大小の組み合わせを示し、残りの7ビットを使って小さい数字2つと大きい数字1つをエンコードする。
 b3-b1が1かつb6,b5がともに1でないならば、小さい数字1つと大きい数字2つのパターンである。(5-7行目)
 b6,b5で数字の大小の組み合わせを示し、残りの4ビットを使って小さい数字1つと大きい数字2つをエンコードする。
 b6-b5,b3-b1が1ならば、全ての数字が大きいパターンである。(8行目)
 残りのビットのうち3ビットを使って3つの大きい数字をエンコードする。b9,b8は使用しない（エンコード時は0で埋められる）。

 例 
下表は特徴的ないくつかの数について、10進数とそのBCD、Chan-Ho、DPDのビットパターンを示す。

 10進数  BCD  Chen–Ho  DPD0050000 0000 0101000 000 0101000 000 01010090000 0000 1001110 000 0001000 000 10010550000 0101 0101000 010 1101000 101 01010790000 0111 1001110 011 1001000 111 1001080 0000 1000 0000 101 000 0000 000 000 10100990000 1001 1001111 000 1001000 101 11115550101 0101 0101010 110 1101101 101 01019991001 1001 1001111 111 1001001 111 1111

 関連項目 
IEEE 754#十進浮動小数点数の交換形式

 参考 

Category:コンピュータのデータ
Category:コンピュータの算術
Category:数の表現
Category:数学に関する記事