読者です 読者をやめる 読者になる 読者になる

Lynx-EyEDの電音鍵盤 新館

広帯域制御屋の駄文とか

周波数領域での信号処理/アダマール変換とユニタリ行列

Lossless

前回まで、ライスゴロム符号化を使った時間領域での音声圧縮・伸長のマイコンへの移植ネタを書きました。

信号処理でもとりわけ画像の信号処理は音声と比較して帯域が広いので周波数領域での信号処理を強いられる事が多いように思えます。今回、アダマール変換に注目しました。理由は簡単そうだから…。(ぉぃ

■ユニタリ行列の必要性

DSPやFPGA連立方程式を求める場合、行列を用いる事が多いと思います。

ベクトルaを正則行列*1とした時

f:id:Lynx-EyED:20110703193746g:image


のようなベクトル内積の解(xの中身)を求める場合は、高校数学の教科書通りに解くならば両辺にaの逆両列のドット積を求め


f:id:Lynx-EyED:20110703193745g:image


このようにして解が求められるはずです。

しかしこの逆行列を求める作業は、2x2行列ならいざ知らず、3x3,4x4となるとかなりシンドイです。

もしaがユニタリ行列である場合、この逆行列を求める手間を軽減してくれます。

ユニタリ行列は次のような性質があります。

f:id:Lynx-EyED:20110703193744g:image
ベクトルaの逆行列がaの転置(行と列を入れ替えたもの)に等しい。(注釈)*2

へぇ・・・・( ゚д゚)ポカーン

なるほど、わからん。




実際の例を見た方が解るかも

こんな条件の時

f:id:Lynx-EyED:20110703193743g:image
f:id:Lynx-EyED:20110703193742g:image
f:id:Lynx-EyED:20110703193741g:image
前述のベクトルの内積はこんな感じ。

f:id:Lynx-EyED:20110703193740g:image



このくらいなら連立方程式を筆算で解いても直ぐ求められてしまうかもしれませんが飽くまで例として。ちなみに(x1,x2)=(3,-1)が答えです。

じつはこの解は速攻求められます。

x1は緑の枠と青の枠同士を積和演算して

f:id:Lynx-EyED:20110703193739g:image


x2は緑の枠と紫の枠を積和演算して
f:id:Lynx-EyED:20110703193738g:image

答えが2倍になってしまってるのは

f:id:Lynx-EyED:20110703193736g:image

という理由です。

◇まとめ:転置して複素共役を取った行列が元の逆行列に等しい行列をユニタリ行列という

◇何が有益か:逆行列計算用マクロを持っていないプロセッサでも簡単な積和演算のみで解が求められ、かつ高速である

次は本題に入ります

アダマール変換(Hadamard transform)

アダマール変換は、アダマール行列に依って求められる関数を基底関数とする変換です。(さっきのユニタリ行列に関連)

フーリエ変換では任意の関数は様々な周期と振幅の三角関数の和で表現出来る事が示されています。

一方アダマール変換ではウォルシュ関数という1と−1のみで表現される符号群で構成します。ただの矩形波です。フーリエ変換では三角関数を用いた周波数での表現になりますが、アダマール変換ではこの周波数に相当する概念をシーケンシ*3と呼びます。

試しにシーケンシ順にウォルシュ関数を並べると

f:id:Lynx-EyED:20110703193914g:image
f:id:Lynx-EyED:20110703193913g:image

f:id:Lynx-EyED:20110703193912g:image
f:id:Lynx-EyED:20110703193911g:image

f:id:Lynx-EyED:20110703193910g:image
f:id:Lynx-EyED:20110703193909g:image

f:id:Lynx-EyED:20110703193908g:image
f:id:Lynx-EyED:20110703193907g:image

この関数群を縦に並べてアダマール行列を構成します

f:id:Lynx-EyED:20110703193906g:image

で、良く出てくるノコギリ波をアダマール変換させてみます
f:id:Lynx-EyED:20110703193905g:image
f:id:Lynx-EyED:20110703193942g:image

アダマール変換は
f:id:Lynx-EyED:20110703193746g:image
ですので、

f:id:Lynx-EyED:20110703193941g:image
となりました。

コレによってノコギリ波をシーケンシ領域(〜周波数領域)に変換出来ました。

このアダマール行列はユニタリ行列なので逆アダマール変換が容易に求められます。

f:id:Lynx-EyED:20110703193940g:image



次回はマイコンにアダマール変換、逆変換を実装します。

◆参考文献



*1:逆行列が存在する、Δ=ad-bcがゼロにならない行列

*2:複素数を含む場合は複素共役を取る必要あり

*3:日本語:交番数