Sistema eficiente de codificación binaria para dígitos decimales utilizados en coma flotante decimal.
El decimal densamente empaquetado ( DPD ) es un método eficaz para codificar dígitos decimales en binario .
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), incluso cuando se utiliza BCD empaquetado . El decimal densamente empaquetado es un código más eficiente que empaqueta tres dígitos en diez bits usando un esquema que permite la compresión o expansión hacia BCD con solo dos o tres retrasos de puerta de hardware . [1]
La codificación decimal densamente empaquetada es un refinamiento de la codificación Chen-Ho ; Ofrece las mismas ventajas de compresión y velocidad, pero la disposición particular de los bits utilizados confiere ventajas adicionales:
- La compresión de uno o dos dígitos (en los cuatro o siete bits óptimos, respectivamente) se logra como un subconjunto de la codificación de tres dígitos. Esto significa que se pueden codificar de forma eficiente números arbitrarios de dígitos decimales (no sólo múltiplos de tres dígitos). Por ejemplo, 38 = 12 × 3 + 2 dígitos decimales se pueden codificar en 12 × 10 + 7 = 127 bits, es decir, se pueden codificar 12 conjuntos de tres dígitos decimales utilizando 12 conjuntos de diez bits binarios y los dos dígitos decimales restantes. se puede codificar utilizando otros siete bits binarios.
- La codificación de subconjunto mencionada anteriormente son simplemente los bits más a la derecha de la codificación estándar de tres dígitos; el valor codificado se puede ampliar simplemente agregando 0 bits iniciales.
- Todos los números BCD de siete bits (del 0 al 79) están codificados de forma idéntica mediante DPD. Esto hace que las conversiones de números pequeños comunes sean triviales. (Esto debe descomponerse en 80, porque requiere ocho bits para BCD, pero la propiedad anterior requiere que la codificación DPD quepa en siete bits).
- El bit de orden inferior de cada dígito se copia sin modificar. Por lo tanto, la parte no trivial de la codificación puede considerarse una conversión de tres dígitos de base 5 a siete bits binarios. Además, los valores lógicos de dígitos (en los que cada dígito es 0 o 1) se pueden manipular directamente sin que sea necesaria ninguna codificación o decodificación.
Historia
En 1969, Theodore M. Hertz, y en 1971, Tien Chi Chen (陳天機) con Irving Tze Ho (何宜慈) idearon códigos de prefijo sin pérdidas (conocidos como codificaciones de Hertz y Chen-Ho [2] ) que empaquetaban tres dígitos decimales en diez bits binarios utilizando un esquema que permitía la compresión o expansión a BCD con solo dos o tres retrasos de puerta en el hardware. El decimal densamente empaquetado es un refinamiento de esto, ideado por Mike F. Cowlishaw en 2002, [1] que se incorporó a los estándares IEEE 754-2008 [3] e ISO/IEC/IEEE 60559:2011 [4] para coma flotante decimal. .
Codificación
Al igual que la codificación Chen-Ho, la codificación DPD clasifica cada dígito decimal en uno de dos rangos, según el bit más significativo de la forma binaria: los dígitos "pequeños" tienen valores del 0 al 7 (binario 0000-0111) y los dígitos "grandes" , 8 a 9 (binario 1000–1001). Una vez que se sabe o se ha indicado que un dígito es pequeño, aún se requieren tres bits más para especificar el valor. Si se ha indicado un valor grande, sólo se requiere un bit para distinguir entre los valores 8 o 9.
Al codificar, los bits más significativos de cada uno de los tres dígitos a codificar determinan uno de los ocho patrones de codificación para los bits restantes, según la siguiente tabla. La tabla muestra cómo, al decodificar, los diez bits de la forma codificada en las columnas b9 a b0 se copian en los tres dígitos d2 a d0 , y los bits restantes se completan con ceros o unos constantes.
Los bits b7, b4 y b0 ( c, fy i) pasan a través de la codificación sin cambios y no afectan el significado de los otros bits. Los siete bits restantes pueden considerarse una codificación de siete bits para tres dígitos de base 5.
Los bits b8 y b9 no son necesarios y se ignoran al decodificar grupos DPD con tres dígitos grandes (marcados como "x" en la última fila de la tabla anterior), pero se completan con ceros al codificar.
Los ocho valores decimales cuyos dígitos son todos 8 o 9 tienen cuatro codificaciones cada uno. Los bits marcados con x en la tabla anterior se ignoran en la entrada, pero siempre serán 0 en los resultados calculados. (Las codificaciones no estándar 3 × 8 = 24 llenan el espacio entre 10 3 = 1000 y 2 10 − 1 = 1023.)
Ejemplos
Esta tabla muestra algunos números decimales representativos y sus codificaciones en BCD, Chen-Ho y decimal densamente empaquetado (DPD):
Ver también
Referencias
- ^ ab 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 : 102–104. doi :10.1049/ip-cdt:20020407. ISSN 1350-2387 . Consultado el 7 de febrero de 2016 .
- ^ 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 .
- ^ Sociedad de Computación IEEE (29 de agosto de 2008). Estándar IEEE para aritmética de punto flotante. IEEE . doi :10.1109/IEEESTD.2008.4610935. ISBN 978-0-7381-5753-5. Norma IEEE 754-2008 . Consultado el 8 de febrero de 2016 .
- ^ ISO/IEC/IEEE 60559:2011. 2011. Archivado desde el original el 3 de junio de 2020 . Consultado el 8 de febrero de 2016 .
- ^ 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 .
Otras lecturas
- 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 de EE. UU.). Armonk, Nueva York, Estados Unidos: International Business Machines Corporation (IBM). US6525679B1 . Consultado el 18 de julio de 2018.[1] 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 europea). Armonk, Nueva York, Estados Unidos: International Business Machines Corporation (IBM). EP1231716A2 . Consultado el 18 de julio de 2018 .[2][3][4] (NB. Esta patente trata sobre DPD).
- Bonten, Jo HM (6 de octubre de 2009) [5 de octubre de 2006]. "Codificación decimal empaquetada IEEE-754-2008". Geldrop, Países Bajos. Archivado desde el original el 11 de julio de 2018 . Consultado el 11 de julio de 2018 .(NB. Puede encontrar una versión anterior aquí: Codificación decimal empaquetada IEEE-754r.)
- 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 .
