Design and FPGA Implementation of a Parallel Structure of

電子情報通信学会技術研究報告, No. CAS2001-43, VLD2001-60, DSP2001-62, pp. 103-110, June, 2001.
ハードウェア実現のための進化論的ディジタルフィルタの並列構成の提案と
その FPGA 上での実現
対馬 尚之，福崎 真理，阿部 正英，川又 政征
東北大学大学院工学研究科電子工学専攻
980-8579 仙台市青葉区荒巻字青葉 05
本稿では，進化論的ディジタルフィルタ (evolutionary digital filter: EDF) のハードウェア実現を目的
あらまし
として，内部モジュールの並列構成を提案し，その主要モジュールを FPGA 上に実装する．提案法では，2 乗平均誤
差の収束特性に劣化が生じない範囲で，生殖アルゴリズムをハードウェアに適したものに変更する．さらに，ハード
ウェアを EDF におけるフィルタリングと係数更新の 2 モジュールで構成する．本稿でターゲットデバイスとした 112
万ゲートの FPGA 上に，主要モジュールであるフィルタリング・適応度計算 (FFC) モジュールと生殖・淘汰 (RS)
モジュール内の無性生殖 (ARS) モジュールを 16bit で実装した．その結果，FFC は 14.4MHz の速度で内部モジュー
ルを 4 個実装可能，ARS は 48.4MHz の速度で無性生殖を行う親と同数である 32 個実装可能であった．
キーワード
適応ディジタルフィルタ，IIR フィルタ，システム同定，FPGA
Design and FPGA Implementation of a Parallel Structure of
Evolutionary Digital Filters for Hardware Implementation
Naoyuki TSUSHIMA ，Mari FUKUZAKI, Masahide ABE and Masayuki KAWAMATA
Department of Electronic Engineering,
Graduate School of Engineering, Tohoku University
Aoba-yama 05, Sendai, 980-8579, Japan
This paper proposes a design of a parallel structure of Evolutionary Digital Filters (EDFs) for
Abstract
hardware implementation, and implements the main EDF modules on the FPGA. In the proposed method, a
reproduction algorithm is changed to a simplified algorithm for the hardware implementation. The hardware EDF
consists of the filtering (Filtering and Fitness Calculation: FFC) module and the coefficient update (Reproduction
and Selection: RS) module. FPGA implementation results show that the FFC module can implement 4 parallel
inner modules and run at 14.4MHz, and the ARS (asexual reproduction and selection) module can implement 32
parallel modules and run at 48.4MHz with 16bits on the 1.12M gates FPGA.
Key words
adaptive digital filter, IIR filter, system identification, FPGA
電子情報通信学会技術研究報告, No. CAS2001-43, VLD2001-60, DSP2001-62, pp. 103-110, June, 2001.
1
まえがき
著者らは，これまでに，進化論的計算手法による適応
ディジタルフィルタである進化論的ディジタルフィルタ
(Evolutionary Digital Filter: EDF) を提案している [1]．
EDF は多くの内部フィルタを持ち，これにより多点探索
を行っているため，LMS アルゴリズムを用いた適応フィ
ルタ (LMS-ADF) よりも，1 入力あたりの乗算回数が多
いという問題点がある．しかし，EDF は生物モデルを
模倣しているため，生物 1 個体に対応する内部フィルタ
を並列に動作させることが容易である．このため，ハー
ドウェア化によるフィルタ単位の並列処理によって高速
動作が期待される．さらに著者らは，分散形 EDF を提
案している [2, 3]．分散形 EDF では EDF の個体群を 4
や 8 に分割し，それぞれの個体群間で個体を移民させる
ことで，適応アルゴリズムレベルでの収束特性の向上を
達成している．
そこで，本稿では，EDF 専用のプロセッサによる並
列処理と分散形 EDF としての分散アルゴリズムをハー
ドウェアによって実現することを目標とする．提案法で
はフィルタリングと係数更新にモジュールを分割し，さ
らにそれぞれのモジュール内で並列処理が容易となる構
成を実現している．
本稿では，まず，これまでに提案してきた EDF の構
造と適応アルゴリズムについて概説する．次に，EDF の
ハードウェア実現に適した EDF の構造について述べる．
最後に，主要モジュールを FPGA 上で実現し，その回路
規模によるモジュールの実装可能数と動作速度について
考察する．
2
進化論的ディジタルフィルタ
2.1 EDF の構造
図 1 は EDF の内部構造をブロック図で表したもので
ある．
EDF は内部に同一の構造の可変フィルタ Fi を複数個
持ち，それぞれに EDF への入力信号 x(k) が分配される．
EDF では，内部フィルタを自由に選択可能である．本
稿では，内部フィルタの構成を直接形 II の IIR フィルタ
とし，内部フィルタ Fi の係数ベクトル W ，及び遅延素
子の出力値である内部状態ベクトル S を
W i (k) = [a1,i (k), a2,i (k), · · · , aN,i (k),
b0,i (k), b1,i (k), · · · , bM,i (k)]
(1)
S i (k) = [si (k − 1), · · · , si (k − max(M, N ))] (2)
とおく．ここで，M と N はフィルタの次数である．本
稿では，上記の係数ベクトル W と内部状態ベクトル S
を用いて，生物個体を
I i (k) = [W i (k), S i (k)]
(3)
目標
入力
x(k)
フィルタ F1
フィルタ F2
y (k) d(k) e (k)
1
1
y (k) 出力選択
1
y (k) d(k) e (k)
2
2
フィルタ
評価
フィルタ FA
y (k) d(k) e (k)
A
A
y (k)
2
出力
y(k)
y (k)
A
S,f
係数更新
図 1: EDF の構造
本稿では，誤差関数として一般的である 2 乗平均誤
差を使用し，時刻 k における内部フィルタ Fi の適応度
fi (k) を

