4.3 Diskret Fourier-transform (DFT)

Steg 1 — finn $w$. Med $N=4$ er
$$w = e^{2\pi i/4} = e^{i\pi/2} = i,$$
og potensene er $w^0=1$, $w^1=i$, $w^2=-1$, $w^3=-i$. Vi trenger de negative potensene: $w^{-1} = -i$, $w^{-2} = -1$, $w^{-3} = i$.

Steg 2 — sett opp summen. Formelen er $\displaystyle c_k = \frac14\sum_{j=0}^{3}f_j w^{-jk}$. Siden $f_1 = f_3 = 0$, bidrar bare $j=0$ og $j=2$:
$$c_k = \frac14\left(1\cdot w^{0} + (-1)\cdot w^{-2k}\right) = \frac14\left(1 - w^{-2k}\right).$$

Steg 3 — regn ut for hver $k$. Her er $w^{-2k} = (-1)^{k}$, siden $w^{-2} = -1$:
$$c_0 = \frac14(1-1) = 0, \qquad c_1 = \frac14(1+1) = \frac12,$$
$$c_2 = \frac14(1-1) = 0, \qquad c_3 = \frac14(1+1) = \frac12.$$

Svar:
$$\hat{c} = \left(0,\ \tfrac12,\ 0,\ \tfrac12\right).$$

Kontroll 1 — middelverdien. $c_0$ skal være gjennomsnittet av $1,0,-1,0$, som er 0. Stemmer.

Kontroll 2 — invers DFT. Bygg $f_j = \sum_k c_k w^{jk} = \tfrac12 w^{j}+\tfrac12 w^{3j}$:
$$f_0 = \tfrac12+\tfrac12 = 1, \qquad f_1 = \tfrac12 i + \tfrac12(-i) = 0,$$
$$f_2 = \tfrac12(-1)+\tfrac12(-1) = -1, \qquad f_3 = \tfrac12(-i)+\tfrac12 i = 0.$$
Vi får tilbake $(1,0,-1,0)$. Stemmer.

Kontroll 3 — konjugert symmetri. Dataene er reelle, så vi må ha $c_{N-k} = \overline{c_k}$. Her er $c_3 = \tfrac12 = \overline{c_1}$, og $c_2 = 0 = \overline{c_2}$. Stemmer.

Tolkning. All energien ligger på $k=1$ og $k=3$, og de to hører sammen som et konjugert par. Regner du ut hva de svarer til i den inverse formelen, får du $\displaystyle \cos\left(\frac{2\pi j}{4}\right)$ — altså er datavektoren nettopp én ren cosinussvingning, samplet i fire punkter. Og det stemmer: $\cos(2\pi j/4)$ for $j=0,1,2,3$ gir $1,0,-1,0$.

a) Test symmetrien. Vi trenger $c_{4-k} = \overline{c_k}$:

- $k=0$: $c_4 = c_0 = 1$, og $\overline{c_0} = 1$. I orden.
- $k=1$: $c_3 = -i$, og $\overline{c_1} = \overline{i} = -i$. I orden.
- $k=2$: $c_2 = 0$, og $\overline{c_2} = 0$. I orden. (Merk at $k=2 = N/2$ er midtfrekvensen, og den må være reell — 0 er reell.)

Signalet er reelt.

Finn det. Den inverse DFT-en er $f_j = \sum_k c_k w^{jk}$ med $w=i$:
$$f_0 = 1+i+0-i = 1,$$
$$f_1 = 1 + i\cdot i + 0 - i\cdot i^{3} = 1 + i^2 - i(-i) = 1-1-1 = -1,$$
$$f_2 = 1+i\cdot i^{2}+0-i\cdot i^{6} = 1 - i - i(-1) = 1-i+i = 1,$$
$$f_3 = 1+i\cdot i^{3}+0-i\cdot i^{9} = 1 + i(-i) - i\cdot i = 1+1+1 = 3.$$
(Her brukte vi $i^6 = i^4i^2 = -1$ og $i^9 = i^8 i = i$.)

$$f = (1,\,-1,\,1,\,3).$$
Alle reelle, slik testen lovet.

