DTFT & DFT formulas

Bilateral sum over all $n$, with $\omega$ in rad/sample. Defined when the sum converges (see existence below).

The integral may be taken over any interval of length $2\pi$. In the $\omega$ convention the $1/2\pi$ belongs to the inverse.

Put $\omega =0$ or $\omega =\pi$ in the analysis equation, or $n=0$ in the inverse. These evaluate such sums and integrals without finding $X(e^{j\omega })$ at all.

For real $a$ the magnitude is $1/\sqrt{1-2a\cos \omega +a^2}$. With $0<a<1$ it peaks at $1/(1-a)$ at $\omega =0$ and falls to $1/(1+a)$ at $\omega =\pi$ (low-pass); for $-1<a<0$ the roles swap (high-pass). For $|a|\ge 1$ there is no DTFT as an ordinary function.

Value $N$ at $\omega =0$ (as a limit). Zeros at $\omega =2\pi m/N$ for integers $m$ that are not multiples of $N$. The main lobe is $4\pi /N$ rad/sample wide, null to null. Unlike the continuous-time sinc, the whole expression is periodic with period $2\pi$. The ratio $\sin (N\omega /2)/\sin (\omega /2)$ on its own has period $2\pi$ only for odd $N$; for even $N$ it changes sign after $2\pi$, and the linear-phase factor changes sign too, so the product is still $2\pi$-periodic.

$h[0]={\omega }_c/\pi$ (as a limit). The sequence is not absolutely summable but is square summable, with energy ${\sum }_n{h}^2[n]={\omega }_c/\pi$ by Parseval. It is non-causal and infinitely long, so it cannot be realised exactly.

A delay of $n_0$ samples adds the linear phase $-\omega n_0$ and leaves $|X|$ unchanged. Multiplying by $(-1{)}^n=e^{j\pi n}$ shifts the spectrum by $\pi$, which turns a low-pass sequence into a high-pass one.

So $|X|$ and $\mathrm{Re}X$ are even in $\omega$, while $\angle X$ and $\mathrm{Im}X$ are odd. A real, even $x[n]$ has a real, even $X$; a real, odd $x[n]$ has a purely imaginary, odd $X$. More generally, for real $x[n]$ the even part $\frac{1}{2}(x[n]+x[-n])$ transforms to $\mathrm{Re}X(e^{j\omega })$ and the odd part $\frac{1}{2}(x[n]-x[-n])$ to $j\mathrm{Im}X(e^{j\omega })$.

Linear (aperiodic) convolution. This is why the output spectrum of an LTI system is the input spectrum times its frequency response.

The integral runs over one period only, so this is a periodic convolution. Windowing $x[n]$ by $w[n]$ smears $X$ with the window's kernel, which is the origin of spectral leakage.

Useful for $\sum nx[n]$ and, together with Parseval, for ${\int }_{-\pi }^{\pi }|dX/d\omega {|}^{2}d\omega =2\pi \sum n^2|x[n]{|}^2$.

Energy in time equals the energy spread over one period of frequency. The general form is ${\sum }_{n}x[n]y^{\ast }[n]=\frac{1}{2\pi }{\int }_{-\pi }^{\pi }X(e^{j\omega })Y^{\ast }(e^{j\omega })d\omega$.

For real $h[n]$ and an input applied for all $n$. Evaluate $H$ at the input frequency in rad/sample; reduce ${\omega }_0$ modulo $2\pi$ first if it is outside $(-\pi ,\pi ]$.

$W_N=e^{-j2\pi /N}$. $X[k]$ is complex in general, even when $x[n]$ is real.

Some texts put $1/\sqrt{N}$ in both directions (the unitary DFT), and then Parseval has no $1/N$. These notes keep $1/N$ in the inverse only.

Exact when $x[n]$ is zero outside $0\le n\le N-1$; a length-$L$ sequence with $L\le N$ is zero-padded to $N$. The samples are spaced $2\pi /N$ apart over one period $[0,2\pi )$.

If $x[n]$ is longer than $N$ (or infinitely long), $N$ samples of its DTFT recover this time-aliased sum, not $x[n]$. It is the time-domain counterpart of the aliasing caused by sampling a signal too slowly.

