ビット逆順アクセス

FFTは信号処理の中でも非常に有名なアルゴリズムです。このアルゴリズムを使う上で必須な処理として「ビット逆順アクセス」があります。これは配列のインデックスのMSB側とLSB側をひっくり返してアクセスするというものです。どうしてこんなみょうちくりんなアクセスが必要なのかはあまたの解説サイト・教科書を見ていただくにしても、FFT自身は重要なアルゴリズムであり、頻繁に使われるためビット逆順アクセスにはハードウェアで対応する価値があります。

ADSP-2191はいささか古臭い方法ですがビット逆順アクセスをモードとして備えています。ビット逆順アクセス・モードに入るには次の命令を実行します。

ena bit_rev;   // enable bit reversal access mode.

そしてビット逆順アクセス・モードから抜け出すには次の命令を実行します。

dis bit_rev;   // enable bit reversal access mode.

ビット逆順アクセス・モードに入るとDAG1の出力の下位16ビットのビット順が反転します。つまり、DAG1のb15-b0がb0-b15としてバスに出力されます。

「と、言われても使い方がぴんとこない」という人がほとんどだと思います。はっきり言って自分でFFTでも書かない限りこんな機能は不必要なので無理して理解する必要はありません。が、どうしても理解しないと気がすまない人のために例題を用意しました。

まず、この機能を使うための前提条件から説明しましょう。

バッファの長さは2の冪で無ければならない。
バッファの長さが2のN乗のとき、このバッファのアドレスは2のN乗の整数倍でなければならない。
Post-modify with update アクセスを用いる
DAG1のアップデート用のMxの値は2^(16-N)でなければならない。
DAG1のIxの初期値はバッファ・アドレスのビット逆順値で無ければならない

と、まぁ大変な制約があります。これに忠実に書いたプログラムを下に示します。このプログラムはEZ-KIT Liteにロードして実行するとbrev配列にビット逆順に値が埋められていくのを観察することができます。前半のinitialループではbrevのアドレスのビット逆順値を求めています。実際のビット逆順アクセスはbit_reverseループです。

上に挙げた制約の4と5は、バッファの中だけビット逆順アクセスをするためのものです。なぜこういうことが必要かというと、我々が欲しているのは特定のバッファ内部だけの逆順アクセスであって、全部のビットを逆順にするのはその手段でしかないためです。そのため、逆順で出力した場合に正しくバッファの先頭アドレスをアクセスし、その後バッファ内インデックスの最上ビットをトグルして下位に向かってキャリーが進むようにするための一連の設定が上の手順となるわけです。

ビット逆順アクセスは何度も述べているようにFFT以外では必要ありません。無理に理解することはありません。

.section/dm data1;
.var buf[16]={ 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
.var dummy;
.align 16;                      // align address as multiple of 16
.var brev[16];
.align 0;

.section/pm program;
.global _main;
.extern _exit;
_main:
        l0=0;
        l4=0;
        sr1=brev;
        ar=0;
        cntr = 16;
        do initial until ce;
                ar=ar+ar;       // shift left result
                ax0=ar;         // temporal result
                ar=sr1 and 1;   // extract LSB
                ar=ar or ax0;   // copy LSB to result
initial:
                sr=lshift sr1 by -1 (hi);
                // now ar has bit reverse of address of brev
        i0=ar;
        m0=0x1000;              // 2^(16-log2(length(bitrev)))
        i4=buf;
        m4=1;

        cntr=16;
        ena bit_rev;
        do bit_reverse until ce;
                ax0=dm(i4+=m4);
bit_reverse:
                dm(i0+=m0)=ax0;
        dis bit_rev;
        jump    _exit;