stringtranslate.com

Codificación Chen-Ho

La codificación Chen-Ho es un sistema alternativo de codificación binaria para dígitos decimales con uso eficiente de la memoria .

El sistema tradicional de codificación binaria para dígitos decimales, conocido como decimal codificado en binario (BCD), utiliza cuatro bits para codificar cada dígito, lo que genera un desperdicio significativo de ancho de banda de datos binarios (ya que cuatro bits pueden almacenar 16 estados y se utilizan para almacenar solo 10), [1] incluso cuando se utiliza BCD empaquetado .

La codificación reduce los requisitos de almacenamiento de dos dígitos decimales (100 estados) de 8 a 7 bits, y los de tres dígitos decimales (1000 estados) de 12 a 10 bits utilizando solo transformaciones booleanas simples, evitando operaciones aritméticas complejas como una conversión de base .

Historia

En lo que parece haber sido un descubrimiento múltiple , algunos de los conceptos detrás de lo que más tarde se conocería como codificación Chen-Ho fueron desarrollados independientemente por Theodore M. Hertz en 1969 [2] y por Tien Chi Chen (陳天機) (1928–) [3] [4] [5] [6] en 1971.

Hertz de Rockwell presentó una patente para su codificación en 1969, que le fue concedida en 1971. [2]

Chen discutió por primera vez sus ideas con Irving Tze Ho (何宜慈) (1921–2003) [7] [8] [9] [10] en 1971. Chen y Ho trabajaban para IBM en ese momento, aunque en diferentes lugares. [11] [12] Chen también consultó con Frank Chin Tung [13] para verificar los resultados de sus teorías de forma independiente. [12] IBM presentó una patente a su nombre en 1973, que fue concedida en 1974. [14] Al menos en 1973, el trabajo anterior de Hertz debe haber sido conocido por ellos, ya que la patente cita su patente como técnica anterior . [14]

Con la colaboración de Joseph D. Rutledge y John C. McPherson, [15] la versión final de la codificación Chen-Ho se distribuyó dentro de IBM en 1974 [16] y se publicó en 1975 en la revista Communications of the ACM . [15] [17] Esta versión incluía varias mejoras, principalmente relacionadas con la aplicación del sistema de codificación. Constituye un código de prefijo similar al de Huffman .

La codificación se denominó esquema de Chen y Ho en 1975, [18] codificación de Chen en 1982 [19] y se conoció como codificación Chen-Ho o algoritmo Chen-Ho desde 2000. [17] Después de haber presentado una patente para ello en 2001, [20] Michael F. Cowlishaw publicó un refinamiento adicional de la codificación Chen-Ho conocida como codificación decimal densamente empaquetada (DPD) en IEE Proceedings – Computers and Digital Techniques en 2002. [21] [22] Posteriormente, DPD se adoptó como la codificación decimal utilizada en los estándares de punto flotante IEEE 754-2008 e ISO/IEC/IEEE 60559:2011 .

Solicitud

Chen observó que los dígitos del cero al siete se codificaban simplemente utilizando tres dígitos binarios del grupo octal correspondiente . También postuló que se podría utilizar una bandera para identificar una codificación diferente para los dígitos ocho y nueve, que se codificarían utilizando un solo bit.

En la práctica, se aplica una serie de transformaciones booleanas al flujo de bits de entrada, comprimiendo los dígitos codificados en BCD de 12 bits por cada tres dígitos a 10 bits por cada tres dígitos. Se utilizan transformaciones inversas para decodificar el flujo codificado resultante a BCD. También se pueden lograr resultados equivalentes mediante el uso de una tabla de consulta .

La codificación Chen-Ho se limita a codificar conjuntos de tres dígitos decimales en grupos de 10 bits (los llamados declets ). [1] De los 1024 estados posibles al usar 10 bits, deja solo 24 estados sin usar [1] ( los bits que no importan generalmente se establecen en 0 en escritura e ignoran en lectura). Con solo un 2,34% de desperdicio, brinda una codificación un 20% más eficiente que BCD con un dígito en 4 bits. [12] [17]

Tanto Hertz como Chen también propusieron esquemas de codificación similares, pero menos eficientes, para comprimir conjuntos de dos dígitos decimales (que requieren 8 bits en BCD) en grupos de 7 bits. [2] [12]

Los conjuntos más grandes de dígitos decimales podrían dividirse en grupos de tres y dos dígitos. [2]

