Diskretna Fourierjeva transformacija/algoritem

• je linearna preslikava, ki slika iz enega vektorskega prostora v n-dimenzionalni prostor. Se pravi, da vektor slikamo v vektor v drugem prostoru. vektorski prostor je obseg in MORA vsebovati primitivni koren

• v kompleksnem prostoru za vsak n obstaja n-ti primitivni koren. Najosnovnejši primer primitivnega korena v kompleksnem prostoru je

• zahtevnost algoritma je reda n log(n)

Literatura (odlomek iz knjige Osnovni algoritmi): http://lalg.fri.uni-lj.si/~vilfan/DFT.pdf

Rekurzivni algoritem

Nimam cajta za teorijo, bom samo postopek v praksi napisal.

1. zapišemo polinom po naraščajočih stopnjah
2. če manjkajo koeficienti do 4 ali 8 dopišemo ničle
3. v prvi delni polinom napišemo koeficiente, ki so poleg x-ov lihe stopnje, v drugi delno pa sode stopnje
4. Točko 3 ponavljamo na delnih polinomih, dokler ne pridemo do polinoma stopnje 0
5. vsakokrat ko obiščemo točko 4 razpolovimo n in se vračamo na 3
6. zapišemo polinome po formuli 3.16 in knjige: formula zgleda:

p(ω^k) = ω^k * p₁(ω^2k) + p₂(ω^2k)

p(ω^{k + r}) = ω^{k + r} * p₁(ω^{2(k + r)}) + p₂(ω^{2(k + r)})

kar je enako

p(ω^{k + r}) = − ω^k * p₁(ω^2k) + p₂(ω^2k)

vseskupaj izhaja iz: n=2r in ω^{j + r} = − ω^j velja še več (ω^{j + r})² = ω²j

1. Nadaljujem s sestavljenjem in povečevanjem n dokler ne pridem do osnovnega n

Da bo stvar bolj jasna:

Primer

p(x) = 1 + 2x + 3x² + 4x³ v Z₅

Pa začnimo: ω je potemtakem 2, n=4

razbijemo na polinoma: p₁(x) = 2 + 4x

p₂(x) = 1 + 3x

ker še nimamo samo x^0 ponovimo vajo

p₁₁(x) = 4

p₁₂(x) = 2

p₂₁(x) = 3

p₂₂(x) = 1

pravtako, ker po prvem razbitju nismo imeli še rezultata smo razbili n=2, torej je naša nove omega 4, ker je 4^2=1, pa zdej začnimo sestavljat:

p₁(ω⁰) = ω⁰ * p₁₁(ω⁰) + p₁₂(ω⁰) = 1 * 4 + 2 = 1

p₂(ω⁰) = ω⁰ * p₂₁(ω⁰) + p₂₂(ω⁰) = 1 * 3 + 1 = 4

zdej se pa prestavimo nazaj na n=4, pa ponovimo

p(ω⁰) = ω⁰ * p₁(ω⁰) + p₂(ω⁰) = 1 * 1 + 4 = 5 = 0

p(ω¹) = ω¹ * p₁(ω²) + p₂(ω²) = 2 * 3 + 3 = 4

Torej je naš rezultat [ 0, 4, 3 ,2 ]

Iterativni algoritem

Imamo p(x), zanima nas pa p(ω⁰), p(ω¹), ..., p(ω^n-1).

p(x) lahko predstavimo tudi kot

p(x) = Q(x)(x-a) + r(x)

predvsem pa uporabljamo lastnost matematike:

p(x) mod(s(x)) = [p(x) mod(s(x))] mod(s(x))

Če uporabimo nekaj srednješolske matematike in se spomnimo, da je stopnja ostanka manjša od deljitelja

st(r(x)) < st(x-a) = 1

in da velja

p(a) = r(a)

Zanima nas torej ostanek r(x)

p(x) = Q(x)(x-a)(x-b)...(x-ž) + r(x)

Pri tem računanju je veliko dragih deljenj, ki pa jih je možno s pravilno razporeditvijo ugodno "poceniti". ω⁰, ω¹, ..., ω^n-1 premešamo in premešane poimenujemo v c₀, c₁, ..., c_n-1.

Za manj operacij vzamemo 2r = n in razdelimo računanje DFT na dva podproblema:

q1(x) = (x-c0)(x-c1)...(x-cr-1)
q2(x) = (x-cr)(x-cr+1)...(x-cn-1)

"Mešanje" potenc ω poteka po točno določeni formuli

c_j = ω^rev(j),

kjer funkcija rev() pomeni operacijo zamenjave vrstnega reda bitov, bit reverse. Tako se npr. pretvorijo indeksi, če imamo 4 potence:

j -> j2 -> rev(j)2 -> rev(j)
0 -> 00 -> 00 -> 0
1 -> 01 -> 10 -> 2
2 -> 10 -> 01 -> 1
3 -> 11 -> 11 -> 3

Konvolucija polinomov