計測自動制御学会東北支部第242回研究集会（2008．5．13）
資料番号242−2

応適S

T⊥

ン一
イア ラ能プ性イ高パのたタ

分散演算を用いディジタルフィルM

キテクチヤ

High−per払rmanceArchitectureofthePipelinedLMSAdaptive
FilterusingDistributedArithmetic
橘内懐次郎†，○内田勝也†，佐藤憤悟十，高橋強††，恒川佳隆†

ShinjiroKITSUNAI†，OKatsuyaUCHIDA†，ShingoSATO†，KyoTAKAHASHI††，Ⅵ）ShitakaTSUNEKAWA††岩手大学，††岩手県工業技術センター†IwateUniversity，††IwatcIndustrialResearchInstitute
キーワード：分散演算（distrib11tedarithmetic），LMSアルゴリズム（LMSalgorith皿），同時更新（simultaneousupdate），パイプライン・アーキテクチャ（pipclinedarchitecture），高サンプリング・レート（high−Samplingrate）
連絡先：〒020−8551盛岡市上田4−3−5岩手大学工学部
橘内債次郎，Tel・＝（O19）621，6468，Fax．＝（019）621−6468，E−mail：t3308OO6＠iwate−u．aC．jp，の乗算器を用いず，加算器とレジスタで適応フィ1． はじめにルタを構成することが可能である．これより，分適応フィルタは，エコーキヤンセラ，ノイズコン

散演算形LMS適応フィルタ（LMSAdaptiveFilter

トローラ，適応等化器，振動制御などさまざまな

usingDistributed ArithITletic，DA−ADF）は，小規分野で用いられ，ますます応用乾田を広げている．

模ハードウエア，低消費電力であり，しかも良好適応フィルタを実現する際には，高速なサンプリな収束特性を示す高性能な適応フィルタである．

ングレート，良好な収束特性，短い出力滞在時間，しかし，部分積のシフト加算を語長回数だけ繰′ト規模ハードウエア，低消費電力などさまざまなり返すDArADFは，これまでの乗算器を用いたパ性能が要求されるが，これらを同時に滴たすこと
イプライン適応フィルタ4）5）6）と比較するとサンは困難であり，高性能なアルゴリズムや効果的なプリングレートが低く，適用範囲が限定される．

アーキテクチャが望まれている．

本報告では，DA−LMSの高速アルゴリズムと効報告者らは，ベクトルの内積演算を効率良く実行
果的なVLSIアーキテクチャを提案する．提案するする分散演算（DistributedArithmetic，DA）をLMS

アルゴリズムは，適応フィルタの基本処理である

適応フィルタ1）に適用して分散演算形LMS適応ア

出力計算と更新動作を同時並列に実行することにルゴリズム（DA−LMS）と効果的なアーキテクチャ

より，処理時間の短縮を可能にする．収束速度をを提案した2）3）この手法では，フィルタリングに計算機シミュレーションによi）評価し，更新に1時おける係数ベクトルと人力信号ベクトルの内積演

刻前の誤差信号を用いているにも関わらず．遅延算に分散演算を適用することにより，比較的規模−1−

時間による収束速度の劣化は非常に小さいことを示す．さらに，提案するアルゴリズムを効果的に実現するⅤⅠ．SIアーキテクチャを示す．

、2．分散演算形LMS適応フィルタ
2．1 分散演算の適用〃一th ordcraddr亡SSVeCtOr

従来，分散演算は定係数ベクトルの内積演算をFig．1BasicstruCtureOfDA−ADF

効率よく実行する手法として知られていたが，係数が時間変化する適応フィルタにおいても効果的

は2の補数形式を用いて次式のように表される．

である．以下，フィルタのタップ数をⅣ，入力信号

β（た）＝一20・む。（た）＋2斗わ1（た）十＋2￣糾】・らβ−1（た）語長をβとして議論を進める．
ここで，むi（た），壱＝0，…，β−1はご（た）の五番目のビッ

図1にDA−ADFの基本構成を示す．分散演算は，ト値を表す．式（1）のⅣ次入力信号ベクトルは適応フィルタの出力計算における〃次係数ベクト
ルlγ（た）とⅣ次入力信号ベクトル5（た）の内積演算

ぎ（た）＝AT（た）ダ〃（た）＝ Ⅳ了1（た）5（ん）と表される．なお，rはマトリクスの転置を表す．

Ⅳ（た）＝〔ぴ。（た），…ルⅣ＿1（軒「

