計測自動制御学会東北支部第228回研究集会（2006．5．17）
資料番号228−5ヒヒ
金円 性

高のルタレーノイフ

係数遅延と出力滞在時間が共に最小となるNCLMS適応ディジタ
VLSIアーキテクチャ

AHigh−PerformanceVLSIArchitectureforNCLMS AdaptiveDigital
FirtersMinimizing SimultaneouslyCoefBcient DelayandLatency
O佐藤憤悟 i，菅野大輔†，高橋強††，恒川佳隆†

OShingoSATO†，DaisukeKANN■0†，KyoTAKAHASHI††，YoshitakaTSUNEKA＼VA††岩手大学，††岩手県工業技術センター†IwateUniversity，††IwateIndustrialResearchInstitute
キーワTド：NCLMS（Non−CanOnicalLMS），スケジューl）ング（scheduling），係数遅延（Coe爪cientDelay）．
出力滞在時間（1atency），パイプラインアーキテクチャ（pipelinedarchitecture）
連絡先：〒020−8551盛岡市上田4−3−5 岩手大学工学部
佐藤憤悟，Tel．：（019）621−6468，Fax．：（019）621−6468，E−mail：t3306014＠iwate−u．aC．jp，

これまで，LMSアルゴリズムのパイプラ

1． まえがき

イン処理向きのアルゴリズムであるDelayed

現在，適応ディジタルフィルタ（AdaptiveDigital

LMS（DLMS）アルゴリズムが提案されている．こFilter，ADF）はエコーキヤンセラ，アダプティブイ

れは，係数更新に遅延を挿入してパイプライン処

コライザ，ノイズキヤンセラなど広範囲に用いら理を行うことにより，高速なサンプリングレートれている．さらに，近年進展の目覚しいブロードを達成可能である．しかし，タップ数の増加に伴っバンド通信やマルチメディアなどの広帯域信号処て収束速度が大きく劣化することが知られてい理への応用や携帯電話，モバイルコンピューティる．ここで，係数更新に挿入される遅延を「更新ングなどのノト型・低消費電力が要求される携帯遅延」と呼ぶことにする．

端末への応用も期待されている．これより，適応また，LMS適応ディジタルフィルタ（LMSAdap−

ディジタルフィルタを実現する際には，高速なサ

tiveDigitalFilter，LMS−ADF）の構造に対して転ンプリングレート，短い出力滞在時間（Latency），置型の構造を有するLMS適応ディジタルフィル

高速な収束速度，小規模なハードウエア，低消費タが提案されている．これはNCLMS適応ディジ電力など実に多くの性能が要求される．しかし，タルフィルタ（Non−CanOnicalLMSAdaptiveDigL

これらの中には相反する性能も含まれるため，要italFilter，NCLMS−ADF）と呼ばれており，フィル求される性能を同時に満たすことはきわめて困

タモジュールの構成がタップ間隔のパイプライン難であり，高性能な適応アルゴリズムと効果的な構成となり出力滞在時間が非常に短い特長を有アーキテクチャが望まれている．

する．しかし，一方でタップ数の増加に伴い収束
−1−

（C）

l ㌫亮適串榊）∫（ん一∧■−2）
ど（A」3）わ（…）（ん）（a）rorcoern亡ieローde】ayco…PenSa−io＝forユd岬雨ondelaycomper−Sntion（SしIm（りFig．1従来法の適応フィルタの構成（a）全体の構成，（b）補正値計算モジュー
ジュール（TM），（d）係数更新モジュール，（e）BTAl▼ル（CFM），（c）タップモ（f）BTA2速度が大幅に劣化することも知られている．この構成のさらなる高性能化を図る．まず，従来法の原因は，出力計算に過去の係数を用いることによアルゴリズムレベルの構成に対して，加算器レる推定誤差が発生するためである．なお，フィル

ベルのVLSIアーキテクチャを導出する．提案法

タ出力の計算に過去の係数を用いることによるの導出は構成に用いられている乗算器内部を含係数の遅延を「係数遅延」と呼ぶことにする．次めた多入力加算器の構成に孜々が提案している

いで，アップサンプリングとダウンサンプリング

