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

分散形進化論的ディジタルフィルタの FPGA上での実現のためのハード ウェア構成
Hardware Structure of Distributed Evolutionary Digital Filters
for a Realization on an FPGA
○ A. S. ジャヤンタ セナラツ ∗ ，阿部 正英 ∗ ，川又 政征 ∗○ A. S. Jayantha Senarath∗ , Masahide Abe∗ , Masayuki Kawamata∗*東北大学大学院工学研究科*Graduate School of Engineering, Tohoku University
キーワード : 適応デ ィジタルフィルタ (Adaptive Digital Filter)，進化論的計算手法 (EvolutionaryComputation)，進化論的ディジタルフィルタ (Evolutionary Digital Filter: EDF)，EDF モジュール (EDF Module)

連絡先 : 〒 980-8579 仙台市青葉区荒巻字青葉 05 東北大学大学院工学研究科電子工学専攻川又研究室
A. S. ジャヤン タ セナラツ， Tel.: (022)217-7095, Fax: (022)263-9169, Email: jayantha@mk.ecei.tohoku.ac.jp

1.

はじめに生物個体に対応する内部フィルタを並列に動作させることが 容易になる．このため，ハード ウェア

著者らは ，進化論的計算手法による適応デ ィジ
タルフィルタである進化論的デ ィジタルフィルタ(Evolutionary Digital Filter: EDF) を提案し てい
る 1) ．EDF には，(1) 多峰性の評価関数空間にお化によるフィルタ単位の並列処理によっても 1 入力当りの処理時間を 短縮することができる．また ，EDF については，FPGA 上に実現することで，その性能を評価し ている 3) ．

いて 極小値にとらわれずに 最小値を 探索できる，(2) 応用にあわせて評価関数を選択できる，(3) 極が 単位円に近い場合でもフィルタの安定性を考慮する必要がない，という利点がある．しかし ，EDFには，LMS アルゴ リズムを用いた適応ディジタルフィルタ (LMS-ADF) よりも，1 入力あたりの処理

そこで，本稿では，まず，EDF の適応アルゴ リズムの概略，EDF モジュールのハード ウェア構成の概略を述べ，分散形 EDF のハード ウェア構成を提案する．その上で，これを FPGA に実装したときの動作周波数とハード ウェア量，サンプ リング周波数について検討する．

時間が長いという問題点がある．これは，EDF が多くの内部フィルタを持ち，これにより多点探索を行っているからである．
この問題を解決する方法とし て，著者らは ，分散形 EDF を提案し ている 2) ．この方法でさらに–1–

$ "# !
9 : 8  * ')& ( %;
# !
$"; A 9 : 8   5 671 3 0 
; 9 : 8 $ " # !  5 241 3 0

$ "# !
9:; 8   ./ ,- +< @ >? =ここで，kは時刻であり，N と M は内部フィルタの次C B>? =; 9: 8; A 9: 8数である．EDF では，フィルタ係数と内部状態を 1組にして生物個体として扱う．ここで，C =max(M, N )とし ，フィルタ係数ベクトル Wi と内部状態ベクト; 9: 8ル Si をそれぞれ ，; 9: 8Wi (k) =[a1,i (k), a2,i (k), . . . , aN,i (k),(3)b0,i (k), b1,i (k), . . . , bM,i (k)]Fig. 1

EDF の構造Si (k) =[si (k − 1), . . . , si (k − C)]

(4)

とおく．

2.

進化論的ディジ タルフィルタ

2.1

進化論的ディジ タルフィルタの構造

進化論的ディジタルフィルタ (EDF) の構造を図1に示す．EDFは係数可変のフィルタを内部に複数EDF では，内部フィルタ Fi の出力誤差 ei (k)を用いて各個体の適応度を計算する．時刻 k に おけ る
出力誤差 ei (k)は目標信号 d(k)と内部フィルタの出力信号 yi (k)により，個持ち，それらの係数を進化論的計算手法に基づ

ei (k) = d(k) − yi (k)く適応アルゴ リズムによって更新する．EDF の内(5)部フィルタ Fi は ，それぞれ 同一の構成を持つ．まとなる．各内部フィルタの適応度fi (k)は，誤差ei (k)た，それらの内部フィルタ Fi の構造は自由に変更と評価期間 T0 の統計量を用いて求められる．例えが 可能である．