これをビットパターンに分解したⅣ×β次アドレ「Tl g（た）＝【β（た），β（た−1），…，β（た−Ⅳ十1）】」（1）

スマトリクスはに対して適用される．入力信号はLSBから入力され，この1ビットとⅣ−1bitのシフトレジスタ出力わ0（た）む0（た−〃十1）むl（た）わ1（た−Ⅳ＋1）

A（た）＝がRAMのアドレス信号（アドレスベクトル）とな（2）

毎＿1（た） ‥ わβ−1（た一〃十1）る．このアドレスベクトルに対してⅣ次係数ベク

スケーリングベクトルダはトルの部分積が定義され，RAM（RandomAccess㌍［−20，2−l，‥・，2−（叫］Memory）に格納される．部分積の数は，Ⅳ次アドレスベクトルに対して2〃個が存在し，これらのTである．式（2）の列ベクトルであるβ個のアドレ部分積を要素とする集合を全適応関数空間（WllOle

スベクトルで指定される適応関数空間P（た）AdaptiveFunctionSpace，WAFS）と呼ぶ．出力計P（た）＝ b。（た），pl（た），…朋−1（た）］T

算は，決定されたβ個のアドレスベクトルに対する部分積をRAMから順に選択して読み出し，シ＝ AT（た）Ⅳ（た）フト加算を実行する．更新動作は，求めた誤差信を用いて，フィルタ出力封（た）は以下のように表さ号e（た）を用いて出力計算に使用した部分積を順にれる．

更新する．ある時刻たにおいて選択される月個の部分積の集合を適応関数空間（AdaptiveFunction

訂（た）＝〆p（た）Space，AFS）と呼ぶ．

また，AFSの更新式はDA−LMSアルゴリズムを以下に示す．人力信号

P（た＋1）＝P（た）十0．5〃Ⅳe（た）ダ−2−である．ここで，誤差信号は

SR：βbi【SSeria15biflreglStere（た）＝d（た）一打（た）alであり，d（呵は所望信号を表す．

聖一里
MIoRAM】

M〝一1βbil

B7Å

2．2 マルチメモリブロック構成押出Shirl．人dder

DA−ADFは，高次においてWAFSを実現する

gnale（々）

RAMの容量が膨大となりハードウエア規模と消●●●費電力の点で不利である．また，膨大な部分積数を有するWAFSを更新することは，収束状態に達するまでに多くの繰り返しを必要とし収束速度が緩慢になる．この問題を解決するために，WAFSをⅣ方向に〃分割するマルチメモリブロック情造（Multi−meInOryblockstructure）を適用する．DA−Fig，2 BasicstructureofMDA−ADF

ADFにマルチメモリブロック構造を適用した分「￣￣‥ −￣￣卜、−散演算形LMS適応フィルタをMDA−ADFと呼ぶ．
Read

図2にMDA−ADFの基本構成，図3にタイミン：：こ：：：：：：：：：：＝

Addl昆（川1eYeト1
Addiuo爪】eYeトt

グチャートを示す．分割数凡才，アドレスベクトル

5hinandAdd吊0爪の次数R（＝N／M）のMDALADFは，要素数2R個のError
Up血teAFS

WAFSをM個有し，WAFSの総容量はMx2Rword

Eiller Outpl：：：である．また，分割数凡才が大きく月が小さいほど

Fig・3 TimingchartoftheMDA−ADF

WAFSの要素数が減少するため，収束速度が向上する．

力の総和により得られ，次式で求められる．

アルゴリズムを以下に示す．財分割されたm番．1J−1目のアドレスマトリクスAm（た）は封（た）＝∑〆pm（た）

（3）

m＝ニーJ

A，れ（た）

また，分割された汀も番目のAFSに対する更新式はむmo（た）わmo（た一月＋1）

わ，乃1（た）わ，rll（た一月＋1）

次のように表される．
Pm（た＋1）＝ Pm（た）＋0．5〃月e（た）ダわγr岬−1）（た） わ，▲r岬−1）（ん一月＋1）

Pm（た）＝ b）m。（た）7pml，…，pm（か1）（瑚と表される．このAm（た）に対するAFSである

m ＝ 0，1，…，〃−1P汀L（た）は次式で表される，

P〔1（た）＝［恥0（た），pml∵・・仁pm（。＿1）（叫丁3．同時更新アルゴリズム

汀L ＝ 0，1，‥・，凡才ー1

