stringtranslate.com

Кодирование Чена–Хо

Кодировка Чэнь-Хо — это альтернативная система двоичного кодирования десятичных цифр, которая эффективно использует память.

Традиционная система двоичного кодирования десятичных цифр, известная как двоично-десятичное кодирование (BCD), использует четыре бита для кодирования каждой цифры, что приводит к значительной потере пропускной способности двоичных данных (поскольку четыре бита могут хранить 16 состояний, а используются для хранения только 10) [1] даже при использовании упакованного BCD .

Кодирование сокращает требования к хранению двух десятичных цифр (100 состояний) с 8 до 7 бит, а трех десятичных цифр (1000 состояний) с 12 до 10 бит, используя только простые булевы преобразования, избегая сложных арифметических операций, таких как преобразование оснований .

История

В том, что, по-видимому, было множественным открытием , некоторые концепции, лежащие в основе того, что позже стало известно как кодирование Чэнь-Хо, были независимо разработаны Теодором М. Герцем в 1969 году [2] и Тянь Чи Ченом (陳天機) (1928–) [3] [4] [5] [6] в 1971 году.

Герц из Роквелла подал заявку на патент на свое кодирование в 1969 году, который был выдан в 1971 году. [2]

Чэнь впервые обсудил свои идеи с Ирвингом Цзе Хо (何宜慈) (1921–2003) [7] [8] [9] [10] в 1971 году. Чэнь и Хо оба работали в IBM в то время, хотя и в разных местах. [11] [12] Чэнь также консультировался с Фрэнком Чин Туном [13] , чтобы независимо проверить результаты своих теорий. [12] IBM подала патент на их имя в 1973 году, который был выдан в 1974 году. [14] По крайней мере к 1973 году ранняя работа Герца должна была быть им известна, поскольку патент ссылается на его патент как на предшествующий уровень техники . [14]

При участии Джозефа Д. Ратледжа и Джона К. Макферсона [15] окончательная версия кодировки Чена–Хо была распространена внутри IBM в 1974 году [16] и опубликована в 1975 году в журнале Communications of the ACM . [15] [17] Эта версия включала несколько уточнений, в первую очередь связанных с применением системы кодировки. Она представляет собой префиксный код типа Хаффмана .

Кодирование упоминалось как схема Чена и Хо в 1975 году [18] , кодирование Чена в 1982 году [19] и стало известно как кодирование Чена–Хо или алгоритм Чена–Хо с 2000 года. [17] После подачи патентной заявки на него в 2001 году [20] Майкл Ф. Коулишоу опубликовал дальнейшее усовершенствование кодирования Чена–Хо, известное как плотно упакованное десятичное (DPD) кодирование, в IEE Proceedings – Computers and Digital Techniques в 2002 году. [21] [22] Впоследствии DPD было принято в качестве десятичного кодирования, используемого в стандартах IEEE 754-2008 и ISO/IEC/IEEE 60559:2011 для чисел с плавающей точкой .

Приложение

Чэнь отметил, что цифры от нуля до семи были просто закодированы с использованием трех двоичных цифр соответствующей восьмеричной группы. Он также предположил, что можно использовать флаг для идентификации другой кодировки для цифр восемь и девять, которые будут закодированы с использованием одного бита.

На практике к потоку входных битов применяется ряд булевых преобразований, сжимающих закодированные в BCD цифры с 12 бит на три цифры до 10 бит на три цифры. Обратные преобразования используются для декодирования полученного закодированного потока в BCD. Эквивалентные результаты также могут быть достигнуты с помощью таблицы поиска .