Las patentes también discuten la posibilidad de adaptar el esquema a dígitos codificados en cualquier otro código decimal que no sea 8-4-2-1 BCD , [2] como por ejemplo Excess-3 , [2] Excess-6 , Jump-at-2 , Jump-at-8 , Gray , Glixon , O'Brien tipo I y código Gray–Stibitz . [a] Los mismos principios también podrían aplicarse a otras bases.

En 1973, parece que se utilizó alguna forma de codificación Chen-Ho en el hardware de conversión de direcciones de la función de emulación opcional IBM 7070/7074 para las computadoras IBM System/370 Modelo 165 y 370 Modelo 168. [23] [24]

Una aplicación destacada utiliza un registro de 128 bits para almacenar 33 dígitos decimales con un exponente de tres dígitos, efectivamente no menos de lo que podría lograrse usando codificación binaria (mientras que la codificación BCD necesitaría 144 bits para almacenar la misma cantidad de dígitos).

Codificaciones para dos dígitos decimales

Codificación de Hertz

Codificación Chen-Ho temprana, método A

Codificación Chen-Ho temprana, método B

Codificación Chen-Ho patentada y definitiva

Codificaciones para tres dígitos decimales

Codificación de Hertz

Codificación temprana de Chen-Ho

Codificación patentada Chen-Ho

Codificación final de Chen-Ho

Eficiencia de almacenamiento

Véase también

Notas

  1. ^ Algunos códigos decimales de 4 bits son particularmente adecuados como alternativas al código BCD 8-4-2-1 : el código Jump-at-8 usa los mismos valores para los estados ordenados 0 a 7, mientras que en los códigos Gray BCD y Glixon los valores para los estados 0 a 7 siguen siendo del mismo conjunto, pero ordenados de manera diferente (lo que, sin embargo, es transparente para las codificaciones Hertz, Chen–Ho o decimal densamente empaquetado (DPD), ya que pasan a través de los bits sin alteraciones). En estos cuatro códigos, el bit más significativo se puede usar como una bandera que denota valores "grandes". Para los dos valores "grandes", todos los bits menos uno permanecen estáticos (los dos bits del medio son siempre cero para el código 8-4-2-1 y uno para el código Jump-at-8, mientras que para el código Gray BCD un bit está establecido y el otro borrado, mientras que para el código Glixon los dos bits inferiores son siempre cero y un bit invertido, por lo que los dos valores "grandes" se intercambian de forma transparente), requiriendo solo adaptaciones menores en la codificación. Otros tres códigos se pueden dividir convenientemente en grupos de ocho y dos estados también, que contienen valores de dos rangos de patrones de bits consecutivos. En el caso de los códigos BCD Excess-6 y Jump-at-2 , el bit más significativo aún se puede usar para distinguir entre los dos grupos, sin embargo, en comparación con el código Jump-at-8, el grupo de valores pequeños ahora contiene solo dos estados y el grupo más grande contiene los ocho valores más grandes. En el caso del código de Gray-Stibitz y del código O'Brien tipo I , el siguiente bit más significativo puede servir como bit de bandera, mientras que los bits restantes forman dos grupos de valores consecutivos. Por lo tanto, estas diferencias siguen siendo transparentes para la codificación.