−1
0 −1
 1 T

fi (k) =
e2i (k − j)
 T0

(5)
j=0
とする．さらに，EDF では，係数更新を期間 T0 毎に 1
回行う．
2.2 EDF の適応アルゴリズム
EDF の適応アルゴリズムは文献 [1] に示される通りで
ある．本節では適応アルゴリズムの各段階の動作につい
て概説する．
2.2.1 初期世代生成
初期世代における個体群は，探索空間に広く分布する
ように，各個体の係数ベクトル W を平均 0，分散 1 の
正規乱数として生成する．また，内部状態ベクトル S は
0 で初期化する．
2.2.2 生殖と淘汰
EDF では内部フィルタを生物個体に対応させる．それ
ぞれの個体が，個体群中において自らの適応度によって
定まる順位に応じて，無性生殖と有性生殖の 2 つの生殖
戦略を選択する．
ここで，P は生物群の集団，N は生物の数を表す．添
え字 a と s はそれぞれ無性生殖と有性生殖を，添え字 p
と c はそれぞれ親と子を表すこととする．
適応度の高い，Nap 個の親 Pap は無性生殖を行う．無
性生殖は，親に近い係数ベクトル W ac,i,j と親と等しい
内部状態ベクトル S ac,i,j を持つ Nac 個の子を生成する
生殖操作であり，以下の式で実現する．
と定義する．
内部フィルタ Fi の時刻 k における出力を yi (k) とす
ると，出力誤差 ei (k) は
W ac,i,j = W ap,i + r · ni,j
ei (k) = d(k) − yi (k)
ここで，i = 1, 2, · · ·, Nap ，j = 1, 2, · · · , Nac とする．ま
た，r は転写ミスを表すパラメータであり，ni,j は平均
0，分散 1 の正規乱数である．
無性生殖において，親とその親から生成された子の中
で次世代に生き残る個体は，最も高い適応度を持つ 1 個
(4)
である．この誤差によって，各内部フィルタの適応度 fi (k)
を決定する．各内部フィルタの適応度 fi (k) は，誤差 ei (k)
の瞬時値，またはある期間 T0 の誤差 ei (k) の統計量を用
いて求める．
S ac,i,j = S ap,i
(6)
(7)
電子情報通信学会技術研究報告, No. CAS2001-43, VLD2001-60, DSP2001-62, pp. 103-110, June, 2001.
体である．Nap 個の無性生殖の親が存在するため，全体
として Nap 個体が次世代に生き残る．
一方，適応度の低い Nsp 個の親 Psp は有性生殖を行う．
有性生殖ではまず，Psp 内から 2 個体ずつ個体を組み合
わせて親となる Nsp /2 組を作る．そして，それぞれの組
が，親の中間の係数ベクトルと初期化された内部状態ベ
クトルを持つ子 1 個体を生成する．有性生殖は以下の式
で実現する．
1
(W sp,k(m) + W sp,l(m) ) + s · nm
2
=0
W sc,m =
S sc,m
(8)
(9)
ここで，k, l ∈ {1, 2, · · · , Nsp }，m = 1, 2, · · · , Nsp /2 と
する．また，無性生殖と同様に，s は転写ミスを表すパ
ラメータであり，nm は平均 0，分散 1 の正規乱数であ
る．さらに，内部状態ベクトルを 0 に初期化するのは，
有性生殖による子は親と大きく異なったフィルタ係数を
有するためである．
有性生殖において次世代に生き残る個体は，親 2 個体の
うち適応度の高い親 1 個体と生成された子である．Nsp /2
個体の親と Nsp /2 個体の子が生き残るので，計 Nsp 個
体が次世代に引き継がれる．
以上より，無性生殖を行う Nap 個体の親それぞれから
Nac 個体の子が生成され，有性生殖を行う Nsp 個体の親
から Nsp /2 個体の子が生成される．これより，EDF に
おける全個体数 A は以下の式で表される．
3
A = Nap (1 + Nac ) + Nsp
2
3
(10)
EDF では，乱数を使用する処理や数値計算が多い．特
に乱数は生成コストが大きいため，できるだけそのコス
トを削減する必要がある．そこで，本節では，EDF の
収束特性を維持したまま，計算量を削減するための適応
アルゴリズムの改良について述べる．
3.1 適応度計算
EDF における各内部フィルタの適応度 fi (k) は，式 (5)
で表される．しかし，EDF の適応アルゴリズムでは，実
際には適応度の厳密な数値は必要なく，各内部フィルタ
間の適応度の大小関係が得られれば良い．そこで，適応
度は以下に示す部分のみを計算する．
e2i (k − j)
(11)
j=0
これにより，乗算 1 回と除算 1 回を省略できる．
この簡単化によって，適応度による個体間の大小関係
は逆になるが，その順序関係が失われないことは明らか
である．このため，この簡単化を行っても，生殖・淘汰
の動作は簡単化前と全く同一である．
3.2
−0.2 − 0.4z −1 + 0.5z −2
1 − 0.6z −1 + 0.25z −2 − 0.2z −3
0.14z −1 + 0.09z −2
P2 (z) =
1 − 1.48z −1 + 0.91z −2 − 0.2z −3
P1 (z) =
(12)
(13)
P1 (z) は，文献 [1] で使用している帯域通過形フィルタ
である．P2 (z) は P1 (z) と次数が等しい低域通過形フィ
ルタである．EDF の内部フィルタには未知システムと
次数の等しいフィルタを使用する．このため，探索空間
は単峰性である．
実験は以下の 2 種類について行う．Case 2 が本稿にお
いて提案する方式である．
Case 1 オリジナル EDF
Case 2 適応度の高い順に親を組み合わせる
ハードウェア実現に向けた適応アルゴリズムの変更
T
0 −1
るための計算量が多い．そこで，本節では，この選択に
乱数を使用しない方式を提案する．
EDF では個体の生殖方法を決定するために，個体を
適応度の高い順に並び替えている．そこで，提案法では，
並び替えられた順をそのまま利用し，親となる 2 個体を
適応度が高い順に組み合わせる．
以下では，提案する有性生殖の親の組み合わせ方の有
効性を示すために，システム同定実験により，提案手法
を用いた場合に 2 乗平均誤差の収束特性が劣化しないこ
とを示す．図 2 にシステム同定実験を行う系の構成を示
す．入力 x(k) は，平均 0，分散 1 の正規白色雑音である．
実験に使用する未知システムは以下の通りである．
有性生殖手法における交叉を行う親の組み合わせ
方の変更
EDF では有性生殖を行う際に，適応度の低い Nsp 個
体の中から重複なくランダムに 2 個体ずつ親となる個体
を選択している．しかし，この選択方法は乱数を生成す
図 3 にシステム同定の結果を示す．未知システムが変
化した場合の追従性能を評価するために，未知システム
を P1 (z) で開始し，k = 3, 000 で P2 (z) に，k = 6, 000
で P1 (z) に変化させている．学習曲線は，収束特性の比
較と図示のために，200 回の独立したシステム同定実験
を行い，10 サンプルごとに平均した 2 乗誤差について
集合平均を取ったものを用いた．
図 3 より，Case 2 は，収束速度と 2 乗平均誤差の値は
ともに，Case 1 と同等の性能が得られていることが分か
る．このため，有性生殖の親の組み合わせには乱数は不
要であり，乱数生成に必要な計算量を削減することがで
きる．
3.3
初期個体生成時と生殖時に使用する乱数生成方法
の変更
EDF では初期個体の生成と生殖時の転写ミスに平均
0，分散 1 の正規乱数を使用している．正規乱数の生成
は一様乱数の生成に比べ，より大きなコストを要するた
め，ハードウェア向きに生成コストの低い乱数生成法を
採用する必要がある．
以下に，本稿において提案する疑似正規乱数生成法
(Case 2) と比較に使用する乱数を示す．これらの乱数は
近似的に平均 0，分散 1 である．
Case 1 Box-Muller 法による正規乱数生成 [4]
3
Case 2
2ui − 3
i=1
Case 3
12
i=1
ui
−6
電子情報通信学会技術研究報告, No. CAS2001-43, VLD2001-60, DSP2001-62, pp. 103-110, June, 2001.
入力
x(k)
未知システム
目標値
P (z)
d(k)
適応フィルタ
出力
H (z)
y(k)
+
-
+
1
誤差
10
Case 1
Case 2
Case 3
e(k)
0
Square error
10
図 2: システム同定の構成
0
−1
10
−2
10
−3
10
10
オリジナルEDF
適応度の高い順に親を組み合わせる場合
−4
10
−1
Square error
10
0
500
Time k
1000
図 4: 初期個体生成時と生殖時に使用する乱数生成
−2
10
方法を変更した場合の 2 乗平均誤差
−3
10
入力
x(k)
FFC
共有メモリ
y
S,f
SFM 1
−4
10
0
5000
Time k
目標
10000
d(k)
SFM 2
RS
SFM Q
図 3: 有性生殖手法における交叉を行う親の組み合
出力
ARS 1
y(k)
SRS
W,S
わせ方を変更した場合の 2 乗平均誤差
y
ARS Nap
図 5: ハードウェア EDF の構成
ここで，ui は 0 ≤ ui < 1 の一様乱数とする．
Case 1 はこれらの中で最も正規分布に近い乱数生成方
式であるが，対数や平方根の計算を含むため計算コスト
が大きい．そこで，Case 1 は 2 乗平均誤差の収束特性の
比較基準として用いる．Case 2 と Case 3 は共に，一様
乱数を足し合わせることで，乱数の分布が中心極限定理
に従って正規分布に近づくことを期待するものである．
上記の 3 方式について 3.2 節と同様にシステム同定実
験を行い，2 乗平均誤差の収束特性の性能比較をする．使
用する未知システムは P1 (z) のみである．図 4 にシステ
ム同定による 2 乗平均誤差の結果を示す．本結果より，
Case 2 と Case 3 はどちらも基準である Case 1 に近い
ことが分かる．
ここで，Case 2 における 2 倍をビットシフトと見なし
て演算量として考慮に入れないことにすると，Case 3 が
12 回の加減算を必要とするのに対し，Case 2 は 3 回の
加減算で済むため，Case 2 がより低コストであることが
分かる．
4
専用ハードウェアでの EDF の実現
4.1 構成
図 5 に本稿で提案するハードウェアでの実現を目標
とした EDF の構成を示す．専用ハードウェアでの EDF
の実現では，EDF の機能単位でハードウェアを分割す
る．このため，フィルタリング・適応度計算 (Filtering
and Fitness Calculation: FFC) モジュールと生殖・淘
汰 (Reproduction and Selection: RS) モジュールの 2 モ
ジュールで構成する．
このような構成としたのは，フィルタリング・適応度
計算は多くの乗算器を持つ必要があるため，回路規模が
大きくなり，EDF のすべての機能を単一の FPGA 上に
実装するのは難しいためである．また，設計や記述の容
易さの面からも機能単位でモジュールが分かれているこ
とが望ましいためである．
本構成により個別のモジュールの並列度を変化させる
ことが可能となり，構成の自由度が向上する．
図 6 に，1 世代すなわち T0 サンプルの信号を処理す
る場合の，専用ハードウェアによる EDF のタイミング
チャートを示す．RS モジュールで生殖と淘汰を行って
いる間に FFC モジュール内にてフィルタリングと適応
度計算を行う．
4.2
フィルタリング・適応度計算モジュール
4.2.1 FFC モジュールのアーキテクチャ
図 7 に FFC モジュールのアーキテクチャを示す．モ
ジュール内では，フィルタリングと適応度計算を実行する
モジュールを並列化し，高速な演算を実現する．このため
の演算用モジュール 1 個を SFM（Single Filter Module）
と呼ぶ．FFC モジュールを Q 個の SFM と入出力制御用
のモジュールで構成する．ここで，Q は FFC モジュー
ル内に並列化する SFM の個数である．
FFC モジュールは多数の個体のフィルタリングと適応
度計算を行うため，個体数が増えると演算時間が長くな
る．このため FFC モジュールには高速な演算機能が要
電子情報通信学会技術研究報告, No. CAS2001-43, VLD2001-60, DSP2001-62, pp. 103-110, June, 2001.
A i : Ii =[Wi ,Si]受信, フィルタリング, 適応度計算, yi 送信
B i : Si , fi 送信
x,d 受信
A1
FFC
D1
RS
A2
B1 B2
Ai
AA
Bi
C1 C2
D2
C i : Si , fi 受信
D i : 生殖，Ii =[Wi ,Si] 送信
BA
Ci
CA
Di
DA
y出力
個体ソート
個体移動
時間
図 6: ハードウェア EDF のタイミングチャート
データバス
共有メモリ
アドレスバス
制御用バス
x
d
入力信号
受信用
バッファ
入力制御
モジュール
y
SFM1
出力
バッファ
SFM2
出力
バッファ
SFM3
出力
バッファ
SFMQ
出力
バッファ
出力信号
書き込み
モジュール
個体情報
送信
RS
モジュール
S, f
個体
受信用
バッファ
I
図 7: FFC モジュールのアーキテクチャ
求される．
4.2.2 SFM のアーキテクチャ
SFM のアーキテクチャを図 8 に示す．また，図 9 に
SFM の処理手順を示す．
SFM はストアドロジックのプロセッサであり，SFM
にアセンブリ言語プログラムを実行させることでフィル
タリングと適応度計算を実現している．
メモリ構造 メモリに対する SFM のバス構造はハーバー
ド・アーキテクチャであり，SFM はプログラムメモリ 1
個とデータメモリ 2 個を備えている．
入出力ポート SFM には，他のモジュールから SFM へ
送信されるデータを保持するための入力ポートがある．
入力ポートには入力信号 x と目標値 d，個体 I を保持す
るレジスタがある．
また，SFM には，SFM から他のモジュールへ送信す
るデータを保持するための出力ポートがある．出力ポー
トには出力信号 y と個体情報 S ，適応度 f を保持するレ
ジスタがある．
下位モジュール SFM は，演算用下位モジュールとし
て，乗算器，絶対値計算器，算術演算器（AU），バレ
ルシフタの 4 個のモジュールを持つ．この 4 個の下位モ
ジュールはフィルタリングと適応度計算に使用される．
また，SFM は制御用の下位モジュールとして，算術演
算器（AU），加算器，インクリメンタ（INC），デクリ
メンタ（DEC），デコーダの 5 個のモジュールを持つ．
このうち，算術演算器（AU），加算器，インクリメンタ
（INC），デクリメンタ（DEC）の 4 個は，メモリのアド
レス生成に使用され，デコーダは命令デコードに使用さ
れる．
レジスタ SFM には，P レジスタとアキュムレータ（ACC）
という 2 種類の演算用レジスタがある．P レジスタは，
乗算結果または絶対値計算結果を保持するレジスタであ
る．ACC は，乗算結果の和を保持するためのレジスタ
である．
また，SFM には，プログラムカウンタ（PC），イン
ストラクションレジスタ（IR），補助レジスタ（AR）と
いう 3 種類の制御用レジスタがある．この他，SFM に
はリピート命令を入れ子に使用するための制御用スタッ
クがある [5]．
命令セット SFM の命令セットは EDF のフィルタリン
グと適応度計算に必要な命令に限定されている．EDF に
必要な命令は IIR フィルタを構成してフィルタリングを
するための命令と適応度を計算するための命令に分類さ
れる．EDF には応用に合わせて誤差関数を選択できる
という利点があり，SFM の命令セットにおいては，3 種
類の誤差関数を使用することができる．使用できる誤差
関数は，2 乗平均誤差，絶対値平均誤差，最大値誤差の
3 種類である．なお，命令コードのビット幅は 16 ビット
固定長である．
4.3
生殖・淘汰モジュール
4.3.1 RS モジュールのアーキテクチャ
図 10 に RS モジュールのアーキテクチャを示す．RS
モジュールは無性生殖・淘汰を行う無性生殖 (Asexual
Reproduction and Selection: ARS) モジュール，有性
生殖・淘汰を行う有性生殖 (Sexual Reproduction and
Selection: SRS) モジュール，そして適応度に応じて個
電子情報通信学会技術研究報告, No. CAS2001-43, VLD2001-60, DSP2001-62, pp. 103-110, June, 2001.
プログラム
メモリ
下位モジュール
データ
メモリ
データ
メモリ
レジスタ
IR
デコーダ
絶対値
計算器
乗算器
16×3
PC
入力
ポート
加算器
プログラムバス
データバス
データバス
P
INC
出力
ポート
AU
x
AR0
d
..
.
AU
AR7
INC
入れ子
命令用
スタック
I
AU
ACC
y
DEC
INC
S, f
シフタ
図 8: SFM のアーキテクチャ
while not done do
begin
T0 サンプル分の x, d を受信;
個体 I を受信;
for T0 サンプル
begin
k := k + 1;
入力 x(k) をフィルタリングし，
出力 y(k) を計算;
出力 y(k) を送信;
誤差 e(k) を計算
end
適応度 f を計算;
個体情報 S と適応度 f を送信
end.
共有メモリ
y
f
ARS,SRS
制御
モジュール
FFC
S, f
個体
受信用
バッファ
I=[W,S] 個体情報
送信
I
ARS1
ARS2
ARSNap
SRS
モジュール
図 10: RS モジュールのアーキテクチャ
図 9: SFM の処理
体をソートし ARS モジュールと SRS モジュールの制御
を行うモジュールから構成される．
ARS モジュールと SRS モジュールはそれぞれ並列に
動作可能である．ARS モジュールは RS モジュール内に
無性生殖を行う親と同数の Nap 個配置され，各 ARS モ
ジュールが親 1 個体が行う無性生殖の処理を担当してい
る．また，SRS モジュールは RS モジュール内に 1 つの
みである．これは通常有性生殖によって生成される子の
数が，無性生殖において親 1 個体から生成される子の数
と同程度であり，処理量の均一化の観点から並列化の必
要は無いと判断したためである．
制御モジュールの動作は 3 段階に分けられる．まず，
FFC モジュールで評価され ARS モジュールと SRS モ
ジュールで生き残った個体の適応度をソートし，次世代
での生殖方法を決定する．次に，決定された生殖方法に
したがって，各 ARS モジュールと SRS モジュール間で
個体情報を入れ替える．最後に，最も適応度の高い個体
を選択し，共有メモリ上からその個体の T0 サンプルの
出力 y を受信して出力する．
現在，RS モジュール内の ARS モジュールについて記
述が完成している．以降では ARS モジュールの詳細に
ついて説明する．
4.3.2 ARS モジュールのアーキテクチャ
ARS モジュールのアーキテクチャを図 11 に示す．ま
た，図 12 に ARS モジュールの処理手順を示す．
ARS モジュールは生殖と淘汰を並列に実行するため
に，無性生殖を行う部分と淘汰を行う部分に分けられ，
それぞれが独立に動作する．
電子情報通信学会技術研究報告, No. CAS2001-43, VLD2001-60, DSP2001-62, pp. 103-110, June, 2001.
ARS,SRSより
疑似正規乱数生成器
r
FFCより
I=[W,S]
S,f
W
乗算器
nrnd
Parent(W,S)
Child(W) new
Child(S,f) new
Child(W) old
Child(S,f) old
f
加算器
個体
カウンタ
f
比較器
S
Child(W,S)
無性生殖
淘汰
FFCへ
ARS,SRSへ
ARS,SRS
制御モジュールへ
図 11: ARS モジュールのアーキテクチャ
begin
無性生殖による子 I 0 の生成;
子 I 0 を送信;
for i := 1 to Nac do
begin
無性生殖による子 I i の生成;
評価済み個体情報 Si−1 と適応度 fi−1 を受信;
受信した個体を淘汰;
子 I i を送信
end
評価済み個体情報 SNac と適応度 fNac を受信;
受信した個体を淘汰;
最も適応度の高い個体の
個体番号 m と適応度 fm を送信;
Im を送信し，親となる個体を受信
end.
図 12: ARS モジュールの処理
個体カウンタ 前述の様に，RS モジュールは最終的な
出力として最も適応度が高い個体の出力 y を出力する．
全個体の適応度は FFC モジュールによって計算された順
に共有メモリに蓄えられているが，この状態で最適個体
の y を出力するには最適個体は何番目に FFC モジュー
ルによって評価されたかを知る必要がある．図 13 に共
有メモリのメモリ空間を示す．
RS モジュールから個体情報を FFC モジュールに出力
する順番は ARS1, ARS2, · · ·, ARSNap , SRS の順番で
あるため，各 ARS モジュールと SRS モジュール内にお
ける最適個体は，何番目に入力されたかが分かっていれ
ば共有メモリ内における最適個体の出力 y のアドレスを
知ることが可能となる．
下位モジュール ARS モジュールにおける下位モジュー
ルは，疑似正規乱数生成器と比較器の 2 つである．疑似
正規乱数生成器では，3.3 節の実験結果で最も生成コス
トが低かった一様乱数を 3 個加算する方法で，疑似正規
共有メモリ
y1(k-T0+1)
1番目の個体の
出力
y1(k-1)
y1(k)
y2(k-T0+1)
2番目の個体の
出力
y2(k-1)
y2(k)
図 13: 共有メモリのメモリ空間
乱数を生成している．なお，一様乱数発生には M 系列を
使用している [6, 7]．比較器は FFC モジュールから新た
に評価されてきた個体の適応度と，内部に保持している
個体の適応度の比較するためのものである．
レジスタ ARS モジュールには大きく分けて，他の ARS
モジュールと SRS モジュールから親として受信した個体
情報を保存する Parent レジスタ，生成された子の情報を
保存する Child レジスタ，疑似正規乱数を保存する nrnd
レジスタを配置してある．
Child レジスタは無性生殖側と淘汰側に分散して存在
している．無性生殖側での Child(W, S) レジスタは，FFC
モジュールに子を送信するために使用される．また，淘汰
には常に 1 つ前の個体と現在の個体との適応度の比較を
行っているため，淘汰側での Child(W )old ，Child(S, f)old
レジスタは 1 つ前の個体情報を保持し，Child(W )new ，
Child(S, f)new は現在の個体情報を保持するために使用
される．
初期世代の生成 ARS モジュールの構成では，生殖用の
回路を用いて初期世代を生成することが可能である．初
期世代において Parent(W, S) レジスタは 0 となってい
電子情報通信学会技術研究報告, No. CAS2001-43, VLD2001-60, DSP2001-62, pp. 103-110, June, 2001.
表 1: EDF のパラメータ設定値
Nap 無性生殖を行う親の数
32
Nac 無性生殖を行う 1 個の親 32
表 3: FFC モジュールの実装結果
SFM の個数 Q クロック周波数
回路規模
[ 個]
[MHz]
[万ゲート]
が生成する子の数
Nsp
N
M
有性生殖を行う親の数
フィルタの次数
32
3
2
T0
評価期間
10
使用言語
フィルタの次数
Synplicity 社 Synplify
配置配線ツール
Xilinx 社 Foundation シリーズ
Xilinx 社 XCV1000BG560-6
（112 万ゲート）
ターゲットデバイス
（FPGA）
る．ここで，疑似正規乱数の出力に r を掛けない乱数を
セレクタで選択すると，Child(W, S) レジスタには疑似
正規乱数生成器で作られた疑似正規乱数がそのまま代入
され，初期世代が生成される．
4.4 FPGA 上での実装結果
以上のアーキテクチャに基づいて，EDF の FFC モ
ジュールと ARS モジュールを実現した．実現に用いた
EDF のパラメータ設定値を表 1 に示す．また，ハード
ウェア開発環境を表 2 に示す．ここで，データ幅は 16bit，
Q14 フォーマットの固定小数点方式とした．
4.4.1 FFC モジュール
表 3 に，FFC モジュール内に並列化する SFM の個数
を 2 のべき乗で変化させて，FFC モジュールを実装し
た時の動作クロック周波数と回路規模を示す．本論文で
用いたデバイスは約 112 万ゲートであるため，最大 4 個
まで SFM を並列化して FFC モジュールを実装できる．
並列化する SFM の個数 Q を増やすと FFC モジュール
の動作クロック周波数は低くなる．これは，SFM の個数
を増やすと，FPGA の配線空間に余裕がなくなり遅延時
間が大きくなるためである．また，SFM の個数 Q と回
路規模は，ほぼ比例の関係になっている．ここで，FFC
モジュールのクリティカルパスは，SFM のメモリを含む
パスである．
4.4.2 ARS モジュール
表 4 に ARS モジュールを実装した時のクロック周波
数と回路規模を示す．RS モジュールには ARS モジュー
ルを無性生殖を行う親の個数である Nap 個実装する必要
がある．この結果より，ARS モジュールの回路規模は，
ターゲットデバイスとした XCV1000 に Nap 個の ARS
モジュールを十分に実装可能な大きさであることが分か
る．動作周波数は FFC モジュールよりも十分に速く，将
来 FFC モジュールを複数個実装した場合にも対応可能
である．ここで，ARS モジュールのクリティカルパス
は，疑似正規乱数生成器からのパスである．
16.3
15.5
25.8
42.7
4
14.4
78.3
表 4: ARS モジュールの実装結果
クロック周波数
回路規模
表 2: ハードウェア開発環境
Verilog-HDL
論理合成ツール
1
2
[MHz]
[万ゲート]
48.4
2.7
5
むすび
本稿では，EDF のハードウェア実現のための並列構成
を提案し，ハードウェア向けに EDF の適応アルゴリズ
ムを変更した．さらに，フィルタリングモジュールであ
る FFC モジュール，出力選択・係数更新処理モジュー
ルである RS モジュール内の ARS モジュールについて
FPGA 上で実現した．
その結果，本稿におけるターゲットデバイスに対して，
FFC モジュールはその内部に SFM を最大 4 個搭載で
き，ARS モジュールは Nap (= 32) 個搭載するのに十分
な回路規模であることが分かった．
RS モジュール内の SRS モジュールと制御モジュール
は現在製作中であるため，今後完成させる予定である．
参考文献
[1] M. Abe and M. Kawamata, “Evolutionary digital
filtering for IIR adaptive digital filters based on the
cloning and mating reproduction,” IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E81–A, no. 3, pp.
398–406, March 1998.
[2] M. Abe and M. Kawamata, “Convergence behavior of partitioned evolutionary digital filters,” Proceedings of IEEE International Symposium on Intelligent Signal Processing and Communication Systems, vol. 1, pp. 486–491, November 2000.
[3] 阿部正英, 川又政征, “分散形進化論的ディジタルフィ
ルタの収束特性の比較,” 第 15 回ディジタル信号処
理シンポジウム講演論文集, no. A2–3, pp. 149–154,
November 2000.
[4] 奥村晴彦, “C 言語による最新アルゴリズム辞典,” 技
術評論社, 1991.
[5] パターソン, ヘネシー, “コンピュータの構成と設計
上,” 日経 BP 社, 1999.
[6] R. C. Tausworthe, “Random numbers generated by
linear recurrence modulo two,” American Mathematical Society Mathematics of Computation,
vol. 19, no. 90, pp. 201–209, 1965.
[7] 柏木濶, “M 系列とその応用,” 昭晃堂, 1996.