ば 次のように適応度 fi (k)を求めることができる．

2.2

fi (k) =適応アルゴリズム

0 −1 1 TX
 T0

j=0

−1
e2i (k − j)
(6)EDF の適応アルゴ リズムは (1) フィルタリング

ここで求められた適応度 fi (k)は，後述する個体の過程と (2) 適応過程に分けることができる．この生殖方法を決める時と EDF の出力となる最も適節ではそれぞれを概説する．

応度の高い個体の出力を選択する時に用いられる．

2.2.1

2.2.2

フィルタリング 過程

適応過程

本稿では，EDF の内部フィルタの構造を直接形

EDF の適応過程では，生殖と選択により係数可II の IIR フィルタとする．内部フィルタ Fi の出力変フィルタの係数を更新する．係数更新する方法

yi (k)は，入力x(k)とフィルタ係数 an,i (k)と bm,i (k)，には ，無性生殖と有性生殖の 2 つがある．EDF でフィルタ係数の内部状態 si (k)から次のように求めは，個体を適応度の高さで 2分し ，適応度の高い個られ る．

体は無性生殖を行い，適応度の低い個体は有性生

si (k)= x(k) −NX

an,i (k)si (k − n)

(1)

殖を行う．
適応度の高い個体は，自分の近傍に子を生成す

n=1

yi (k)=MX
m=0bm,i (k)si (k − m)(2)る無性生殖を行う．これは，適応度の高い個体は，評価関数空間における最適値の近傍にあると考えられるためである．無性生殖では Nap 個体の親 Pap–2–が ，それぞれ Nac 個体の子 Pac を生成する．また ，& ! 

1 個体の親と 生成され る子の中で ，最も適応度の %  高い個体のみが 次世代に引き継がれ る．無性生殖   は以下の式で実現され る．

Wac,i,j=Wap,i + r · ni,j(7)Sac,i,j=Sap,i(8)# "! 

  ! 
#   

ここで，i = 1, 2, . . . , Nap ，j = 1, 2, . . . , Nac とする．
また，r は転写ミスの大きさであり，ni,j は平均 0，#$ ! 

   

分散 1 の正規乱数ベクト ルである．生成され た子は親と似た遺伝子を持つため，内部状態 S はそのFig. 2まま引き継がれ る．

分散形 EDF の構造

適応度の低い個体は ，有性生殖を行う．有性生
殖では，Nsp 個体の親 Psp が 2 個体 1 組になり，それ分割し た生物群に EDF の構造と適応アルゴ リズ

ぞれ 1 個体の子 Psc を生成する．そし て，生成されムを適用するために，分散形遺伝的アルゴ リズム

た子と親 2 個体の中で 適応度の高い方の個体が 次(Distributed Genetic Algorithm: DGA) の分割方世代に引き継がれる．有性生殖は以下のような式法を用いている 4) ．図 2は ，分散形 EDF のブ ロッで実現され る．

ク図である．

Wsc,m=¢
1¡
Wsp,k(m) + Wsp,l(m) + s · nm(9)2Ssc,m=0(10)分散形 EDF は，複数の sub-EDF と出力選択部からな る．各 sub-EDF には ，同一の入力 x(n) を与える．出力選択部では ，もっとも適応度の高い

ここで，k(m)と l(m)は，{1, 2, . . . , Nsp }の中から重複な く選ばれ るものとし ，m = 1, 2, . . . , Nsp /2 とする．また sは転写ミスの大きさであり，nm は平sub-EDF の出力を全体の出力y(n)として選択する．
また分散形 EDF では，各 sub-EDF をリング 状に結合し ，隣接する sub-EDF 間で個体を交換する．

均 0，分散 1の正規乱数ベクトルである．生成された子の遺伝子は親の遺伝子とは掛け離れてし まう
ため内部状態 S は 0に設定され る．

まず，同じ サ イズの S 個の小さな生物群にもとの EDF の生物群を分割する．各 sub-EDF は，分割された生物群を 1つ持ち，生物数が少なくなった点を除いて，元の EDF と同じ 処理を行う．また，

3.

分散形進化論的ディジタルフィ

ある時間間隔で各 sub-EDF の個体を交換する．

