|
|
| Linia 1: |
Linia 1: |
| <math>n</math>
| |
|
| |
|
| {{algorytm|Algorytm Szybkiej Transformaty Fouriera|algorytm_fft|
| |
| 3=
| |
| STF(<math>a = (a_0,\ldots,a_{n-1})</math>)
| |
| '''if''' <math>n</math> nieparzyste '''then'''
| |
| dodaj wyraz <math>a_n</math> do <math>a</math>
| |
| zwiększ <math>n</math>
| |
| '''if''' <math>\frac{n}{2}=1</math> '''then''' '''return''' a
| |
| <math>\omega_n = e^{\frac{2\pi i}{n}}</math>
| |
| <math>\omega = 1</math>
| |
| <math>a^{[0]} = (a_0, a_2, \ldots, a_{n-2})</math>
| |
| <math>a^{[1]} = (a_1, a_3, \ldots, a_{n-1})</math>
| |
| <math>y^{[0]} = SFT(a^{[0]})</math>
| |
| <math>y^{[1]} = SFT(a^{[1]})</math>
| |
| '''for''' k=0 '''to''' <math>\frac{n}{2}-1</math> '''do'''
| |
| <math>y_k = y_k^{[0]} + \omega y_k^{[1]}</math>
| |
| <math>y_{k+\frac{n}{2}} = y_k^{[0]} - \omega y_k^{[1]}</math>
| |
| \omega = \omega \omega_n
| |
| '''return''' y
| |
| }}
| |
