６．５ アダマール（Hadamard）変換 （１）アダマール変換とは

Presentation on theme: "６．５ アダマール（Hadamard）変換 （１）アダマール変換とは"— Presentation transcript:

1 ６．５ アダマール（Hadamard）変換 （１）アダマール変換とは
乗算を使わず加算と減算だけで実行できる直交変換 1896年，素数定理の証明で有名なフランス人 Jacques Salomon Hadamardの名前からこう呼ばれる。 日本では，符号理論の「アダマール変換の発案者として有名。 (注） 「Hadamard」はハダマルドと読みそうだが， フランス人の名前なので「アダマール」と読もう。 また，アダマール行列は， ウォルシュ（Walsh）関数を標本化したものとみなすことができるので， ウォルシュ・アダマール変換（WHT:Walsh Hadamard Transform）と 呼ばれることもある。

2 （２）変換のためのアダマール行列の定義 以下のように再帰的に定義される。 （例）

3 （３）符号変化の回数 符号変化の回数が少ない順に並べる行列を使用する。 （例） 波形としてCos波の変わりに
矩形波を使っていると考えることができる。

4 （４）アダマール変換の定義 次のような行列式として定義される。 逆アダマール変換

5 ＶＢＡでの記述 ①データ宣言とパルス信号の設定 （色々な信号を設定してみよう）
ＶＢＡでの記述　①データ宣言とパルス信号の設定 （色々な信号を設定してみよう） Private Const Num = 8 Private Const PI = Private X(Num) As Double Private Y(Num) As Double Private Z(Num) As Double Private HMat(8, 8) As Double Private Sub パルス() For K = 0 To Num - 1 X(K) = -1 If K >= 3 And K <= 5 Then X(K) = 1 Next X(Num) = X(0) End Sub

6 VBAでの記述 ②結果設定とボタンのＣＬＩＣＫイベントハンドラ
Private Sub 結果設定() With Worksheets("Sheet3") .Cells(1, 1) = "No.": .Cells(1, 2) = "X" .Cells(1, 3) = "Y": .Cells(1, 4) = "Z" For K = 0 To Num .Cells(K + 2, 1) = K: .Cells(K + 2, 2) = X(K) .Cells(K + 2, 3) = Y(K): .Cells(K + 2, 4) = Z(K) Next End With End Sub Sub Sheet3_ボタン1_Click() パルス set8HMAT HT IHT 結果設定

7 VBAでの記述 ③８行８列のアダマール行列設定（その１）
Private Sub set8HMAT() For I = 0 To 7 HMat(0, I) = 1 Next V = 1 If I >= 4 Then V = -1 HMat(1, I) = V If I >= 2 And I <= 5 Then V = -1 HMat(2, I) = V If I = 2 Or I = 3 Or I = 6 Or I = 7 Then V = -1 HMat(3, I) = V

8 VBAでの記述 ④８行８列のアダマール行列設定（その２）
For I = 0 To 7 V = 1 If I = 1 Or I = 2 Or I = 5 Or I = 6 Then V = -1 HMat(4, I) = V Next If I = 1 Or I = 2 Or I = 4 Or I = 7 Then V = -1 HMat(5, I) = V If I = 1 Or I = 3 Or I = 4 Or I = 6 Then V = -1 HMat(6, I) = V If (I Mod 2) <> 0 Then V = -1 HMat(7, I) = V End Sub

9 VBAでの記述 ⑤アダマール変換と逆アダマール変換
Private Sub HT() 'Hadamard変換 For I = 0 To Num - 1 Y(I) = 0 For J = 0 To Num - 1 Y(I) = Y(I) + HMat(I,J)* X(J) Next Y(Num) = Y(0) End Sub Private Sub IHT() '逆Hadamard変換 Z(I) = 0 Z(I) = Z(I) + HMat(I,J) *Y(J) Z(Num) = Z(0) For I = 0 To Num Z(I) = Z(I) / Num Hmat(I,J)は －１または１なので 加算と減算に 置き換えることができる。

10 （５）確認

11 （６）高速アダマール変換 ＦＦＴと同様，時間間引き等による高速ＨＴが可能である。 g[0] g[4] g[2] g[6] g[1] g[5]
第１ステップ 第2ステップ 第3ステップ g[0] G[0] g[4] G[1] －１ G[2] g[2] －１ －１ g[6] G[3] －１ g[1] G[4] －１ －１ g[5] G[5] －１ －１ －１ g[3] G[6] －１ －１ g[7] G[7] －１

12 ＶＢＡでの記述 ①ＦＨＴ（その１） （その他のプログラムはＨＴと同じ）
ＶＢＡでの記述　①ＦＨＴ（その１） （その他のプログラムはＨＴと同じ） Private Sub FHT() 'Hadamard変換) For i = 0 To Num Y(i) = X(i) Next 'ビット逆順の並び替え For J = 0 To Num - 1 JP = J: JX = 0: k = 1 Do While k < Num MD = JP Mod 2 JX = JX * 2 + MD JP = JP \ 2 k = k * 2 Loop If J < JX Then temp = Y(J): Y(J) = Y(JX): Y(JX) = temp End If

13 ＶＢＡでの記述 ②ＦＨＴ（その２） 'FHTの計算 n_half = Num \ 2: Ne = 1
ＶＢＡでの記述　②ＦＨＴ（その２） 'FHTの計算 n_half = Num \ 2: Ne = 1 Do While Ne < Num 符号 = 1 n_half2 = n_half * 2 For JP = 0 To Num - 1 Step n_half2 JX = 0 For J = JP To JP + n_half - 1 jnh = J + n_half xtmp = 符号 * Y(jnh) Y(jnh) = Y(J) - xtmp Y(J) = Y(J) + xtmp JX = JX + Ne Next 符号 = -符号 n_half = n_half \ 2 Ne = Ne * 2 Loop Y(Num) = Y(0) End Sub

14 ＶＢＡでの記述 ③ＩＦＨＴ（その１） Private Sub IFHT() '逆Hadamard変換 For i = 0 To Num
ＶＢＡでの記述　③ＩＦＨＴ（その１） Private Sub IFHT() '逆Hadamard変換 For i = 0 To Num Z(i) = Y(i) Next 'ビット逆順の並び替え For J = 0 To Num - 1 JP = J: JX = 0: k = 1 Do While k < Num MD = JP Mod 2 JX = JX * 2 + MD JP = JP \ 2 k = k * 2 Loop If J < JX Then temp = Z(J): Z(J) = Z(JX): Z(JX) = temp End If 　'FHTの計算 n_half = Num \ 2: Ne = 1 Do While Ne < Num

15 ＶＢＡでの記述 ④ＩＦＨＴ（その２） Do While Ne < Num 符号 = 1 n_half2 = n_half * 2
ＶＢＡでの記述　④ＩＦＨＴ（その２） Do While Ne < Num 符号 = 1 n_half2 = n_half * 2 For JP = 0 To Num - 1 Step n_half2 JX = 0 For J = JP To JP + n_half - 1 jnh = J + n_half xtmp = 符号 * Z(jnh) Z(jnh) = Z(J) - xtmp Z(J) = Z(J) + xtmp JX = JX + Ne Next 符号 = -符号 n_half = n_half \ 2 Ne = Ne * 2 Loop Z(Num) = Z(0) For i = 0 To Num Z(i) = Z(i) / Num End Sub

16 ＦＨＴ結果