Rekurziven DFT na primeru

Primer uporabe diskretne fourierjeve transformacije

Primer iz prosojnic Rekurzivni DFT.ppt, v kolobarju Z5.

Torej, imaš polinom p(x) = 1 + 2x + 3x^2 + 4x^3 - torej n=4 (ker je n-1=stopnja polinoma). Rad bi izračunal vrednosti tega polinoma v točkah w^0, w^1, w^2, w^3 - torej DFT. Recimo, da delaš v Z5 (vsta števila morajo biti {0,1,2,3,4} - gledaš po modulu 5), koren enote pa je w=2.

Narediš rekurzivni razcep polinoma na sodi in lihi del po običajnem postopku (glej powerpoint vaje od Burgole). Dobiš binarno drevo:

Kako dobiš w^0, w^1 itd. na vsakem nivoju drevesa pod vsako številko?

1. Prvi nivo: samo napišeš številke po vrsti (w^0, w^1, w^2, w^3 - tu boš dobil končne vrednosti/rezultat).

2. Drugi nivo: Kvadriraš w iz prejšnje vrstice in gledaš potence po modulu 4 (ker je n=4): dobiš od leve proti desni:

(w^0)^2 = w^0

(w^1)^2 = w^2

(w^2)^2 = w^4 = w^0 (ker je po mod 4)

(w^3)^2 = w^6 = w^2

3. Zadnji nivo: kvadriraš w iz prejšnje vrstice, od L proti D pride: (w^0)^2 = w^0, (w^2)^2 = w^0, (w^0)^2 = w^0, (w^2)^2 = w^0

(na sliki se mogoče grdo vidi - zadnji nivo je vse w^0)

Sedaj se lotiš dejanskega računanja. Računaš od spodnjega nivoja drevesa proti vrhu.

Računaš po formulah

p(w^k) = w^k * pL(w^2k) + pS(w^2k) leve polovice

p(w^[k+r]) = -w^k * pL(w^2k) + pS(w^2k) desne polovice

r=n/2 -> pri nas r=2.

Rezultat mora priti tak:

Do njega prideš pa tako:

spodnji nivo

Samo prepišeš številke 4, 2, 3, 1.

srednji nivo

Uporabiš rezultate iz prejšnjega (spodnjega) nivoja.

Izračun bo tule od leve proti desni (zaradi preglednosti) - računaš po modulu 5, ker je Z5.

leva veja drevesa

leva polovica

• k=0 (vzameš tisti k, ki je napisan spodaj pod številko!): p(w^0) = w^0 * pL(w^0) + pS(w^0) = 1 * pL + pS = 1 * 4 + 2 = 6 mod 5 = 1 (pL in pS sta iz enega nivoja nižje)

desna polovica

• k=0, r=2 (vzameš vedno r=2) - k=0, ker uporabiš isti k kot pri računanju levega dela

p(w^[0+2]) = -w^0 * pL(w^0) + pS(w^0) = -1*4 + 2 = -2 mod 5 = 3

desna veja drevesa

leva polovica

• k=0: p(w^0) = w^0 * pL(w^0) + pS(w^0) = 1 * pL + pS = 1 * 3 + 1 = 4 mod 5 = 4 (pL in pS sta iz enega nivoja nižje)

desna polovica

• k=0, r=2:

p(w^[0+2]) = -w^0 * pL(w^0) + pS(w^0) = -1*3 + 1 = -2 mod 5 = 3

zgornji nivo

leve polovice

k=0: p(w^0) = 1*1 + 4 = 5 mod 5 = 0 (pL si vzel iz leve veje drevesa, pS pa iz desne).

k=1: p(w^1) = 2*pL(w^2) + pS(w^2) = 2*3 + 3 = 9 mod 5 = 4

desne polovice - istoležno vzameš iste k-je kot pri levi polovici, r=2

izračun za w^2: k=0, r=2 -> p(w^[0+2]) = p(w^2) = -w^0 * pL(w^0) + pS(w^0) = -1*1 + 4 =3 mod 5 = 3

izračun za w^3: k=1, r=2 -> p(w^[1+2]) = -w^1 * pL(w^2) + pS(w^2) = -2*3 + 3 = -3 mod 5 = 2

Rezultat: p(w^0) = 0, p(w^1) = 4, p(w^2) = 3, p(w^3) = 2

Opombe:

Q: zakaj je pol v enacbi p1 pa p2 v odvisnosti od w^2k, če pa nikol ne vstavljaš (vedno sam uporabiš cifro)?

A: fora tega zapisa je verjetno bolj v notaciji (da veš kateri rezultat iz prejšnjega nivoja uporabit). Nekje v enačbi imaš recimo pS(w^2k) = pS(w^4) - vidiš aha, rabim sodi del w^4 iz prejšnejga nivoja.

Q: na konc racunas nad w^2 in w^3, vzel si pa k=0 in k=1.. zakaj? js bi mislu da vzames k=2 in k=3?

A:

Fora je ravno v tem, da vedno izračunaš samo levo polovico z običajnimi k-ji, pri desni polovici pa potem porabiš r. Recimo čisto na vrhu moraš zračunat 4 w-je (w^0 do w^3) - izračunaš jih samo polovico, torej 2 (w^0 in w^1), pri desni polovici pa uporabiš tadrugo formulo (k+r). V bistvu si lahko tkole predstavljaš vrstni red računanja:

w^0: k=0

w^2: k=0, r=2

w^1: k=1

w^3: k=1, r=2

w^0, w^1 sta leva polovica -> uporabiš normalen k.

w^2, w^3 sta desna polovica -> uporabiš k iz levega dela (npr. 2 = 0 + 2 -> k=0, r=2) in pa r kot nekakšen offset.

Drugače lohk - če se prav spomnim - računaš tud vse s samo eno formulo in jemlješ k-je tko kot si ti rekel (kar po vrsti), ampak je to počasneje pa na izpitu verjetno ne dobiš pik za tak postopek.

Za n=8 bi mel recimo na zgornjem niovju w^i po vrsti tako, da je i=0,1,2,3,4,5,6,7.

Zdej bi izračunal leve 4 po običajni formuli p(w^k):

k=0...

k=1...

k=2...

k=3...

-> Sedaj si prišel do desne polovice. "Resetiraš" štetje k-jev na 0 in uporabljaš r = 8/2 = 4.

dejanski k=4 -> vzameš k=0, r=4

dejanski k=5 -> vzameš k=1, r=4

dejanski k=6 -> vzameš k=2, r=4

dejanski k=7 -> vzameš k=3, r=4