ラップアラウンド無しのFIRフィルタ

FIRフィルタをマイコンで実装するときに、一番大きなオーバーヘッドとなるのは何でしょうか。MAC演算？二つのロード命令？違います。バッファからのロード時にラップアラウンドが発生することが、最大のオーバーヘッドになります。

FIRアルゴリズムでは読み出し位置がラップアラウンドするため、一番内側のループの中にIF文を置き、ポインタがバッファの端まで来たか監視しなければなりません。ここのオーバーヘッドは甚大です。

以下ではこのオーバーヘッドを抑えるためのラップアラウンド解消方法を説明します。

FIRフィルタのラップアラウンド処理

図1に典型的なFIRフィルタの実装における、データの扱い方を示します。

図1 典型的なFIRフィルタの実装

主要なデータはインパルス応答を格納する配列h(n)と、状態変数です。状態変数は入力サンプルの履歴を保存する循環バッファで、遅延線(delay line)とも呼びます。この辺は2191空挺団時代のFIRフィルタも参照してください。

さて、FIRフィルタのアルゴリズムはサンプルをひとつ持ってきて状態変数の先頭に納め、そのたびにh(n)と状態変数の内積を計算します。ここで、ポイントは2つ。

• サンプルの格納位置
• 内積を取るときの先頭

です。これは状態変数が循環バッファであることから来る問題です。結論から言えば、最新のサンプルは最古のサンプルを上書きする位置に格納し、内積を取るときの先頭データは格納したばかりの最新サンプルになります。一方、h(n)は常に先頭からアクセスします。当然ながら、内積のデータ長（タップ数）はh(n)の長さであるNです。

このあたりの事情を考えながら、図1を眺めると、内積を取っている間に状態変数である配列の端までアクセスが到達することがわかります。その場合、他端にラップ・アラウンドしなければなりません。そのため、FIRアルゴリズムでは、一番内側のループの中で積和演算を実行するたびに、ポインタが状態変数の端に達していないか確認する必要があります。この処理はサンプル周波数Sとタップ数Ｎに比例する負荷になります。

これが今回問題にしている点です。

解決策

状態変数のアクセスからラップアラウンドをなくすことが今回の目的ですが、蓋を開けてみると、これは頓智に類する問題であったとがっかりするかもしれません。ラップアラウンドをなくすには、状態変数の長さを2倍に取ります。そして、状態変数の前半と後半には同じデータを格納します（図2）。

図2 ラップアラウンドを排除する構成

このデータ型でラップアラウンド処理を省くと、状態変数のアクセス中にオーバーランが発生します。しかし、そのオーバーランは状態変数の後半をアクセスするだけであり、かつそこには前半と同じデータが格納されています。そのため、結果的にラップアラウンドを施したのと同じデータが供給されます。

この方法では最新のサンプルを前半と後半の2箇所に格納しなければならりませんが、そのオーバーヘッドはタップ数Nとは無関係ですので無視しえます。また、この方法でもサンプルの格納場所についてはラップアラウンド処理が必要ですが、これもタップ数Nと無関係です。

まとめ

DSPはこの問題を特殊なアドレッシングモードで解決します。しかし、いつの間にかムーアの法則が便利な手段を可能にしていたのでした。

状態変数を2倍にせずにh(n)を2つ連続して確保する方法もありますが、原理はまったく同じです。