「FFT」の編集履歴（バックアップ）一覧はこちら

「FFT」(2010/11/30 (火) 19:53:04) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

*FFT Butterfly DIT動作
**基数２
>A = A * W0 + (B * Wn)
>B = A * W0 - (B * Wn)
-Wn: Twiddle Factor
-W0: 回転子が0の位置、正規化値ともいえる。次のように規定される。
--Real=(入力Twiddle Factorビット幅-2)^2
--Imagine=0

*FFT Butterfly DIF動作
**基数２
>A = (A + B) * W0
>B = (A - B) * Wn
**基数４
>A = (A + B + C + D) * W0
>B = (A -iB - C +iD) * Wn
>C = (A - B + C - D) * Wn1
>D = (A +iB - C -iD) * Wn2

A出力は「Twiddle Factorビット幅-2)^2」を乗算することで出力を正規化している。
A出力の０ビットから下位「入力Twiddle Factorビット幅-2」ビットはZ（ハイインピーダンス）になるので、代わりに0をassignしておくこと。

*基数2FFT
ω：回転子
>A =  A + B
>B = (A - iB)ω
*基数4FFT
>A = A + B  + C + D
>B = (A - iB　- C + iD)ω
>C = (A - B  + C - D)ω2
>D = (A + iB　- C - iD)ω3
*16ポイントFFT時の基数２、基数４FFTの回転子の変化
**基数２DIT
|要素|>|>|>|回転子|
|0|0|0|0|0|
|1|0|0|0|8|
|2|0|0|8|4|
|3|0|0|8|12|
|4|0|8|4|2|
|5|0|8|4|10|
|6|0|8|12|6|
|7|0|8|12|14|
|8|8|4|2|1|
|9|8|4|2|9|
|10|8|4|10|5|
|11|8|4|10|13|
|12|8|12|6|3|
|13|8|12|6|11|
|14|8|12|14|7|
|15|8|12|14|15|
||stage1|stage2|stage3|stage4|

**基数２DIF
|要素|>|>|>|回転子|
|0|0|0|0|0|
|1|0|0|0|8|
|2|0|0|0|4|
|3|0|0|0|12|
|4|0|0|0|2|
|5|0|0|0|10|
|6|0|2|0|6|
|7|0|2|0|14|
|8|0|0|0|1|
|9|1|0|0|9|
|10|2|0|4|5|
|11|3|0|4|13|
|12|4|4|0|3|
|13|5|4|0|11|
|14|6|6|4|7|
|15|7|6|4|15|
||stage1|stage2|stage3|stage4|
-θの計算:毎ステージごとにTwiddleの刻みを半分に

**基数４ DIF
|要素|>|回転子|
|0|0|0|
|1|0|0|
|2|0|0|
|3|0|0|
|4|0|4|
|5|1|4|
|6|2|4|
|7|3|4|
|8|0|8|
|9|2|8|
|10|4|8|
|11|6|8|
|12|0|12|
|13|3|12|
|14|6|12|
|15|9|12|
||stage1|stage2|
-θの計算:毎ステージごとにTwiddleの刻みを1/4に
----
-θの計算
--毎ステージごとにTwiddleの刻みを半分に
-配列の要素をスペクトルに
--√(実数^2 + 虚数^2)
-DIFとDITがある
-基数4と基数2でやる方法がある
--基数4：クロックあたりの効率がいい（高速）が回路規模は大きくなる
--基数2：クロックあたりの効率は悪い（低速）が回路規模は小さくなる
----
#image(dif-dit.png,width=280,dif-dit.png,blank)

-[[６４点高速フーリエ変換回路>http://www.ie.u-ryukyu.ac.jp/~wada/design07/spec_j.html]]
リンク

*FFT Butterfly DIT動作
**基数２
>A = A * W0 + (B * Wn)
>B = A * W0 - (B * Wn)
-Wn: Twiddle Factor
-W0: 回転子が0の位置、正規化値ともいえる。次のように規定される。
--Real=(入力Twiddle Factorビット幅-2)^2
--Imagine=0

*FFT Butterfly DIF動作
**基数２
>A = (A + B) * W0
>B = (A - B) * Wn
**基数４
>A = (A + B + C + D) * W0
>B = (A -iB - C +iD) * Wn
>C = (A - B + C - D) * Wn1
>D = (A +iB - C -iD) * Wn2

A出力は「Twiddle Factorビット幅-2)^2」を乗算することで出力を正規化している。
A出力の０ビットから下位「入力Twiddle Factorビット幅-2」ビットはZ（ハイインピーダンス）になるので、代わりに0をassignしておくこと。

*基数2FFT
ω：回転子
>A =  A + B
>B = (A - iB)ω
*基数4FFT
>A = A + B  + C + D
>B = (A - iB　- C + iD)ω
>C = (A - B  + C - D)ω2
>D = (A + iB　- C - iD)ω3
*16ポイントFFT時の基数２、基数４FFTの回転子の変化
**基数２DIT
|要素|>|>|>|回転子|
|0|0|0|0|0|
|1|0|0|0|8|
|2|0|0|8|4|
|3|0|0|8|12|
|4|0|8|4|2|
|5|0|8|4|10|
|6|0|8|12|6|
|7|0|8|12|14|
|8|8|4|2|1|
|9|8|4|2|9|
|10|8|4|10|5|
|11|8|4|10|13|
|12|8|12|6|3|
|13|8|12|6|11|
|14|8|12|14|7|
|15|8|12|14|15|
||stage1|stage2|stage3|stage4|
-θの計算:
要素の添え字を二進数で桁ごとにn3,n2,n1,n0と割り当てる
|桁(2^x)|3|2|1|0|
|stage0|n3|0|0|0|
|stage1|n2|n3|0|0|
|stage2|n1|n2|n3|0|
|stage3|n0|n1|n2|n3|

**基数２DIF
|要素|>|>|>|回転子|
|0|0|0|0|0|
|1|0|0|0|8|
|2|0|0|0|4|
|3|0|0|0|12|
|4|0|0|0|2|
|5|0|0|0|10|
|6|0|2|0|6|
|7|0|2|0|14|
|8|0|0|0|1|
|9|1|0|0|9|
|10|2|0|4|5|
|11|3|0|4|13|
|12|4|4|0|3|
|13|5|4|0|11|
|14|6|6|4|7|
|15|7|6|4|15|
||stage1|stage2|stage3|stage4|
-θの計算:毎ステージごとにTwiddleの刻みを半分に

**基数４ DIF
|要素|>|回転子|
|0|0|0|
|1|0|0|
|2|0|0|
|3|0|0|
|4|0|4|
|5|1|4|
|6|2|4|
|7|3|4|
|8|0|8|
|9|2|8|
|10|4|8|
|11|6|8|
|12|0|12|
|13|3|12|
|14|6|12|
|15|9|12|
||stage1|stage2|
-θの計算:毎ステージごとにTwiddleの刻みを1/4に
----
-θの計算
--毎ステージごとにTwiddleの刻みを半分に
-配列の要素をスペクトルに
--√(実数^2 + 虚数^2)
-DIFとDITがある
-基数4と基数2でやる方法がある
--基数4：クロックあたりの効率がいい（高速）が回路規模は大きくなる
--基数2：クロックあたりの効率は悪い（低速）が回路規模は小さくなる
----
#image(dif-dit.png,width=280,dif-dit.png,blank)

-[[６４点高速フーリエ変換回路>http://www.ie.u-ryukyu.ac.jp/~wada/design07/spec_j.html]]
リンク