stringtranslate.com

Codificación Chen-Ho

La codificación Chen-Ho es un sistema alternativo de codificación binaria que ahorra memoria para dígitos decimales .

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 sólo 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 sólo 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 conoció como codificación Chen-Ho fueron desarrollados de forma independiente 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 fue concedida en 1971. [2]

Chen discutió sus ideas por primera vez 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 aportaciones de Joseph D. Rutledge y John C. McPherson, [15] la versión final de la codificación Chen-Ho circuló dentro de IBM en 1974 [16] y se publicó en 1975 en la revista Communications of the ACM . [15] [17] Esta versión incluyó 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 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 estaban simplemente codificados 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 dígitos codificados en BCD de 12 bits por tres dígitos a 10 bits por 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 mediante el uso de 10 bits, solo quedan 24 estados sin usar [1] (con bits de "no importa" generalmente establecidos en 0 al escribir e ignorados al leer). Con sólo un 2,34% de desperdicio, proporciona 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 se podrían dividir 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 fe 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 IBM 7070/7074 opcional 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, en realidad no menos de lo que se podría lograr 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 Hertz

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

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

Codificación Chen-Ho final y patentada

Codificaciones para tres dígitos decimales

Codificación Hertz

Codificación temprana de Chen-Ho

Codificación Chen-Ho patentada

Codificación final Chen-Ho

Eficiencia de almacenamiento

Ver 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 del 0 al 7, mientras que en Gray BCD y Glixon codifica los valores para los estados 0 a 7 siguen siendo del mismo conjunto, pero ordenados de manera diferente (lo cual, sin embargo, es transparente para las codificaciones Hertz, Chen-Ho o decimal densamente empaquetada (DPD), ya que pasan a través de los bits sin cambios) . En estos cuatro códigos, el bit más significativo se puede utilizar como indicador que indica valores "grandes". Para los dos valores "grandes", todos los bits excepto uno permanecen estáticos (los dos bits del medio son siempre cero para 8-4-2-1 y uno para el código Jump-at-8, mientras que para el código Gray BCD se establece un bit y el otro se borra, 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 sólo adaptaciones menores en la codificación. Otros tres códigos también se pueden dividir convenientemente en grupos de ocho y dos estados, que contienen valores de dos rangos de patrones de bits consecutivos. En el caso de los códigos BCD y Jump-at-2 Excess-6 , 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 pequeños Los valores ahora contienen solo dos estados y el grupo más grande contiene los ocho valores más grandes. En el caso del código O'Brien tipo I y Gray-Stibitz , el siguiente bit más significativo puede servir como bit de bandera, y los bits restantes forman nuevamente dos grupos de valores consecutivos. Por 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. LCCN  2009939668.
  2. ^ abcdefgh Hertz, Theodore M. (2 de noviembre de 1971) [15 de diciembre de 1969]. "Sistema de almacenamiento compacto de números decimales" (Patente). Whittier, California, Estados Unidos: 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. ^ "Escuchamos que..." Física Hoy . vol. 12, núm. 2. Instituto Americano de Física (AIP). 1959. pág. 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 pagina)
  4. ^ Parker, David (2003). "Miembro honorario - Una mención - Profesor Chen Tien Chi" (PDF) . Lista de becarios honorarios. La 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". La Universidad China de Hong Kong (CUHK). 2013-01-12. 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) [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 (Como si estuviera soñando). 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. ^ "A un científico se le encomendó la tarea de establecer un parque industrial orientado a la ciencia". Boletín científico . vol. 11, núm. 2. Taipei, Taiwán: Consejo Nacional de Ciencias . 1979-02-01. pag. 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 de alta tecnología: Irving T. Ho". Información de Taiwán . 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, Estados Unidos. 2000-01-11. Archivado desde el original el 26 de junio de 2020 . Consultado el 2 de mayo de 2017 .
  10. ^ "Irving T. Ho". Noticias del Mercurio de San José . 2003-04-26. 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 enteros decimal-binario (memorándum interno para Irving Tze Ho). Laboratorio de Investigación IBM San José, San José, California, EE.UU.: IBM .
  12. ^ abcdefghij Chen, Tien Chi (29 de marzo de 1971). Compresión de números decimales (PDF) (memorándum interno para Irving Tze Ho). Laboratorio de Investigación IBM San José, San José, California, EE.UU.: IBM . págs. 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 (15 de octubre de 1974) [18 de junio de 1973]. 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, Estados Unidos: 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 almacenamiento eficiente". Comunicaciones de la ACM . 18 (1). Laboratorio de investigación de IBM San José, San José, California, EE. UU. y División de productos de sistemas IBM, 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 almacenamiento eficiente". Informe de Investigación RJ 1420 (Informe técnico). Laboratorio de Investigación IBM San José, San José, California, EE.UU.: IBM .
  17. ^ abcd Cowlishaw, Michael Frederic (2014) [junio de 2000]. "Un resumen de la codificación de datos decimales de 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. CÓDIGO  CACMA2. Archivado desde el original el 3 de junio de 2020 . Consultado el 3 de junio de 2020 .(1 página) (NB. Una publicación que también analiza las alternativas y variaciones de Chen-Ho).
  19. ^ Sacks-Davis, Ron (1 de noviembre de 1982) [enero de 1982]. "Aplicaciones de representaciones de números redundantes a la aritmética decimal". La revista informática . 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 (25 de febrero de 2003) [20 de mayo de 2002, 27 de enero de 2001]. Escrito en Coventry, Reino Unido. "Codificador/descodificador de decimal a binario" (Patente). Armonk, Nueva York, Estados Unidos: International Business Machines Corporation (IBM). Patente estadounidense US6525679B1 . Consultado el 18 de julio de 2018.(6 páginas) [7] y Cowlishaw, Michael Frederic (7 de noviembre de 2007) [14 de enero de 2004, 14 de agosto de 2002, 24 de septiembre de 2001, 27 de enero de 2001]. Escrito en Winchester, Hampshire, Reino Unido. "Codificador/descodificador de decimal a binario" (Patente). Armonk, Nueva York, Estados Unidos: 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 de la IEE: Computadoras y técnicas digitales . 149 (3). Londres, Reino Unido: Institución de Ingenieros Eléctricos (IEE): 102–104. doi :10.1049/ip-cdt:20020407. ISSN  1350-2387 . 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 decimal densamente empaquetado". cuadribloc . Archivado desde el original el 3 de julio de 2018 . Consultado el 16 de julio de 2018 .
  24. ^ Función 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 (Expediente N° 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)

Otras lecturas