符号付き除算(非回復法)

[] [] []


前項の回復法では引きすぎたら引く前の値に戻したが、戻さずに次の桁で足しても同じ結果になる(例え-1/8=-1/2+1/4+1/8。この方法は引き放し法、非回復法、Non-Restoringとよばれる。

回復法では、商はビットごとに0,1でなく+1,-1で得られるので、次の手順で0,1に直せばよい

 +1のビットをp[N-1:0]とおくと,-1のビットは~p[N-1:0]だから

  q[N:0] = p[N-1:0] - ~p[N-1:0] = p[N-1:0]+{1'b1,p[N-1:0]}+1'b1 = (1'b1<<N)+{p[N-1:0],1'b1}

 例) q=(+1)*22+(-1)*21+(-1)*20 =1のときp[2:0]=3'b100 q[3:0]=4'b1000+{3'b100,1'b1}=4'b0001

【非回復法】符号なし/符号なし

例)a[2:0]=101 (5)  d[1:0]=11 (3)

          _______  10  手順

       11)  101.0  ( 1)  r={2'b00,a[2]}

q[2]=+1 -) 11      ( 3)  d

          ---

          110      (-2)  t=r-d <0

           100     (-4)  r={r[1:0],a[1]}

q[1]=-1  +) 11     ( 3)  d

           ---

           111     (-1)  t=r-d <0

            111    (-1)  r={r[1:0],a[0]}

q[0]=-1   +) 11    ( 3)  d

            ---

            010    ( 2)  t=r-d >=0

             10.0  ( 4)  r={t[1:0],1'b0}

q[-1]=+1   -) 1.1  ( 3)  d

            -----

             00.1  ( 1)  t=r-d >=0

 

切捨の場合q[2:0]=+4-2-1=1

丸めの場合q[2:-1]=+4-2-1+0.5=1.52

 

 

 

←引き算はq[2](aMSB)から始める

if(r<0) q[i]=-1 t=r+d  逆符号にして引く

 else    q[i]=+1 t=r-d  そのまま引く

 

 

 

 

 

 

0<=r<1(切捨)にするにはq[0]まで求めて終わり

 +1のビットをp[i]とおくと

 q[3:0] = 4'b1000+{p[2:0],1'b1}

 t<0(引きすぎ)のときはq=q-1にすればよいので

 if(t<0) q[3:0]=4'b1000+{p[2:0],1'b0}

 else    q[3:0]=4'b1000+{p[2:0],1'b1}

-0.5<=r<0.5(丸め)にするにはq[-1]まで求めて

 if(t<0) q[3:-1]=5'b10000+{p[2:-1],1'b0}

 else    q[3:-1]=5'b10000+{p[2:-1],1'b1}

 さらにq[3:0]=q[3:0]+q[-1]とすればよいので

 if(t<0) q[3:0]=4'b1000+p[2:-1]

 else    q[3:0]=4'b1000+p[2:-1]+1'b1

回復法は減算だけ使うのに対して、非回復法は加減算両用の組合せ回路を使い動作速度が遅くなりそうだが、正÷正だけでなく負÷正も同じ回路で扱える利点がある。そこで、符号つき整数の除算を考える

被除数a: 符号付き、整数部WAビット

除数d:  符号付き、整数部WDビット

q    符号付き、整数部WA+1ビット、小数部FQビット。(-2WA/(-1)=2WA だからqの整数部aより1ビット多く必要)

剰余r = a-d*q  切捨て0 r|d|*2-FQ  または丸め -|d|*2-FQ-1 r|d|*2-FQ-1

簡単な例としてWA=3,WD=2,FQ=0の場合で手計算してみると、次のように被除数と除数が同符号ならば引いて異符号なら足していけばよい。

【非回復法】負/

例)a[2:0]=100 (-4)  d[1:0]=11 (-1)

          _______  10  手順

       11)11100.0

          111      (-1)  r={符号拡張a[2]}

q[2]=+1 -)111      (-1)  d

          ---

          000      ( 0)  t=r-d

           000     ( 0)  r={t[1:0],a[1]}

q[1]=-1  +)111     (-1)  d

           ---

           111     (-1)  t=r+d

            110    (-2)  r={t[1:0],a[0]}

q[0]=+1   -)111    (-1)  d

            ---

            111    (-1)  t=r-d

             11.0  (-2)  r={t[1:0],a[0]}

q[-1]=+1   -)11.1  (-1)  d

             ---

             11.1  (-1)  t=r-d

 

