計測自動制御学会東北支部 第 280 回研究集会 (2013.5.29)
資料番号 280-3

部分的転置形構造に基づく分散演算形適応ディジタルフィルタの高性能アーキテクチャ
High-Performance Architecture for LMS Adaptive Filter Using
Distributed Arithmetic Based on Partially Transposed Structure○猪股了 ∗ ，佐藤辰海 ∗ ，高橋強 ∗∗ ，恒川佳隆 ∗○ Inomata Ryo∗ , Sato Tatsumi∗ , Takahashi Kyo∗∗ ,Tsunekawa Yoshitaka∗*岩手大学, **岩手県工業技術センター*Iwate University, **Iwate Industrial Research Inst
キーワード : 分散演算 (distributed arithmetic)，同時更新 (simultaneous update)，
カットセットリタイミング (cutset retiming)，準奇対称性 (pseudo-odd symmetry property)，
収束特性 (convergence characteristic)

連絡先 : 〒 020-8551 盛岡市上田 4-3-5 岩手大学工学部 恒川佳隆
Tel.: (019)621-6468，Fax.: (019)621-6468，E-mail: tsune@iwate-u.ac.jp

1.

はじめに加算により求められ，2N 個の部分積は適応プロ

適応フィルタ (Adaptive Digital Filter, ADF)
はノイズキャンセラ，エコーキャンセラ，適応等化器などの様々な分野で応用されている．そのことから，小規模ハードウェア，低消費電力，良好な収束特性，短い出力滞在時間などが要求される．しかし，これらを同時に満たすことは困難であり，高性能なアルゴリズムや効果的なアーキテクチャが望まれている．
これまで，LMS 適応フィルタ 1) に分散演算(Distributed Arithmetic, DA) を適用した，分散演算形 LMS 適応フィルタ (LMS Adaptive Dig-ital Filter using Distributed Arithmetic, DAADF) が提案された．分散演算は出力計算における係数ベクトルと入力信号ベクトルの内積演算に適用し，出力信号は N 次入力信号ベクトルセスにより逐次更新する．ここで部分積の全集合を全適応関数空間 (Whole Adaptive FunctionSpace, WAFS) と呼ぶ．また，高次の場合でのハードウェア規模増加と収束速度劣化を抑制する手法として，WAFS を分割するマルチメモリ
ブロック構造 (Multi-memory Block Structure)を適応した DA-ADF(MDA-ADF) があり，出力計算と更新動作を並列に実行することで高サンプリングレートを実現可能な同時更新アルゴリ
ズム (Simultaneous Update Algorithm) を適用した MDA-ADF(SMDA-ADF)2) ，カットセットリタイミングを適用することで出力滞在時間を短縮した，部分的転置形構造を有する SMDA-ADF(NCMDA-ADF，以下，従来型適応フィルタ) が提案されている 3) ．のビットパターンで指定される部分積のシフト–1–

本報告では，従来型適応フィルタの構造に対[して準奇対称性を利用し，収束速度の向上を図F = −20 , 2−1 , · · · , 2−(B−1)

る．さらに，4 入力 2 出力加算器 (4-2 加算器) を]T(6)適用することで，ハードウェア規模の増加を抑ここで，bi (k)，i = 0, · · · , B − 1，は x(k) の i 番制した構成を提案する．最後に，収束特性評価目のビットである．
マルチメモリブロック構造は，DA-ADF の高および VLSI 評価を行うことで，本提案型アー

次における RAM 容量の増加抑制と更新確率のキテクチャの有効性を明らかにする．

減少に伴う収束速度の劣化を補償する．分割数

2.

分散演算形 LMS 適応フィルタ

2.1

