「計算機アーキテクチャ１」講義資料１ -- 符号付き乗算、乗数のリコード、非回復型除算 -高木直史１．符号付き乗算２の補数表現の数同士を直接掛け合わせることもできる。被乗数を X=[xn-1xn-2…x1x0]、乗数を Y=[yn-1yn-2 n−2 …y1y0]（いずれも２の補数表現）とする。Y = −2n−1 yn−1 + ∑𝑖=0 2i yi であるから、X × Y = −2n−1 yn−1X + n−2 ∑𝑖=0 2i yi X となる。Y の下位から順に部分積 yi X を生成して桁をずらして累算して行き、最後の部分積は－yn-1 X とすればよい。－X は X の２の補数を取ればよい。（各桁を反転し、最下位に１を加える。最下位に加える１は、加算の際の最下位への桁上げ入力とすればよい。）X が負である場合、累算の途中結果が負となる。負数は２の補数で表せばよいが、最上位桁の位置が異なる二数を加算する場合、符号拡張が必要である。２．乗数のリコードによる部分積の削減逐次型乗算において、生成される（非０の）部分積の個数を少なくできれば、計算を高速化できる。そのような手法として、Booth の方法が知られている。Booth の方法では、２進数 011…11 が 100… 0T （T は-1 ．を表す。）と表されることを利用して、乗数をリコード（recode）する。リコードされた乗数の桁 yj が-1 のとき、部分積は –X 2j となり、累算では X 2j を減ずることになる。乗数の中に１がｍ個連続する部分がある場合、ｍ回の加算を１回の減算と１回の加算に置き換えることができる。シフトのみで加減算を行わない場合に１ステップの時間を短くできるような演算器では、高速化に有効である。表１に Booth の方法における乗数のリコード規則を示す。たとえば、0111101011111001 → 1000T1T10000T01T と変換される。Booth の方法を用いると、累算の途中結果が負数になる場合がある。負数は２の補数で表せばよい。（符号拡張が必要） Booth の方法では、長さ１の１の列（孤立した１）を 1T に変換するため、たとえば、010101 は 1T1T1T と変換され、乗数のリコードにより、累算における加減算の回数が増えてしまう場合がある。加減算の回数を最少にするには、乗数を非零桁の数が最少の２進 SD 表現（各桁が{-1,0,1}の２進表現）にリコードすればよい。このリコードは、表２に示す規則に従い、最下位から順に変換することにより行える。たとえば、 0111101011111001 → 10000T0T0000T001 と変換される。この変換では、ある種の桁上げ（表中の cj）が伝搬する。表２：非零桁の数が最少の２進 SD 表現へのリコード規則．状況 yj+1 yj cj cj+1 yj 表１：Booth の方法における乗数のリコード規則．状況 yj yj-1 yj 0 0 0 0 0 0 の列の中 0 0 1 0 1 0 の列の開始 0 0 0 0 の列の中 0 1 0 0 1 孤立した 1 0 1 1 1 の列の終了 0 1 1 1 0 1 の列の終了 1 0 -1 1 の列の開始 1 0 0 0 0 0 の列の終了 1 1 0 1 の列の中 1 0 1 1 -1 孤立した 0 1 1 0 1 -1 1 の列の開始 1 1 1 1 0 1 の列の中 1 ３．非回復型除算法（引き放し法）ｎビット符号なし２進整数の除算について考える。被除数をＸ、除数をＹ、商をＺ、剰余をＲとする。Ｘ、Ｙ、Ｚ、Ｒは、すべてｎビット符号なし２進整数である。教科書で示されている除算法は、基数２の減算シフト型除算法である。基数２の減算シフト型除算法では、商を上位から１ビットずつ求めていく。i 回の繰り返し計算後の商の中間結果を Qn-i＝[qn-1qn-2…qn-i0…0]、剰余の中間結果を Rn-i とする。（計算法により、qj ∊ {0,1} とは限らないので、ＺではなくＱで表している。）Rn=X、Qn=0 とし、j=n－1 から 0 について、 Rj := Rj+1－qj 2j Y Q j := Qj+1＋qj 2j という漸化式に従って計算を行う。教科書の除算法は、回復型除算法（引き戻し法）と呼ばれる。回復型除算法では qj ∊ {0,1}であり、まず、 Rj’=Rj+1－2j Y を計算し、Rj’が非負なら qj=1、Rj = Rj’とし、Rj’が負なら qj=0、Rj = Rj’＋2j Y とする。したがって、Rj は必ず非負になり、0≦Rj<2j Y が成り立つ。もちろん、２進表現の商Ｚのｊ桁目 zj は qj である。非回復型除算法では、Rj+1－qj 2j Y が負になっても、これをそのまま Rj とする。回復型除算法に比べ、加減算の回数が少なくなる。上記の漸化式で、qj ∊ {-1,1}とし、R j+1 が非負なら qj を１、負なら qj を-1 とする。常に-2j Y <Rj<2j Y が成り立つ。商を通常の２進表現に変換する必要があるが、２進表現の商Ｚのｊ桁目 zj は qj-1 が１なら１、-1 なら０となり、変換には特に計算の必要はない。ただし、R0 が非負なら z0 を１、剰余Ｒを R0 とし、負なら z0 を 0、Ｒを R0＋Y とする。商の変換を漸化式に組み込むことも可能である。Rn-1=X－2n-1 Y とし、j=n－2 から 0 について、R j+1 が非負なら zj+1 を１、負なら zj+1 を-1 とし、Rj := Rj+1－zj+1 2j Y とすればよい。以下に基数２の非回復型除算の例を示す。（Rj は２の補数表現で表している。） (1) 1011÷0101 (2) 1001÷0011 0000 1011 -010 1 0000 1001 q3=1 - 001 1 1110 0011 + 01 01 1111 0001 q2=-1 (z3=0) + 00 11 1111 0111 + 0 101 1111 0100 q2=-1 (z3=0) 1111 1101 q1=-1 (z2=0) + 0 011 0000 0001 - 0101 q3=1 q1=-1 (z2=0) 0000 0011 q0=1 (z1=1) - 0011 z0=0 0000 0000 商：0010 余り：0001 q0=1 (z1=1) z0=1 商：0011 余り：0000 2