Kontroll: middelverdien er $\displaystyle \frac{1-1+1+3}{4} = 1 = c_0$. Stemmer.

b) Test symmetrien. For $k=1$: $c_3 = i$, mens $\overline{c_1} = -i$. De er ulike, så symmetrien brytes, og signalet er ikke reelt.

Finn det likevel, som kontroll:
$$f_0 = 1+i+0+i = 1+2i,$$
$$f_1 = 1+i\cdot i+0+i\cdot i^{3} = 1-1+1 = 1,$$
$$f_2 = 1+i\cdot i^2+0+i\cdot i^6 = 1-i-i = 1-2i,$$
$$f_3 = 1+i\cdot i^3+0+i\cdot i^9 = 1+1-1 = 1.$$
$$f = \left(1+2i,\ 1,\ 1-2i,\ 1\right).$$
To av komponentene er komplekse. Testen stemmer.

Poenget med oppgaven. I a) kunne vi svart «ja, reelt» på tjue sekunder uten å regne ut den inverse i det hele tatt. Det er hele nytten av testen — og det er den ferdigheten delpunktet er ute etter.

Merk forskjellen mellom de to vektorene: bare fortegnet på $c_3$ er endret. Én fortegnsfeil er alt som skal til for å ødelegge symmetrien — og det er også derfor testen er en så god kontroll på egen regning.

a) $w=i$, så $w^{-1}=-i$, $w^{-2}=-1$, $w^{-3}=i$.

$$c_0 = \frac14\left(3+1-1+1\right) = 1.$$
$$c_1 = \frac14\left(3+1\cdot(-i)+(-1)(-1)+1\cdot i\right) = \frac14\left(3-i+1+i\right) = 1.$$
$$c_2 = \frac14\left(3+1\cdot(-1)+(-1)\cdot 1+1\cdot(-1)\right) = \frac14\left(3-1-1-1\right) = 0.$$
$$c_3 = \overline{c_1} = 1 \qquad \text{(etter reell-testen, siden dataene er reelle)}.$$

$$\hat{c} = \left(1,\ 1,\ 0,\ 1\right).$$

Kontroll: middelverdien av $3,1,-1,1$ er $\displaystyle \frac{4}{4}=1 = c_0$. Stemmer.

b) Skiftet. $\tilde{f} = (1,\,-1,\,1,\,3)$.

$$\tilde{c}_0 = \frac14\left(1-1+1+3\right) = 1.$$
$$\tilde{c}_1 = \frac14\left(1+(-1)(-i)+1\cdot(-1)+3\cdot i\right) = \frac14\left(1+i-1+3i\right) = \frac{4i}{4} = i.$$
$$\tilde{c}_2 = \frac14\left(1+(-1)(-1)+1\cdot1+3\cdot(-1)\right) = \frac14\left(1+1+1-3\right) = 0.$$
$$\tilde{c}_3 = \overline{\tilde{c}_1} = -i.$$

$$\hat{\tilde{c}} = \left(1,\ i,\ 0,\ -i\right).$$

Kontroll mot skifteegenskapen. Teoremet sier $\tilde{c}_k = w^k c_k$ med $w=i$:

$k$	$w^k$	$c_k$	$w^kc_k$	$\tilde{c}_k$ regnet direkte
0	$1$	$1$	$1$	$1$
1	$i$	$1$	$i$	$i$
2	$-1$	$0$	$0$	$0$
3	$-i$	$1$	$-i$	$-i$

Alle fire stemmer. $\blacksquare$
Legg merke til amplitudene. Før skiftet: $\left|c_k\right| = (1,1,0,1)$. Etter: $\left|\tilde{c}_k\right| = (1,1,0,1)$. Identiske — bare fasene er endret. Det er nøyaktig det teoremet lover, og det er en gratis kontroll på at du ikke har regnefeil.
Merk også at $\tilde{f} = (1,-1,1,3)$ er den samme datavektoren vi fant i eksempel 2a. Det er ikke tilfeldig: koeffisientvektoren der var $(1,i,0,-i)$, som er nøyaktig $\hat{\tilde{c}}$ her.

