Una representación binaria redundante (RBR) es un sistema numérico que utiliza más bits de los necesarios para representar un solo dígito binario, de modo que la mayoría de los números tienen varias representaciones. Un RBR es diferente a los sistemas numéricos binarios habituales , incluido el complemento a dos , que usa un solo bit para cada dígito. Muchas de las propiedades de un RBR difieren de las de los sistemas de representación binaria regulares. Lo más importante es que un RBR permite la adición sin usar un transporte típico. [1] Cuando se compara con la representación no redundante, un RBR hace que la operación lógica bit a bit sea más lenta, pero las operaciones aritméticas son más rápidas cuando se usa un ancho de bit mayor. [2]Por lo general, cada dígito tiene su propio signo que no es necesariamente el mismo que el signo del número representado. Cuando los dígitos tienen signos, ese RBR también es una representación de dígitos con signo .
Conversión de RBR
Un RBR es un sistema de notación de valor posicional . En un RBR, los dígitos son pares de bits, es decir, para cada lugar, un RBR usa un par de bits. El valor representado por un dígito redundante se puede encontrar usando una tabla de traducción. Esta tabla indica el valor matemático de cada posible par de bits.
Como en la representación binaria convencional, el valor entero de una representación dada es una suma ponderada de los valores de los dígitos. El peso comienza en 1 para la posición más a la derecha y aumenta en un factor de 2 para cada posición siguiente. Por lo general, un RBR permite valores negativos. No hay un bit de signo único que indique si un número representado de forma redundante es positivo o negativo. La mayoría de los números enteros tienen varias representaciones posibles en un RBR.
A menudo, una de las varias representaciones posibles de un número entero se elige como la forma "canónica", por lo que cada número entero tiene sólo una posible representación "canónica"; la forma no adyacente y el complemento a dos son opciones populares para esa forma canónica.
Un valor entero se puede volver a convertir desde un RBR usando la siguiente fórmula, donde n es el número de dígitos y d k es el valor interpretado del k -ésimo dígito, donde k comienza en 0 en la posición más a la derecha:
La conversión de un RBR a un complemento a dos de n bits se puede realizar en tiempo O (log ( n )) utilizando un sumador de prefijo . [3]
Ejemplo de representación binaria redundante
Dígito | Valor interpretado |
---|---|
00 | −1 |
01 | 0 |
10 | 0 |
11 | 1 |
No todas las representaciones redundantes tienen las mismas propiedades. Por ejemplo, utilizando la tabla de traducción de la derecha, el número 1 se puede representar en este RBR de muchas formas: "01 · 01 · 01 · 11" (0 + 0 + 0 + 1), "01 · 01 · 10 · 11 "(0 + 0 + 0 + 1)," 01 · 01 · 11 · 00 "(0 + 0 + 2−1) o" 11 · 00 · 00 · 00 "(8−4−2−1) . Además, para esta tabla de traducción, invertir todos los bits ( NO puerta ) corresponde a encontrar el inverso aditivo ( multiplicación por -1 ) del número entero representado. [4]
En este caso:
Operaciones aritmeticas
Las representaciones redundantes se utilizan comúnmente dentro de unidades lógicas aritméticas de alta velocidad .
En particular, un sumador de acarreo y ahorro utiliza una representación redundante. [ cita requerida ]
Adición
La operación de adición en todos los RBR es sin acarreo, lo que significa que el acarreo no tiene que propagarse por todo el ancho de la unidad de adición. En efecto, la adición en todos los RBR es una operación de tiempo constante. La suma siempre llevará la misma cantidad de tiempo independientemente del ancho de bits de los operandos . Esto no implica que la suma sea siempre más rápida en un RBR que su equivalente en complemento a dos , pero que la adición eventualmente será más rápida en un RBR con un ancho de bits creciente porque el retardo de la unidad de suma del complemento a dos es proporcional a log ( n ) (donde n es el ancho de bits). [5] La suma en un RBR toma un tiempo constante porque cada dígito del resultado se puede calcular independientemente uno del otro, lo que implica que cada dígito del resultado se puede calcular en paralelo. [6]
Sustracción
La resta es lo mismo que la suma, excepto que el inverso aditivo del segundo operando debe calcularse primero. Para representaciones comunes, esto se puede hacer dígito por dígito.
Multiplicación
Muchos multiplicadores de hardware utilizan internamente la codificación Booth , una representación binaria redundante.
Operaciones lógicas
Las operaciones lógicas bit a bit, como AND , OR y XOR , no son posibles en representaciones redundantes. Si bien es posible realizar operaciones bit a bit directamente en los bits subyacentes dentro de un RBR, no está claro que esta sea una operación significativa; Hay muchas formas de representar un valor en un RBR, y el valor del resultado dependería de la representación utilizada.
Para obtener los resultados esperados, es necesario convertir los dos operandos primero en representaciones no redundantes. En consecuencia, las operaciones lógicas son más lentas en un RBR. Más precisamente, toman un tiempo proporcional a log ( n ) (donde n es el número de dígitos) en comparación con un tiempo constante en complemento a dos .
Sin embargo, es posible convertir parcialmente sólo la parte menos significativa de un número representado de forma redundante a una forma no redundante. Esto permite que operaciones como el enmascaramiento de los k bits bajos se puedan realizar en tiempo log ( k ).
Referencias
- ^ Phatak, Dhananjay S .; Koren, Israel (agosto de 1994). "Sistemas de números de dígitos firmados híbridos: un marco unificado para representaciones de números redundantes con cadenas de propagación de acarreo limitadas" (PDF) . Transacciones IEEE en computadoras . 43 (8): 880–891. CiteSeerX 10.1.1.352.6407 . doi : 10.1109 / 12.295850 .
- ^ Lessard, Louis Philippe (2008). "Aritmética rápida en FPGA usando aparatos binarios redundantes" . Consultado el 12 de septiembre de 2015 .
- ^ Veeramachaneni, Sreehari; Krishna, M. Kirthi; Avinash, Lingamneni; Reddy P., Sreekanth; Srinivas, MB (mayo de 2007). Novedoso convertidor binario a binario redundante de alta velocidad que utiliza redes de prefijo (PDF) . Simposio Internacional IEEE sobre Circuitos y Sistemas (ISCAS 2007). Nueva Orleans. doi : 10.1109 / ISCAS.2007.378170 .
- ^ Lapointe, Marcel; Huynh, Huu Tue; Fortier, Paul (abril de 1993). "Diseño sistemático de filtros recursivos canalizados". Transacciones IEEE en computadoras . 42 (4): 413–426. doi : 10.1109 / 12.214688 .
- ^ Yu-Ting Pai; Yu-Kumg Chen (enero de 2004). El sumador anticipado de acarreo más rápido (PDF) . Segundo Taller Internacional IEEE sobre Diseño, Pruebas y Aplicaciones Electrónicas (DELTA '04). Perth. doi : 10.1109 / DELTA.2004.10071 .
- ^ José, Bijoy; Radhakrishnan, Damu (diciembre de 2006). Sumadores binarios redundantes optimizados con retardo . 13th IEEE International Conference on Electronics, Circuits and Systems, 2006. (ICECS '06). Lindo. doi : 10.1109 / ICECS.2006.379838 .