MDANADFの高速アルゴリズムを検討する．
MDA−ADFは出力計算，誤差計算，更新動作の各フィルタ出力は分割されたAFSを用いた個別の出√−3−rObservationNoise〔亘〕 ＝⇒pm．Bt（kl）PⅢn（k） ㌔l（k）pm・B崇しk）p爪包lしk）Read ト 芋 ！・−−！ 1▲

U山ateトー・l
1＿▲

▲

▲

トーー・i ‡OI

B2 Bl

Fig・4 ReadandUpdateprocedure
Fig．5 Simulationmodel
動作をシーケンシャルに実行するが，1時刻前の誤こ土で，勘は以下に示す五番目の要素以外は0のス差信号を用いて出力計算と更新動作を並列に実行ケーリングベクトルである，（パイプライン化）することを考える．過去の誤差信号を用いて係数を更新する手法は，ディレー

ダ。＝ト2∩，0，0，・・・，0，叫r，ドアップデートと呼ばれ，収束速度の劣化を許容

ダ1＝［0，2￣1，0，…，0，0］r，して適応フィルタをパイプライン化する手法として知られている7）8）9）．この手法では，過去のダ′ゴ＿1＝［0，0，…，0，2【β吊］T誤差を用いて係数を更新した後に出力計算を実行する．しかし，提案法におけるディレードアップ

ここで，Pnl，i（頃は〟分割されたm番目のAFSであデートでは，分散演算の特徴である出力計算におり，添え字の壱は時亥腑こおける官（＝0，1，…，β−1）

けるβ回のAFSの読み出しと更新動作におけるβ番目に更新されたことを表す，ここで，回の更新動作を同時に実行する．この際，出力計

Pm（た）≡Pm，月−1（た−1）

算は重みの′トさいアドレスベクトル，更新動作は重みの大きいアドレスベクトルから更新動作を実である，更新式は次式で表される．

行する．この提案するアルゴリズムを同時更新ア
ルゴリズムと呼び，WAFSの読み出し・更新の様子

且恒（た＋1）＝ Pm，j（た）＋0・5〃翫（た冊1げi，を図4に示す．なお，このアルゴリズムを用いた

宜 ＝ 0，1，…，β−1．

適応フィルタを同時更新形MDA−ADF（MDA−ADF（4）

なお，誤差信号e（た）はusingSimultaneousupdate，SMDA−ADF）と呼ぶことにする．提案する同時更新アルゴリズムを以下

e（た）＝d（た）一y（た）に示す．フィルタ出力封（た）と分割された適応関数（5）である．

空間の出力yⅣl（頃は次式で表される・．＼J−1

4．収束年寺性

y（た）＝ ∑裾（た），γn＝0

システム同定問題に対する従来のMDA−ADFとβ−1訂m（た）＝ ∑∫月一卜壱Pm，月−⊥一i（紆SMDA＿ADFの収束特性を比較する．シミュレーシ

j＝0ョンモデルを図5に示す．ここでヤ 未知システム
は32タップ低域通過FIRフィルタ，入力信号は平均0．0，分散1．0の白色ガ＼ゥス雑音，観測信号は平均−4−

0 1000 2000 3000 4000 5000

0 1000 2000 3000 4000 5000
1teration

1teration

Fig・6 ComparisonofthcconvergencecharacteristicsbetweenMDAaJldSMDAalgorithm（a）MDA−ADF（b）SMDA−ADF（Ⅳ−1）×月個のレジスタを内部に有レ，適応関数

1sanlPlepeHod
門pモIineSbgeO．＝抑山川車叩心血

空間の要素を指定するアドレスマトリクスを凡才個Read
A血机ionleYel−1

ト・一ト十−■−に分割された適応関数空間モジュ」ルに供給する．

Ad出しio11王eノCl」

Sh；nandAddi【jDnト十・−トー■−−

M個の適応関数空間モジュール（AFSM）は，2R

ト・−■−トーーーーーーー

個のラッチ，セレクタ，コントローラ，加算器からMpeli−−eSbgel
Emru匝・￠蛸（構成され，フィルタ出力計算に用いる関数空間の咄

要素の読み出しと，更新のための読み出し書き込」
一一

F机erOlllp山みを行う．コントローラは，アドレスマトリクスから1つのアドレスベクトルを選択し，選択信号をFig・8 TimingchartoftheproposedArchitectureセレクタに供給する．なお，出力計算は最小重みO．0，分散10￣6の入力信号とは無相関の白色ガウを持つアドレスベクトルから順次実行する．適応ス雑音を加えた．また，ステップサイズパラメー

関数空間は，従来法ではRAMを使用していたが，タほMSEが−58・5［dB］ を示す借を選択し，WAFS

