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

We want to transform a length $N1$ real sequence using a length $N2 = N1∕2$ complex FFT. The input real sequence is,

N1∑- 1 N2∑- 1 N2∑- 1 g(n) = g(2n′) + g(2n′ + 1) n=0 n′=0 n′=0

(1)

The output complex sequence is

N∑1-1 G (k ) = g(n)W nk (2) N1 n=0 N∑2-1 ′ 2n′k N∑2-1 ′ (2n′+1)k = g(2n )W N1 + g (2n + 1)W N1 (3) n′=0 n′=0 N∑2-1 N∑2-1 = x1(n′)W Nn′k + W kN x2(n ′)W nN′k (4) n′=0 2 1 n′=0 2 k = X1 (k) + W N1X2 (k ) k = 0,1, ...,N2 - 1 (5)

We use this relation to find G(k) for $k = 0,1,...,N2 - 1$ and use symmetry of real transforms to find G(k) for other values of k in the steps below.

For the $N2$ even-indexed values:
$x1(n′) = g(2n′) n′ = 0,1,...,N2 - 1$ (6)

For the $N2$ odd-indexed values:
$x2(n′) = g(2n′ + 1) n′ = 0,1,...,N2 - 1$ (7)

Form a complex sequence of length $N2$ :
$x (n′) = x (n ′) + jx (n′) n ′ = 0,1,...,N - 1 1 2 2$ (8)
Calculate
$N∑2-1 X (k ) = x(n ′)W nk k = 0,1,...,N2 - 1 n′=0 N2$ (9)

using a $N2$ length complex FFT
For $k = 0,1,...,N2 - 1$ :
${ * X (k) = 0.5[X (k)+X *((N - k)) ] = 0.5[X (0) + X (0)] if k ≡ 0 1 2 N 0.5[X (k) + X *(N2 - k)] if k ≡ 1, ...,N2 - 1$ (10)

${ - 0.5j[X (0) - X *(0)] if k ≡ 0 X2 (k) = - 0.5j[X (k )- X *((N2 - k ))N ] = - 0.5j[X (k) - X *(N2 - k)] if k ≡ 1,...,N2 - 1$ (11)
For $k = 0,...,N - 1 2$ , calculate:
$G (k) = X1 (k) + W kN1X2 (k)$ (12)
For the single value $k = N1 ∕2$ :
$G (N1∕2 ) = 0.5([X (0) + X *(0)] + j[X (0) - X *(0)])$ (13)
For $k = N1 ∕2 + 1,...,N1 - 1$ , use symmetry of real transforms:
$G (k) = G *(N1 - k)$ (14)

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.