ルタ

分散形 EDF のアルゴ リズムは 以下のようにな

EDF の問題点である 1 入力当りの処理時間が 長いという問題を解決することと，内部フィルタをる．

while

並列に動作させることを目標にして，分散形 EDF入力信号がある．

Step 1.

Tm 世代間，各 sub-EDF で生殖，評価，選択・淘汰を行う．

を提案し ている．この節では ，分散形 EDF の概

Step 2.

要を述べる．
分散形 EDF では ，生物群を分割することによりフィルタリングと係数更新を並列化する．この–3–すべての sub-EDF に対し て以下の手続きを行う．

Step 2-1.

sub-EDF Ei の個体の中でTable 1

EDF と分散形 EDF の個体数の比較
EDF

sub-EDF

分散形 EDF

無性生殖における親個体の数

Nap

Nap /S

Nap

無性生殖を行う親 1 個体が 生成する子孫の数

Nac

Nac

Nac

有性生殖における親の数

Nsp

Nsp /S

Nsp

Table 2

EDF モジュール version 2 の仕様

Nap
Nac

無性生殖を行う親の数3232

    6 6 4 5 36 45 3 9 9 < = ;
7 45 3無性生殖を行う 1 匹の親が生成する子孫の数

rNspsT0STm
Nm0.1
320.5
10411


8 45 3

無性生殖の転写ミスの大きさ

"!#$%&(') *+,-.
/012

 : 8 4 5 3 有性生殖を行う親の数
有性生殖の転写ミスの大きさ

Fig. 3

評価期間

EDF モジュール version 2 のハード ウェ
ア構成

生物群の分割数 (sub-EDF の数)
個体交換する世代の間隔

sub-EDF 間で交換する個体数

4.

EDF モジュール version 2 のハード ウェア構成

4.1

ハード ウェア構成

適応度の高い順に Nm 個体を隣接す
る sub-EDF Ei+1 にコピ ーする．

Step 2-2.

sub-EDF Ei+1 では ，Nm

本節では ，著者らが 提案し ている EDF のハー個体をランダ ムに選択し ，Ei からド ウェアモジュールである EDF version 2 3) のハー

コピ ーされた個体を置き換える．

ド ウェア構成を概説する．

EDF モジュール version 2 のハード ウェア構成

end
各 sub-EDF では ，無性生殖と 有性生殖を 行う
親の数は ，それぞれ Nap /S と Nsp /S となる．これに よって 元の EDF と 分散形 EDF の適応度評価
され る個体の総数は等し くなる．よって，各 sub-EDF で適応度評価され る個体の総数 As は 次式で表され る．

Nap
Nap
Nsp
1 Nsp
As =+Nac ++SSS2 S

を図 3に示す．EDF モジュール version 2 は，フィルタリング・適応度計算と係数更新を実現するモジュールとソートモジュールの 2つの下位モジュールを持つ．表 3に EDF モジュール version 2 の仕様を示す．小数点表示方式は ，ハード ウェア記述の容易さと EDF で扱うフィルタの係数の範囲を考慮して固定小数点の Q14 フォーマットに設定され(11)ている．ここで，Q14 フォーマットとは 2 進小数点以下の数字の個数が 14 個となるように小数点が置

表 1に ，評価され る個体数の詳細を示す．

かれ るフォーマットをさす．

以降で述べる EDF，sub-EDF，分散形 EDF ハード ウェアモジュールでは上記のパラメータを表 2のように設定し た．

–4–

Table 3EDF

   

固定小数点 (Q14)

デ ータビット 幅16 bits
Nap + Nsp <= 64<N<3,
M==2     

512 × 16 bits，
256 × 16 bits     

個体数4.2!  
% #$ "

小数点表示方式

フィルタ次数メモリ!  
% #$ "EDF モジュール version 2 の仕様

個体メモリ3 4/1 .

3 02/ 1 .

        (  

& #$ "'  

EDF モジュール version 2 の特徴

EDF モジュール version 2 のフィルタリング・適        
9 76 8 5- +* , )!  

   % #$ "Fig. 4分散形 EDF のハード ウェア構成

