Плотно упакованная десятичная дробь ( DPD ) - эффективный метод двоичного кодирования десятичных цифр.
Традиционная система двоичного кодирования десятичных цифр, известная как двоично-десятичная дробь (BCD), использует четыре бита для кодирования каждой цифры, что приводит к значительной потере полосы пропускания двоичных данных (поскольку четыре бита могут хранить 16 состояний и используются для хранения только 10), даже при использовании упакованного BCD . Плотно упакованный десятичный код - это более эффективный код, который упаковывает три цифры в десять битов с использованием схемы, которая позволяет выполнять сжатие из BCD или расширение в него только с двумя или тремя задержками аппаратного затвора . [1]
Плотно упакованное десятичное кодирование является усовершенствованием кодирования Чен – Хо ; он дает те же преимущества сжатия и скорости, но особое расположение используемых бит дает дополнительные преимущества:
- Сжатие одной или двух цифр (в оптимальные четыре или семь битов соответственно) достигается как подмножество трехзначного кодирования. Это означает, что можно эффективно кодировать произвольное количество десятичных цифр (а не только кратные трем цифрам). Например, 38 = 12 × 3 + 2 десятичных цифры могут быть закодированы в 12 × 10 + 7 = 127 бит, то есть 12 наборов из трех десятичных цифр могут быть закодированы с использованием 12 наборов из десяти двоичных битов и оставшихся двух десятичных цифр. может быть закодирован с использованием дополнительных семи двоичных битов.
- Упомянутое выше подмножество кодирования - это просто крайние правые биты стандартного трехзначного кодирования; закодированное значение можно расширить, просто добавив начальные 0 битов.
- Все семибитовые числа BCD (от 0 до 79) идентично кодируются DPD. Это делает преобразование обычных малых чисел тривиальным. (Это должно быть 80, потому что для этого требуется восемь бит для BCD, но указанное выше свойство требует, чтобы кодировка DPD соответствовала семи битам.)
- Младший бит каждой цифры копируется без изменений. Таким образом, нетривиальную часть кодирования можно рассматривать как преобразование трех цифр с основанием 5 в семь двоичных разрядов. Кроме того, логические значения в цифровом формате (в которых каждая цифра равна 0 или 1) могут управляться напрямую без необходимости какого-либо кодирования или декодирования.
История [ править ]
В 1969 году Теодор М. Герц и в 1971 году Тьен Чи Чен (陳 天機) с Ирвингом Цзе Хо (何宜慈) разработали префиксные коды без потерь (называемые кодировками Герца и Чен-Хо [2] ), в которых три десятичных знака были упакованы в десять. двоичные биты, использующие схему, которая допускает сжатие или расширение до BCD с аппаратными задержками только с двумя или тремя затворами. Плотно упакованная десятичная дробь является усовершенствованием этого метода, разработанного Майком Ф. Коулишоу в 2002 году [1], который был включен в стандарты IEEE 754-2008 [3] и ISO / IEC / IEEE 60559: 2011 [4]стандарты для десятичных чисел с плавающей запятой .
Кодировка [ править ]
Как и кодирование Чен – Хо, кодирование DPD классифицирует каждую десятичную цифру в один из двух диапазонов в зависимости от самого старшего бита двоичной формы: «маленькие» цифры имеют значения от 0 до 7 (двоичные 0000–0111), а «большие» цифры , От 8 до 9 (двоичные 1000–1001). После того, как стало известно или было указано, что цифра мала, для указания значения все еще требуются еще три бита. Если указано большое значение, требуется только один бит, чтобы различать значения 8 и 9.
При кодировании старший бит каждой из трех кодируемых цифр выбирает один из восьми шаблонов кодирования для оставшихся битов в соответствии со следующей таблицей. В таблице показано, как при декодировании десять битов закодированной формы в столбцах с b9 по b0 копируются в три цифры с d2 по d0 , а остальные биты заполняются постоянными нулями или единицами.
| Закодированное значение DPD | Десятичные цифры | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Кодовое пространство (1024 состояния) | b9 | b8 | b7 | b6 | b5 | b4 | b3 | Би 2 | b1 | b0 | d2 | d1 | d0 | Закодированные значения | Описание | Вхождения (1000 состояний) | |
| 50,0% (512 штатов) | а | б | c | d | е | ж | 0 | грамм | час | я | 0 abc | 0 def | 0 гхи | (0–7) (0–7) (0–7) | Три маленькие цифры | 51,2% (512 штатов) | |
| 37,5% (384 государства) | а | б | c | d | е | ж | 1 | 0 | 0 | я | 0 abc | 0 def | 100 я | (0–7) (0–7) (8–9) | Две маленькие цифры, одна большая | 38,4% (384 государства) | |
| а | б | c | грамм | час | ж | 1 | 0 | 1 | я | 0 abc | 100 f | 0 гхи | (0–7) (8–9) (0–7) | ||||
| грамм | час | c | d | е | ж | 1 | 1 | 0 | я | 100 с | 0 def | 0 гхи | (8–9) (0–7) (0–7) | ||||
| 9,375% (96 штатов) | грамм | час | c | 0 | 0 | ж | 1 | 1 | 1 | я | 100 с | 100 f | 0 гхи | (8–9) (8–9) (0–7) | Одна маленькая цифра, две большие | 9,6% (96 штатов) | |
| d | е | c | 0 | 1 | ж | 1 | 1 | 1 | я | 100 с | 0 def | 100 я | (8–9) (0–7) (8–9) | ||||
| а | б | c | 1 | 0 | ж | 1 | 1 | 1 | я | 0 abc | 100 f | 100 я | (0–7) (8–9) (8–9) | ||||
| 3,125% (32 штата, 8 использовано) | Икс | Икс | c | 1 | 1 | ж | 1 | 1 | 1 | я | 100 с | 100 f | 100 я | (8–9) (8–9) (8–9) | Три большие цифры, биты b9 и b8 являются не забочусь | 0,8% (8 штатов) | |
Биты b7, b4 и b0 ( c, fи i) проходят кодирование без изменений и не влияют на значение других битов. Остальные семь битов можно рассматривать как семибитное кодирование для трех цифр с основанием 5.
Биты b8 и b9 не нужны и игнорируются при декодировании групп DPD с тремя большими цифрами (помечены как «x» в последней строке таблицы выше), но при кодировании заполняются нулями.
Восемь десятичных значений, все цифры которых равны 8 или 9, имеют четыре кодировки каждое. Биты, отмеченные x в приведенной выше таблице, игнорируются при вводе, но всегда будут равны 0 в вычисленных результатах. (8 × 3 = 24 нестандартных кодирования заполняют промежуток между 10 3 = 1000 и 2 10 = 1024.)
Примеры [ править ]
В этой таблице показаны некоторые репрезентативные десятичные числа и их кодировки в BCD, Chen – Ho и плотно упакованном десятичном формате (DPD):
| Десятичная дробь | BCD | Чен – Хо | 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 |
См. Также [ править ]
- Десятичное число с двоичным кодом (BCD)
- Двоичное целое десятичное число (BID)
- десятичный32 формат с плавающей запятой
- десятичный формат с плавающей запятой
- десятичный128 формат с плавающей запятой
- ДЕКАБРЬ RADIX 50 / MOD40
- IBM SQUOZE
Ссылки [ править ]
- ^ a b Коулишоу, Майкл Фредерик (2002-08-07) [май 2002]. «Плотно упакованное десятичное кодирование» . IEE Proceedings - Компьютеры и цифровые методы . Лондон, Великобритания: Институт инженеров-электриков (IEE). 149 (3): 102–104. DOI : 10.1049 / IP-CDT: 20020407 . ISSN 1350-2387 . Проверено 7 февраля 2016 .
- ^ Cowlishaw, Майкл Фредерик (2014) [июнь 2000]. «Краткое изложение кодирования десятичных данных Чен-Хо» . IBM . Архивировано 24 сентября 2015 года . Проверено 7 февраля 2016 .
- ^ IEEE Computer Society (2008-08-29). Стандарт IEEE для арифметики с плавающей запятой . IEEE . DOI : 10.1109 / IEEESTD.2008.4610935 . ISBN 978-0-7381-5753-5. IEEE Std 754-2008 . Проверено 8 февраля 2016 .
- ^ ISO / IEC / IEEE 60559: 2011 . 2011. Архивировано 03 июня 2020 года . Проверено 8 февраля 2016 .
- ^ Cowlishaw, Майкл Фредерик (2007-02-13) [2000-10-03]. «Резюме плотно упакованного десятичного кодирования» . IBM . Архивировано 24 сентября 2015 года . Проверено 7 февраля 2016 .
Дальнейшее чтение [ править ]
- Коулишоу, Майкл Фредерик (25 февраля 2003 г.) [20 мая 2002 г., 27 января 2001 г.]. Написано в Ковентри, Великобритания. «Кодер / декодер от десятичного к двоичному» (Патент США). Армонк, Нью-Йорк, США: Международная корпорация бизнес-машин (IBM). US6525679B1 . Источник 2018-07-18 [1] и Коулишоу, Майкл Фредерик (2007-11-07) [2004-01-14, 2002-08-14, 2001-09-24, 2001-01-27]. Написано в Винчестере, Хэмпшир, Великобритания. «Кодер / декодер от десятичного к двоичному» (Европейский патент). Армонк, Нью-Йорк, США: Международная корпорация бизнес-машин (IBM). EP1231716A2 . Проверено 18 июля 2018 . [2] [3] [4] (NB. Этот патент касается DPD.)
- Бонтен, Джо Х.М. (2009-10-06) [2006-10-05]. «Упакованное десятичное кодирование IEEE-754-2008» . Архивировано 11 июля 2018 года . Проверено 11 июля 2018 .(NB. Более старую версию можно найти здесь: Packed Decimal Encoding IEEE-754r .)
- Савард, Джон Дж. Г. (2018) [2007]. «Кодирование Чен – Хо и плотно упакованная десятичная дробь» . квадиблок . Архивировано 3 июля 2018 года . Проверено 16 июля 2018 .