分散演算の適用を M ，アドレス線数を R = N/M とすると，適応関数空間は M 個に分割される．また，R 個のアドレスベクトルで指定される m 番目の適応分散演算は内積演算をテーブルルックアップに関数空間 Pm (k) は 式 (7) となる．
[より効率よく計算する手法であり，原理的にはPm (k) =処理時間は語長 B にのみ依存する．以下，フィ= ATm (k)Hm (k)ルタのタップ数を N ，各信号の語長を B とすあり， 式 (1) で表される．

(7)

このように分割することで，容量 2R の WAFSを M 個有するため，総容量は M · 2R となる．

y(k) = H T (k)X(k)H(k) = [h0 (k), h1 (k), · · · , hN −1 (k)]]Tm = 0, · · · , M −1

ると，フィルタ出力 y(k) は N 次係数ベクトル

H(k) と N 次入力ベクトル X(k) の内積演算でpm0 (k), pm1 , · · · , pm(B−1) (k)T(1)

またフィルタ出力 y(k)，更新式，誤差信号 e(k)(2)は，所望信号を d(k) とすると，次式で表される．

X(k) = [x(k), x(k − 1), · · · , x(k − N + 1)]T (3)y(k) =
ここで分散演算は 式 (1) に対して適用される．

M−1∑

F T Pm (k)

(8)

m=0

Pm (k + 1) = Pm (k) + 0.5µRe(k)F (9)また T は転置を表す．出力計算は B 個のアドe(k) = d(k) − y(k)レスベクトルによって順次指定される部分積を(10)WAFS から読み出してシフト加算により行う．
更新動作は，誤差信号 e(k) を用いて出力計算時2.2に用いた部分積を順に更新する．時刻 k における

B 個の部分積は WAFS の部分集合であり，これを適応関数空間 (Adaptive Function Space,AFS)と呼ぶ． 式 (3) の N 次入力信号ベクトルは以下のように表わされる．

同時更新アルゴリズム

同時更新アルゴリズムは，適応フィルタの処理過程である出力計算と更新動作を並列化する手法である．これにより 1 サンプルによる処理時間が短縮可能となる．また，並列化する手法
では，同時更新アルゴリズムの他にディレード

X(k) = A(k)F(4)

アップデートと呼ばれる手法もあり，この 2 つまた，ビットパターンに分解した N × B 次アの手法は 1 時刻前の出力信号を用いて誤差信号ドレスマトリクス A(k)，スケーリングベクトルを求めている．そのためディレードアップデー

F は， 式 (5) ， 式 (6) で表される．

トでは過去の誤差信号を使用することにより収A(k) = b0 (k)b1 (k)..
.

······..
.

b0 (k − N + 1)
b1 (k − N + 1)..
.

bB−1 (k) · · · bB−1 (k − N + 1)

T (5)

束速度が劣化してしまう．しかし，同時更新アルゴリズムでは，出力計算は LSB 側から，更新動作は MSB 側から順次実行し，ビットレベルでのアップデートを行う．これにより，出力計–2–Fig. 1

Structure of SMDA-ADF

Fig. 4

cutset retiming

かし SMDA-ADF は，高次で BTA(Binary Tree

Fig. 2Adder) の段数が増加してしまうために出力滞在

Timing chart of SMDA-ADF

時間が増加し，サンプリングレートが減少する．

2.4

カットセットリタイミング

転置形構造は従来の構造に対してカットセットリタイミングを実行することにより導出される．カットセットリタイミングとは，入出力の時間差関係を保持したまま挿入されている遅延器を再配置する手法である． 図 4 にその仕組み

Fig. 3

WAFSMを示す．まず 図 4 (a) に示すように，シグナル算に更新された関数空間を使用でき，収束速度の劣化を抑制することが可能である．

2.3

フローグラフ SG にカットセット CS を設定して，SG1 と SG2 に分割する．次いで， 図 4 (b)に示すように SG2 から SG1 に流れる信号線に対しては遅延器，SG1 から SG2 に流れる信号線

SMDA-ADFに対しては逆時間の遅延器を挿入する．ここでSMDA-ADF の構成を 図 1 に，タイミングチ

逆時間の遅延器とは，時刻 k の信号 n(k) に対しャートを 図 2 に示す．ここで，M 個の WAFSMて n(k + 1) を出力するような要素である．最後(WAFS Module) は部分積を格納するメモリ，入に，遅延器と逆時間の遅延器が存在する信号線