高速4入力2出力加算器を適用する．これにより，を用いたFIRフィルタの係数を分離して係数の遅VLSI向きの規則性と係数遅延のさらなる減少を延の最大値を大幅に減少させ，収束速度を改善同時に実現する．また係数遅延の減少により，補する構成が提案されていが）．

正項生成に必要なハードウェア量を削減することが可能となる．同時に，演算器のスケジューリン

これに対して，我々は係数遅延と出力滞在時間が最小となる適応ディジタルフィルタの構成を提グを行うことでクリティカルパスを減少させ，更案してきた．この構成は従来のNCLMS−ADFのなる高速化を達成する．最後に，提案法のVLSI構成に基づいており，従来と同等の出力滞在時アーキテクチャを示し1JLSI評価を行う．これに間を達成しつつ，同時に係数遅延を大幅に削減より提案法の有効性を明らかにする．

することで従来のNCLMSよりも高速な収束速度を達成できる高性能なアルゴリズムである．
本稿では，これまでの構成を従来法とし．このー2−

廷時間の評価値としてIland，nOr，nOtゲートを2．ノ従来法の構成1△と定義した単位ゲート遅延を用いる2）．
従来法の構成を回1に示す．この構成はタッ

まず，加算器を桁上げ先見加算器（CLAA）、乗プ出力の計算と並列に動作する多入力加算器を算器をBoothアルゴリズムとWallace木を用いた用いており，これにより大略に係数遅延を減少で構成とする．B（〕Othアルゴリズムはシフト反転，きている．なお加算器，乗算器の滞在時間をそれ判別を行うのみであるため，ハードウェア規模はぞれ㌔dd，㌦上土とすると，従来法のピッチ勺は1 ＝ ㌔dd＋「m烏小さくなる．そのため，乗算器は加算器の集合体として扱うことができ，構成の大部分を多入力（1）加算器で橋成することが可能となる．そこで，提である．また，係数遅延の最大値が最′」、となる偶案法で用いる多入力加算器について検討する．

成として最終ステージ以外には1タップを配置し，3．1 多入力カロ算器の構成最終ステージに残りのタップを配置する構成を用いている．これは各ステージでタップ出力と並列多入力加算器の構成は一般的に桁上げ伝播加算に動作する多人力加算器の入力数を多くするた器（CPA）やCLAAを開いたバイナリツリーアダーめである．多人力加算器には加算段数の異なる方式と桁上げ保存形式がある，前者の場合，桁上バイナリツリーアダー（BinaryrIteeAdder，BTA）

げ伝播が行われるため，語長の増加に対して速度のBTAlとBTA2を用いており，これらの加算段が低下し高速化が難しくなる．これに対し桁上げ数は以下のように決定される．まず，加算器と乗保存形式は桁上げ信号を伝播する必要がないた

算器の滞在時間の比を次のように定義する．

m＝し慧」

め語長に依存しない高速な処理が可能となる．
桁上げ保存形式にも1柏11ace木や冗長2進加算（2）木，4人力2出力加算木などの構成法がある．Ⅴ托止

ここで，Lα」はα以下の最大の整数を表す．BTAl

1ace木は，加算段数がlog3／2∧「（〃は入力数を表す）は乗算器と並列に動作するため，加算段数はTm烏であり高速な処理が可能であるが，配線やレイア以下の最大の段数となり，ケ托となる．また，BTA2

ウトが複雑になi）VLSIに適していない．冗長2進はタップモジュールの計算の出力と並列に動作す

加算木は，規則的な橘造でレイアウトが容易でるため，加算段数は㌔dd＋㌦lJと以￣Fの最大の段数あり，加算段数はlog2Ⅳに比例し高速な処理が可となり，m＋1となる．なお，mの値ほ使用する加能であるが，2進表現から冗長2進表現に変換す算器と乗算器の方式や演算語長に依存する．よっるのに時間を要する．これに対して，4入力2出力て，〃1の値により各ステージに配置される多入力

加算木は規則的な構造でレイアウトが容易であ加算器の段数は決定される．これより，全タップ

り，加算段数はlog2∧rに比例し高速な処理が可能

