平均値の除算(回復法)

[] [] []


ここまで被除数aと除数dは任意としてきたので商q1からaまでの値をとるが、qのとりうる範囲がある値qmaxより小さいことがわかっている場合は、aMSBから始めていた引き算をqmaxMSBから始めればよく、通常より少ない引き算(小さい回路)で除算ができる。

例えばN個の値xi (0) の平均はxiの最大値より必ず小さくなるので、この方法が使える。

1) 加重平均  

2) 調和平均  

今、除数と商のビット幅を与えて次のようにおく。

除数a: 符号なし、整数部WD+WQ-FQビット(q*dのビット幅だけ必要)

除数d:  符号なし、整数部WDビット

q:   符号付き、整数部WQ-FQビット、小数部FQビット。

剰余r = a-d*q 切捨て0 rd*2-F の場合、a,dの範囲は-2da+2d

         丸め -d*2-F-1 rd*2-F-1の場合、a,dの範囲は-2da(2-2-F-1)*d

           ( -2q2-2-Fだからa=d*q+r(2-2-F+2-F-1)*d=(2-2-F-1)*d )

◇◇

このアルゴリズムをVivadoHLS合成可能なCコードで書くと次のようになる。符号なし除算(回復法)と比べて引き算の開始位置をaMSBからqMSBへ変更しただけである。

#include <ap_int.h>

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

 * division a/d = q + e

 *   input range: 0<=a<=d*q_max , 0<d

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

template <int WD,int WQ,int FQ>

ap_ufixed<WQ,WQ-FQ> div_avg_trn

    (ap_uint<WD+WQ-FQ> a        // (i) dividend

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

    ) {

    ap_uint<WD+WQ> b = (ap_uint<WD+WQ>) a.range(WD+WQ-FQ-1,0) << FQ;

    ap_uint<WD+1> r;

    ap_int<WD+1>  t;

    ap_ufixed<WQ,WQ-FQ> q;      // (o) quotient

    for(int i=WQ-1; i>=0; i--) {

        if(i==WQ-1) {

            r = b.range(WD+i,i);

        } else {

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

        }

        t = r - d.range(WD-1,0);

        q[i] = !t[WD];

    }

    return q;

}

#include <ap_int.h>

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

* division a/d = q + e

 *   input range: 0<=a<=d*q_max , 0<d

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

template <int WD,int WQ,int FQ>

ap_ufixed<WQ,WQ-FQ> div_avg_rnd

    (ap_uint<WD+WQ-FQ> a        // (i) dividend

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

    ) {

    ap_uint<WD+WQ+1> b = (ap_uint<WD+WQ+1>) a.range(WD+WQ-FQ-1,0) << (FQ+1);

    ap_uint<WD+1> r;

    ap_int<WD+1>  t;

    ap_ufixed<WQ,WQ-FQ> q;      // (o) quotient

    for(int i=WQ; i>=0; i--) {

        if(i==WQ) {

            r = b.range(WD+i,i);

        } else {

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

        }

        t = r - d.range(WD-1,0);

        if(i==0) {

            q.range(WQ-1,0) = q.range(WQ-1,0) + !t[WD];

        } else {

            q[i-1] = !t[WD];

        }

    }

    return q;

}

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

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

    const int WD = 2;

    const int WQ = 3;

    const int FQ = 1;

    ap_uint<WD+WQ-FQ> a;

    ap_uint<WD>       d;

    ap_ufixed<WQ,WQ-FQ> q;

    double e;

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

        for(int i=0; i<=j*(pow(2,WQ-FQ)-1); i++) {

            a = i;

            d = j;

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

            /* 切り捨ての場合 */

            q = div_avg_trn<WD,WQ,FQ>(a,d);

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

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

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

            /*丸めの場合 */

            q = div_avg_rnd<WD,WQ,FQ>(a,d);

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

            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;

}


[] [] []