力信号により部分積を選択するセレクタ，部分に対してこれらを打ち消すことで， 図 4 (c) の積を加算するシフト加算器などから構成される．

構成が得られる．以上がカットセットリタイミ

図 3 に WAFSM の構成を示す．WAFSM は更ングのプロセスであるが， 図 4 (c) の構成は逆新機能も有しており，1 時刻前の出力計算に寄時間の遅延器が挿入されているため実現不可能

与した部分積を出力計算と同時に更新する．しである．実際にカットセットリタイミングを適–3–

Fig. 6Fig. 5

Structure of NCMDA-ADF

Flow of cutset retiming

用し，逆時間の遅延器が挿入された際には時間のシフトを行い，因果律を満たす構成を導出しFig. 7なければならない．

2.5

Timing chart of NCMDA-ADF

イプライン化するために WAFSM2 ∼WAFSM4

部分的転置形構造の導出の出力加算ラインを BTA 化する．

実際に SMDA-ADF に対してカットセットリ以上より導出した部分的転置形構造を有するタイミングを実行する．簡単化のためにタップ

SMDA-ADF(NCMDA-ADF) を 図 6 に示す．

数を 8， 図 5 の BTA 部を加算器が縦続に接続

この構成においてモジュール出力は，入力信号されているものとして考える．のビットパターンの LSB 側から順次部分積を読まず， 図 5 (a) に示すようにカットセット CSみ出してシフト加算することにより得られ，フィを WAFSM1 と WAFSM2 の間に設定し SG1 とルタ出力は時刻 k における WAFSM1 の出力に，SG2 に分割する．次いで，SG2 から SG1 に流

時刻 k − 1 における WAFSM2 ∼WAFSMM のモれる信号線には遅延器，SG1 から SG2 に流れジュール出力和を加えて得られる．また，更新方る信号線には逆時間の遅延器を挿入する．ここ

向は出力計算とは異なり，MSB 側から順次行う．

で， 図 5 (b) では誤差フィードバックラインに遅延ラインは出力計算と更新の 2 ラインを有す逆時間の遅延器が挿入されており，このままでる．部分的転置形構造は WAFSM1 と WAFSM2は因果律を満たさず実現不可能なため，誤差信の間のみにカットセットリタイミングを適用し，号と入力信号の時間差を保持したまま時間のシフィルタ部の WAFSM2 以降に多くのモジューフトを行う．これにより，更新用の遅延ラインルを配置でき，係数遅延を最小に抑えた特殊なには遅延器が挿入され，誤差フィードバックラ転置形構造である．

インの逆時間の遅延器が打ち消されることで，また，NCMDA-ADF のタイミングチャート

図 5 (b) の非因果的な構成は 図 5 (c) の因果律を 図 7 に示す．NCMDA-ADF は WAFSM1 とを満たす構成となる．最後に，フィルタ部をパBTA を並列に動作させている．SMDA-ADF は–4–

3.

提案型適応フィルタ3.1

準奇対称性の利用

2 の補数形式を用いた分散演算形適応フィル
タのアルゴリズムでは，収束状態の適応関数空間においてアドレスがビット反転の関係にある部分積は, 互いに異符号で絶対値が近似的に等しい準奇対称性を有することが知られている 4) ．

Fig. 8

提案法では，更新動作時に通常の更新要素とStructure of HNCMDA-ADF準奇対称の関係にある要素を同時に更新する．
これまでは所望信号 d(k) と出力信号 y(k) の差から誤差信号 e(k) を一つだけ求めていたが，提案法では e(k) と −e(k) の二つを同時に求める．

e(k) は通常の更新要素であるアドレスベクトルによって指定される部分積を更新する誤差信号で，−e(k) は準奇対称の更新要素，つまりビット反転を行ったアドレスベクトルによって指定される部分積を更新する誤差信号である．適応