数Ⅳと†れ′が決まるとステージ数は一意に決定さである6）．以上より，本稿では多入力加算器に4れ，係数遅延の最大値も一意に決定される．

人力2出力加算器（以下，4−2加算器とする）を用いて実現する．ここで，図2に我々が提案している高速4−2加算器の棉成を示す．これは上位ビッ

3．提案法の導出

トヘの桁上げを高速に出力できるTypelFAと，1

本章では従来法のVISI向きアーキテクチャをつの入力を3△だけ遅らせて入力できるType2FA導出する．導出の際には語長は16ビットとし，遅の2種類の全加算器を接続することで構成され−3−由一叫、（り（b）（a）Fig．2 高速4−2加算器の構成
Fig．4 STEPlの構成．（a）従来の構成，（b）提案法の構成￣￣三二￣ ニーニー

Fig．5 STEP2の碍成，（a）従来の構成，（b）提案
Fig．3 補正値計算モジュール法の構成

る．従来の4−2加算器が12△なのに対し，この高のように，補正値計算モジュールは3つの段階か

速4−2加算器は9△となり3△高速である1．

らなる構成と見なすことができる．ここでは，各段階ごとに構成を導出していく．

次に，この高速4−2加算器を用いた提案法の構成について示す．従来法の構成はフィルタモジ
ュール，誤差信号生成モジュー［STEPlの構成］

ル，補正値計算モ

図4にSTEPlの構成を示す．ここでは入力信ジュール，係数更新モジュールの4つから構成さ号同士の乗算とその値の累積加算を行っている．

れている．この構成に高速4−2加算器を用いた場

本構成では，乗算後に行う加算処理を乗算器内吾β合，VISI向きの規則性と係数遅延や演算時間ので行う．これにより累積加算を行う加算器を削減削減を同時に実現することができる．本稿では，できる．また清算時間は55△となり，従来法と比さらなる高速化を達成するために，よi）効果的な較して12△の清算時間を短縮できる．

演算器のスケジューリングを行いクリティカルパスを短縮する．スケジューリングを行う際は比較［STEP2の構成］

的に自由度の低い補正値生成モジュールと係数更図5にSTEP2の構成を示す．ここでは，STEPl

新モジュール，誤差信号生成モジューで求められた2個の累積加算値の減算を行い，さルから先に導出し，それらの構成に応じてフィルタモジューらに減算結果と誤差信号との乗算を行う構成とルの構成を導出する．

なっている．本構成では，この部分でクリティカルパスとなるのを回避するため演算器のスケジューリングを行う．図5（b）に示すように，それぞれの3．2 補正値生成モジュール累積加算値と誤差信号との乗算のみを行い，減算補正値計算モジュールの構成を図3に示す．こ処理を次の段階に移行する．これにより，STEP2での清算時間を減少させることができる．

1naTld，nOr，nOげ−トを1△と定義した単位ゲート遅延を用いたときの評価値である2）．
ー4−〟）（人−−1）

ど（万一1）．rルー
ノノ√（万一封1）／I。り）

ノJ▲．（り（b）

Fig．7・係数更新モジュールの構成、（a）従来の橋Fig・6 STEP3の構成，（a）従来の碍成，（b）提案成，（b）提案法の構成

法の構成

州−り守

［STEP3の構成］

図6にSTEP3の構成を示す，ここでは，STEP2までに求められた値を多入力加算器で加算して2）補正された誤差信号亡（た−2）を求める構成となっ，（a）ている．本構成では，まず1段目の4−2加算器でFig．8 誤差生成モジュー構成，（b）提案法の構成

STEP2からスケジューリングにより移行された（b）

ルの偶成，（a）従来法の減算処理を行う．2，3，4段目でこれらの加算処理をきる．さらに，従来の構成と比較して12△の演算行い，5段目で補正対象の誤差信号との加算を行時間を短縮することが可能である，う．最後に6段目の加算器で桁上げ保存形式から通常の2進形式へと変換する．このSTEP3におけ

3．4 誤差信号生成モジュールるゲート遅延は54△であり，これまでの最大ゲー
ト遅延55△よりも′トさい．