切捨の場合q[2:0]=+4-2+1=34

丸めの場合q[2:-1]=+4-2+1+0.5=3.54

【非回復法】負/

例)a[2:0]=101 (-3)  d[1:0]=11 (-1)

          _______  10  手順

       11)11101.0

          111      (-1)  r={符号拡張a[2]}

q[2]=+1 -)111      (-1)  d

          ---

          000      ( 0)  t=r-d

           000     ( 0)  r={t[1:0],a[1]}

q[1]=-1  +)111     (-1)  d

           ---

           111     (-1)  t=r+d

            111    (-1)  r={t[1:0],a[0]}

q[0]=+1   -)111    (-1)  d

            ---

            000    ( 0)  t=r-d

             00.0  ( 0)  r={t[1:0],a[0]}

q[-1]=-1   +)11.1  (-1)  d

             ---

             11.1  (-1)  t=r+d

 

切捨の場合q[2:0]=+4-2+1=3

丸めの場合q[2:-1]=+4-2+1-0.5=2.53

 

 

 

←引き算はq[2](aMSB)から始める

if(rdが異符号) q[i]=-1 t=r-(-d) 符号を変えて引く

 else              q[i]=+1 t=r-(+d) そのまま引く

 

 

 

 

 

 

 

0<=r<|d|(切捨て)にするにはq[0]まで求めて終わり

 +1のビットをp[i]とおくと

 q[3:0]=4'b1000+{p[2:0],1'b1}

 t<0(引きすぎ)のときは、d>=0ならばq=q-1,

 d<0ならばq=q+1とすればよいので

 if(t<0) q[3:0]=4'b1000+{p[2:0],1'b0}+(d<0)?2'b10:0

 else    q[3:0]=4'b1000+{p[2:0],1'b1}

-0.5d<=r<0.5d(丸め)にするにはq[-1]まで求めて

 if(t<0) q[3:-1]=5'b10000+{p[2:-1],1'b0}+(d<0)?2'b10:0

 else    q[3:-1]=5'b10000+{p[2:-1],1'b1}

 d>=0ならばq[3:0]=q[3:0]+q[-1](切上げ),

 d<0ならばq[3:0]=q[3:0](切捨て)とすればよいので

 if(t<0) q[3:0]=4'b1000+p[2:-1]+(d<0)? 1:0

 else    q[3:0]=4'b1000+p[2:-1]+(d<0)? 0:1

 

【非回復法】正/

例)a[2:0]=011 ( 2)  d[1:0]=11 (-1)

          _______  10  手順

       11)00010.0

          000      ( 0)  r={符号拡張a[2]}

q[2]=-1 +)111      (-1)  d

          ---

          111      (-1)  t=r-d

           111     (-1)  r={t[1:0],a[1]}

q[1]=+1  -)111     (-1)  d

           ---

           000     ( 0)  t=r+d

            000    ( 0)  r={t[1:0],a[0]}

q[0]=-1   +)111    (-1)  d

            ---

            111    (-1)  t=r-d

             11.1  (-1)  r={t[1:0],a[0]}

q[-1]=+1   -)11.1  (-1)  d

             ----

             00.0  ( 0)  t=r-d

 

切捨の場合q=-4+2-1=-3-2

丸めの場合q=-4+2-1+0.5=-2.5-2

【非回復法】正/

例)a[2:0]=011 ( 3)  d[1:0]=11 (-1)

          _______  10  手順

       11)00011.0

          000      ( 0)  r={符号拡張a[2]}

q[2]=-1 +)111      (-1)  d

          ---

          111      (-1)  t=r-d

           111     (-1)  r={t[1:0],a[1]}

q[1]=+1  -)111     (-1)  d

           ---

           000     ( 0)  t=r+d

            001    ( 1)  r={t[1:0],a[0]}

q[0]=-1   +)111    (-1)  d

            ---

            000    ( 0)  t=r-d

             00.0  ( 0)  r={t[1:0],a[0]}

q[-1]=-1   +)11.1  (-1)  d

             ----

             11.1  (-1)  t=r-d

 

切捨の場合q=-4+2-1=-3

丸めの場合q=-4+2-1-0.5=-3.5-3

◇◇

このアルゴリズムをVivadoHLSで合成可能なCコードで書くと次のようになる。ここで商qを小数点以下まで求めるためにa/d =q*2-FQ すなわちa*2FQ/d=qが整数になるようにしている。またa,dは整数型ap_int< >としたが、固定小数点型ap_fixed< >に置き換えてもそのまま使えるように、小数点の位置に依存しないa.range( )d.range( )で書いてある。

