Una representación binaria redundante (RBR) es un sistema de numeración 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. Una RBR es diferente a los sistemas de numeración binarios habituales , incluido el complemento a dos , que utilizan un solo bit para cada dígito. Muchas de las propiedades de una RBR difieren de las de los sistemas de representación binaria regulares. Lo más importante es que una RBR permite la adición sin utilizar un acarreo típico. [1] En comparación con la representación no redundante, una 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 utiliza un ancho de bits 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, esa RBR también es una representación de dígitos con signo .
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 utiliza un par de bits. El valor representado por un dígito redundante se puede encontrar utilizando una tabla de traducción. Esta tabla indica el valor matemático de cada par de bits posible.
Al igual que 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 solo bit de signo 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, se elige una de las diversas representaciones posibles de un número entero como forma "canónica", de modo que cada número entero solo tiene 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 convertir nuevamente desde un RBR utilizando 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]
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 esta RBR de muchas maneras: "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 ( puerta NOT ) corresponde a encontrar el inverso aditivo ( multiplicación por −1 ) del entero representado. [4]
En este caso:
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 ]
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 adición siempre tomará la misma cantidad de tiempo independientemente del ancho de bits de los operandos . Esto no implica que la adición sea siempre más rápida en un RBR que su equivalente en complemento a dos , sino que la adición eventualmente será más rápida en un RBR con un ancho de bits creciente porque el retraso de la unidad de adición en complemento a dos es proporcional a log( n ) (donde n es el ancho de bits). [5] La adición en un RBR toma un tiempo constante porque cada dígito del resultado puede calcularse independientemente de los demás, lo que implica que cada dígito del resultado puede calcularse en paralelo. [6]
La resta es lo mismo que la suma, excepto que primero se debe calcular el inverso aditivo del segundo operando. En el caso de las representaciones comunes, esto se puede hacer dígito por dígito.
Muchos multiplicadores de hardware utilizan internamente la codificación Booth , una representación binaria redundante.
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 se trate de una operación significativa; existen 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 primero los dos operandos en representaciones no redundantes. En consecuencia, las operaciones lógicas son más lentas en una 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 solo 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 ).
