FFT stride pattern formula

Question

Edit

I have found a solution and I posted it below. Thanks to everyone who tried to help!

Question

I have implemented the radix-2 DIT FFT algorithm but I could not find a formula to determine the strides of the butterfly operations based on the stage. Let me clarify the terminology:

Terminology

For $N=8$ , the first stage would be to rearrange the array with bit-reverse order and then keep going with the "butterfly" stage which is the repeated pattern that you can see with 2 inputs and two outputs. We are not really interested in the operation itself here.

As you can see at each stage the butterfly operation maintains its structure, but the stride and the span change.

Issue

My problem here is to find a formula that links the stride and the span at a given $n-th$ stage and the $b-th$ butterfly.

$$ stride( n, b) $$ $$ span ( n, b) $$

I have found a formula for the span, which depends only on the stage $n$:

$$ span(n) = floor \left( \frac{N}{ 2^{N-n}} \right) $$

But I can't figure out a formula for the stride.

My solution

At the moment my solution is to run a small algorithm to populate a vector with the starting indexes at each stage. The algorithm works by knowing the span and doing the same thing I'd do manually. The patterns are:

N = 8
      b = 0  1  2  3
Stage 0 > 0, 2 ,4 ,6
Stage 1 > 0, 1 ,4 ,5
Stage 2 > 0, 1 ,2 ,3

N = 16
      b = 0  1  2  3  4   5   6   7
Stage 0 > 0, 2, 4, 6, 8, 10, 12, 14
Stage 1 > 0, 1, 4, 5, 8,  9, 12, 13
Stage 2 > 0, 1, 2, 3, 8,  9, 10, 11
Stage 3 > 0, 1, 2, 3, 4,  5,  6,  7

Answer 1

I have found a solution. Borrowing the idea from EEC 281 — VLSI Digital Signal Processing Notes on the RRI-FFT , I noticed that the inner butterfly can be grouped together. It can be seen better from this image:

• First stage has $N/2$ groups , each with $1$ butterfly.
• Second stage has $N/4$ groups, each with $2$ butterflies.
• ...
• Last stage has $1$ group with $N/2$ butterflies.

Hence, my solution was to generate a function to keep track of

• Number of butterflies per stage $B(s)$
• Number of groups per stage $G(s)$
• Stride of the group $SG(s)$

Notice that $$G(s) * B(s) = \frac{N}{2} , \forall s$$

And use such functions for generating the access indexes.

Here's the code I wrote, in case anyone is interested:

def gen_idx(N):
    
    S = int(math.log2(N))
    
    B = lambda s : int(N/(2**(S-s)))
    G = lambda s : int(N/(2**(s+1)))
    
    SG = lambda s : 2*B(s)
    
    vec_idx = [0 for i in range(N//2)]
    idx     = 0
    
    for s in range(S):
               
        idx = 0
        
        for g in range( G(s) ):
            
            for b in range( B(s)  ):
                
                vec_idx[idx] = SG(s)*g + b
                idx += 1
                
        print( vec_idx )

Which outputs, for N = 16

[0, 2, 4, 6, 8, 10, 12, 14]
[0, 1, 4, 5, 8, 9, 12, 13]
[0, 1, 2, 3, 8, 9, 10, 11]
[0, 1, 2, 3, 4, 5, 6, 7]

But then we can merge the two inner loops into one, knowing that

$$ \begin{alignat*}{4} g = floor \left( \frac{k}{B(s)} \right) \\ b = k \mod B(s) \\ k = 0 .. \frac{N}{2} \end{alignat*} $$

We can finally find the formula that we (I) were looking for:

$$ stride(s,k) = floor \left( \frac{k}{B(s)} \right) * SG(s) + k \mod B(s) $$