Плотно упакованная десятичная дробь - Densely packed decimal

Плотно упакованная десятичная дробь (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, а остальные биты заполняются постоянными нулями или единицами.

Плотно упакованные правила десятичного кодирования^[5]
Кодовое пространство (1024 состояния)	b9	b8	b7	b6	b5	b4	b3	Би 2	b1	b0	d2	d1	d0	Закодированные значения	Описание	Вхождения (1000 состояний)
Кодированное значение DPD											Десятичные цифры
50,0% (512 штатов)	а	б	c	d	е	ж	0	грамм	час	я	0abc	0def	0Гхи	(0–7) (0–7) (0–7)	Три маленькие цифры	51,2% (512 штатов)
37,5% (384 государства)	а	б	c	d	е	ж	1	0	0	я	0abc	0def	100я	(0–7) (0–7) (8–9)	Две маленькие цифры, один большой	38,4% (384 государства)
	а	б	c	грамм	час	ж	1	0	1	я	0abc	100ж	0Гхи	(0–7) (8–9) (0–7)
	грамм	час	c	d	е	ж	1	1	0	я	100c	0def	0Гхи	(8–9) (0–7) (0–7)
9,375% (96 штатов)	грамм	час	c	0	0	ж	1	1	1	я	100c	100ж	0Гхи	(8–9) (8–9) (0–7)	Одна маленькая цифра, два больших	9,6% (96 штатов)
	d	е	c	0	1	ж	1	1	1	я	100c	0def	100я	(8–9) (0–7) (8–9)
	а	б	c	1	0	ж	1	1	1	я	0abc	100ж	100я	(0–7) (8–9) (8–9)
3,125% (32 штата, 8 использовано)	Икс	Икс	c	1	1	ж	1	1	1	я	100c	100ж	100я	(8–9) (8–9) (8–9)	Три большие цифры, биты b9 и b8 - это все равно	0,8% (8 штатов)

Биты b7, b4 и b0 (c, ж и я) проходят через кодировку без изменений и не влияют на значение других битов. Остальные семь битов можно рассматривать как семибитное кодирование трех цифр с основанием 5.

Биты b8 и b9 не нужны и игнорируется при декодировании DPD-групп с тремя большими цифрами (помечены как «x» в последней строке таблицы выше), но при кодировании заполняются нулями.

Восемь десятичных значений, все цифры которых равны 8 или 9, имеют четыре кодировки каждое. Биты, отмеченные x в приведенной выше таблице, игнорируются при вводе, но всегда будут равны 0 в вычисленных результатах (8 × 3 = 24 нестандартных кодирования заполняют в промежутке между 10³ = 1000 и 2¹⁰ = 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

Смотрите также

дальнейшее чтение

Коулишоу, Майкл Фредерик (2003-02-25) [2002-05-20, 2001-01-27]. Написано в Ковентри, Великобритания. «Десятичный в двоичный кодер / декодер» (Патент США). Армонк, Нью-Йорк, США: Международная корпорация бизнес-машин (IBM). US6525679B1. Получено 2018-07-18 [1] и Коулишоу, Майкл Фредерик (2007-11-07) [2004-01-14, 2002-08-14, 2001-09-24, 2001-01-27]. Написано в Винчестере, Хэмпшир, Великобритания. «Десятичный в двоичный кодер / декодер» (Европейский патент). Армонк, Нью-Йорк, США: Международная корпорация бизнес-машин (IBM). EP1231716A2. Получено 2018-07-18. [2][3][4] (NB. Этот патент касается DPD.)
Бонтен, Джо Х. М. (2009-10-06) [2006-10-05]. «Упакованное десятичное кодирование IEEE-754-2008». В архиве из оригинала 2018-07-11. Получено 2018-07-11. (NB. Более старую версию можно найти здесь: Упакованное десятичное кодирование IEEE-754r.)
Савард, Джон Дж. Г. (2018) [2007]. «Кодирование Чен – Хо и плотно упакованная десятичная дробь». квадиблок. В архиве из оригинала 2018-07-03. Получено 2018-07-16.

[Cowlishaw_2002-1] а ^б Коулишоу, Майкл Фредерик (2002-08-07) [май 2002]. «Плотно упакованное десятичное кодирование». Протоколы IEE - Компьютеры и цифровые методы. Лондон, Великобритания: Институт инженеров-электриков (IEE). 149 (3): 102–104. Дои:10.1049 / ip-cdt: 20020407. ISSN 1350-2387. Получено 2016-02-07.

[Cowlishaw_2000_CH-2] Коулишоу, Майкл Фредерик (2014) [июнь 2000]. "Краткое описание кодирования десятичных данных Чен-Хо". IBM. В архиве из оригинала от 24.09.2015. Получено 2016-02-07.

[IEEE-754_2008-3] IEEE Computer Society (29 августа 2008 г.). Стандарт IEEE для арифметики с плавающей запятой. IEEE. Дои:10.1109 / IEEESTD.2008.4610935. ISBN 978-0-7381-5753-5. IEEE Std 754-2008. Получено 2016-02-08.

[ISO-60559_2011-4] ISO / IEC / IEEE 60559: 2011. 2011. В архиве из оригинала 2020-06-03. Получено 2016-02-08.

[Cowlishaw_2000-5] Коулишоу, Майкл Фредерик (2007-02-13) [2000-10-03]. "Краткое описание плотно упакованного десятичного кодирования". IBM. В архиве из оригинала от 24.09.2015. Получено 2016-02-07.

[1]

[2]

[3]

[4]

[5]