Densely packed decimal
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つのうちから選択される。下表にそのパターンを示す。
| 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 |
関連項目
[編集]参考
[編集]Bonten, J.H.M.. “Packed Decimal Encoding IEEE-754r”. 2007年8月24日時点のオリジナルよりアーカイブ。2008年9月10日閲覧。
- ^ *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.
- ^ Cowlishaw, M. F. (2000年10月3日). “Summary of Densely Packed Decimal encoding”. 2008年9月10日閲覧。