Gęsto upakowane dziesiętne
Gęsto upakowane dziesiętne ( DPD ) to wydajna metoda binarnego kodowania cyfr dziesiętnych .
Tradycyjny system binarnego kodowania cyfr dziesiętnych, znany jako kodowanie binarne dziesiętne (BCD), wykorzystuje cztery bity do zakodowania każdej cyfry, co powoduje znaczne marnotrawstwo przepustowości danych binarnych (ponieważ cztery bity mogą przechowywać 16 stanów i są używane do przechowywania tylko 10), nawet przy użyciu spakowanego BCD . Gęsto upakowane dziesiętne to bardziej wydajny kod, który pakuje trzy cyfry w dziesięć bitów przy użyciu schematu, który umożliwia kompresję z BCD lub rozszerzenie do BCD z tylko dwoma lub trzema opóźnieniami bramki sprzętowej .
Gęsto upakowane kodowanie dziesiętne jest udoskonaleniem kodowania Chen – Ho ; daje te same korzyści w zakresie kompresji i prędkości, ale szczególny układ zastosowanych bitów zapewnia dodatkowe korzyści:
- Kompresja jednej lub dwóch cyfr (odpowiednio do optymalnych czterech lub siedmiu bitów) jest osiągana jako podzbiór kodowania trzycyfrowego. Oznacza to, że można skutecznie zakodować dowolne liczby cyfr dziesiętnych (nie tylko wielokrotności trzech cyfr). Na przykład 38 = 12 × 3 + 2 cyfry dziesiętne można zakodować w 12 × 10 + 7 = 127 bitów - to znaczy 12 zestawów trzech cyfr dziesiętnych można zakodować przy użyciu 12 zestawów dziesięciu bitów binarnych i pozostałych dwóch cyfr dziesiętnych można zakodować za pomocą kolejnych siedmiu bitów binarnych.
- Wspomniane powyżej kodowanie podzbioru to po prostu skrajne prawe bity standardowego trzycyfrowego kodowania; zakodowaną wartość można rozszerzyć po prostu przez dodanie początkowych bitów 0.
- Wszystkie siedmiobitowe numery BCD (od 0 do 79) są kodowane identycznie przez DPD. To sprawia, że konwersje zwykłych małych liczb są trywialne. (To musi się zepsuć przy 80, ponieważ wymaga to ośmiu bitów dla BCD, ale powyższa właściwość wymaga, aby kodowanie DPD mieściło się w siedmiu bitach).
- Najmłodszy bit każdej cyfry jest kopiowany w niezmienionej postaci. Zatem nietrywialną część kodowania można uznać za konwersję z trzech cyfr o podstawie 5 na siedem bitów binarnych. wartościami logicznymi liczonymi cyframi (w których każda cyfra to 0 lub 1) można manipulować bezpośrednio, bez konieczności kodowania lub dekodowania.
Historia
W 1969 roku Theodore M. Hertz, aw 1971 Tien Chi Chen ( 陳天機 ) wraz z Irvingiem Tze Ho ( 何宜慈 ) opracowali bezstratne kody prefiksów (określane jako kodowanie Hertza i Chen – Ho ), które spakowały trzy cyfry dziesiętne na dziesięć bitów binarnych za pomocą schemat, który umożliwiał kompresję z BCD lub ekspansję do BCD z zaledwie dwoma lub trzema opóźnieniami bramek w sprzęcie. Gęsto upakowane dziesiętne to udoskonalenie tego, opracowane przez Mike'a F. Cowlishawa w 2002 r., Które zostało włączone do standardów IEEE 754-2008 i ISO / IEC / IEEE 60559: 2011 dla dziesiętnych zmiennoprzecinkowych .
Kodowanie
Podobnie jak kodowanie Chen – Ho, kodowanie DPD klasyfikuje każdą cyfrę dziesiętną do jednego z dwóch zakresów, w zależności od najbardziej znaczącego bitu postaci binarnej: „małe” cyfry mają wartości od 0 do 7 (binarnie 0000–0111), a „duże” cyfry , od 8 do 9 (binarnie 1000–1001). Gdy wiadomo lub wskazano, że cyfra jest mała, do określenia wartości potrzebne są jeszcze trzy bity. Jeśli wskazano dużą wartość, wystarczy jeden bit, aby rozróżnić wartości 8 lub 9.
Podczas kodowania najbardziej znaczące bity każdej z trzech cyfr, które mają być zakodowane, określają jeden z ośmiu wzorców kodowania dla pozostałych bitów, zgodnie z poniższą tabelą. Tabela pokazuje, jak podczas dekodowania dziesięć bitów zakodowanej postaci w kolumnach od b9 do b0 jest kopiowanych do trzech cyfr od d2 do d0 , a pozostałe bity są wypełniane stałymi zerami lub jedynkami.
| Wartość zakodowana w DPD | Cyfry dziesiętne | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Przestrzeń kodowa (1024 stany) | b9 | b8 | b7 | b6 | b5 | b4 | b3 | b2 | b1 | b0 | d2 | d1 | d0 | Zakodowane wartości | Opis | Zdarzenia (1000 stanów) | |
| 50,0% (512 stanów) | A | B | C | D | mi | F | 0 | G | H | I | 0ABC | 0pok | 0ghi | (0–7) (0–7) (0–7) | Trzy małe cyfry | 51,2% (512 stanów) | |
| 37,5% (384 stany) | A | B | C | D | mi | F | 1 | 0 | 0 | I | 0ABC | 0pok | 100 I | (0–7) (0–7) (8–9) |
Dwie małe cyfry, jedna duża |
38,4% (384 stany) | |
| A | B | C | G | H | F | 1 | 0 | 1 | I | 0ABC | 100 ż | 0ghi | (0–7) (8–9) (0–7) | ||||
| G | H | C | D | mi | F | 1 | 1 | 0 | I | 100 c | 0pok | 0ghi | (8–9) (0–7) (0–7) | ||||
| 9,375% (96 stanów) | G | H | C | 0 | 0 | F | 1 | 1 | 1 | I | 100 c | 100 ż | 0ghi | (8–9) (8–9) (0–7) |
Jedna mała cyfra, dwie duże |
9,6% (96 stanów) | |
| D | mi | C | 0 | 1 | F | 1 | 1 | 1 | I | 100 c | 0pok | 100 I | (8–9) (0–7) (8–9) | ||||
| A | B | C | 1 | 0 | F | 1 | 1 | 1 | I | 0ABC | 100 ż | 100 I | (0–7) (8–9) (8–9) | ||||
| 3,125% (32 stany, 8 używanych) | X | X | C | 1 | 1 | F | 1 | 1 | 1 | I | 100 c | 100 ż | 100 I | (8–9) (8–9) (8–9) | Trzy duże cyfry, bity b9 i b8 to nieważne | 0,8% (8 stanów) | |
Bity b7, b4 i b0 ( c , f i i ) są przepuszczane przez kodowanie bez zmian i nie wpływają na znaczenie pozostałych bitów. Pozostałe siedem bitów można uznać za kodowanie siedmiobitowe dla trzech cyfr o podstawie 5.
Bity b8 i b9 nie są potrzebne i są ignorowane podczas dekodowania grup DPD z trzema dużymi cyframi (oznaczone jako „x” w ostatnim wierszu powyższej tabeli), ale podczas kodowania są wypełniane zerami.
Osiem wartości dziesiętnych, których wszystkie cyfry to 8 lub 9, ma po cztery kody. Bity oznaczone x w powyższej tabeli są ignorowane na wejściu, ale zawsze będą miały wartość 0 w obliczonych wynikach. (3 × 8 = 24 niestandardowe kodowania wypełniają lukę między 10 3 = 1000 a 2 10 = 1024.)
Przykłady
Ta tabela przedstawia niektóre reprezentatywne liczby dziesiętne i ich kodowanie w BCD, Chen – Ho i gęsto upakowane dziesiętne (DPD):
| Dziesiętny | 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 |
Zobacz też
- Dziesiętny kodowany binarnie (BCD)
- Binarna liczba całkowita dziesiętna (BID)
- decimal32 format zmiennoprzecinkowy
- decimal64 format zmiennoprzecinkowy
- format dziesiętny128 zmiennoprzecinkowy
- DEC RADIX 50 / MOD40
- IBM SQUOZE
Dalsza lektura
- Cowlishaw, Michael Frederic (2003-02-25) [2002-05-20, 2001-01-27]. Napisane w Coventry w Wielkiej Brytanii. „Koder / dekoder dziesiętny na binarny” (patent USA). Armonk, Nowy Jork, USA: International Business Machines Corporation (IBM). US6525679B1 . Źródło 2018-07-18 [1] i Cowlishaw, Michael Frederic (2007-11-07) [2004-01-14, 2002-08-14, 2001-09-24, 2001-01-27]. Napisane w Winchester, Hampshire, Wielka Brytania. „Koder / dekoder dziesiętny na binarny” (patent europejski). Armonk, Nowy Jork, USA: International Business Machines Corporation (IBM). EP1231716A2 . Źródło 2018-07-18 . [2] [3] [4] (Uwaga: ten patent dotyczy DPD.)
- Bonten, Jo HM (2009-10-06) [2006-10-05]. „Pakowane kodowanie dziesiętne IEEE-754-2008” . Geldrop, Holandia. Zarchiwizowane od oryginału w dniu 2018-07-11 . Źródło 2018-07-11 . (Uwaga. Starszą wersję można znaleźć tutaj: Packed Decimal Encoding IEEE-754r .)
- Savard, John JG (2018) [2007]. „Kodowanie Chen – Ho i gęsto upakowane dziesiętne” . czworokąt . Zarchiwizowane od oryginału w dniu 2018-07-03 . Źródło 2018-07-16 .