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
- 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}
-
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.
-
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}
-
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}
-
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}
-
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
-
"FFT of Pure Real Sequences", Engineering Productivity Tools Ltd.
- Hayes, Monson H., Digital Signal Processing.