誤差信号生成モジュールの構成を図8に示す．

STEP3への人力数は語長16ビットの場合で32

従来法でほこのモジュールで誤差信号を生成し人力となる．本構成では1時刻の更新遅延もしくさらにステップサイズとの乗算を行っていた．しは係数遅延を補正するために2入力必要とするたかし，この構成では誤差信号生成モジュールがクめ，補正値計算モジュールで実現可能な遅延量はリティカルパスとなり，高速化の妨げとなる．そ16となる．このうちパイプライン処理による更こで，本構成ではステップサイズと誤差信号との新遅延に3時刻を使用するため，実現可能なタッ乗算に対してスケジューリングを行い，図8にプ数は係数遅延の最大値が13になるタップ数で示すように純粋な誤差信号のみを生成する構成ある．そのタップ数は極めて膨大な数になる．とする．しかし，ステップサイズが乗算された誤差信号〟re（た）が補正値生成モジュール及び係数更3．3 係数更新モジュール新モジュールにおいて必要とされる．そこで，以下のようにそれぞれ計算式に着目して乗算器の係数更新モジュールの構成を図7に示す．ニ

スケジューリングを行う．

こでは係数更新値を求めるために入力信号と誤【補正値生成式］差信号の累積加算を行っている．本構成では，乗タップ数Ⅳにおける適応ディジタルフィルタの算後に行う加算処理を乗算器内部で行う．これに誤差信号占（たぃこ付加される補正胤l（頃は次式で与より累積加算を行う加算器を削減することがで−5→g（た−2）／も（た） ん…（た）Fig．9 スケジューリング後の補正値計算モジュー

Fig．1〔〕スケジューリング後の係数更新モジュー

ルの構成

ルの構成えられる．

遅延線で遅延させていく．これにより，ステップサイズが乗算された遅延信号を実現する．

ノ坤）＝−2〃［占（た−4），占（た一叶…，占（た一方−5）］∑忘1ご（た−3−申（た−4一言）［係数更新式］∑㌫1ご（た−3一恒（た−5−一五）係数更新式は以下のように表される．

∑㌫1ご（た−3←車（た−6五）∑㌫1ご（た−3−車（た−∴7−1）

ガ（た＋1）＝ガ（た）＋2√⊥∈（た−3）ズ（た−3）（5）∑㌫1ご（た−3−壱）ご（た−8−ま）

ここで，ガ（吊，ズ（可はそれぞれタップ係数ベク

トル，入力信号ベクトルを表し，∑㌫し1ズ（た−3−車（た−5−5−′り（3）ガ（ん）＝［項た）舟（た），…声〃＿1（た）］ア

ここでご（た）は人力信号であり，gはフィルタのス

ズ（た）＝［諾（た），ご（た−1），…，ご（た−∵Ⅳ＋1）1T

テージ数である．この式を変形すると，である．ここで，式（5）を次のように変形する・

A（た）＝−［∂（た−4），∂（た−5），…，占（た−5−5）］∑㌫12〃∬（た−3一言）ご（た・−4一壱）

月（た＋1）＝ガ（た）＋∈（た−3）（2杵ズ（た−3））∑㌫12〃J（た−3−j）ご（た−5−i）（6）∑㌫12〃ご（た一3一言）エ（た−6【り×∑㌫12揮（た一3−j）ご（た一7−壱）

式（6）は，ステップサイズをあらかじめ入力信∑㌫12〃∬（た−3一宜）ご（た一8一言）号に乗算できることを示している．そこで提案法
では補正値計算モジュールと同様に人力遅延線を∑㌫し12〃坤−3一彦）∬（た一方−5一宣）介して〃エ（た）の遅延信号を実現する・図10にその構成を示す．これより，係数更新モジュールに（4）となり，式（4）は，ステップサイズがあらかじめ対して新たな入力遅延線が必要となるが，これは入力信号に乗算できることを示している．そこで補正値計算モジュールの入力遅延線と共有可能で提案法では，入力信号とステップサイズを乗算すある．

るようにスケジューリングを行う．図9にスケジューリングを行った場合の補正値計算モジュー

3．5 フィルタモジュール

