Representación binaria redundante

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. Una RBR es diferente de los sistemas numéricos 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 suma sin utilizar un acarreo típico. ^{[ 1 ]} En comparación con la representación no redundante, una RBR hace que las operaciones lógicas bit a bit sean más lentas, pero las operaciones aritméticas son más rápidas cuando se utiliza un mayor ancho de bits. ^{[ 2 ]} Normalmente, 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 posicional . En un RBR, los dígitos son pares de bits; es decir, para cada posición, se utiliza un par de bits. El valor representado por un dígito redundante se puede encontrar mediante 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. Generalmente, una representación binaria redundante (RBR) permite valores negativos. No existe un bit de signo único que indique si un número representado de forma redundante es positivo o negativo. La mayoría de los enteros tienen varias representaciones posibles en una RBR.

A menudo, una de las varias representaciones posibles de un número entero se elige como la forma "canónica", de modo que cada número entero tiene solo una representación "canónica" posible; la forma no adyacente y el complemento a dos son opciones populares para esa forma canónica.

Un valor entero se puede convertir de nuevo a partir de 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:

${\displaystyle \sum _{k=0}^{n-1}d_{k}2^{k}}$

La conversión de un RBR a 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 puede representarse 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 ( compuerta NOT ) corresponde a encontrar el inverso aditivo ( multiplicación por −1 ) del entero representado. ^{[ 4 ]}

En este caso:${\displaystyle d_{k}\in \{-1,0,1\}}$

Las representaciones redundantes se utilizan habitualmente dentro de las unidades aritmético-lógicas de alta velocidad .

En particular, un sumador con acarreo guardado utiliza una representación redundante.

Suma

La operación de suma en todos los RBR es sin acarreo, lo que significa que el acarreo no tiene que propagarse a través de todo el ancho de la unidad de suma. En efecto, la suma en todos los RBR es una operación de tiempo constante. La suma siempre tomará 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 , sino que la suma eventualmente será más rápida en un RBR con un ancho de bits creciente porque el retardo de la unidad de suma en 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 de los demás, lo que implica que cada dígito del resultado se puede calcular en paralelo. ^{[ 6 ]}

Las operaciones lógicas bit a bit, como AND , OR y XOR , no son posibles en las representaciones redundantes. Si bien es posible realizar operaciones bit a bit directamente sobre los bits subyacentes dentro de una RBR, no está claro que esta sea una operación significativa; existen muchas maneras de representar un valor en una 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 a representaciones no redundantes. En consecuencia, las operaciones lógicas son más lentas en una representación RBR. Más precisamente, requieren un tiempo proporcional a log( n ) (donde n es el número de dígitos) en comparación con el 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 realizar operaciones, como enmascarar los k bits menos significativos, en tiempo logarítmico (log( k )).