Плотно упакованная десятичная дробь ( 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 |
Смотрите также
Рекомендации
- ^ a b Коулишоу, Майкл Фредерик (2002-08-07) [май 2002]. «Плотно упакованное десятичное кодирование» . IEE Proceedings - Компьютеры и цифровые методы . Лондон, Великобритания: Институт инженеров-электриков . 149 (3): 102–104. DOI : 10.1049 / IP-CDT: 20020407 . ISSN 1350-2387 . Проверено 7 февраля 2016 .
- ^ Коулишоу, Майкл Фредерик (2014) [июнь 2000]. «Краткое изложение кодирования десятичных данных Чен-Хо» . IBM . Архивировано 24 сентября 2015 года . Проверено 7 февраля 2016 .
- ^ IEEE Computer Society (29 августа 2008 г.). Стандарт 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 .
- ^ Коулишоу, Майкл Фредерик (13 февраля 2007) [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 .