Плотно упакованная десятичная дробь
Плотно упакованные десятичные числа ( 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 штата) | б9 | б8 | b7 | б6 | б5 | б4 | б3 | б2 | б1 | б0 | d2 | d1 | д0 | Закодированные значения | Описание | События (1000 штатов) | |
| 50.0% (512 штатов) | а | б | с | д | и | ж | 0 | г | час | я | 0 абв | 0 защита | 0 гхи | (0–7) (0–7) (0–7) | 3 маленькие цифры | 51.2% (512 штатов) | |
| 37.5% (384 штата) | а | б | с | д | и | ж | 1 | 0 | 0 | я | 0 абв | 0 защита | 100 я | (0–7) (0–7) (8–9) | 2 маленькие цифры, 1 большая цифра | 38.4% (384 штата) | |
| а | б | с | г | час | ж | 1 | 0 | 1 | я | 0 абв | 100 ф | 0 гхи | (0–7) (8–9) (0–7) | ||||
| г | час | с | д | и | ж | 1 | 1 | 0 | я | 100 с | 0 защита | 0 гхи | (8–9) (0–7) (0–7) | ||||
| 9.375% (96 штатов) | г | час | с | 0 | 0 | ж | 1 | 1 | 1 | я | 100 с | 100 ф | 0 гхи | (8–9) (8–9) (0–7) | 1 маленькая цифра, 2 большие цифры | 9.6% (96 штатов) | |
| д | и | с | 0 | 1 | ж | 1 | 1 | 1 | я | 100 с | 0 защита | 100 я | (8–9) (0–7) (8–9) | ||||
| а | б | с | 1 | 0 | ж | 1 | 1 | 1 | я | 0 абв | 100 ф | 100 я | (0–7) (8–9) (8–9) | ||||
| 3.125% (32 штата, 8 использовано) | х | х | с | 1 | 1 | ж | 1 | 1 | 1 | я | 100 с | 100 ф | 100 я | (8–9) (8–9) (8–9) | 3 большие цифры, b9, b8: плевать | 0.8% (8 штатов) | |
Биты b7, b4 и b0 ( c, f и i) передаются через кодировку без изменений и не влияют на значение других битов. Остальные семь битов можно считать семибитной кодировкой трех цифр по основанию 5.
Биты b8 и b9 не нужны и игнорируются при декодировании групп DPD с тремя большими цифрами (отмечены знаком «х» в последней строке таблицы выше), но при кодировании заполняются нулями.
Восемь десятичных значений, все цифры которых равны 8 или 9, имеют по четыре кодировки каждое.Биты, отмеченные x в таблице выше, игнорируются при вводе, но в вычисленных результатах всегда будут равны 0.(3 × 8 = 24 нестандартных кодировки заполняют пробел между 10 3 = 1000 и 2 10 − 1 = 1023.)
Примеры
[ редактировать ]В этой таблице показаны некоторые типичные десятичные числа и их кодировки в 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 |
См. также
[ редактировать ]- Двоично-десятичный код (BCD)
- Двоично-цело-десятичное число (BID)
- decimal32 формат с плавающей запятой
- формат чисел с плавающей запятой decimal64
- десятичный формат с плавающей запятой128
- РАДИКС ДЕКАБРЯ 50 / MOD40
- IBM СКВОЗЕ
Ссылки
[ редактировать ]- ^ Jump up to: а б Коулишоу, Майкл Фредерик (7 августа 2002 г.) [май 2002 г.]. «Плотно упакованное десятичное кодирование» . Труды IEE - Компьютеры и цифровая техника . 149 (3). Лондон, Великобритания: Институт инженеров-электриков : 102–104. дои : 10.1049/ip-cdt:20020407 . ISSN 1350-2387 . Архивировано из оригинала 20 мая 2017 г. Проверено 7 февраля 2016 г.
- ^ Коулишоу, Майкл Фредерик (2014) [июнь 2000 г.]. «Краткое описание кодирования десятичных данных Чен-Хо» . ИБМ . Архивировано из оригинала 24 сентября 2015 г. Проверено 7 февраля 2016 г.
- ^ Компьютерное общество IEEE (29 августа 2008 г.). Стандарт IEEE для арифметики с плавающей запятой . ИИЭЭ . дои : 10.1109/IEESTD.2008.4610935 . ISBN 978-0-7381-5753-5 . Стандарт IEEE 754-2008 . Проверено 8 февраля 2016 г.
- ^ ИСО/МЭК/ИИЭР 60559:2011 . 2011. Архивировано из оригинала 3 июня 2020 г. Проверено 8 февраля 2016 г.
- ^ Коулишоу, Майкл Фредерик (13 февраля 2007 г.) [03 октября 2000 г.]. «Краткое описание плотно упакованного десятичного кодирования» . ИБМ . Архивировано из оригинала 24 сентября 2015 г. Проверено 7 февраля 2016 г.
Дальнейшее чтение
[ редактировать ]- Коулишоу, Майкл Фредерик (25 февраля 2003 г.) [20 мая 2002 г., 27 января 2001 г.]. Написано в Ковентри, Великобритания. «Кодер/декодер из десятичных чисел в двоичные» (патент США). Армонк, Нью-Йорк, США: Международная корпорация Business Machines (IBM). US6525679B1 . Проверено 18 июля 2018 г. [1] и Коулишоу, Майкл Фредерик (7 ноября 2007 г.) [14 января 2004 г., 14 августа 2002 г., 24 сентября 2001 г., 27 января 2001 г.]. Написано в Винчестере, Хэмпшир, Великобритания. «Кодер/декодер из десятичных чисел в двоичные» (Европейский патент). Армонк, Нью-Йорк, США: Международная корпорация Business Machines (IBM). ЕР1231716А2 . Проверено 18 июля 2018 г. [2] [3] [4] (Примечание. Этот патент касается компании DPD.)
- Бонтен, Джо ХМ (6 октября 2009 г.) [05 октября 2006 г.]. «Упакованная десятичная кодировка IEEE-754-2008» . Гелдроп, Нидерланды. Архивировано из оригинала 11 июля 2018 г. Проверено 11 июля 2018 г. (Примечание. Более старую версию можно найти здесь: Packed Decimal Encoding IEEE-754r .)
- Савард, Джон Дж. Г. (2018) [2007]. «Кодирование Чена – Хо и плотно упакованная десятичная дробь» . четырехблок . Архивировано из оригинала 3 июля 2018 г. Проверено 16 июля 2018 г.