冗長バイナリ表現

冗長2進表現（RBR）は、 1つの2進数字を表すのに必要なビット数よりも多くのビットを使用する数値システムであり、ほとんどの数値には複数の表現方法があります。RBRは、各数字に1ビットを使用する2の補数などの通常の2進数値システムとは異なります。RBRの特性の多くは、通常の2進表現システムと異なります。最も重要なのは、RBRでは通常のキャリーを使用せずに加算できることです。^[1]冗長でない表現と比較すると、RBRではビット単位の論理演算が遅くなりますが、より広いビット幅を使用すると算術演算が速くなります。 ^[2] 通常、各数字には独自の符号があり、それは必ずしも表される数字の符号と同じではありません。数字に符号がある場合、そのRBRも符号付き数字表現です。

RBR は位取り記数法システムです。RBR では、数字はビットのペアです。つまり、RBR は各位にビットのペアを使用します。冗長な数字によって表される値は、変換テーブルを使用して見つけることができます。このテーブルは、可能な各ビットのペアの数学的値を示します。

従来の 2 進表現と同様に、与えられた表現の整数値は、各桁の値の加重合計です。加重は、右端の位置の 1 から始まり、次の位置ごとに 2 倍ずつ増加します。通常、RBR では負の値が許容されます。冗長的に表現された数値が正か負かを示す単一の符号ビットはありません。ほとんどの整数は、RBR で複数の表現が可能です。

多くの場合、整数の複数の可能な表現のうちの 1 つが「標準」形式として選択されるため、各整数には 1 つの可能な「標準」表現のみがあります。その標準形式としては、非隣接形式と 2 の補数が一般的に選択されます。

整数値は、次の式を使用して RBR から逆変換できます。ここで、nは桁数、d _{k は}k番目の桁の解釈された値です。kは右端の位置で 0 から始まります。

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

RBRからnビットの2の補数への変換は、プレフィックス加算器を使用してO(log( n ))時間で実行できます。 ^[3]

すべての冗長表現が同じ特性を持つわけではない。例えば、右の変換表を使用すると、このRBRでは数字1をさまざまな方法で表現できる。「01·01·01·11」（0+0+0+1）、「01·01·10·11」（0+0+0+1）、「01·01·11·00」（0+0+2−1）、または「11·00·00·00」（8−4−2−1）。また、この変換表では、すべてのビットを反転（NOTゲート）することは、表現された整数の加法逆数（−1の乗算）を見つけることに相当する。 ^[4]

この場合：${\displaystyle d_{k}\in \{-1,0,1\}}$

冗長表現は、高速算術論理ユニット内でよく使用されます。

特に、キャリーセーブ加算器は冗長表現を使用します。^[要出典]

すべての RBR の加算演算は桁上がりなしです。つまり、桁上がりが加算ユニットの全幅に渡って伝播する必要はありません。実際、すべての RBR の加算は定数時間演算です。加算には、オペランドのビット幅に関係なく、常に同じ時間がかかります。これは、RBR での加算が2 の補数での加算よりも常に高速であることを意味するのではなく、2 の補数加算ユニットの遅延が log( n ) ( nはビット幅)に比例するため、ビット幅が増加すると RBR での加算が最終的に高速になることを意味します。 ^[5] RBR での加算には定数時間がかかります。これは、結果の各桁を互いに独立して計算できるためです。つまり、結果の各桁を並列に計算できることを意味します。^[6]

減算は加算と同じですが、2 番目のオペランドの加法逆数を最初に計算する必要がある点が異なります。一般的な表現では、これは桁ごとに実行できます。

多くのハードウェア乗算器は、冗長なバイナリ表現である ブース エンコーディングを内部的に使用します。

AND、OR、XORなどのビット単位の論理演算は、冗長表現では実行できません。RBR内の基になるビットに対して直接ビット単位の演算を実行することは可能ですが、これが意味のある演算であるかどうかは明らかではありません。RBR で値を表現する方法は多数あり、結果の値は使用される表現によって異なります。

期待される結果を得るには、まず 2 つのオペランドを非冗長表現に変換する必要があります。その結果、RBR では論理演算が遅くなります。より正確には、2 の補数では定数時間かかるのに対し、RBR では log( n ) ( nは桁数)に比例した時間がかかります。

ただし、冗長的に表現された数値の最下位部分のみを非冗長形式に部分的に変換することは可能です。これにより、下位kビットをマスクするなどの操作を log( k ) 時間で実行できます。