1D as a 3D FFT - what’s wrong here? I implemented the algorithm to calculate 2D DFT derived from 1D DFT.
It works great, and makes my calculations much more efficiency then regular 1D DFT.

But now I want to make 3D DFT derived from 1D DFT and it doesn’t work for me. For 3 days I’ve tried to solve it, but I can’t, so I would like to ask you for help.

I make all math transforms by following the explanations in found in book “Theory and application of digital signal processing” Lawrence R. Rabiner, Bernard Gold - chapter 6.8 titled “A Unified Approach to the FFT“.

According to book example, let’s say we have $\ N=60 $ point signal. Let me remind definition of the DFT, which is:

$\ X ( k ) = \sum _ { n = 0} ^ { N - 1} x ( n ) W ^ { n k } $

$\ N=60 $ points we can expres as a $ 60= 5\times 12 $. So $\ n $ and $\ k $ can be written as:

$\ n = M l + m $

$\ k = L r + s $

Where:

$\ M = 12 $

$\ L = 5 $

$\ l = 0,1,..,L - 1 $

$\ m = 0,1,..,M - 1 $

$\ s = 0,1,..,L - 1 $

$\ r = 0,1,..,M - 1 $

So now we can write DFT as:

$\ X ( k ) = X ( L r + s ) = \sum _ { m = 0} ^ { M - 1} \sum _ { l = 0} ^ { L - 1} x ( M l + m ) W ^ { ( M l + m ) ( L r + s ) } $

And after some tweaking with power of W, we find that:

$\ W ^ { ( M l L r ) }  = 1 $

And we can write DFT as:

$\ X ( L r + s ) = \sum _ { m = 0} ^ { M - 1} W ^ {m (L r + s) } \sum _ { l = 0} ^ { L - 1} x ( M l + m ) W ^ { M s l } $

So great. Now I have 2D DFT, and it works great for me.

THE PROBLEMS STARTS HERE

Following my example with $\ N=60=5x12 $, we can see that 12 can be expressed as $\ 12=3x4 $.

So $\ m $ and $\ r $, which have values $\ 0, 1, …, M-1 $, we can express as:

$\ m = Z c + z $

$\ r = C v + y $

Where:

$\ Z = 4 $

$\ C = 3 $

$\ c = 0, 1, .., C - 1 $

$\ z = 0, 1, .., Z - 1 $

$\ y = 0, 1 , .., C - 1 $

$\ v = 0, 1, .., Z - 1 $

So now the $\ n $ and $\ k $ are:

$\ n = M l + Z c + z $

$\ k = L (C v + y) + s $

And then the DFT is:

$\ X ( k ) = X ( L (C v + y) + s ) = \sum _ { z = 0} ^ { Z - 1} \sum _ { c = 0} ^ { C - 1} \sum _ { l = 0} ^ { L - 1} x ( M l + Z c + z ) W ^ { ( M l + Z c + z ) ( L (C v + y) + s ) } $

And now after some tweaking with power of W, we find that:

$\ W ^ { ( M l L C v ) }  = 1 $

$\ W ^ { ( M l L y ) }  = 1 $

$\ W ^ { ( Z c L C v ) }  = 1 $

And finally we can write DFT as:

$\ X ( L (C v + y) + s ) = \sum _ { z = 0} ^ { Z - 1} W ^ {z (L C v + L y + s) } \sum _ { c = 0} ^ { C - 1} W ^ {c (Z L y + Z s) } \sum _ { l = 0} ^ { L - 1}x ( M l + Z c + z ) W ^ { M s l } $

And it doesn’t work for me, I have some crazy output values. And Have no idea if my math transforms (which I described above) are wrong, or maybe I just made wrong implementation. Of course I am not asking you about my implementation (which I haven’t shown here). First I want to be sure that my math transforms are OK?

For any help great thanks in advance.
OK, I need to answer my own question.
The math transform I described is GOOD, the problem was like always, stupid mistake in the code. But Stanleys answer helped me much. Thanks a lot.