Python Implementation of Real Sequence Transform using Half-length Complex FFT

John Bryan

Overview

We want to transform a length $N_1$ real sequence using a length $N_2=N_1/2$ complex FFT. The input real sequence is

\begin{equation} \sum_{i=0}^{N_1=1} g(n)=\sum_{n'=0}^{N_2-1}g(2n')+\sum_{n'=0}^{N_2-1}g(2n'+1) \tag{eq. 1} \end{equation}


The output complex sequence is \begin{align} G(k)&=\sum_{n=0}^{N_1-1}g(n)W_{N_1}^{nk} \tag{eq. 2} \\ \\ &=\sum_{n=0}^{N_2-1}g(2n')W_{N_1}^{2n'k} + \sum_{n=0}^{N_2-1}g(2n'+1)W_{N_1}^{(2n'+1)k} \tag{eq. 3} \\ \\ &=\sum_{n=0}^{N_2-1}x_1(n')W_{N_2}^{n'k} +W_{N_1}^k\sum_{n=0}^{N_2-1}x_2(n')W_{N_2}^{n'k} \tag{eq. 4} \\ \\ &=X_1(k)+W_{N_1}^kX_2(k) \quad k=0,1,...,N_2-1 \tag{eq. 5} \end{align}
We us this relation to find G(k) for $k=0,1,...,N_2-1$ and use symmetry of real transforms to find G(k) for other values of k in the steps below.

Steps

1. For the $N_2$ even-indexed values: \begin{equation} x_1(n')=g(2n')\quad n'=0,1,...,N_1-1 \tag{eq. 6} \end{equation} For the $N_2$ odd-indexed values: \begin{equation} x_2(n')=g(2n'+1)\quad n'=0,1,...,N_2-1 \tag{eq. 7} \end{equation} Form a complex sequence of length N_2: \begin{equation} x(n')=x_1(n')+jx_2(n')\quad n'=0,1,...,N_2-1 \tag{eq. 8} \end{equation}
2. Calculate \begin{equation} X(k)=\sum_{n=0}^{N_2-1}x(n')W_{N_2}^{nk}\quad k=0,1,...,N_2-1 \tag{eq. 9} \end{equation} using a $N_2$ length complex FFT.
   
   
3. For k=0,1,...$N_2$-1: \begin{equation} X_1(k)=0.5[X(k)+X^*((N_2-k))_N]= \begin{cases} 0.5[X(0)+X^*(0)], & \text{if $k=0$} \\[2ex] 0.5[X(k)+X^*(N_2-k)], & \text{if $k=1,...,N_2-1$} \end{cases} \tag{eq. 10} \end{equation}
   \begin{equation} X_2(k)=-0.5j[X(k)-X^*((N_2-k))_N]= \begin{cases} -0.5[X(0)-X^*(0)], & \text{if $k=0$} \\[2ex] -0.5[X(k)-X^*(N_2-k)], & \text{if $k=1,...,N_2-1$} \end{cases} \tag{eq.11} \end{equation}
4. For $k=0,...N_2-1$, calculate \begin{equation} G(k)=X_1(k)+W_{N_1}^kX_2(k) \tag{eq. 12} \end{equation}
5. For the single value $k=N_1/2$: \begin{equation} G(N_1/2)=0.5[X(0)+X^*(0)]+j[X(0)-X^*(0)]) \tag{eq. 13} \end{equation}
6. For $k=N_1/2+1,...,N_1-1$, use symmetry of real transforms: \begin{equation} G(k)=G^*(N_1-k) \tag{eq. 14} \end{equation}

Python Implementation

• Python Implementation. The performance of the half-length complex fft plus additional steps algorithm is compared to that of processing the real sequence using a full-length complex fft.

Results

References

1. "FFT of Pure Real Sequences", Engineering Productivity Tools Ltd.
2. Hayes, Monson H., Digital Signal Processing.