Hustě zabalené desetinné číslo - Densely packed decimal

Tento článek je o efektivní metodě pro kódování BCD. Jednodušší, ale méně efektivní metodu najdete v tématu Desetinná čísla .

Hustě zabalené desetinné číslo ( DPD ) je účinná metoda pro binární kódování desetinných číslic.

Tradiční systém binárního kódování desítkových číslic, známý jako binárně kódované desetinné číslo (BCD), používá ke kódování každé číslice čtyři bity, což má za následek značné plýtvání šířkou pásma binárních dat (protože čtyři bity mohou ukládat 16 stavů a ​​používají se k ukládání pouze 10), a to i při použití zabaleného BCD . Hustě zabalený desítkový je efektivnější kód, který zabalí tři číslice do deseti bitů pomocí schématu, které umožňuje kompresi z BCD nebo rozšíření na BCD pouze se dvěma nebo třemi zpožděními hardwarové brány .

Hustě zabalené desetinné kódování je zdokonalením kódování Chen -Ho ; poskytuje stejné výhody komprese a rychlosti, ale konkrétní uspořádání použitých bitů přináší další výhody:

  • Komprese jedné nebo dvou číslic (na optimální čtyři nebo sedm bitů) je dosažena jako podmnožina tříciferného kódování. To znamená, že libovolný počet desetinných číslic (nejen násobky tří číslic) lze efektivně kódovat. Například 38 = 12 × 3 + 2 desetinných číslic lze kódovat 12 × 10 + 7 = 127 bitů - to znamená, že 12 sad tří desetinných číslic lze kódovat pomocí 12 sad deseti binárních bitů a zbývajících dvou desetinných číslic lze kódovat pomocí dalších sedmi binárních bitů.
  • Výše zmíněné kódování podmnožiny je prostě bity nejvíce vpravo standardního tříciferného kódování; kódovanou hodnotu lze jednoduše rozšířit přidáním úvodních 0 bitů.
  • Všechna sedmbitová čísla BCD (0 až 79) jsou kódována shodně pomocí DPD. Díky tomu jsou převody běžných malých čísel triviální. (To se musí rozdělit na 80, protože to vyžaduje osm bitů pro BCD, ale výše uvedená vlastnost vyžaduje, aby se kódování DPD vešlo do sedmi bitů.)
  • Bit nižšího řádu každé číslice je kopírován bez úpravy. Netriviální část kódování lze tedy považovat za převod ze tří základních 5 číslic na sedm binárních bitů. Dále lze s číslicovými logickými hodnotami (ve kterých je každá číslice buď 0 nebo 1) přímo manipulovat, aniž by bylo nutné jakékoli kódování nebo dekódování.

Dějiny

V roce 1969 Theodore M. Hertz a v roce 1971 Tien Chi Chen (陳 天機) s Irvingem Tze Ho (何宜慈) vymysleli bezztrátové předponové kódy (označované jako kódování Hertz a Chen -Ho ), které zabalily tři desetinné číslice do deseti binárních bitů pomocí schéma, které umožňovalo kompresi nebo rozšíření na BCD s pouze dvěma nebo třemi zpožděním brány v hardwaru. Hustě zabalené desetinné číslo je vylepšení, které vytvořil Mike F. Cowlishaw v roce 2002 a které bylo začleněno do standardů IEEE 754-2008 a ISO/IEC/IEEE 60559: 2011 pro desetinnou čárku .

Kódování

Stejně jako kódování Chen -Ho, kódování DPD klasifikuje každou desetinnou číslici do jednoho ze dvou rozsahů v závislosti na nejvýznamnějším bitu binární formy: „malé“ číslice mají hodnoty 0 až 7 (binární 0000–0111) a „velké“ číslice , 8 až 9 (binární 1000–1001). Jakmile je známo nebo bylo uvedeno, že číslice je malá, jsou k určení hodnoty stále zapotřebí další tři bity. Pokud byla uvedena velká hodnota, je k rozlišení mezi hodnotami 8 nebo 9 zapotřebí pouze jeden bit.

Při kódování určují nejvýznamnější bity každé ze tří kódovaných číslic jeden z osmi kódovacích vzorů pro zbývající bity podle následující tabulky. Tabulka ukazuje, jak se při dekódování zkopíruje deset bitů kódované formy ve sloupcích b9 až b0 do tří číslic d2 až d0 a zbývající bity se vyplní konstantními nulami nebo jedničkami.

Hustě zabalená pravidla pro dekadické kódování
Hodnota kódovaná DPD Desetinné číslice
Prostor kódu (1024 států) b9 b8 b7 b6 b5 b4 b3 b2 b1 b0 d2 d1 d0 Kódované hodnoty Popis Výskyty (1000 států)
50,0% (512 států) A b C d E F 0 G h já 0 abc 0 def 0 ghi (0–7) (0–7) (0–7) Tři malé číslice 51,2% (512 států)
37,5% (384 států) A b C d E F 1 0 0 já 0 abc 0 def 100 i (0–7) (0–7) (8–9) Dvě malé číslice,
jedna velká 		38,4% (384 států)
A b C G h F 1 0 1 já 0 abc 100 f 0 ghi (0–7) (8–9) (0–7)
G h C d E F 1 1 0 já 100 c 0 def 0 ghi (8–9) (0–7) (0–7)
9,375% (96 států) G h C 0 0 F 1 1 1 já 100 c 100 f 0 ghi (8–9) (8–9) (0–7) Jedna malá číslice,
dvě velká 		9,6% (96 států)
d E C 0 1 F 1 1 1 já 100 c 0 def 100 i (8–9) (0–7) (8–9)
A b C 1 0 F 1 1 1 já 0 abc 100 f 100 i (0–7) (8–9) (8–9)
3,125% (32 států, 8 použitých) X X C 1 1 F 1 1 1 já 100 c 100 f 100 i (8–9) (8–9) (8–9) Tři velké číslice, bity b9 a b8, je to jedno 0,8% (8 států)

Bity b7, b4 a b0 ( c, fa i) procházejí kódováním beze změny a neovlivňují význam ostatních bitů. Zbývajících sedm bitů lze považovat za sedmbitové kódování pro tři základní 5 číslic.

Bity b8 a b9 nejsou potřeba a jsou ignorovány při dekódování skupin DPD se třemi velkými číslicemi (v posledním řádku tabulky výše označeny jako „x“), ale při kódování jsou vyplněny nulami.

Osm desetinných hodnot, jejichž číslice jsou všechny 8 s nebo 9 s, má čtyři kódování. Bity označené x v tabulce výše jsou na vstupu ignorovány, ale ve vypočítaných výsledcích budou vždy 0. (8 × 3 = 24 nestandardních kódování vyplní mezeru mezi 10 3  = 1 000 a 2 10  = 1024.)

Příklady

Tato tabulka ukazuje některá reprezentativní desetinná čísla a jejich kódování v BCD, Chen -Ho a hustě zabalených desetinných číslech (DPD):

Desetinný 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

Viz také

Reference

Další čtení