Fig. 9関数空間の 2 箇所を同時に更新するため，収束

WAFS of HNCMDA-ADF

速度は従来の 2 倍に向上する． 図 8 に準奇対称
高次において BTA 段数が増加し出力滞在時間性を利用した NCMDA-ADF(HNCMDA-ADF)が増加してしまう．しかし，NCMDA-ADF はの構成を， 図 9 に準奇対称性を利用した WAFSBTA の出力滞在時間が WAFSM1 の出力滞在時を示す．

間以内であれば，モジュール出力の加算回数は1 回のみで済むことから，出力滞在時間の短縮

3.2

4 入力 2 出力加算器とサンプリングレートの向上を可能とする．
図 6 の構造から導出されるアルゴリズムを以

提案型適応フィルタでは 4 入力 2 出力加算器

下に示す．部分積の指定は入力信号ベクトルのビ(4-2 加算器) を BTA とシフト加算器に用いる．

ットパターンを用いる．フィルタ出力は 式 (11) で

4-2 加算器は桁上げ保存形式を用いており，桁示される．

上げ信号を伝搬させずに次の加算に持ち越してy(k) = y0 (k) +M−1∑

処理することが可能である．また，4-2 加算器

ym (k − 1)

(11)

m=1

ym (k) = F T Pm (k)はハードウェア効率がよく，多入力の加算に使用する場合，CLA 加算器を用いる場合と比べて(12)ハードウェア量を削減可能となる．よって，提また，部分積の集合である m 番目の適応関数空案型適応フィルタでは CLA 加算器を使用して間の更新式は， 式 (13) のようになる．

いた部分と 4-2 加算器を適切に置き換えることでハードウェア利用の効率化を図る．

Pm (k + 1) = Pm (k) + 0.5µRe(k − 1)F (13)–5–

Fig. 13
Fig. 10

Proposed Filter

BTA using 4-2 adder
ここでは 図 11 に示す 4-2 加算器を用いたシフト加算器を使用して，2 つの WAFS に対して1 つのシフト加算器を使用する新たな WAFSMを提案する．その構成を 図 12 に示す．提案型

WAFSM を使用することで，使用するシフト加算器の総数を削減することができる．

Fig. 11準奇対称性を利用し，4-2 加算器を使用したShift Adder using 4-2 adderBTA，シフト加算器を適用した提案型適応フィルタの構成を 図 13 に示す．この構成において

WAFS1 と WAFSM の部分には従来の WAFSMを使用することとする．理由として，WAFS1 に新たな WAFSM を使用するとシフト加算後の出力が 2 つあるため，加算を 1 回追加する必要があり，出力滞在時間が増加してしまうからであFig. 12

3.3

Proposed WAFSM

る．また， 図 13 では分割数が偶数の場合を想定しているが，奇数の場合は WAFSM に対してアーキテクチャも 4-2 シフト加算器を適用することができる．
提案型適応フィルタは HNCMDA-ADF のフィ提案型適応フィルタは 4-2 加算器を適用する

ルタ部を改良する．改良点は BTA とシフト加ことで出力滞在時間は従来のまま，ハードウェ算器についてであり，4-2 加算器を使用した構ア規模を削減できる．

成を提案する．
まず BTA について，従来の BTA では CLA加算器を M − 1 個使用していたのに対し，提4.

収束特性評価案型適応フィルタに用いる BTA は 4-2 加算器を各適応フィルタの収束特性をシステム同定問

M/2−1 個と CLA 加算器 1 個で構成でき，BTA

題に対する計算機シミュレーションにより評価のみの比較では面積を約 25 ％削減可能である．

する．評価対象は LMS-ADF，従来型適応フィ

4-2 加算器を使用した BTA を 図 10 に示す．

ルタの NCMDA-ADF，提案型適応フィルタの従来の WAFSM は，WAFS とシフト加算器をProposed である．評価量はインパルス応答誤差それぞれ 1 つずつ使用して構成していた ( 図 3 )．