#include <ap_int.h>

/********************************************************************

 * division a/d = q + e (d>0) , a/d = q - e (d<0)

 *   input range: d!=0

 *   error range: 0<=e<2**(-FQ) (truncation)

 *******************************************************************/

template <int WA,int WD,int FQ>

ap_fixed<WA+FQ+1,WA+1> div_int_trn

    (ap_int<WA> a       // (i) dividend

    ,ap_int<WD> d       // (i) divisor

    ) {

    ap_int<WA+FQ> b = (ap_int<WA+FQ>) a.range(WA-1,0) << FQ;

    ap_int<WD+1> r;

    ap_int<WD+1> t;

    ap_uint<WA+FQ> p;

    ap_fixed<WA+FQ+1,WA+1> q;   // (o) quotient

    for(int i=WA+FQ-1; i>=0; i--) {

        if(i==WA+FQ-1) {

            r = (ap_int<1>) b[i];

        } else {

            r = (t.range(WD-1,0),b[i]);

        }

        p[i] = (r[WD]==d[WD-1]);

        t = (r[WD]==d[WD-1])? r - (ap_int<WD>) d.range(WD-1,0)

                            : r + (ap_int<WD>) d.range(WD-1,0);

    }

    q.range(WA+FQ,0) = (1<<(WA+FQ))+(p,!t[WD])+((t[WD]&d[WD-1])?2:0);

    return q;

}

#include <ap_int.h>

/*******************************************************************

 * division a/d = q + e (d>0) , a/d = q - e (d<0)

 *   input range: d!=0

 *   error range: -2**(-FQ-1)<=e<2**(-FQ-1) (rounding)

 ******************************************************************/

template <int WA,int WD,int FQ>

ap_fixed<WA+FQ+1,WA+1> div_int_rnd

    (ap_int<WA> a       // (i) dividend

    ,ap_int<WD> d       // (i) divisor

    ) {

    ap_int<WA+FQ+1> b = (ap_int<WA+FQ+1>) a.range(WA-1,0) << (FQ+1);

    ap_int<WD+1> r;

    ap_int<WD+1> t;

    ap_uint<WA+FQ+1> p;

    ap_fixed<WA+FQ+1,WA+1> q;   // (o) quotient

    for(int i=WA+FQ; i>=0; i--) {

        if(i==WA+FQ) {

            r = (ap_int<1>) b[i];

        } else {

            r = (t.range(WD-1,0),b[i]);

        }

        p[i] = (r[WD]==d[WD-1]);

        t = (r[WD]==d[WD-1])? r - (ap_int<WD>) d.range(WD-1,0)

                            : r + (ap_int<WD>) d.range(WD-1,0);

    }

    q.range(WA+FQ,0) = (1<<(WA+FQ)) + p + (t[WD]==d[WD-1]);

    return q;

}

このコードは次のテストベンチで検証してある。

int main(int argc, char *argv[]) {

    const int WA = 4;

    const int WD = 3;

    const int FQ = 0;

    ap_uint<WA> a;

    ap_uint<WD> d;

    ap_fixed<WA+FQ+1,WA+1> q;

    double e;

   

    for(int j=-pow(2,WD-1); j<pow(2,WD-1); j++) {

        if(j==0) continue;

        for(int i=-pow(2,WA-1); i<pow(2,WA-1); i++) {

            a = i;

            d = j;

            cout << "-- a=" << setw(3) << a << " d=" << setw(3) << d;

      /* 切捨ての場合 */

            q = div_int_trn<WA,WD,FQ>(a,d);

            e = a.to_double() / d.to_double() - q.to_double();

            if(d<0) e = -e;

            cout << " q_trn=" << setw(6) << q << " e=" << setw(10) << e;

            if(!(0<=e && e<pow(2,-FQ))) cout << " FAIL";

            /* 丸めの場合 */

            q = div_int_rnd<WA,WD,FQ>(a,d);

            e = a.to_double() / d.to_double() - q.to_double();

            if(d<0) e = -e;

            cout << " q_rnd=" << setw(6) << q << " e=" << setw(10) << e;

            if(!(-pow(2,-FQ-1)<=e && e<pow(2,-FQ-1))) cout << " FAIL";

            cout << endl;

        }

    }

    return 0;

}


[] [] []