応度計算処理は ステート マシン 制御方式である．
これは ，その 前の EDF モジュール version 1 のアセンブ リ言語制御方式から変更された．これによって，処理クロック数削減と回路規模削減を実
現し ている 3) ．し かし ，ステート マシン 制御方式する．この migrator モジュールによって sub-EDF間の個体の交換が 行われ る．分散形 EDF では 並列化の容易性と通信量を考慮し て sub-EDF を リング 状に結合させて個体交換を行う．に変更し たことによりフィルタ構造と誤差関数の変更は回路合成を行わない限り不可能になる．これは，アセンブ リ言語を使わないため汎用性が 減少し たからである．EDF モジュール version 2 ではフィルタ構造を直接形 II の IIR フィルタ，誤差関数を 2 乗平均誤差関数に固定する．そし て，制御方式をステート マシン 制御に変更し ，効率よくそれぞれの sub-EDF の出力信号 yi (k)とそれぞれの出力の適応度fiは出力選択モジュールに入力される．その中から最も高い適応度 fi に対する sub-EDF の出力信号 yi (k)を分散形 EDF の出力として選択し て出力する．

5.2

処理することにより，実際の計算以外の余計な処

sub-EDF 間の通信

sub-EDF モジュール間の通信過程のフローチャー

理クロック数を削減する．

トを図 5に示す．ここでフローチャートの 2 番目の5.

分散形 EDF のハード ウェア構成

5.1

プロセスで隣接する sub-EDF に個体交換開始信号を送信し てから状態が 変わる．それと同時に sendレジスタの内容を常に出力し 続ける．状態が変わっハード ウェア構成て隣接する sub-EDF から 個体情報を受け 取る状

分散形 EDF のハード ウェア構成を図4に示す．今態になって，新し い個体を take レジスタで受け取回設計した分散形 EDF モジュールでは，sub-EDFる．このような操作は sub-EDF モジュールがすべの数 S を 4にし た．それぞれの sub-EDF モジューて同期を取って同じ クロックで動作し ているため

ルは ，前節で説明し た EDF モジュール version 2に可能になる．この方法によって sub-EDF 間の通である．ここでは EDF モジュール version 2 をそ信を行う部分が 非常に少ないハード ウェア資源でのまま使うのではなく，モジュール間の通信がで実現可能になる．

きるように migrator モジュールを埋め込んで使用–5–Table 4使用言語
論理合成，

  !    "#%$'   [ _ &)( * + , - . / , 0 1 2 3 4567 8 9:;

配置配線ツール
Target Device

Table 5< = "#       
> ? &@A#bc

Verilog-HDL
Xilinx 社
Foundation ISE 6.2i
Xilinx 社 Virtex-II(XC2V3000-4FG676)

migrator モジュールの論理合成結果

migrator モジュール

論理合成

回路規模

29slices
264.2MHz

動作周波数< = "#@
 #G 1  >  ?
H&IA JB KA#FPGA 実装環境

境で行った．

6.1

migrator モジュール