ルの構成を示す．このモジュールへの入力は通常

図11tこ従来法のフィルタモジュールの構のFIRディジタルフィルタヘの人力と同様に信号成を示す．各タップ出力の計算に着目すると，線に遅延器を配置した入力遅延線を介して行う．

図12（a）に示す乗算器を用いており、人力信号そして，入力信号ご（た）が入力されたと同時にスとタップ係数を乗算して1つの積を得ている．しテップサイズとの乗算を行い，信号〃ご（た）を入力
一6−

ヅ（ん）

R】terou叩U【Fig．11従来法のフィルタモジュールの棉成（d）Fig・13 ステージ0の構成，（a・）従来法の構成，（b）
提案法の構軋（c）タップ出力回路，（d）多入力加算器（MultjOperan（1Ad（1er，MOA）タイプ1の構成
図13にステージ0の構成を示す．掟案法では乗P、〝。

算器を桁上げ保存形で構成しており，多入力加算（a）器タイプ1がこの乗算器と並列に動作する．ここ（b）

Fig・12 乗算器の構成（16ビット），（a）従来の乗で，多入力加算器タイプ1は3段の4−2加算木であ算器の構成，（b）桁上げ保存形式で出力する乗算り，その入力数は16である．そして，タップ出力回路の構成と4−2加算木の出力を4−2加算器で加算し，CLAAで桁上げ保存形式から通常の2進数へと変換し，かし，最終的に要求される信号はフィルタ自体の最終的なフィルタ出力を得る．

出力であり，各タップ出力は必ずしも1出力であステージ0の清算時間は54△であり，これまでる必要はない．そこで，各タップ出力に用いる乗導出してきたモジュールのクリティカルパスであ算器に図12（b）を用いる．これにより，乗算器

る55△より短い値である．

内部に用いられる最終段の加算器を取り除くことができ，各ステージのクリティカルパスを大幅［ステージ1の構成］に短縮できる．乗算の演算時間の短縮は，回路の図14にステージ1の構成を示す．ここでは，高速化や多入力加算器の段数増加による係数遅タップ出力回路を桁上げ保存形式の乗算器で構延の削減などを実現できる．さらに，フィルタ内成し，デイレーアダーラインの多人力加算器タイ部の加算器を高速も2加算器のみで実現できるた

プ2の出力と加算を行う．そして，残りの人力線め，非常に規則的な構造を達成できる．

に対してはタップ出力と並列に動作する多入力加以下，提案法のフィルタモジュールを1ステー算器タイプ3を挿入する．ここで，多入力加算器ジごとに導出していく．

タイプ2は4段の4・−2加算木，タイプ3は6段の4−2加工ステージ0の構成】

算木であり，入力数はそれぞれ32，128である．
−71

（a）

（b）

Fig．15 最終ステージの構成，（a）従来法の構成，（b）提案法の構成

TAblel ステージ数とタップ数の関係
ステージ数 文献3の構成 従来法の構成 ヨ是冥法の構成
0234622122448963299232
1，984121，9128，122，30430、752983，072ルであり，桁上げ保存形式で出力する．

∵以上の操作により，フィルタモジュールの構成が導かれる．表1に文献3に示されている係数

遅延が極めて小さい構成，従来法の構成1）と，今∴回掟案したVLSI向き構成のステージとタップ数の関係を示す．これより，提案法の構成では従来法よりも係数遅延を抑えることが可能となる．

3．6 全体の構成構成したすべてのモジュールを組み合わせることにより，図16の構成が得られる．この構成では，多入力加算器として4−2加算木を多数用いておi），特にフィルタモジュールで非常に規則的な（C）構造を達成している．そして，これまでの構成とFig．14 ステージ1の構成，（a）従来法の構成，（b）

比較して12△のクリティカルパス削減を達成して提案法の構成，（c）多人力加算器の構成いるため，より高連な処理が可能となる．
以降，最終ステージまで同様の構成である．

4．VLSI評価【最終ステージ〕

図15に最終ステージの構成を示す．このス

提案する適応ディジタルフィルタのVLSIアー

テージは4タップの出力の加算処理を行うモジュー

