論 文
LU分解の3次元配列への拡張に基づく3次元ディジタルフィルタの分解
について
大木真 橋口住久
（平成2年8月31日受理）
Decomposition of Three-Dimensional Digital Filters Based on the
Extension of LU Decomposition to Three-Dimensional Matrices
MakotoOHKI SumihisaHASHIGUCHI Abstract The decompsition of three−dimensional（3−D）digital filters is considered． For that purpose， the LU decomposition is extended to 3−D matrices and applied to the coefficient matrices of three−variable polynomials． The results of the extended decomposition have many Oor l components as the LU decomposition． In the realization of digital filters， O or l compo− nents of the transfer functions do not need multipliers． Consequently， the decomposition is useful for the realization of 3−D digital filters．
1． ま えがき
一般に，1次元ディジタルフィルタの実現において は，伝達関数の分子および分母多項式を因数分解するこ とにより，様々な実現構造を得ることができる。一方， 多次元ディジタルフィルタの伝達関数の分子および分母 多項式は多変数多項式となるが，多変数多項式は一般に は因数分解が可能でないため，多次元ディジタルフィル タの実現構造を考えることは，1次元の場合のようには 容易ではない1）2）。 この問題に関して，2次元ディジタルフィルタの場 合にはジ2変数多項式の係数がつくる行列に行列の分解 手法を適用することによって，2変数多項式を1変数多 項式の積和形に分解する方法が提案されている3）4）5）6）。 この場合，行列の分解手法としてはジョルダン分解，特 異値分解，LU分解などの方法を利用することができ，分 解手法によってそれぞれ異なった特徴を持っ分解が得ら れる。 3次元ディジタルフィルタに対しても，同様の方法 により分解を考えることが可能であるが，そのためには， 3次元ディジタルフィルタの伝達関数の係数がつくる3 次元配列を分解する方法が必要となる。そのような分解 を実現するためには，2種類の方法が考えられる。1っ の方法は，3次元配列を行列に並べ換え，これに対して 行列の分解手法を適用する方法であり，Nikiasらによっ て試みられた4）。この方法は，行列の多様な分解手法を 利用することができる利点があるが，3次元配列をいわ ば押し？ぶしてしまうため，もとの3次元配列が持って いる対称性などの幾何学的な性質が分解結果に反映され ない。また，この方法によって3変数多項式を分解する と，その結果はッリー状の構造となるため，多項式の次 数が増加するとッリーの裾が急激に広がる傾向がある。 3次元配列を分解するもう1つの方法は，3次元配 列を直接分解するように，行列の分解手法を拡張するこ とである。これによって，もとの3次元配列が持ってい る幾何学的性質を反映するような分解結果を得ることが できる。また，この場合の分解結果は比較的単純な縦続 ・並列接続になる。そのような拡張としては，現在のとこ ろ，3次元外積展開が知られている7）。3次元外積展開 は，行列の特異値分解を3次元配列に拡張したものであ り，展開を中途で打ち切った場合の誤差が2乗ノルムの 意味で最小となる特徴がある。これは，ディジタルフィ ルタの設計においてはきわめて有用な特徴である8）。 一方，ディジタルフィルタの実現問題においては，ハ ードウェア規模を抑えるためにできる限り乗算器の少な い構造が要求されるため，伝達関数の分解結果が0，1 要素を多く含むことが望ましい。この観点からは，行列 のLU分解の3次元配列への拡張が有用であると考えら同様に分解後の要素の中に0や1の占める割合が高く， 3次元ディジタルフィルタの実現において有用である。
2． 行列のLU分解
行列Aの要素をA（i，D，ベクト・レuの要素をu（i） のように書くこととすると，AのLU分解は以下のよう に書くことができる。 ただし， A＝UE］yt一じ1∴1閻
U ＝［Ul…Ur］ 1 u、（2） 1 μ1（3） u2（3）0
1 u，（r＋1） Ul（L）u、（L） … ・r（L） Σ＝di・g（σ1，σ、，…，σr）vt＝
［ i：1 1 Vl（2） Vl（3） 1 v2（3）0
（1） … v1（L） … v2（L） 1Vr（r十1）… Vr（L） また，rは行列Aの階数である。式から分かるように， LU分解は行列Aを対角要素が1の上および下三角行列 σ，vtと対角行列Σの積に分解する。従って，分解結 果は多くの0，1要素を含む。 3次元配列に拡張する場合の便宜のために，ここで は式（1）を以下の形で表しておく。 ただし， r A＝uΣv‘＝Σ・。（u，・x・v。） P＝1 Up ＝（0，…，0，1，Up（P＋1），…，Up（L））t Vp＝（0ヂ・・，0，1，Vp（P＋1），…，vρ（L））t （2） である。ここで，⑧はベクトルの外積（outer prod− uct）を表す。ベクトルα1，…，αNの外積の要素を， ［α1⑭…㊦αN］（il，・一一，iN）と表すとすると，外積とは具 体的には以下のような演算である。 ［α1⑧… ⑧αN］（il，… ，iN）＝α1（il）・一一αN（iN） （3） 2っのベクトルの外積は階数1の行列であり，3っのベ クトルの外積を取れば3次元配列となる。なお，式（2） を要素表示すれば，以下のようになる。r
砲」）＝Σσ，（u，（i）V。（」）） P＝13． LU分解の3次元配列への拡張
（4） LU分解は，スカラーσ1およびベクトルUl， Vl からっくられる行列σ1（Ul⑭v1）の第1行および第1 列が，行列Aの第1行（A（1，」），」＝1，…，L）およ び第1列（A（i，1），i＝1，…，L）に一致するようにσ1， Ul， Vlを定め，次に，σ2（u2⑭v2）の第2行および第 2列が，A一σ1（Ul⑧Vl）の第2行と第2列と一致す るようにσ2，U2， V2を定める…，という操作を行 っていると見なすことが可能である。そこで，3次元配列B∈RLxLxLに対しても，スカラーσ1および
ベクトルu1， Vl，ω1によってつくられる3次元配列 σ1（Ul・X v、 OP・w、）の（i，」，1），（1，ゴ， k），（i，1， k）i，」， k＝1，…，L の位置にある要素が，3次元配列B の
（i，」，1），（1，」，克），（i，1， k） i，」，k＝1，…，Lの位置に ある要素を正確に表現し… ，という操作を行う分解を 考える。ただし，σP，Up， vρ，ωPの0，1以外の要素の 総数が3（L−p）十1であるのに対して，表現されるべき Bの要素は3（L−P＋1）2−3（L−P＋1）＋1個存在す るため，Up， Vp，ωρは単に大きさLのベクトルでは自 由度が不足する。そこで，必要な自由度が得られるよう に分解の項を増やして以下のような分解を考える。 r L 8＝Σσ。Σu，，⑧v。，⑧w。q P＝1 q＝P 要素表示で表せば， ただし， r L B（i，」，k）ニΣ・，Σ・，，（i）・，，（」）ω，，（k） e・ P＝1 q＝P Upq＝（0，…，0，1，Upq（P＋1），…，uρq（L））t v，，＝（0，…，0，1，・，，（P＋1），…，v。，（L））‘ ωpq＝（0，…，0，1，ωpq（P＋1），…，ωpq（L））t （5） （6） この分解は，LU分解と同様にUpg， Vρq，ωpqに多くの 0，1要素を含む。 具体的には，以下のように分解を求める。第41号 1．p＝1，2，…に対して，以下を繰り返す。 （a）次の連立方程式を解く。 B（P，P，P）＝σpL L B（i，P，P）＝σ，Σ u。，（i）， i−P，…，L q：ρ B（P，」，P）＝σ， 2 v，q（」），」＝P，…，L q：’ B（P，P，k）一σ，Σ w。，（k）， k＝ρ，…，L q㌘ B（i，」，P）＝σ， 2 ・。，（i）・。，（」）， q＝P i＝P，…，L j＝ρ，…，L L B（P，あゐ）一σ， 2 ・，，（」）ω，，（k）， q＝P j＝P，…，L k＝・P，…，L L B（i，p，k）＝σ。 ￡ u。，（りω，，（k）， q＝P τ＝P，…，L k＝P，…，L （b）B色」法）を次の式で置き換える。 L B（i，」，k）一σ，Σ Upa（り・，，（」）ω，，（k） q＝P 2．B＝0となったら終了する。 （7） （8） （9） （10） （11） （12） （13） （14） ただし，行列のLU分解を求める場合には，解くべき方 程式が連立1次方程式であったのに対して，1．（a）の方 程式は連立2次方程式であるから，変数の数と式の数が 一致していたとしても必ずしも解が存在するとは限らな い。解が存在しない場合は，さらに分解の項数を増やし て連立方程式を解くことを試みるが，その場合も解くべ き式は連立2次方程式であるから，解の存在は自明では ない。Lが小さい場合には，付録に示すように解の存在 条件および解自体を明確に求めることができるが，Lが 大きくなると，ニュートン法などの数値解法を用いて計 算を行い，計算過程が収束するかどうかによって解の存 在を判断しなければならなくなる。解の存在条件の明確 化は，今後の課題である。
4． 3次元ディジタルフィルタの分解
前節において述べた分解を用いると，B（‘，」，k）を係 数として持つ3変数多項式F（Z1，Z2，Z3）は，以下のよう に1変数多項式の積和形に分解される。 F（Zl，・、，・、）＝ΣB（i，ik）zl−L・］−L・ξ一L i，ik＝1 Ul1（Zl）V11（Z2）Wt l（Z3） U12〈Z1）V12（z2）Wi 2（Z3） UIL（z1） VIL（z2） WIL（z3） U22（z1）V22（z2）W22（z3） U23（Z1）V23（Z2）W23（Z3） U2、（Z1）V2、（z2）W2L（Z3） Urr（z1）Vrr（z2）Wrr（z3） 1 ’ ↓ ‘ 1 ’ UrL〈Zl）VrL（z2）Wr L（z3） 図一1 3変数多項式の分解 Fig．1 Decomposition of 3−variable polynomials． L r L ＝ΣΣ・，Σu，，（i）v。，（元）ω，，（k）・｛−L・1−％ξ一L ら」，夫＝1ρ＝1 q＝ρ一妄昆（曇刷司
（Σ ・。，（ル｛−Lj＝1）（差噺ぽ） L L ＝Σσ。Σu．（z・）Vp9（z2）ω。，（z、） （15） P＝1 q＝P これを，ブロックダイグラムで表せば図一1のようになる。 次に，3次元ディジタルフィルタの伝達関数は2っの 3変数多項式を用いて，以下のように書くことができる。 1V（Z、，Z2，Z3） ∬（X、，Z2，Z3）＝ 1−D（Zl，Z2，Z3） （16） ただし，D（Zl，Z2，Z3）は定数部分が0の3変数多項式であ る。これを，ブロックダイアグラムによって表せば図一2 のようになる。図中における3変数多項式N（Zl，z2， z3） およびD（Zl， z2， z3）の部分を，それぞれ図一1の形に分解 することによって，3次元ディジタルフィルタを1次元 ディジタルフィルタのブロックに分解することができる。N（Zl’z2・z3） D（zlgz2・z3） 図一2 3次元ディジタルフィルタの伝達関数 Fig．2 Transfer function of 3−D digital filters．
5． 数値例
一15＋」5 ・；1・応 z；1・4・潟 z1 十 5 一15一ノ5十一 z；1一石 z；1・4「5 0．5 P Z1 5 図一3 提案された方法による分解結果 Fig．3 Decomposition result by the proposed method． 以下の3変数多項式を，本報告において提案した方 法によって分解する。 ゐ ∬（・、，・、，・、）一ΣB（i，元，k）zl”L・｛−L・ξ一L ら3，k＝1 ＝10＋5・ii＋5・；1＋・；1 十4zrlz；1十z；1zJ1十z王ilz；12；1 （17） 示せば，以下のようになる。 H（Zl，z2，z3） ＝ （zi−1十1）｛z；1（z∫1十4）十5｝ 十｛（z；1十5）十z；1｝ （19） ブロックダイアグラムによって表せば，図一4のようにな る。図から分かるように，本報告において提案した方法 多項式の係数から成る3次元配列Bは，以下のように なる。 ん＝1 克＝2B
」＝1 」＝2 」＝1 ゴ＝2 ‘＝1 1 0 4 5 ‘＝2 1 1 5 10 このBを，3．において述べた方法によって分解すると， 次の結果が得られる。 σ1＝0．5鋤一
i1，寧ヅ
鋤一
i1，苧）‘
・、、一 i1，∼rs）‘ ・、2− i1，一・Es）‘ ω、、一 i1，4＋∼rs）’ w、2− i・，・一調y σ2・＝1．0 u22・＝（0，1）t v22＝（0，1）t ω22＝（0，1）‘ 従って，F（91，X2，Z3）は以下のように分解されることに なる。 H（Zl，z2， z3）＝1十〇．5｛ （・ii＋5禁）＠瓢＋・，i5）（ギ＋4＋es） 5− vg ＋（zii＋ ）（z；1−〉宮）（・；1＋4一万）｝ 5 （18） ブロックダイアグラムによって表せば，図一3のようにな る。比較のためにNikiasらの方法4）による分解結果を 一iz1＋1
’一@t Z2z3◆4
−1 一1z3＋5
図一4 Nikiasの方法による分解結果 Fig．4 Decomposition result by Nikias，s method． から得られる分解結果は単純な縦続・並列接続になるの に対し，Nikiasらの方法から得られる分解結果はツリー 状になる。ここで，Nikiasらの方法から得られる分解結 果は，そのツリーの裾（図の右側部分）において4本の パスに分かれるのに対して，提案された方法による分解 結果は，それよりも少ない3本のパスに分かれる。分解 する伝達関数の次数が増大すれば，両者の差はより顕著 になると考えられる。 6． ま と め 3次元ディジタルフィルタの分解を行うために，行 列のLU分解を3次元配列に拡張する方法について提案 した。本分解法は，分解結果に多くの0，1要素を含む ため，3次元ディジタルフィルタの実現において有用で ある。ただし現在の所，分解の存在条件が必ずしも明確 でない。また，提案された分解法をサイズの大きな3次 元配列に適用すると，連立2次方程式を数値解法によっ て解くためにかなりの計算量を必要とする。従って，存 在条件を明確にすること，および，より効率的な計算方 法を開発することが今後の課題である。山梨大学工学部研究報告 第41号