提案法では図8の様に読み出しと書き込みを同の分割数はM＝32，16，8（R＝1，2，4）とした．収束特性

時に実行することが可能な構成を用いている．Aすを図6に示す．MDA，SMDAともに，小さいR個の適応関数空間からの出力はバイナリツリーアに対して高速な収束速度を示していることがわか

ダー（BTA）により加算され，シフト加算器を用いlる．提案するSMDA−ADFは従来のMDA−ADFと同て出力を計算する．また，誤差の計算は出力計算等の良好な収束特性を示すことがわかる．と並列に実行される．この際，シフトレジスタには初期値として所望信号d（た）と符号反転の際に加える値，1〉をLSBに与えている．これにより，提案

5．アーキテクチャ法ではフィルタ出力と誤差信号を同時に求めるこ提案するVLSIアーキテクチャを図7，タイミとが可能になる．以上で，フィルタ出力と誤差信ングチャートを図8に示す．入力信号レジスタは号を求めるパイプラインステージは動作を完了す・J−−

わ。（た）あ▲（と）わB．、（た）（a）む。（た）占▲（た）わ2（ん）わ3（た）付いIbitDeby＼り∫（た−1）ズ（た−2）けlズ（た−3）

Fig．7 ProposedVLSIarchitecture（a）BlockdiagTam（b）Adaptivefunctionspacemodule（AFSM）（c）
ExampleoftheinputregisterforN＝4，R＝2，B＝4（d）StpructureoftheAdaptivefunctionspace（e）
Exampleofthebinary−treeadder（BTA）for4−input（f）Structureoftheshiftpadder
る．次いで，適応関数空間は出力計算のための読とである．

み出しと並列にシフトされた誤差信号を用いて更新される．更新動作は，最大量みを持つアドレス

参考文献

ベクトルから順次実行される．

1）B．Widrow and M．E・Hoffっ LAdaptive Switching
Circuit，1960．

6． まとめ

1IRE EWSCON Conv．RecL，pP96−104L2）恒川，高取豊叫三浦，い分散演算によるマルチプ
ライヤレスLMS適応フィルタの高性能アーキテクチャ， 信学論（A），VOl．J−82−A．no・10・pp・1518−1528，

本報告では，従来の分散演算形LMS適応フィル

OcL1999．

3）高橋，恒川，豊臥三浦， ハーフメモリアルゴリ
ズムに基づく分散演算形LMS適応フィルタの高性
能アーキテクチャー1，信学論（A）∴陶1．J−84−ANo・6タの高速アルゴリズムと効果的アーキテクチャを提案した．収束特性は従来のMDA−ADFと同等のpp．777−787，Jlln（−2001・

良好な収束速度を示すことを計算機シミュレーショ

4）KJ，Raghunath and K・K・Parhi，く−AlOO MHz
pIPe−1ined RLS adaptive fi1ter？ Proc・IEEEンにより検証した．

ICASSP■95．Detroit，Michigan，r）p・3187−3190，

今後の課題は，収束速度の詳細な評価を進める

May1995．

5）松原，西川，貴家． DelayedLMSアルゴリズムとともに，収束条件の理論的解析を行うこと，提に基づくパイプライン適応フィルタ． 信学論（A）．

案したVLSIアーキテクチャのVLSI評価を行うこⅤ（）l．J79−A．no．5，pp．1050−1057，May1996・−6一6）A．Harada，K．Nishikawa aIldH．Kiya． Pipelined
Architecture of the LMS Adaptive DigitalFiト
ter with the Minimun Outpllt La七eIICy，11IE上CE
TraIIS・Funda工nentals、pp．1578−1585、Vol．E81−A
No，81998

7）R．HairniNCohen．H．Herzberg，andY．Be）ery，； De−
1ayed adaptive LMS filterlng：Currcnt rcsults；
Proc・IEEEICASSP 90，Pp．1273−1276，Apri1
199（）．

8）G．LoIlg、F・Ling，andJ．G・Proakiポ・ T土1e LMS
algorithm with dclayed coe侃cient adaptation，
1EEE Trans− Aco11St・Speech SignalProc（！SS・，
VOl．37，nO．9，pp・1397−1405，Sept．1989．
9）G・Long．F．Ling，andJ．G．Proakis Corrections
to− The LMSalgorithmwith delayed coefBcient
adaptation∵∵肥EETrans．Acoust．SI−eeChSignal
Process．，VOl．40，nO．1、pp．230−232，．Jall．1992．

−7・−