Radix-4で計算を行う場合、上記の説明では-2～+2の5つの値を取りうるとしたが、一般的にRadix-r (但し、rは偶数とする)の計算を行う場合、- r/2 ～ + r/2の範囲の整数を取りうるようにすれば、0も含めて、全体ではr+1個の値が取りうることになり、1個の冗長シンボルがあることになる。このような割り当てを最小冗長(Minimally Redundant)なシンボル割り当てという。これに対して、-(r-1)～+(r-1)の値を許容すると、全体では2r-1の状態を取りうることになり、r-1個の冗長シンボルがあることになる。このような割り当てを最大冗長(Maximally Redundant)な状態割り当てという。

Radix-4の最大冗長な状態割り当てを行うと、部分商としてとりうる値は-3～+3となる。従って、次回以降の繰り返しで部分剰余から引きうる最大の値は-(3/4+3/16+3/64+...)であり、各繰り返しでの部分剰余Pは-D～+Dの範囲に納まっていれば良い。これを図にすると次のようになる。

図14:Radix-4の最大冗長シンボル割り当てを行ったPDプロット

上の図に示すように、最小冗長から最大冗長に冗長度を増やすと、Qiの値がどちらでも良いという重なり領域が+/- 2D/3から+/- Dに増加する。この図では部分剰余Pは16分割されているが、実は半分の分割でも塗り分けることができ、全体で32マスのテーブルで部分商Qiを求めることが出来る。

つまり、冗長度を大きくすると、PDプロットのマスを粗くすることができ、部分商選択テーブルが小さくなり、物量、速度の点で有利になる。しかし、radix-4の場合で言うと、Qi=3のケースに対応するため除数Dの3倍を作る必要が出るので、次の図に示す回路構成において黄色で示した加算器と、マルチプレクサに3倍を選択する入力が必要となる。

図15:最大冗長方式のRadix-4割り算器

つまり、冗長度を増やすと、テーブルは小さくなるが、加算器とセレクタが増加するというトレードオフがあり、どちらを優先するかということになる。

SRT割り算器をさらに高速化する

これまでの説明では、部分剰余の計算にキャリーを完全に伝搬させて、完全な加算結果を得るアダーを使うように書いてきたが、この構成では、アダーの速度で割り算のループの速度が制約されてしまうということになる。

これを更に高速化するため、乗算器の項で述べたキャリーセーブアダー(Carry Save Adder:CSA)を使う構成が用いられる。キャリーセーブアダーはサムとキャリーに分割して格納された部分剰余と、部分商選択テーブルで指定された倍率の除数の3入力を加算し、結果をサムとキャリーにして部分剰余レジスタに格納する。このCSAは1ビット分のフルアダーN個で構成でき、信号が通過するのは1ビットフルアダー1段だけであるので、キャリーを伝播させて完全なサムを得るアダーと比べて非常に高速である。

次の図16でクリーム色に塗った部分が、CSAを使う場合に図15から変更点する部分である。まず、部分剰余を更新するアダーをCSAに替え、サムとキャリーの形で部分剰余を作り、部分剰余を格納する部分剰余Hレジスタもサムとキャリーの両方を記憶するように拡張する。

図16:CSAを使った割り算器の高速化。青のラインがループのクリティカルバスを示す

一方、サムとキャリーに別れていては、部分商選択テーブルは引けないので、ここではキャリーを伝播させるキャリープロパゲーションアダー (Carry Propagation Adder:CPA)を入れて正しい部分剰余を作る。このCPAは部分剰余の全ビットの長さは必要なく、(次のPentium 4のバグの項で述べるように、これが曲者であるが)テーブルを引くのに十分な精度があるだけのビット幅で良い。

青いラインで示したクリティカルパスにはCSAとCPAの二つのアダーが入り、単純にアダーの数だけを見ると、前の図より増えているのであるが、テーブルを引くための部分剰余のビット数は比較的少ないので、小さく高速なCPAで済む。また、3入力のCSAは1ビットのフルアダーと同じ遅延時間であり、両者を合計しても図13などに使われている部分剰余全体の長いビット数のCPAより高速になる。

但し、この構成では剰余がサムとキャリーで表現された形式で残ってしまうので、正しい剰余が必要な場合は、後処理の段階で、CPAを使ったアダーでサムとキャリーを加算する必要がある。