Decimation in Time

When $N$ is even, the DFT summation can be split into sums over the odd and even indexes of the input signal:

$$X(\omega_k) \isdef _{N,k}\{x\} \isdef \sum_{n=0}^{N-1} x(n) e^{-j\omega_k n T}, \quad \omega_k \isdef \frac{2\pi k}{NT}$$

$$= \sum_{{\stackrel{n=0}{\vspace{2pt}\mbox{\tiny$n$\ even}}}}^{N-2} ... ...stackrel{n=0}{\vspace{2pt}\mbox{\tiny$n$\ odd}}}}^{N-1} x(n) e^{-j\omega_k n T}$$

$$= \sum_{n=0}^{\frac{N}{2}-1} x(2n) e^{-j2\pi \frac{k}{N/2} n} + e^{j2\pi\frac{k}{N}}\sum_{n=0}^{\frac{N}{2}-1} x(2n+1) e^{-j2\pi \frac{k}{N/2} n},$$

$$= \sum_{n=0}^{\frac{N}{2}-1} x_e(n) W_{N/2}^{kn} + W_N^k \sum_{n=0}^{\frac{N}{2}-1} x_o(n) W_{N/2}^{kn}$$

$$\isdef _{\frac{N}{2},k}\{ _2(x)\}$$

$$\mathop{\quad} +\;W_N^k\cdot _{\frac{N}{2},k}\{ _2[ _1(x)]\}, \protect$$ (A.1)

where $x_e(n)\isdef x(2n)$ and $x_o(n)\isdef x(2n+1)$ denote the even- and odd-indexed samples from $x$. Thus, the length $N$ DFT is computable using two length $N/2$ DFTs. The complex factors $W_N^k=e^{-j\omega_k}=\exp(-j2\pi k/N)$ are called twiddle factors. The splitting into sums over even and odd time indexes is called decimation in time. (For decimation in frequency, the inverse DFT of the spectrum $X(\omega_k)$ is split into sums over even and odd bin numbers $k$.)