$\tilde{X}[k]={\sum }_{n=0}^{N-1}\tilde{x}[n]W_N^{kn}$ is the $N$-point DFT of one period, extended periodically in $k$. A periodic sequence is not summable, so its DTFT is a train of impulses at the bin frequencies $2\pi k/N$. If the Fourier-series coefficients are defined as $a_k=\tilde{X}[k]/N$, the same result reads $2\pi {\sum }_k{a}_k\delta (\omega -2\pi k/N)$. Check: $\tilde{x}[n]=1$ gives $\tilde{X}[k]=N$ at multiples of $N$ and $0$ elsewhere, hence $2\pi {\sum }_k\delta (\omega -2\pi k)$.

For a sequence sampled at $F_s$. Bins $k$ and $N-k$ correspond to $\pm F_k$: for $k>N/2$, bin $k$ represents the negative frequency $(k-N)F_s/N$. For even $N$, bin $N/2$ is $F_s/2$.

$\mathbf{X}=F_N\mathbf{x}$ with $[F_N{]}_{kn}=W_N^{kn}$ (row $k$, column $n$, both counted from $0$). $F_N$ is symmetric. With $F_4$ memorised, a 4-point DFT needs only additions, subtractions and multiplications by $\pm j$ (a swap of real and imaginary parts with a sign change).

$F_N{F}_N^{\ast }=NI$, so $F_N/\sqrt{N}$ is unitary. Applying the DFT twice returns the circularly time-reversed sequence $x[(-n{)}_N]$ scaled by $N$; four applications return $N^2\mathbf{x}$. Hence every eigenvalue of $F_N$ is one of $\pm \sqrt{N}$, $\pm j\sqrt{N}$.

For $1\le k\le N-1$. So $X[0]$ is real and, for even $N$, $X[N/2]$ is real. Only $X[0]$ to $X[N/2]$ need computing for even $N$ ($X[0]$ to $X[(N-1)/2]$ for odd $N$); the rest are conjugates. If $x[n]$ is real and circularly even, $x[n]=x[(N-n{)}_N]$, then $X[k]$ is real and circularly even; if it is real and circularly odd, $x[n]=-x[(N-n{)}_N]$, then $X[k]$ is purely imaginary and circularly odd.

Both sequences are treated as length $N$ (zero-padded if shorter). Multiplying two $N$-point DFTs and inverting always gives the circular convolution, not the linear one.

With $W_N=e^{-j2\pi /N}$ and $1/N$ in the inverse, the $1/N$ is on the frequency side. Leaving it out gives an answer $N$ times too large.

The last two need $N$ even. $X[0]$ is $N$ times the mean of $x[n]$, and $x[0]$ is the mean of the $X[k]$.

Valid whenever $N\ge \max (N_1,N_2)$. For $\max (N_1,N_2)\le N<N_1+N_2-1$, only the first $N_1+N_2-1-N$ samples can differ from the linear result; samples $n=N_1+N_2-1-N$ to $N-1$ equal it.

$N_1$ and $N_2$ are the lengths of the two sequences. For a radix-2 FFT, take the next power of $2$ at or above $N_1+N_2-1$.

$N$ is the DFT length, including any zero padding.

$L$ is the number of genuine data samples and $T_0=L{T}_s$ the observation time. This is a rule of thumb, not an exact threshold: the main lobe of the rectangular window is $2F_s/L$ wide null to null, and whether two tones about $F_s/L$ apart show as two peaks also depends on their relative phase. Only a longer record improves it. Other windows lower the side lobes at the cost of a wider main lobe.

$X_e[k]$ and $X_o[k]$ are the $N/2$-point DFTs of the even-indexed samples $x[2r]$ and the odd-indexed samples $x[2r+1]$. Repeat the split until only 2-point DFTs remain.

For $r=0,1,\dots ,N/2-1$. The first and second halves of the input are combined, and the even- and odd-indexed outputs each come from an $N/2$-point DFT.

Complex multiplications $M$ and complex additions $A$: each of the $N$ outputs needs $N$ products and $N-1$ additions.

${\log }_{2}N$ stages of $N/2$ butterflies. The count includes trivial multiplications by $W_N^0=1$ and by $-j$, which a practical program skips; use the formula as stated unless a question says otherwise. One complex multiplication, done directly as $(a+jb)(c+jd)=(ac-bd)+j(ad+bc)$, costs 4 real multiplications and 2 real additions.