半正定値計画法を用いたマルチレートディジタルフィルタ設計

Design of multirate digital filters by semi-definite programming○ 永原 正章 (京都大学), 山本 裕 (京都大学), スティーブン P. ボイド (スタンフォード大学)

M. Nagahara (Kyoto University), Y. Yamamoto (Kyoto University),
S. P. Boyd (Stanford University)
Abstract This paper proposes a new design methodology for interpolators, based on the modern
sampled-data control theory. In contrast to the conventional ﬁlter designs where the methods aremostly based on frequency domain approximation techniques, the proposed method makes use of
the sampled-data H ∞ control theory, thereby allowing for optimizing the intersample behavior andaliasing eﬀects. The method is executable for high conversion ratio by semi-deﬁnite programming.

はじめに

1wc

yc-F (s) - Sh

ディジタルフィルタ設計には，窓関数法や等リプルフィ
ルタ，双一次変換法など様々な設計手法がある [6, 8]．こA/D

ydxduduczc- ↑ L -K(z) - Hh/L -P (s) D/A

れらの手法は，ある望ましい特性（例えば理想ローパス特性）を近似する手法であり，その近似には対象となる
図 1: インターポレータの信号処理系信号処理系全体の特性は考慮されていない．したがって設計の際には，それぞれの信号処理系に応じて近似手法を適切に選ぶ必要がある．また，これらの設計法は，元の連続時間信号がナイキスト周波数以下に完全に帯域制限されていると仮定して離散時間領域での議論となっている．しかし現実には連続時間信号を完全に帯域制限することは不可能であり，元信号にはナイキスト周波数以上の成分も含まれる．したがって，より厳密な設計をするためには，連続時間信号と離散時間信号が混在したサンプル値系として信号処理系を捉えなければならない．
この問題に対し，[3] ではディジタルフィルタ設計に
サンプル値 H∞

従来の設計法 [4] では，インターポレータにおけるアップサンプラの定数が大きい場合，設計問題が大きくなりすぎて現実的な時間では解けなかった．本研究では，問題を半正定値計画問題 [5] として定式化することにより，現実的な時間で大きな規模の問題が解けることを示す．

2問題設定
本節ではインターポレータの設計問題を定式化する．
図 1 のブロック線図は，アナログ入出力を含めたイン制御理論を導入し，連続時間信号に対ターポレータの信号処理系を示している．アナログの入する最適信号復元問題が議論されている．この手法によ

力信号 wc ∈ L2 [0, ∞) にたいして連続時間ローパスフィり，ナイキスト周波数以上の周波数成分をも考慮した設

ルタ F (s) を作用させ信号 yc を得る．この信号 yc は計が可能となる．この研究以降，サンプル値制御理論を

周波数特性 F (s) を持つアナログ信号であり，F (s) は離用いたディジタル信号処理系の研究が行われている (た散化されるべき信号源の先見情報であると考えることがとえば [4])．

できる．従来のディジタル信号処理では，この F (s) と本研究では，これらの研究をもとに FIR (Finite Im-いう特性は考慮されていない1 ．次にこの信号 yc はサンpulse Response) 型インターポレーションフィルタ設計にサンプル値制御理論を導入し，信号復元の最適化を

プル周期 h で動作するサンプラ Sh によって離散時間信H∞設計により行う．

号 yd に変換される．この信号はディジタル装置へ記録されたり，またディジタル通信路を通して伝送される．

本研究で考慮する信号処理系は複数のサンプル周波数ディジタル信号 yd から元信号 yc を復元するさいに，が存在するマルチレート系であり，また信号の復元に離散化したときのサンプル周期よりも速い周期で動作す連続時間の遅れを許すため無限次元系となる．本稿でるホールド要素を用いてアナログ信号に変換するシステ

は，これを離散時間リフティングを用いて単一レート系

ムがオーバーサンプル D/A 変換器である [6, 8]．このへと変換し，ファーストサンプル・ファーストホールド

オーバーサンプル D/A 変換器では図 1 のようにイン(FSFH) 近似 [7] を用いて有限次元離散時間系へと変換する．

1 離散時間領域での取り扱いでは，F (s) はナイキスト周波数以下にカットオフ周波数を持つ理想フィルタである．

本節では，ファーストサンプルファーストホールド近- e−τ swc-F (s) yc+- Sh - ↑ L -K(z) - Hh/L?
f-ec−-P (s) 6

似 [7] を用いて，この問題が有限次元単一レート系の設計問題に帰着されることを示す．なお，簡単のため，FIRフィルタのタップ数を n = L とする．
まず離散時間リフティングを定義する．

TLL := (↓ L) 1 z . . . z L−1,

L−11 z −1 . . . z −L+1 (↑ L).
L :=図 2: インターポレータ設計の誤差系
ターポレータ K(z)(↑ L) が用いられる．この信号の流れは次のようになる: 離散時間信号 yd がアップサンプラ(2)↑ L によってサンプル周期 h/L の離散時間信号 xd に変つぎの定理が成り立つ．