migrator モジュールは 分散形 EDF モジュール`aを 構成する sub-EDF の中に 埋め込まれ る．この<B= "#        @ CDE !"#%$'] &)( * + , - . / , 0 . - F 2\^567 8 9:;

モジュールは上記で説明し た通りの過程で動作する．このモジュールの論理合成結果は表 5のようになる．

6.2

    P  Q BAB &TL MBN O
 0BUV RW S . - F # 2567 8EBAX

sub-EDF モジュール

sub-EDF の構造は EDF version 2 とする．subEDF 間の個体交換はモジュールの中に埋め込まれる migrator モジュールによって行われる．そのようにして構成された sub-EDF モジュールの論理合YZ

成結果を表 6に示す．EDF version 2 と比較し た結果も一緒に示す．表 6より，回路規模が減少し ，動Fig. 5

作周波数は同じであることがわかる．回路規模が個体交換過程のフローチャート減少するのは sub-EDF の内部フィルタの数 (個体6.

数) が 減少するからである．また ，動作周波数が論理合成と配置配線結果

同じ になっているのは ，回路のクリティカルパス

本節で，migrator モジュールと sub-EDF モジューが 変わらないためと考えられ る．

ル ，分散形 EDF モジュールの論理合成結果と配置配線結果を示す．論理合成と配置配線は表 4の環–6–

Table 6

分散形 EDF モジュールの論理合成結果

モジュール

sub-EDFEDF version 2モジュール

分散形 EDFEDF version 2

回路規模

1286slices
76.7MHz1351slices
76.7MHz

回路規模

4964slices
76.7MHz1351slices
76.7MHz

動作周波数

6.3

Table 7sub-EDF モジュールの論理合成結果

動作周波数

分散形 EDF モジュール

Table 9分散形 EDF と EDF version 2 モジュールの配置配線結果

図2に示したように sub-EDF モジュールを 4つ組み合わせて分散形 EDF モジュールとする．その時，モジュール

分散形 EDFEDF version 2

それぞれの sub-EDF の出力を出力選択モジュール

回路規模

5479slices
76.7MHz
23.7kHz1512slices
76.7MHz
5.8kHz動作周波数に入力させ，もっとも適応度の高い sub-EDF 出力

サンプ リングを分散形 EDF の出力とし て選択する．この分散周波数形 EDF モジュールの論理合成結果は表 7のようになる．ここで，EDF を一つのモジュールとして設6.4計し たときの場合 (EDF モジュール version 2) と性能評価

表 9に分散形 EDF と EDF モジュール version 2比較する．
表7より，分散形 EDF の場合，EDF version 2 モの配置配線結果を示す．使用した FPGA とツールジュールより少し 小さい sub-EDF を 4 つ並列に動は表4のとおりである．また，分散形 EDF と EDF作し ているために回路規模は EDF version 2 の回モジュール version 2 の 1 個体が 入力信号 1 サン路規模の 3.7 倍になっていることが 確認できる．

プルを処理するのに必要なクロック数について表

分散形 EDF モジュールの動作周波数は表 6 で示

8に 示し た．これらの表から ，sub-EDF モジュー

し た sub-EDF モジュールと同じ になる．それは ，ルを 4 並列にし た分散形 EDF のサンプ リング 周

sub-EDF モジュールを 4つ並列に動作させるので，波数は 23.7kHz となり，4.1 倍に 性能が 向上する

クリティカルパスは 1 個の sub-EDF と同じになることがわかった．また，表 7より回路規模は 3.6 倍ためである．になることもわかった．

表 8に分散形 EDF と sub-EDF ，EDF version 2の 1 個体が入力信号 1 サンプルを処理するために7.

必要なクロック数を示す．表 8より，ど のモジュー
ルもフィルタリング・適応度計算と係数更新に同じ クロック数が必要になることがわかる．これは，一つの個体のフィルタリング・適応度計算と係数更新の過程はど のモジュールでも同じ となるからである．しかし ，ソートに必要なクロックは個体まとめ

本論文では，著者らがこれまでに提案した EDF
モジュール version 2 のハード ウェア構成を利用し ，分散形 EDF のハード ウェア構成を提案し た．そし て，提案するハード ウェア構成を用いた分散形

EDF モジュールを FPGA 上に実装し ，回路規模と動作周波数を評価し た．

数に比例し ているため，モジュール内の個体数が減少するとクロック数も減少する．

–7–

Table 8

sub-EDF と分散形 EDF の 1 個体が入力信号 1 サンプルを処理するのに必要なクロック数

モジュール

分散形 EDF

sub-EDFEDF version 29.6

9.6

9.6

2.0
0.09
0.03

2.00.09-

2.00.4-

フィルタリング・
適応度計算
係数更新ソート
個体交換

参考文献
1) M. Abe and M. Kawamata, “Evolutionary digital filtering for IIR digital filters based on
the cloning and mating reproduction,” IEICE
Trans. Fundamentals, vol. E81-A, no. 3, March1998.
2) M. Abe and M. Kawamata, “Distributed evolultionary digital filters for IIR adaptive digital filters,” IEICE Trans. Fundamentals, vol. E84-A,
no. 8, August 2001.
3) 阿部正英, 荒井拡貴, 川又政征, “進化論的デ ィ
ジタルフィルタのハード ウェア実現のための構成とその FPGA 上での実現,” 第 17 回 回路とシ ステム, 軽井沢ワークショップ , pp. 117–122,April 2004.
4) R. Tanese, “Distributed genetic algorithms,”
Proc. Third International Conference on Genetic Algorithm, June 1989.

–8–