筆算で割り算を行う場合は、商の値を仮定して、それに除数を掛けた値を比除数から引くという作業を繰り返す。例えば、10230÷129のような割り算を筆算でやる場合には、下図のように書いて、

まず、一桁目のところの"?"に何が立つかの見当をつける。8が立つかなと考えてやってみると、実は少し大きすぎて余りが-9になってしまう。従って、除数を元に戻して、商を7に修正してやり直すということになる。この例のように、10進数で計算する場合は仮定する商の値は0~9の値を取りうるが、2進数で計算する場合は、一桁の取りうる値は"0"か"1"であるので話は簡単で、"1"を仮定して引き算を行い、結果がマイナスになれば、引き算を元に戻して、商を"0"にすれば良い。

筆算をハード化した引き戻し法

この2進化した筆算の手順を回路化すると、次の図に示すような回路になる。除数(Divisor)、被除数(Dividend)ともにNビットの長さとすると、除数レジスタと商(Quotient)レジスタはNビット、被除数レジスタは、2Nビットの長さを持つ。そして、商と被除数レジスタは、1ビットの左シフト機能を備えている。

図1:2進数1桁づつを処理する引き戻し法の割り算器

説明を簡単にするために、被除数、除数ともにプラスであるとする。まず、除数(Divisor)レジスタに除数を入れる。そして。そして、被除数(Dividend)レジスタの下半分に被除数を入れ、被除数レジスタの上位の半分はゼロクリアしておく。

割り算のステップでは、アダーで被除数レジスタの上半分の部分から除数を引いて、その結果が正であれば、被除数レジスタに引き算の結果を格納する。そして、商レジスタの最下位ビットに"1"を入れる。アダーのキャリーが結果がマイナスであることを示しているので、図1の回路では、キャリーを否定して商レジスタへの入力としている。そして、商レジスタへの格納は、以前の内容を1ビット左シフトし、空いた最下位ビットに入力データを格納する。そして、被除数レジスタは上位と下位を結合した状態で1ビット左へシフトする。

筆算の場合には、商を立てる桁と部分剰余が右の下位の桁にずれていくが、ハードウェアで計算する場合は、このように左シフトして計算を行う方が都合が良い。一方、引き算の結果がマイナスになってしまった場合は引き過ぎであり、商として"1"は立たないので、次のサイクルで、引き算を行ってしまった被除数レジスタの値(部分剰余)に除数を足して、元に戻す。そして、1ビット左にシフトして、次のステップを行う。

ということで、引き算の結果が一度もマイナスにならなければNサイクルで終わるが、最悪、いつも引き算の結果がマイナスになり、次のサイクルで元に戻すという操作が必要になると2Nサイクルを必要とする。この方法は、結果がマイナスになってしまった場合、部分剰余を元に戻すので、Restoring Division(引き戻し法)と呼ばれる。

図1の回路では、別個に設けた商レジスタに商を格納したが、動作を良く見ると、商レジスタは毎サイクル下位ビットから1ビットづつ使われ、被除数レジスタは毎サイクル下位ビットが空いていくので、商を被除数レジスタに格納してやれば1個のレジスタで共用が可能である。

図2:商レジスタを被除数レジスタの下位半分と共用した割り算器の構成

この、図2のようにすれば、被除数レジスタの下位半分に最終結果の商が入ることになり、Nビット長の商レジスタが節約できる。