Frequency ranges of the even and odd term of DFT while developing a FFT algorithm

28 Views Asked by At

I'm reading this book: "Theory and application of digital signal processing" by Lawrence R. Rabiner and Bernard Gold.

During the development of the classical matrix refactorization used to build a FFT algorithm:

Where: $W^{nk} = e^{-2\pi j nk/N}$ ; with $k=0,1,...,N-1$

and DFT defined as: $$X(k)=\sum_{n=0}^{N-1}x(n)W^{nk}$$

The classical splitting of even and odd terms is expressed as:

$$X(k)=\sum_{n=0}^{\frac{N}{2}-1}x_1(n)W^{nk}_{N/2} + W^{k}_{N}\sum_{n=0}^{\frac{N}{2}-1}x_2(n)W^{nk}_{N/2}$$

$$X(k) = X_1(k) + W_N^kX_2(k)$$

But the authors say that $X_1(k)$ and $X_2(k)$ are defined only for $0 \leq k \leq N/2-1$.

Extracted directly from the book at page 359:

"Since $X(k)$ is defined for $0 \leq k \leq N-1$ and $X_1(k)$ and $X_2(k)$ are defined for $0 \leq k \leq N/2-1$"

I don't understand from where emerge the differences in the definition of ranges of $k$ between $X$ and $X_1$, $X_2$