Кодирование Чена-Хо ограничено кодированием наборов из трех десятичных цифр в группы по 10 бит (так называемые деклеты ). [1] Из 1024 состояний, возможных при использовании 10 бит, оно оставляет неиспользованными только 24 состояния [1] (при этом биты don't care обычно устанавливаются в 0 при записи и игнорируются при чтении). При потерях всего 2,34% оно дает на 20% более эффективное кодирование, чем BCD с одной цифрой в 4 битах. [12] [17]

И Герц, и Чен также предложили похожие, но менее эффективные схемы кодирования для сжатия наборов из двух десятичных цифр (требующих 8 бит в BCD) в группы по 7 бит. [2] [12]

Большие наборы десятичных цифр можно разделить на трех- и двузначные группы. [2]

В патентах также обсуждается возможность адаптации схемы к цифрам, закодированным в любых других десятичных кодах, кроме 8-4-2-1 BCD , [2] например, Excess-3 , [2] Excess-6 , Jump-at-2 , Jump-at-8 , Gray , Glixon , O'Brien type-I и коде Gray–Stibitz . [a] Те же принципы можно применить и к другим основаниям.

В 1973 году некоторая форма кодирования Чена-Хо, по-видимому, использовалась в аппаратном обеспечении преобразования адресов дополнительной функции эмуляции IBM 7070 / 7074 для компьютеров IBM System/370 Model 165 и 370 Model 168. [23] [24]

В одном известном приложении 128-битный регистр используется для хранения 33 десятичных цифр с трехзначным показателем степени, что фактически не меньше того, что можно было бы получить с помощью двоичного кодирования (тогда как для кодирования BCD потребовалось бы 144 бита для хранения того же количества цифр).

Кодировки для двух десятичных цифр

Кодирование Герца

Раннее кодирование Чена–Хо, метод А

Раннее кодирование Чена–Хо, метод B

Запатентованная и окончательная кодировка Чена–Хо

Кодировки для трех десятичных цифр

Кодирование Герца

Раннее кодирование Чэнь-Хо

Запатентованное кодирование Чена–Хо

Окончательное кодирование Чена–Хо

Эффективность хранения

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

Примечания

  1. ^ Некоторые 4-битные десятичные коды особенно хорошо подходят в качестве альтернативы коду 8-4-2-1 BCD : код Jump-at-8 использует те же значения для упорядоченных состояний от 0 до 7, тогда как в кодах Грея BCD и Гликсона значения для состояний от 0 до 7 по-прежнему из того же набора, но упорядочены по-другому (что, однако, прозрачно для кодировок Герца, Чена–Хо или плотно упакованной десятичной (DPD), поскольку они проходят через биты без изменений). В этих четырех кодах старший бит может использоваться как флаг, обозначающий «большие» значения. Для двух «больших» значений все биты, кроме одного, остаются статическими (два средних бита всегда равны нулю для кода 8-4-2-1 и один для кода Jump-at-8, в то время как для кода Грея BCD один бит установлен, а другой очищен, тогда как для кода Гликсона два нижних бита всегда равны нулю, а один бит инвертирован, таким образом, два «больших» значения прозрачно меняются местами), требуя лишь незначительных изменений в кодировке. Три других кода можно удобно разделить на группы по восемь и два состояния, также содержащие значения из двух диапазонов последовательных битовых комбинаций. В случае кодов Excess-6 BCD и Jump-at-2 старший бит все еще может использоваться для различения двух групп, однако, по сравнению с кодом Jump-at-8, группа малых значений теперь содержит только два состояния, а большая группа содержит восемь больших значений. В случае кода О'Брайена типа I и Грея-Стибитца следующий по значимости бит может служить флаговым битом, а оставшиеся биты снова образуют две группы последовательных значений. Поэтому эти различия остаются прозрачными для кодирования.

Ссылки

  1. ^ abc Мюллер, Жан-Мишель; Бризебар, Николя; де Динешен, Флоран; Жаннерод, Клод-Пьер; Лефевр, Винсент; Мелькионд, Гийом; Револь, Натали ; Стеле, Дэмиен; Торрес, Серж (2010). Справочник по арифметике с плавающей запятой (1-е изд.). Биркхойзер . дои : 10.1007/978-0-8176-4705-6. ISBN 978-0-8176-4704-9. LCCN  2009939668.
  2. ^ abcdefgh Герц, Теодор М. (1971-11-02) [1969-12-15]. "Система для компактного хранения десятичных чисел" (Патент). Уиттиер, Калифорния, США: North American Rockwell Corporation . Патент США US3618047A . Получено 2018-07-18 .(8 страниц) [1][2] (Примечание. В этом истекшем патенте обсуждается система кодирования, очень похожая на Chen-Ho, также указанная в качестве предшествующего уровня техники в патенте Chen–Ho.)
  3. ^ "We hear that..." Physics Today . Vol. 12, no. 2. American Institute of Physics (AIP). 1959. p. 62. doi :10.1063/1.3060696. ISSN  0031-9228. Архивировано из оригинала 24.06.2020 . Получено 24.06.2020 .(1 страница)
  4. ^ Паркер, Дэвид (2003). "Почетный член - Цитата - Профессор Чэнь Тянь Чи" (PDF) . Список почетных членов. Китайский университет Гонконга (CUHK). Архивировано (PDF) из оригинала 2014-12-25 . Получено 2020-06-24 .(2 страницы)
  5. ^ "CHEN Tien Chi". Китайский университет Гонконга (CUHK). 2013-01-12. Архивировано из оригинала 2015-10-23 . Получено 2016-02-07 .
  6. ^ Wong, Andrew WF (2014-08-15) [2014-07-04, 2014-06-23, 2013-09-16, 2007-07-16, 2007-06-07, 2007-06-04, 2007-05-20, 2007-02-16]. 陳天機 Chen Tien Chi: 如夢令 Ru Meng Ling (Как будто мечтая). Классические китайские стихи на английском языке (на китайском и английском языках). Перевод Hongfa (宏發), Huang (黃). Архивировано из оригинала 2020-06-25 . Получено 2020-06-25 .
  7. ^ "Ученым поручено создать научно-ориентированный промышленный парк". Science Bulletin . Vol. 11, no. 2. Taipei, Taiwan: National Science Council . 1979-02-01. p. 1. ISSN  1607-3509. OCLC  1658005. Архивировано из оригинала 25-06-2020 . Получено 24-06-2020 .(1 страница) [3]
  8. ^ Ценг, Ли-Лин (1988-04-01). "Лидерство в сфере высоких технологий: Ирвинг Т. Хо". Taiwan Info . Архивировано из оригинала 2016-02-08 . Получено 2016-02-08 .[4]
  9. ^ «Тайваньская Кремниевая долина: Эволюция промышленного парка Синьчжу». Институт международных исследований Фримена Спогли . Стэнфордский университет , Стэнфорд, Калифорния, США. 2000-01-11. Архивировано из оригинала 2020-06-26 . Получено 2017-05-02 .
  10. ^ "Ирвинг Т. Хо". San Jose Mercury News . 2003-04-26. Архивировано из оригинала 2020-06-25 . Получено 2020-06-25 .
  11. ↑ Чэнь, Тянь Чи (1971-03-12). Схема преобразования десятично-двоичных целых чисел (внутренняя записка Ирвингу Цзе Хо). Исследовательская лаборатория IBM в Сан-Хосе, Сан-Хосе, Калифорния, США: IBM .
  12. ^ abcdefghij Чен, Тянь Чи (1971-03-29). Сжатие десятичных чисел (PDF) (Внутренняя записка Ирвингу Цзе Хо). Исследовательская лаборатория IBM в Сан-Хосе, Сан-Хосе, Калифорния, США: IBM . стр. 1–4. Архивировано (PDF) из оригинала 17.10.2012 . Получено 07.02.2016 .(4 страницы)
  13. ^ IBM资深专家Фрэнк Тунг博士8月4日来我校演讲 [Старший эксперт IBM доктор Фрэнк Тунг пришел в нашу школу 4 августа, чтобы выступить с речью] (на китайском и английском языках). Гуанчжоу, Китай: Южно-Китайский технологический университет (SCUT). 04 августа 2004 г. Архивировано из оригинала 8 декабря 2004 г. Проверено 6 февраля 2016 г.
  14. ^ abcdefghi Chen, Tien Chi; Ho, Irving Tze (1974-10-15) [1973-06-18]. Написано в Сан-Хосе, Калифорния, США и Покипси, Нью-Йорк, США. "Аппарат преобразования двоично-десятичных чисел" (Патент). Армонк, Нью-Йорк, США: International Business Machines Corporation (IBM). Патент США US3842414A . Получено 2018-07-18 .(14 страниц) [5][6] (Примечание. Этот истекший патент касается алгоритма Чена–Хо.)
  15. ^ abcdefghijkl Chen, Tien Chi; Ho, Irving Tze (январь 1975 г.) [апрель 1974 г.]. «Эффективное представление десятичных данных с точки зрения хранения». Communications of the ACM . 18 (1). Исследовательская лаборатория IBM San Jose, Сан-Хосе, Калифорния, США и Отделение продуктов IBM Systems, Покипси/Ист-Фишкилл, Нью-Йорк, США: Ассоциация вычислительной техники : 49–52. doi : 10.1145/360569.360660 . ISSN  0001-0782. S2CID  14301378.(4 страницы)
  16. ^ Чэнь, Тьен Чи; Хо, Ирвинг Цзе (1974-06-25). «Эффективное представление десятичных данных с точки зрения хранения». Исследовательский отчет RJ 1420 (технический отчет). Исследовательская лаборатория IBM в Сан-Хосе, Сан-Хосе, Калифорния, США: IBM .
  17. ^ abcd Cowlishaw, Michael Frederic (2014) [июнь 2000]. "A Summary of Chen-Ho Decimal Data encoding". IBM . Архивировано из оригинала 2015-09-24 . Получено 2016-02-07 .
  18. ^ Смит, Алан Джей (август 1975 г.) [апрель 1975 г.]. «Комментарии к статье TC Chen и IT Ho». Communications of the ACM . 18 (8). Калифорнийский университет , Беркли, Калифорния, США: 463. doi :10.1145/360933.360986. eISSN  1557-7317. ISSN  0001-0782. S2CID  20910959. CODEN  CACMA2. Архивировано из оригинала 2020-06-03 . Получено 2020-06-03 .(1 страница) (Примечание. Публикация, в которой также обсуждаются альтернативы и вариации Чэнь–Хо.)
  19. ^ Сакс-Дэвис, Рон (1 ноября 1982 г.) [январь 1982 г.]. «Применение избыточных представлений чисел в десятичной арифметике». The Computer Journal . 25 (4). Кафедра компьютерных наук, Университет Монаша , Клейтон, Виктория, Австралия: Wiley Heyden Ltd : 471–477. doi : 10.1093/comjnl/25.4.471 .(7 страниц)
  20. ^ Cowlishaw, Michael Frederic (2003-02-25) [2002-05-20, 2001-01-27]. Написано в Ковентри, Великобритания. "Десятично-двоичный кодер/декодер" (Патент). Армонк, Нью-Йорк, США: International Business Machines Corporation (IBM). Патент США US6525679B1 . Получено 2018-07-18(6 страниц) [7] и Cowlishaw, Michael Frederic (2007-11-07) [2004-01-14, 2002-08-14, 2001-09-24, 2001-01-27]. Написано в Винчестере, Хэмпшир, Великобритания. "Десятично-двоичный кодер/декодер" (Патент). Армонк, Нью-Йорк, США: International Business Machines Corporation (IBM). Европейский патент EP1231716A2 . Получено 2018-07-18 .(9 страниц) [8][9][10] (Примечание. В этом патенте о DPD также обсуждается алгоритм Чена–Хо.)
  21. ^ Cowlishaw, Michael Frederic (2002-08-07) [май 2002]. "Densely Packed Decimal Encoding". IEE Proceedings - Computers and Digital Techniques . 149 (3). Лондон, Великобритания: Institution of Electrical Engineers (IEE): 102–104. doi :10.1049/ip-cdt:20020407. ISSN  1350-2387. Архивировано из оригинала 20 мая 2017 г. Получено 07 февраля 2016 г.(3 страницы)
  22. ^ Cowlishaw, Michael Frederic (2007-02-13) [2000-10-03]. "A Summary of Densely Packed Decimal encoding". IBM . Архивировано из оригинала 2015-09-24 . Получено 2016-02-07 .
  23. ^ Savard, John JG (2018) [2007]. "Chen-Ho Encoding and Densely Packed Decimal". quadibloc . Архивировано из оригинала 2018-07-03 . Получено 2018-07-16 .
  24. ^ 7070/7074 Compatibility Feature для IBM System/370 Models 165, 165 II и 168 (PDF) (2-е изд.). IBM . Июнь 1973 [1970]. GA22-6958-1 (Файл № 5/370-13). Архивировано (PDF) из оригинала 2018-07-22 . Получено 2018-07-21 .(31+5 страниц)

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