コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

Densely packed decimal

出典: フリー百科事典『ウィキペディア(Wikipedia)』

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

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

DPDはChen–Ho符号英語版を洗練させたものである。圧縮率と速度の利点はそのままに、加えて特徴的なビットの配置により以下の利点がある。

  • 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 符号化規約[2]
DPD符号 10進数字
b9 b8 b7 b6 b5 b4 b3 b2 b1 b0 d2 d1 d0 符号化元の値 説明
a b c d e f 0 g h i 0abc 0def 0ghi (0–7) (0–7) (0–7) 全て小さい数字
a b c d e f 1 0 0 i 0abc 0def 100i (0–7) (0–7) (8–9) 小2つ、大1つ
a b c g h f 1 0 1 i 0abc 100f 0ghi (0–7) (8–9) (0–7)
g h c d e f 1 1 0 i 100c 0def 0ghi (8–9) (0–7) (0–7)
a b c 1 0 f 1 1 1 i 0abc 100f 100i (0–7) (8–9) (8–9) 小1つ、大2つ
d e c 0 1 f 1 1 1 i 100c 0def 100i (8–9) (0–7) (8–9)
g h c 0 0 f 1 1 1 i 100c 100f 0ghi (8–9) (8–9) (0–7)
x x c 1 1 f 1 1 1 i 100c 100f 100i (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 DPD
005 0000 0000 0101 000 000 0101 000 000 0101
009 0000 0000 1001 110 000 0001 000 000 1001
055 0000 0101 0101 000 010 1101 000 101 0101
079 0000 0111 1001 110 011 1001 000 111 1001
080 0000 1000 0000 101 000 0000 000 000 1010
099 0000 1001 1001 111 000 1001 000 101 1111
555 0101 0101 0101 010 110 1101 101 101 0101
999 1001 1001 1001 111 111 1001 001 111 1111

関連項目

[編集]

IEEE 754#十進浮動小数点数の交換形式

参考

[編集]

Bonten, J.H.M.. “Packed Decimal Encoding IEEE-754r”. 2007年8月24日時点のオリジナルよりアーカイブ。2008年9月10日閲覧。

  1. ^ *Cowlishaw, M. F. (May 2002). “Densely packed decimal encoding”. IEE Proceedings – Computers and Digital Techniques (Institution of Electrical Engineers) 149 (3): 102–104. doi:10.1049/ip-cdt:20020407. ISSN 1350-2387. 
  2. ^ Cowlishaw, M. F. (2000年10月3日). “Summary of Densely Packed Decimal encoding”. 2008年9月10日閲覧。