換される．アップサンプルされた信号にはイメージング定理 1 インターポレータの誤差系 T にたいして，有成分が生じるので [6, 8]，これを除去するためにディジ限次元離散時間系 {G1,N , G2,N : k = 0, 1, . . . , L, N =タルフィルタ K(z) をほどこす．ここでフィルタ K(z)は FIR フィルタK(z) =nαk z −k(k)1, 2, . . . } が存在して，次式が成り立つ．
L
(k) lim G1,N +αk G2,N  = T .
N →∞ 
∞k=0k=0とする．この出力信号 ud は，サンプル周期 h/L で動作する 0 次ホールド Hh/L により連続時間信号 uc に変換される．このホールド出力信号はアナログフィルタ

P (s) によって平滑化され出力信号 zc が得られる．

証明

離散時間リフティング (2) を用いて，インターポ

レータ K(z)(↑ L) は次のように書ける．

K(z)(↑ L) = L−1
L K(z), ,ここでの設計目的は，与えられた F (s)，P (s)，L にたK(z):= LL K(z)L−1
L

いしてアナログの入力信号 yc を忠実に復元するようなデL=ィジタルフィルタ K(z) を求めることである．そこで元信度の時間遅れが許されるため τ := mh (m は非負の整数）の時間遅れ e−mhs を挿入する．このブロック線図において入力信号 wc から誤差信号 ec (t) := zc (t) − uc (t − mh)までのシステムを T とおく．このとき設計問題は次の

T0 ...

10αk φk (z).

k=0号とインターポレータの出力を比較するために図 2 のブロック線図を考える．ここで，信号の復元処理にはある程

ただし

φ0 (z) :=φ1 (z) :=10 ...

01

0

T0...

0,T,

プロパな P (s)，アップサンプラ定数 L，遅れステップ...
T
φL−1 (z) := 0 0 . . . 0 1,
T
.
φL (z) := z −1 0 . . . 0m が与えられたとする．このとき与えられた正数 γ にたいして，


ここで K(z)は 1 入力 L 出力の LTI システムであり，ように定式化される:問題 1 安定かつ厳密にプロパな F (s) および安定かつT wc 2
T  :=sup< γ,wc ∈L2 [0,∞) wc 2(1)を満たす FIR フィルタ K(z) の係数 αk , k = 0, 1, . . . , Lを求めよ．

3

有限次元問題への帰着
問題 1 は連続時間の時間遅れ要素を含む無限次元系のマルチレート信号処理におけるポリフェーズ表現 [6, 8]
h を導入する．に相当する．つぎに一般化ホールド H

h := Hh/L L−1 .
HL
以上より図 2 のマルチレート系は図 3 の単一レート系へと等価変換される．
つぎにサンプル値系図 3 にたいして FSFH(ファーストサンプルファーストホールド) 近似 [7] を導入する．

設計問題であり，またアップサンプラ (↑ L) を含むマル

FSFH 手法とは，周期 h のサンプル値系の連続時間入チレート系の設計問題でもある．

出力を， 周期 h/N （N は自然数）のサンプラとホー問題 3 [周波数の分割] 評価関数

- e−τ swc
F (s)- Sh - K(z)-H h -P (s)?
g-ec
6−Jnω (α)

L(k)jωhjωh :=max
αk G2,N (e )
G1,N (e ) +ω=ω1 ,... ,ωnω 
k=0

図 3: 単一レート系への変換

ẽd


ec
Sh/N wcw̃dT  Hh/N を最小化する FIR フィルタ係数 α = (α0 , α1 , . . . , αL )を求めよ．
この問題 3 を半正定値計画問題に定式化する．まずAi := G1,N (ejωi h ),図 4: FSFH 離散化
ルドによって離散化し，系を近似的に離散時間系へ変換する手法である．
（図 4）．この手法により，周期 h のサ

ARi := Re Ai ,AIi := Im Ai ,R
Bik:= Re Bik ,I
Bik:= Im Biki = 1, 2, . . . , nω ,ンプル値系 T にたいして近似離散時間系


TN (z) := G1,N (z) + G21,N (z)K(z)G
22,N (z)= G1,N (z) +L(k)

αk G2,Nk=0(k)G2,N := G21,N (z)φk (z)G22,N (z)が得られ (付録参照)，さらに文献 [7] により，N → ∞で TN ∞ → T  となる．24

半正定値計画問題としての定式化(k)Bik := G2,N (ejωi h ),k = 0, 1, . . . , Lとおくと
L(k)jωhjωh αk G2,N (e )
G1,N (e ) +
k=0


LL





RRI
I=  Ai +αk Bik + j Ai +αk Bik 
k=0k=0 AR + L α B R −AI − L α B I 
ii
k=0 k ik
k=0 k ik=LIRR AIi + L
αBA+αBi
k=0 k ik
k=0 k ik=: Xi (α),i = 1, 2, . . . , nω

前節までで，サンプル値系の設計問題は離散時間系の設計問題へ帰着された．すなわち，問題は以下の最適化問題として定式化される．と書ける．したがって，問題 3 は次のように定式化できる．すなわち，

問題 2 評価関数


L



(k)jωhjωh J(α) := max G1,N (e ) +αk G2,N (e )
ω∈[0,π/h] 
k=0を最小化する FIR フィルタ係数 α = (α0 , α1 , . . . , αL )を求めよ．
この問題は ω ∈ [0, π/h] が連続パラメータであり，線形半無限計画問題として定式化されるが [2]，本研究では，

Xi (α) ≤ t,i = 1, 2, . . . , nωの制約条件のもとで t を最小化するような α を求めよ．
ここで (3) の不等式条件は以下の不等式条件と等価である．
tI
Xi (α)TXi (α)
tI≥ 0,i = 1, 2, . . . , nω

したがって，問題 3 は以下の半正定値計画問題に定式化

周波数 ω を有限個に分割し半正定値計画問題として定された．

式化する．すなわち，周波数を次のように分割する．

問題 4 [半正定値計画問題] 不等式制約条件
tI
Xi (α)≥ 0, i = 1, 2, . . . , nωTXi (α)
tI0 ≤ ω1 < ω2 < · · · < ωnω ≤ π/hすなわち，問題 2 の最適化問題を次の問題で近似する．

(3)のもとで t を最小化するような α を求めよ．

A

Gain Response

付録

35
3025

定理 1 の中の G1,N , G21,N , G22,N は以下で与えら

L=64れる．
L=32

G1,N (z) := z −m FdN (z),20
Gain (dB)

L=16

G21,N (z) := −PdN (z)H,

15
10FdN := LN Sh/N F Hh/N L−1
N ,5PdN := LN Sh/N P Hh/N L−1
N ,S := [1, 0, . . . , 0],0⎡-5-1010-1100Frequency (rad/sec)⎢H := ⎢⎣

N −1⎤q..

⎥⎥,⎦.
q

図 5: フィルタ K(z) のゲイン応答

5設計例までで定式化した半正定値計画問題を解くことにより設計する．まず F (s)，P (s) として次のフィルタを用いる．

F (s) =1,s+1



FdN , PdN の状態空間実現は [1] などを参照のこと．

[1] T. Chen and B. A. Francis: Optimal SampledData Control Systems, Springer, New York (1995)[2] 平林, 陶山: ディジタルフィルタ設計への数理計画

P (s) = 1.

また，サンプル周期を h = 1，FSFH の分割数を N = L(すなわち N = 16, 32, 64)，むだ時間を m = 0，周波数の分割を 0 [rad/sec] から π [rad/sec] まで等間隔に 6 分割とする．設計によって得られたインターポレーション
フィルタのゲイン応答を図 5 に示す．

おわりに
本論文では，マルチレート信号処理におけるインターポレータの設計問題をサンプル値 H ∞ 制御の枠組みで定式化した．また，そのサンプル値制御問題に対して等価離散時間系が存在することを示し，半正定値計画問題として定式化した．本論文では省略したが，提案した手法と同様にして，デシメータのサンプル値最適化設計も半正定値計画問題として定式化できる．
なお，半正定値計画問題 4 における行列 Xi (α) はその要素がほとんど 0 の疎行列である．この構造をうまく利用することにより，数値計算に必要なメモリのサイズを小さくすることが可能であると考えられ，今後の課題である．

L blocks⎤⎫
1 ⎪⎪⎢ . ⎥⎬.. ⎥ l.
q := ⎢⎣⎦⎪
⎪
⎭
1
⎡

参考文献

ここでは，L = 16, 32, 64 のインターポレータを前節

6

G22,N := SFdN (z)法の応用, システム/制御/情報, Vol. 47, No. 6,pp. 284–289 (2003)[3] P. P. Khargonekar and Y. Yamamoto: Delayed
signal reconstruction using sampled-data control,
Proc. of 35th Conf. on Decision and Control, pp.
1259–1263 (1996)[4] 永原, 山本: インターポレータのサンプル値 H ∞設計, システム制御情報学会論文誌, Vol. 14, No.
10, pp. 483–489 (2001)[5] L. Vandenberghe, S. Boyd: Semideﬁnite Programming, SIAM Review, Vol. 38, pp. 49–95 (1996)[6] P. P. Vidyanathan: Multirate Systems and Filter
Banks, Prentice Hall, Englewood Cliﬀs, (1993)[7] Y. Yamamoto, A. G. Madievski and B. D. O. Anderson: Approximation of frequency response forsampled-data control systems, Automatica, vol.
35, pp. 729-734 (1999)[8] G. Zelniker and F. J. Taylor: Advanced Digital
Signal Processing: Theory and Applications, Marcel Dekker (1994)