Referencias

  1. ^ abc Müller, Jean-Michel; Brisebarre, Nicolás; de Dinechin, Florent; Jeannerod, Claude-Pierre; Lefèvre, Vicente; Melquiond, Guillaume; Revol, Nathalie ; Stehlé, Damián; Torres, Serge (2010). Manual de aritmética de coma flotante (1 ed.). Birkhäuser . doi :10.1007/978-0-8176-4705-6. ISBN 978-0-8176-4704-9. Número de serie LCCN  2009939668.
  2. ^ abcdefgh Hertz, Theodore M. (1971-11-02) [1969-12-15]. "Sistema para el almacenamiento compacto de números decimales" (Patente). Whittier, California, EE. UU.: North American Rockwell Corporation . Patente estadounidense US3618047A . Consultado el 18 de julio de 2018 .(8 páginas) [1][2] (NB. Esta patente vencida analiza un sistema de codificación muy similar a Chen-Ho, también citado como técnica anterior en la patente Chen–Ho).
  3. ^ "Oímos que..." Physics Today . Vol. 12, no. 2. American Institute of Physics (AIP). 1959. p. 62. doi :10.1063/1.3060696. ISSN  0031-9228. Archivado desde el original el 24 de junio de 2020 . Consultado el 24 de junio de 2020 .(1 página)
  4. ^ Parker, David (2003). "Honorary Fellow - A Citation - Professor Chen Tien Chi" (PDF) . Lista de miembros honorarios. Universidad China de Hong Kong (CUHK). Archivado (PDF) desde el original el 25 de diciembre de 2014. Consultado el 24 de junio de 2020 .(2 páginas)
  5. ^ "CHEN Tien Chi". Universidad China de Hong Kong (CUHK). 12 de enero de 2013. Archivado desde el original el 23 de octubre de 2015. Consultado el 7 de febrero de 2016 .
  6. ^ Wong, Andrew WF (15 de agosto de 2014) [4 de julio de 2014, 23 de junio de 2014, 16 de septiembre de 2013, 16 de julio de 2007, 7 de junio de 2007, 4 de junio de 2007, 20 de mayo de 2007, 16 de febrero de 2007]. 陳天機 Chen Tien Chi: 如夢令 Ru Meng Ling (Como si soñara). Poemas chinos clásicos en inglés (en chino e inglés). Traducido por Hongfa (宏發), Huang (黃). Archivado desde el original el 25 de junio de 2020. Consultado el 25 de junio de 2020 .
  7. ^ "Se le asigna a un científico la tarea de crear un parque industrial orientado a la ciencia". Science Bulletin . Vol. 11, no. 2. Taipei, Taiwán: Consejo Nacional de Ciencias . 1 de febrero de 1979. pág. 1. ISSN  1607-3509. OCLC  1658005. Archivado desde el original el 25 de junio de 2020. Consultado el 24 de junio de 2020 .(1 página) [3]
  8. ^ Tseng, Li-Ling (1 de abril de 1988). "Liderazgo en alta tecnología: Irving T. Ho". Taiwan Info . Archivado desde el original el 8 de febrero de 2016. Consultado el 8 de febrero de 2016 .[4]
  9. ^ "Silicon Valley de Taiwán: la evolución del parque industrial de Hsinchu". Instituto Freeman Spogli de Estudios Internacionales . Universidad de Stanford , Stanford, California, EE. UU. 11 de enero de 2000. Archivado desde el original el 26 de junio de 2020. Consultado el 2 de mayo de 2017 .
  10. ^ "Irving T. Ho". San Jose Mercury News . 26 de abril de 2003. Archivado desde el original el 25 de junio de 2020. Consultado el 25 de junio de 2020 .
  11. ^ Chen, Tien Chi (12 de marzo de 1971). Esquema de conversión de números enteros decimales a binarios (Memorando interno a Irving Tze Ho). IBM San Jose Research Laboratory, San José, California, EE. UU.: IBM .
  12. ^ abcdefghij Chen, Tien Chi (29 de marzo de 1971). Compresión de números decimales (PDF) (Memorando interno a Irving Tze Ho). IBM San Jose Research Laboratory, San José, California, EE. UU.: IBM . pp. 1–4. Archivado (PDF) desde el original el 17 de octubre de 2012. Consultado el 7 de febrero de 2016 .(4 páginas)
  13. ^ IBM资深专家Frank Tung博士8月4日来我校演讲 [El Dr. Frank Tung, experto senior de IBM, vino a nuestra escuela el 4 de agosto para dar un discurso] (en chino e inglés). Guangzhou, China: Universidad Tecnológica del Sur de China (SCUT). 2004-08-04. Archivado desde el original el 8 de diciembre de 2004 . Consultado el 6 de febrero de 2016 .
  14. ^ abcdefghi Chen, Tien Chi; Ho, Irving Tze (1974-10-15) [1973-06-18]. Escrito en San José, California, EE. UU. y Poughkeepsie, Nueva York, EE. UU. "Aparato de conversión decimal codificado en binario" (Patente). Armonk, Nueva York, EE. UU.: International Business Machines Corporation (IBM). Patente estadounidense US3842414A . Consultado el 18 de julio de 2018 .(14 páginas) [5][6] (NB: Esta patente vencida trata sobre el algoritmo Chen–Ho).
  15. ^ abcdefghijkl Chen, Tien Chi; Ho, Irving Tze (enero de 1975) [abril de 1974]. "Representación de datos decimales con eficiencia de almacenamiento". Comunicaciones de la ACM . 18 (1). IBM San Jose Research Laboratory, San José, California, EE. UU. e IBM Systems Products Division, Poughkeepsie/East Fishkill, Nueva York, EE. UU.: Association for Computing Machinery : 49–52. doi : 10.1145/360569.360660 . ISSN  0001-0782. S2CID  14301378.(4 páginas)
  16. ^ Chen, Tien Chi; Ho, Irving Tze (25 de junio de 1974). "Representación de datos decimales con eficiencia de almacenamiento". Informe de investigación RJ 1420 (informe técnico). IBM San Jose Research Laboratory, San José, California, EE. UU.: IBM .
  17. ^ abcd Cowlishaw, Michael Frederic (2014) [junio de 2000]. "Un resumen de la codificación de datos decimales Chen-Ho". IBM . Archivado desde el original el 24 de septiembre de 2015 . Consultado el 7 de febrero de 2016 .
  18. ^ Smith, Alan Jay (agosto de 1975) [abril de 1975]. "Comentarios sobre un artículo de TC Chen e IT Ho". Comunicaciones de la ACM . 18 (8). Universidad de California , Berkeley, California, EE. UU.: 463. doi :10.1145/360933.360986. eISSN  1557-7317. ISSN  0001-0782. S2CID  20910959. CODEN  CACMA2. Archivado desde el original el 2020-06-03 . Consultado el 2020-06-03 .(1 página) (NB: Una publicación que también analiza las alternativas y variaciones de Chen-Ho).
  19. ^ Sacks-Davis, Ron (1982-11-01) [enero de 1982]. "Aplicaciones de representaciones numéricas redundantes a la aritmética decimal". The Computer Journal . 25 (4). Departamento de Ciencias de la Computación, Universidad de Monash , Clayton, Victoria, Australia: Wiley Heyden Ltd : 471–477. doi : 10.1093/comjnl/25.4.471 .(7 páginas)
  20. ^ Cowlishaw, Michael Frederic (2003-02-25) [2002-05-20, 2001-01-27]. Escrito en Coventry, Reino Unido. "Decimal to binary coder/decoder" (Patente). Armonk, Nueva York, EE. UU.: International Business Machines Corporation (IBM). Patente estadounidense US6525679B1 . Consultado el 18 de julio de 2018.(6 páginas) [7] y Cowlishaw, Michael Frederic (2007-11-07) [2004-01-14, 2002-08-14, 2001-09-24, 2001-01-27]. Escrito en Winchester, Hampshire, Reino Unido. "Decimal to binary coder/decoder" (Patente). Armonk, Nueva York, EE. UU.: International Business Machines Corporation (IBM). Patente europea EP1231716A2 . Consultado el 18 de julio de 2018 .(9 páginas) [8][9][10] (NB. Esta patente sobre DPD también analiza el algoritmo Chen-Ho).
  21. ^ Cowlishaw, Michael Frederic (7 de agosto de 2002) [mayo de 2002]. "Codificación decimal densamente empaquetada". Actas del IEE - Computadoras y técnicas digitales . 149 (3). Londres, Reino Unido: Institution of Electrical Engineers (IEE): 102–104. doi :10.1049/ip-cdt:20020407. ISSN  1350-2387. Archivado desde el original el 20 de mayo de 2017 . Consultado el 7 de febrero de 2016 .(3 páginas)
  22. ^ Cowlishaw, Michael Frederic (13 de febrero de 2007) [3 de octubre de 2000]. "Un resumen de la codificación decimal densamente empaquetada". IBM . Archivado desde el original el 24 de septiembre de 2015 . Consultado el 7 de febrero de 2016 .
  23. ^ Savard, John JG (2018) [2007]. "Codificación Chen-Ho y decimales densamente empaquetados". quadibloc . Archivado desde el original el 2018-07-03 . Consultado el 2018-07-16 .
  24. ^ Característica de compatibilidad 7070/7074 para IBM System/370 modelos 165, 165 II y 168 (PDF) (2.ª ed.). IBM . Junio ​​de 1973 [1970]. GA22-6958-1 (N.º de archivo 5/370-13). Archivado (PDF) desde el original el 22 de julio de 2018. Consultado el 21 de julio de 2018 .(31+5 páginas)

Lectura adicional