キテクチャをVtSI設計システムPARTHENON
ー8−中一5十り 笹（トユ∫」）l（り 〟項一1）

1（ト∧「）仰（A一〃一∫−2）

項叫．仏1ト∧一−1）

上（々−ユ）（d）Fig・16 提案法の構成，（a）全体の構成，（b）タップモジュール（TM），（c）係数更新モジュール，（d）補正値計算モジュールにより設計および評価を行う．設計ルールは

構成1）を用いた．その結果を表2に示す．

0．恥mCMOSスタンダードセルとし，電源電圧は表より，提案法の構成はクリティカルパスを5・0［Ⅴ〕とした．語長は16ビットとし，フィルタの削減したことにより，文献3や従来法と比較してタップ数は128とした．そして，比較対象として

16，39［れIHz］と高速なサンプリングレートを達成

従来のNCLMSの構成，文献3の構成，従来法のし，従来のNCI」MSよりも短い出力滞在時間であ−9−−Table2 VLSIevaluationsfor128HtaPS．
従来のNCLMSの構成
MaCllilleCyCleト1S］

Samplingrate［MHz］
1日も印Cy【ns）

Powerdissipation［W］
Area［mmコ］

Number of gates

文献3の構成

195
5．13
65
7．02
119．18
1TO71，491

提案法の構成従来法の構成1

95
9，621126．63
111．79953，982

72

61
16．39
61
9，1098．48
833，539

13、89

72
9．0】
】17．n3

1，014．037

る叫ns】を達成できた．また，多入力加算器に4−2良好な収束特性，低消費電力，小規模ハードウェ加算器を規則的に周いたことにより同時にハーアなどを同時に実鶉可能である．

ドウェア量も削減することができた．これにより，他の構成と比較してサンプリングレート1［MHz］

参考文献当たりの消費電力を低くすることが可能となった．
1）高橋，菅野，恒川， 係数遅延と出力滞在時以上から，提案法は高速性や短い出力滞在時間が最小なFIRフィルタを用いた適応ディジ間，小規模ハードウェア，低消費電力など要求される多くの性能を同時に満たすことができる

タルフィルタの高性能パイプラインアーキ．なテクチャ ，電子情報通信学会投稿中

お，本稿では語長が16ビットにおけるアーキテク
チャの導出およびVlSI評価を行ったが，語長のK72）Hwang

ComputerArith−増加に対しても本提案の手法で同様の性能を有

metic／Principles，Architecture，and De−

するVLSIアーキテクチャの導出が可能である．

sign， JohnWiley＆Sons（1979）

3）J．Okello，H．Ochi，Y．Itoh，Y．Fuk11iandM．

5．むすび

Kobayashi，A NewArchitectureforlmple−

mentingPipelinedFIRADFBasedonClas−

本稿では，係数遅延と出力滞在時間が最小となる適応ディジタルフィルタのVLSIアーキテク

SificationofCoe航cients，チャを提案した．提案法は，従来法のアルゴリズ

OnCircuitsaIldSystems−ⅠⅠ‥AnalogandDig−

ムレベルの構成をさらに高性能化するために加italSignalProcessing，Vol．49、No．6，PpA18−

算器レベルでVtSI向きの構成を導出した．さら426，JuIle2002．に，構成をスケジューリングすることでクリティ

IEEETlansactions

4）H・T・Kung， Why Systolic Architec−

カルパスを減少させ，高速なサンプリングレー

t11re？．

トを達成した．導出した構成は，特にフィルタモ

IEEE Computer，Vol．15，No．1，Pp．37−

46，1982．

ジュールにおいて極めて規則的な構造を実現し

5）C．L，Seitz， Concurrent VLSIArchitec−ている．さらに収束速度の劣化原因である係数遅延も削減することができた．係数遅延の減少

ture，は，補正項生成に必要なハードウェアも削減可能

No．12、pp．1247−1265，1984．

である．以上から提案法はタップ数に依存し、ない

IEEETranS．OnComputers，Vol．C−33，

6）高木直史，算術演算のVtSIアルゴリズム，コ

短い出力滞在時間，高速なサンプリングレート，ロナ社（2005）

一10−