nou

your dft code

3 mins read ·

Discrete Fourier Transform: Create your onw code

outline

equations

        \ \ \ \ \ \ \ \

X(ω)=∫−∞+∞x(t)e−jωt dt(1)\tag{1} X(\omega) = \int_{-\infty}^{+\infty} x(t) e^{-j \omega t} \ dt

        \ \ \ \ \ \ \ \

X(ω)≈∑n=0∞x(tn)e−jωtn Δt(2)\tag{2} X(\omega) \approx \sum_{n=0}^{\infty} x(t_n) e^{-j \omega t_n} \ \Delta t

        \ \ \ \ \ \ \ \

ejωt=cos⁡ωt+jsin⁡ωt(0)\tag{0} e^{j \omega t} = \cos \omega t + j \sin \omega t

        \ \ \ \ \ \ \ \

x(t)=3sin⁡20πt+4cos⁡5πt+1(4)\tag{4} x(t) = 3 \sin 20\pi t + 4 \cos 5\pi t + 1

matrix

Is it possible to formulate all in matrix form?

ykRe=∑n=0N−1xncos⁡(2πknN)(5)\tag{5} y_k^{\rm Re} = \sum_{n=0}^{N-1} x_n \cos \left( \frac{2\pi kn}{N} \right)

ykIm=−∑n=0N−1xnsin⁡(2πknN)(6)\tag{6} y_k^{\rm Im} = -\sum_{n=0}^{N-1} x_n \sin \left( \frac{2\pi kn}{N} \right)

[111…111cos⁡(2πN⋅1)cos⁡(2πN⋅2)…cos⁡(2πN⋅(N−2))cos⁡(2πN⋅(N−1))1cos⁡(2πkN⋅1)cos⁡(2πkN⋅2)…cos⁡(2πkN⋅(N−2))cos⁡(2πkN⋅(N−1))⋮⋮⋮⋱⋮⋮1cos⁡(2π(N−2)N⋅1)cos⁡(2π(N−2)N⋅2)…cos⁡(2π(N−2)N⋅(N−2))cos⁡(2π(N−2)N⋅(N−1))1cos⁡(2π(N−1)N⋅1)cos⁡(2π(N−1)N⋅2)…cos⁡(2π(N−1)N⋅(N−2))cos⁡(2π(N−1)N⋅(N−1))][x0x1x2⋮xN−2xN−1]=[y0Rey1Rey2Re⋮yN−2ReyN−1Re] \left[ \begin{array}{cccccc} 1 & 1 & 1 & \dots & 1 & 1 \newline \newline 1 & \cos \left( \frac{2\pi}{N} \cdot 1 \right) & \cos \left( \frac{2\pi}{N} \cdot 2 \right) & \dots & \cos \left( \frac{2\pi}{N} \cdot (N-2) \right) & \cos \left( \frac{2\pi}{N} \cdot (N-1) \right) \newline \newline 1 & \cos \left( \frac{2\pi k}{N} \cdot 1 \right) & \cos \left( \frac{2\pi k}{N} \cdot 2 \right) & \dots & \cos \left( \frac{2\pi k}{N} \cdot (N-2) \right) & \cos \left( \frac{2\pi k}{N} \cdot (N-1) \right) \newline \newline \vdots & \vdots &\vdots & \ddots & \vdots & \vdots \newline \newline 1 & \cos \left( \frac{2\pi(N-2)}{N} \cdot 1 \right) & \cos \left( \frac{2\pi(N-2)}{N} \cdot 2 \right) & \dots & \cos \left( \frac{2\pi (N-2)}{N} \cdot (N-2) \right) & \cos \left( \frac{2\pi (N-2)}{N} \cdot (N-1) \right) \newline \newline 1 & \cos \left( \frac{2\pi(N-1)}{N} \cdot 1 \right) & \cos \left( \frac{2\pi(N-1)}{N} \cdot 2 \right) & \dots & \cos \left( \frac{2\pi(N-1)}{N} \cdot (N-2) \right) & \cos \left( \frac{2\pi(N-1)}{N} \cdot (N-1) \right) \end{array} \right] \left[ \begin{array}{c} x_0 \newline \newline x_1 \newline \newline x_2 \newline \newline \vdots \newline \newline x_{N-2} \newline \newline x_{N-1} \end{array} \right] = \left[ \begin{array}{c} y_0^{\rm Re} \newline \newline y_1^{\rm Re} \newline \newline y_2^{\rm Re} \newline \newline \vdots \newline \newline y_{N-2}^{\rm Re} \newline \newline y_{N-1}^{\rm Re} \end{array} \right]

[000…000sin⁡(2πN⋅1)sin⁡(2πN⋅2)…sin⁡(2πN⋅(N−2))sin⁡(2πN⋅(N−1))0sin⁡(2πkN⋅1)sin⁡(2πkN⋅2)…sin⁡(2πkN⋅(N−2))sin⁡(2πkN⋅(N−1))⋮⋮⋮⋱⋮⋮0sin⁡(2π(N−2)N⋅1)sin⁡(2π(N−2)N⋅2)…sin⁡(2π(N−2)N⋅(N−2))sin⁡(2π(N−2)N⋅(N−1))0sin⁡(2π(N−1)N⋅1)sin⁡(2π(N−1)N⋅2)…sin⁡(2π(N−1)N⋅(N−2))sin⁡(2π(N−1)N⋅(N−1))][x0x1x2⋮xN−2xN−1]=[y0Rey1Rey2Re⋮yN−2ReyN−1Re] \left[ \begin{array}{cccccc} 0 & 0 & 0 & \dots & 0 & 0 \newline \newline 0 & \sin \left( \frac{2\pi}{N} \cdot 1 \right) & \sin \left( \frac{2\pi}{N} \cdot 2 \right) & \dots & \sin \left( \frac{2\pi}{N} \cdot (N-2) \right) & \sin \left( \frac{2\pi}{N} \cdot (N-1) \right) \newline \newline 0 & \sin \left( \frac{2\pi k}{N} \cdot 1 \right) & \sin \left( \frac{2\pi k}{N} \cdot 2 \right) & \dots & \sin \left( \frac{2\pi k}{N} \cdot (N-2) \right) & \sin \left( \frac{2\pi k}{N} \cdot (N-1) \right) \newline \newline \vdots & \vdots &\vdots & \ddots & \vdots & \vdots \newline \newline 0 & \sin \left( \frac{2\pi(N-2)}{N} \cdot 1 \right) & \sin \left( \frac{2\pi(N-2)}{N} \cdot 2 \right) & \dots & \sin \left( \frac{2\pi (N-2)}{N} \cdot (N-2) \right) & \sin \left( \frac{2\pi (N-2)}{N} \cdot (N-1) \right) \newline \newline 0 & \sin \left( \frac{2\pi(N-1)}{N} \cdot 1 \right) & \sin \left( \frac{2\pi(N-1)}{N} \cdot 2 \right) & \dots & \sin \left( \frac{2\pi(N-1)}{N} \cdot (N-2) \right) & \sin \left( \frac{2\pi(N-1)}{N} \cdot (N-1) \right) \end{array} \right] \left[ \begin{array}{c} x_0 \newline \newline x_1 \newline \newline x_2 \newline \newline \vdots \newline \newline x_{N-2} \newline \newline x_{N-1} \end{array} \right] = \left[ \begin{array}{c} y_0^{\rm Re} \newline \newline y_1^{\rm Re} \newline \newline y_2^{\rm Re} \newline \newline \vdots \newline \newline y_{N-2}^{\rm Re} \newline \newline y_{N-1}^{\rm Re} \end{array} \right]

refs

Tags: