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

Overview

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.

Steps

  1. 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)

  2. 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

  3. 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)

  4. For k = 0,...,N  -  1
           2  , calculate:
    G (k) = X1 (k) + W kN1X2 (k)
    (12)

  5. For the single value k = N1 ∕2  :
    G (N1∕2 ) = 0.5([X (0) + X *(0)] + j[X (0) - X *(0)])
    (13)

  6. For k = N1 ∕2 + 1,...,N1 - 1  , use symmetry of real transforms:
    G (k) = G *(N1  - k)
    (14)

Python Implementation

References