Hustě zabalené desetinné místo - Densely packed decimal
Hustě zabalené desetinné místo (DPD) je efektivní metoda pro binární kódování desetinný číslice.
Tradiční systém binárního kódování pro desetinná místa, známý jako binárně kódované desetinné místo (BCD), používá ke kódování každé číslice čtyři bity, což má za následek významné 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 uložení pouze 10), i když používají zabalený BCD. Hustě zabalené desetinné číslo je efektivnější kód, který zabalí tři číslice do deseti bitů pomocí schématu, které umožňuje kompresi z BCD nebo jeho rozšíření na pouze dvě nebo tři zpoždění hardwarové brány.[1]
Hustě zabalené desítkové kódování je zdokonalením Chen – Ho kódování; poskytuje stejné výhody komprese a rychlosti, ale konkrétní uspořádání použitých bitů poskytuje další výhody:
- Komprese jedné nebo dvou číslic (do optimálních čtyř nebo sedmi bitů) je dosaženo jako podmnožina třímístného kódování. To znamená, že libovolný počet desetinných míst (nejen násobky tří číslic) lze efektivně kódovat. Například 38 = 12 × 3 + 2 desetinná místa lze kódovat na 12 × 10 + 7 = 127 bitů - to znamená, že lze 12 sad tří desetinných číslic kódovat pomocí 12 sad deseti binárních bitů a zbývající dvě desetinná místa lze kódovat pomocí dalších sedmi binárních bitů.
- Výše uvedené kódování podmnožiny je jednoduše nejpravějšími bity standardního tříciferného kódování; kódovanou hodnotu lze rozšířit jednoduše přidáním úvodních 0 bitů.
- Všechna sedmbitová čísla BCD (0 až 79) jsou kódována identicky 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 kódování DPD muselo zapadnout do sedmi bitů.)
- Bit nižšího řádu každé číslice je kopírován beze změny. Za netriviální část kódování lze tedy považovat převod ze tří číslic základny na sedm binárních bitů. Dále číslicově logické hodnoty (ve kterém je každá číslice buď 0 nebo 1) lze manipulovat přímo, 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 Irving Tze Ho (何宜慈) vymyslel bezztrátový prefixové kódy (dále jen Hertz a Chen – Ho kódování[2]), který zabalil tři desetinná místa do deseti binárních bitů pomocí schématu, které umožňovalo kompresi z BCD nebo její expanzi na BCD s pouze dvěma nebo třemi zpožděními brány v hardwaru. Hustě zabalená desetinná čárka je zdokonalením, které vymyslel Mike F. Cowlishaw v roce 2002,[1] který byl začleněn do IEEE 754-2008[3] a ISO / IEC / IEEE 60559: 2011[4] standardy pro desetinná místa plovoucí bod.
Kódování
Stejně jako kódování Chen – Ho i 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 naznačeno, že číslice je malá, jsou ke stanovení hodnoty stále zapotřebí další tři bity. Pokud byla indikována velká hodnota, je k rozlišení mezi hodnotami 8 nebo 9 zapotřebí pouze jeden bit.
Při kódování vybere nejvýznamnější bit každé ze tří číslic, které mají být kódovány, jeden z osmi kódovacích vzorů pro zbývající bity, podle následující tabulky. Tabulka ukazuje, jak při dekódování deset bitů kódované formy ve sloupcích b9 přes b0 jsou zkopírovány do tří číslic d2 přes d0a zbývající bity jsou vyplněny konstantními nulami nebo jednotkami.
| Hodnota kódovaná DPD | Desetinná čísla | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Kódový prostor (1024 států) | b9 | b8 | b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 | d2 | d1 | d0 | Zakódované hodnoty | Popis | Výskyty (1 000 států) | |
| 50,0% (512 států) | A | b | C | d | E | F | 0 | G | h | i | 0abc | 0def | 0ghi | (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 | i | 0abc | 0def | 100i | (0–7) (0–7) (8–9) | Dvě malé číslice, jeden velký | 38,4% (384 států) | |
| 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) | ||||
| 9,375% (96 států) | G | h | C | 0 | 0 | F | 1 | 1 | 1 | i | 100C | 100F | 0ghi | (8–9) (8–9) (0–7) | Jedna malá číslice, dva velké | 9,6% (96 států) | |
| d | E | C | 0 | 1 | F | 1 | 1 | 1 | i | 100C | 0def | 100i | (8–9) (0–7) (8–9) | ||||
| A | b | C | 1 | 0 | F | 1 | 1 | 1 | i | 0abc | 100F | 100i | (0–7) (8–9) (8–9) | ||||
| 3,125% (32 států, 8 použitých) | X | X | C | 1 | 1 | F | 1 | 1 | 1 | i | 100C | 100F | 100i | (8–9) (8–9) (8–9) | Tři velké číslice, bity b9 a b8 jsou je mi to jedno | 0,8% (8 států) | |
Bity b7, b4 a b0 (C, F a i) procházejí kódováním beze změny a nemají vliv na význam ostatních bitů. Zbývajících sedm bitů lze považovat za sedmibitové kódování pro tři číslice 5 základny.
Bity b8 a b9 nejsou nutné a ignorováno při dekódování skupin DPD se třemi velkými číslicemi (označenými jako „x“ v posledním řádku tabulky výše), 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á každé čtyři kódování. Bity označené x v tabulce výše jsou při vstupu ignorovány, ale ve vypočítaných výsledcích budou vždy 0. (8 × 3 = 24 nestandardních kódování vyplní v mezeře mezi 103 = 1000 a 210 = 1024.)
Příklady
Tato tabulka ukazuje některá reprezentativní desetinná čísla a jejich kódování v BCD, Chen – Ho a hustě zabalených desetinách (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é
- Binárně kódované desetinné místo (BCD)
- Binární celé číslo v desítkové soustavě (NABÍDKA)
- formát s desetinnou čárkou
- formát s desetinnou čárkou
- desetinný formát s plovoucí desetinnou čárkou
- DEC RADIX 50 / MOD40
- IBM SQUOZE
Reference
- ^ A b Cowlishaw, Michael Frederic (08.08.2002) [květen 2002]. "Hustě zabalené desítkové kódování". Sborník IEE - Počítače a digitální techniky. Londýn, Velká Británie: Instituce elektrotechniků (IEE). 149 (3): 102–104. doi:10.1049 / ip-cdt: 20020407. ISSN 1350-2387. Citováno 2016-02-07.
- ^ Cowlishaw, Michael Frederic (2014) [červen 2000]. "Souhrn kódování desetinných dat Chen-Ho". IBM. Archivováno od původního dne 2015-09-24. Citováno 2016-02-07.
- ^ IEEE Computer Society (2008-08-29). Standard IEEE pro plovoucí desetinnou čárkou aritmetiku. IEEE. doi:10.1109 / IEEESTD.2008.4610935. ISBN 978-0-7381-5753-5. IEEE Std 754-2008. Citováno 2016-02-08.
- ^ ISO / IEC / IEEE 60559: 2011. 2011. Archivováno z původního dne 2020-06-03. Citováno 2016-02-08.
- ^ Cowlishaw, Michael Frederic (2007-02-13) [2000-10-03]. "Shrnutí hustě zabaleného desetinného kódování". IBM. Archivováno od původního dne 2015-09-24. Citováno 2016-02-07.
Další čtení
- Cowlishaw, Michael Frederic (2003-02-25) [2002-05-20, 2001-01-27]. Napsáno v Coventry ve Velké Británii. "Decimal to binary coder / decoder" (Americký patent). Armonk, New York, USA: International Business Machines Corporation (IBM). US6525679B1. Citováno 2018-07-18 [1] a Cowlishaw, Michael Frederic (2007-11-07) [2004-01-14, 2002-08-14, 2001-09-24, 2001-01-27]. Napsáno ve Winchesteru, Hampshire ve Velké Británii. "Decimal to binary coder / decoder" (Evropský patent). Armonk, New York, USA: International Business Machines Corporation (IBM). EP1231716A2. Citováno 2018-07-18. [2][3][4] (Pozn. Tento patent se týká DPD.)
- Bonten, Jo H. M. (06.10.2009) [10.10.2006]. „Zabalené desetinné kódování IEEE-754-2008“. Archivováno od originálu 11. 7. 2018. Citováno 2018-07-11. (Pozn. Starší verzi najdete zde: Zabalené desetinné kódování IEEE-754r.)
- Savard, John J. G. (2018) [2007]. „Chen – Ho kódování a hustě zabalené desetinné číslo“. quadibloc. Archivováno z původního dne 2018-07-03. Citováno 2018-07-16.