比 (Impulse Response Error Ratio, IRER)，未–6–

Table 1

Comparison of the VLSI evaluations (N = 128，B = 16)
LMS-ADF NCMDA-ADF Proposed

Number of address lines
Number of divisions
Sampling rate [MHz]Latency [ns]Power dissipation [mW/MHz]
Area [mm2 ]Number of gates

2.41
302
781
102.31
932,8285.

2642.78
342
3,753
27.51
243,955

2642.78
342
3,888
29.76
255,549

VLSI 評価

LMS-ADF，従来型の NCMDA-ADF，提案
型適応フィルタの Proposed を VLSI 設計シス
テム PARTHENON により設計および評価を行う．設計ルールは 0.6µmCMOS スタンダードセルとし，電源電圧は 5.0V である．演算に用いたデータ形式は 2 の補数表現による 16 ビッ
ト固定小数点型であり，タップ数は全て 128 とし，NCMDA-ADF，Proposed のアドレス線数は 2 とした．表 1 に VLSI 評価結果を示す．まず，

LMS-ADF と分散演算を適用している他 2 つを比較すると，面積とゲート数は 70 ％以上の削減

Fig. 14 Comparison of the convergence characteristics
知システムは低域通過 FIR フィルタ，入力信号は-1∼1 の範囲の値を取る一様乱数とした．未知システムの出力には観測雑音として-50dB の入力とは無相関な白色雑音を加え，ステップサイズ
パラメータは IRER が-50dB となるように選択した．またタップ数は全て 128 とし，NCMDA-ADF，Proposed のアドレス線数は 2 である．

が可能となる．分散演算を適用することでマルチプライヤレスな構成となるためハードウェア規模は大幅に削減可能である．次に，NCMDA-ADF と Proposed の比較を行う．Proposed は，消費電力が約 3.6 ％，面積が約 8.2 ％，ゲート数が約 4.8 ％増加している．Proposed は 4-2 加算器を使用することで面積等を約 8 ％程度の増加に留まらせた上で，収束速度を約 2 倍に向上させるため，ハードウェア効率の良い構成である．

図 14 に収束特性を示す．Proposed は準奇対称性を利用しているため，NCMDA-ADF と6.

まとめ比較して約 2 倍の収束速度を示している．また

本報告では，従来の NCMDA-ADF に準奇対

Proposed は LMS-ADF と比較しても収束速度称性を利用した．さらに 4-2 加算器を適用するはほぼ同等であり，提案型適応フィルタは良好ことで，出力滞在時間はそのままでハードウェな収束速度を有することが分かる．

ア規模の増加を抑制しながら収束速度を向上させる構成を提案した．このことから，提案型適応フィルタは適応フィルタに要求される多くの–7–性能を同時に満たすことが可能な高性能アーキテクチャであることを明らかにした．
今後の課題としては，カットセットリタイミングの適用による転置形構造の導出は自由度が高いことから，複数個所に設定するなど他の構造について検討を行うことである．

参考文献
1) B. Widrow and M. E. Hoﬀ,“Adaptive Switching Circuit,” IRE EWSCON Conv. Rec.,
pp96-104, 1960.
2) 橘内慎次郎, 内田勝也, 佐藤慎悟, 高橋 強, 恒川佳隆, “分散演算を用いたパイプライン LMS 適応ディジタルフィルタの高性能アーキテクチャ”,
計測自動制御学会東北支部第 242 回研究集会,
242-2, May 13, 2008.
3) 佐藤辰海, 高橋強, 恒川佳隆, “転置形構造を有する分散演算形 LMS 適応フィルタ”, 平成 24 年
度電気関係学会東北支部連合大会講演論文集,
1|04, Aug 30, 2012.
4) 高橋 強, 恒川佳隆, 豊田真嗣, 三浦守, “ハーフメモリアルゴリズムに基づく分散演算形 LMS
適応フィルタの高性能アーキテクチャ”, 信学論(A), vol.J84-A, no.6, pp777-787, June 2001.

–8–