|
FFT乗算 |
|
FFT乗算原理の確認 |
| 最終更新日：2006/04/18 |
●概要
FFTは俄かに実現するのは困難なので、素のDFTで実際に確認を行った。２要素同士の乗算をDFTで行った。
回転子は予めテーブル化してある(下表)。但し、N=4 なので、値は単純となっている。超簡単な複素構造体と、複素乗算関数を作成し、確認した。
DFT 回転子行列
| 1 | 1 | 1 | 1 |
| 1 | -j | -1 | j |
| 1 | -1 | 1 | -1 |
| 1 | j | -1 | -j |
IDFT 回転子行列
| 1 | 1 | 1 | 1 |
| 1 | j | -1 | -j |
| 1 | -1 | 1 | -1 |
| 1 | -j | -1 | j |
表で、j は虚数単位(一応電気出身なので、どうしても j を使ってしまう)
●結果
11 * 11 = 121 の例(10進数とすれば、121で正解)
1111 * 1111 = ? の例
100進数だとすれば、桁上げ処理を行い、1234321 を得る。
1000進数と思えば、11011 * 11011 となり、そのまま解答となる。
1000進数とすれば、999999 * 999999 = 999998000001
下位は、001
真中は、1996002 + 998 = 1997000で、000
上位は、998001 + 1997 = 999998で、
999998000001 となる。
同じく、千万進数とすれば、そのままが解答となる。つまり、
9990000999 * 9990000999 = 99800119960020998001
入力に矛盾がなければ、N進数と勝手に思えば良い。桁上げは一般的に生じるとし、常に処理する必要がある。以上、どうやらDFT乗算は本当らしい。
○コード例
上記試験に使用したつたないコードを紹介する。
Structure WW '複素構造体
Public Re As Double
Public Im As Double
Sub New(ByVal R As Double, ByVal I As Double)
Me.Re = R
Me.Im = I
End Sub
End Structure
Dim A(), B(), C() As Double '入力データ
Dim FA(), FB(), FC() As WW 'フーリエ変換
'回転子行列(順)
Dim FW(,) As WW = { _
{New WW(1, 0), New WW(1, 0), New WW(1, 0), New WW(1, 0)} _
, {New WW(1, 0), New WW(0, -1), New WW(-1, 0), New WW(0, 1)} _
, {New WW(1, 0), New WW(-1, 0), New WW(1, 0), New WW(-1, 0)} _
, {New WW(1, 0), New WW(0, 1), New WW(-1, 0), New WW(0, -1)}}
'回転子行列(逆)
Dim RW(,) As WW = { _
{New WW(1, 0), New WW(1, 0), New WW(1, 0), New WW(1, 0)} _
, {New WW(1, 0), New WW(0, 1), New WW(-1, 0), New WW(0, -1)} _
, {New WW(1, 0), New WW(-1, 0), New WW(1, 0), New WW(-1, 0)} _
, {New WW(1, 0), New WW(0, -1), New WW(-1, 0), New WW(0, 1)}}
Private Sub btnGo_Click(ByVal sender As System.Object, ByVal e As
System.EventArgs) Handles btnGo.Click
Dim i, j As Integer
Dim W As WW
ReDim A(3)
ReDim B(3)
ReDim C(3)
A(0) = txtA0.Text
A(1) = txtA1.Text
B(0) = txtB0.Text
B(1) = txtB1.Text
ReDim FA(3)
ReDim FB(3)
ReDim FC(3)
'被乗数のDFT
For i = 0 To 3
For j = 0 To 3
W = ComplexM(New WW(A(j), 0),
FW(i, j)) 'データの虚数部は0
FA(i).Re = FA(i).Re + W.Re
FA(i).Im = FA(i).Im + W.Im
Next
Next
'乗数のDFT
For i = 0 To 3
For j = 0 To 3
W = ComplexM(New WW(B(j), 0),
FW(i, j)) 'データの虚数部は0
FB(i).Re = FB(i).Re + W.Re
FB(i).Im = FB(i).Im + W.Im
Next
Next
'コンボリューション(畳み込み)
For i = 0 To 3
FC(i) = ComplexM(FA(i), FB(i)) 'ここがミソ
Next
'結果のIDFT
For i = 0 To 3
For j = 0 To 3
W = ComplexM(FC(j), RW(i, j))
C(i) = C(i) + W.Re
'結果は実数部のみ採用
Next
C(i) = C(i) / 4
Next
txtc0.Text = C(0).ToString
txtc1.Text = C(1).ToString
txtc2.Text = C(2).ToString
txtc3.Text = C(3).ToString
End Sub
'複素乗算
Private Function ComplexM(ByVal A As WW, ByVal B As WW) As WW
ComplexM.Re = A.Re * B.Re - A.Im * B.Im
ComplexM.Im = A.Re * B.Im + B.Re * A.Im
End Function