a) Båndbegrensning. Skriv leddene med Eulers formler:
$$2\cos\!\left(\frac{2\pi j}{8}\right) = e^{2\pi ij/8}+e^{-2\pi ij/8}, \qquad \cos\!\left(\frac{4\pi j}{8}\right) = \tfrac12\left(e^{2\pi i\cdot2j/8}+e^{-2\pi i\cdot 2j/8}\right).$$

Signalet inneholder altså frekvensene $m = 0, \pm1, \pm2$. Alle oppfyller $|m| < N/2 = 4$, så signalet er båndbegrenset for $N=8$. Ingen aliasing, og koeffisientene kan leses av eksakt.

Uttelling her: begrunnelsen er selve poenget. Å skrive at «alle frekvenser er mindre enn 4 i tallverdi» er det som gjør resten av besvarelsen gyldig.

b) Avlesning. Etter ortogonalitetsrelasjonen har leddet $e^{2\pi imj/N}$ DFT-koeffisient 1 i indeks $m$ og 0 ellers. Med $w = e^{2\pi i/8}$, og med negativ indeks $-m$ oversatt til $N-m$:

- konstanten 1 gir $c_0 = 1$;
- $e^{2\pi ij/8}$ gir $c_1 = 1$, og $e^{-2\pi ij/8}$ gir $c_{7} = 1$;
- $\tfrac12 e^{2\pi i\cdot 2j/8}$ gir $c_2 = \tfrac12$, og $\tfrac12 e^{-2\pi i\cdot2j/8}$ gir $c_{6} = \tfrac12$.

Alle øvrige er null:
$$\hat{c} = \left(1,\ 1,\ \tfrac12,\ 0,\ 0,\ 0,\ \tfrac12,\ 1\right).$$

Kontroll av reell-testen. Dataene er reelle, så vi må ha $c_{8-k} = \overline{c_k}$. Her er alle koeffisientene reelle, og $c_7 = c_1 = 1$, $c_6 = c_2 = \tfrac12$, $c_5 = c_3 = 0$, og $c_4 = 0$ er reell. Stemmer.

(At alle $c_k$ er reelle, henger sammen med at signalet bare består av cosinusledd — altså at det er en like funksjon av $j$. Samme regel som for Fourier-koeffisienter i kap. 3.3.)

c) Kontroll ved direkte regning.

Middelverdien. Regn ut alle åtte $f_j$:
$$f_0 = 1+2+1 = 4, \quad f_1 = 1+\sqrt2+0 = 1+\sqrt2, \quad f_2 = 1+0-1 = 0, \quad f_3 = 1-\sqrt2+0 = 1-\sqrt2,$$
$$f_4 = 1-2+1 = 0, \quad f_5 = 1-\sqrt2+0, \quad f_6 = 1+0-1 = 0, \quad f_7 = 1+\sqrt2+0.$$
(Her er $2\cos(2\pi j/8) = 2\cos(\pi j/4)$, som for $j=1$ gir $\displaystyle 2\cdot\frac{\sqrt2}{2} = \sqrt2$.)

Summen er $4 + 2(1+\sqrt2) + 2(1-\sqrt2) + 0+0+0+0 = 4+2+2 = 8$, så
$$c_0 = \frac{8}{8} = 1.$$
Stemmer med avlesningen.

Første datapunkt. Den inverse DFT-en gir $f_0 = \sum_k c_k w^{0} = \sum_k c_k = 1+1+\tfrac12+0+0+0+\tfrac12+1 = 4$. Og direkte fra formelen er $f_0 = 1+2\cos0+\cos0 = 1+2+1 = 4$. Stemmer.

Hva sjangeren tester. Tre ting: at du kan skrive om cosinus til eksponentialer, at du vet hvilken indeks en negativ frekvens havner på ($-m$ blir $N-m$), og at du kan begrunne båndbegrensningen. Ingen av delene krever regning — men alle tre må stå.

Og hva som skjer uten båndbegrensning. Hadde signalet inneholdt et ledd med $m=5$, ville det gitt bidrag i indeks $5$ — men også vært umulig å skille fra $m=-3$, altså indeks 5 igjen. Da er avlesningen ikke lenger entydig, og du må si det.