FFT of size 1536

I just want to know how can we implement the FFT of size 1536. With reading
the literature I came to know that we do it by splitting 1536 into three
block of 512 and then take their fft. In the end we combine all the ffts
and multiply with the respective twiddle factors to and apply the radix 3
stage. Can anyone help me with the C coding regarding it. Suppose that I
have done the coding for three 512 sub transforms . Now I want to go to the
radix 3 stage.

Am 25.04.13 18:57, schrieb coolboy03:
> I just want to know how can we implement the FFT of size 1536. With reading
> the literature I came to know that we do it by splitting 1536 into three
> block of 512 and then take their fft. In the end we combine all the ffts
> and multiply with the respective twiddle factors to and apply the radix 3
> stage. Can anyone help me with the C coding regarding it. Suppose that I
> have done the coding for three 512 sub transforms . Now I want to go to the
> radix 3 stage.
>

I'd just download kissfft and let it do the dirty parts. It's free for 
almost everything and does mixed-radix (as well as Bluestein-) FFT. If 
you need maximum performance and can live with GPL, FFTW is your friend. 
Otherwise, buy a library (e.g. MKL from Intel) to do it. In terms of 
performance any of those three solutions will likely be faster than your 
own code. For example, doing 512 the Cooley-Tukey way all the way down 
to length 2 is usually not the fastest way.

	Christian

On 4/25/2013 11:57 AM, coolboy03 wrote:
> I just want to know how can we implement the FFT of size 1536.

"how can _we_ implement..."
  India ?

> With reading
> the literature I came to know that we do it by splitting 1536 into three
> block of 512 and then take their fft. In the end we combine all the ffts
> and multiply with the respective twiddle factors to and apply the radix 3
> stage. Can anyone help me with the C coding regarding it. Suppose that I
> have done the coding for three 512 sub transforms . Now I want to go to the
> radix 3 stage.

For any purpose other then homework, use FFT size of 2048 and pad data 
with zeroes.

VLV

Vladimir Vassilevsky <nospam@nowhere.com> wrote:
> On 4/25/2013 11:57 AM, coolboy03 wrote:
>> I just want to know how can we implement the FFT of size 1536.
 
> "how can _we_ implement..."
>  India ?
 
>> With reading
>> the literature I came to know that we do it by splitting 1536 into three
>> block of 512 and then take their fft. In the end we combine all the ffts
>> and multiply with the respective twiddle factors to and apply the radix 3
>> stage. Can anyone help me with the C coding regarding it. Suppose that I
>> have done the coding for three 512 sub transforms . 
>> Now I want to go to the radix 3 stage.
 
> For any purpose other then homework, use FFT size of 2048 and pad data 
> with zeroes.

Unless the data is periodic in 1536 samples.

-- glen

On Thu, 25 Apr 2013 11:57:55 -0500, "coolboy03" <95038@dsprelated>
wrote:

>I just want to know how can we implement the FFT of size 1536. With reading
>the literature I came to know that we do it by splitting 1536 into three
>block of 512 and then take their fft. In the end we combine all the ffts
>and multiply with the respective twiddle factors to and apply the radix 3
>stage. Can anyone help me with the C coding regarding it. Suppose that I
>have done the coding for three 512 sub transforms . Now I want to go to the
>radix 3 stage.

Is there a reason to not just do a DFT of length 1536?   If this is
for a sim or analysis a DFT of that length can be computed pretty
quickly these days.   Implementation in code of a DFT of any length is
far simpler than the tricks that need to be employed to get such a
length with FFTs.





Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

"coolboy03" <95038@dsprelated> wrote in message 
news:3o-dnTO9FNoO_eTMnZ2dnUVZ_h-dnZ2d@giganews.com...
>I just want to know how can we implement the FFT of size 1536. With reading
> the literature I came to know that we do it by splitting 1536 into three
> block of 512 and then take their fft. In the end we combine all the ffts
> and multiply with the respective twiddle factors to and apply the radix 3
> stage. Can anyone help me with the C coding regarding it. Suppose that I
> have done the coding for three 512 sub transforms . Now I want to go to 
> the
> radix 3 stage.
>
>
Not in C but matlab:
function Y = dft_mixedradix(x, N1, N2)
% N1*N2 point DFT.
% Y = dft_mixedradix(x, N1, N2);
N  = numel(x);
mx = reshape(x, N1, N2); % x -> matrix: N1xN2 in column-major order
mn = (0:N1-1)' * (0:N2-1);
tw = exp(-1i * 2 * pi / N .* mn); % twiddlefactor
Y1 = fft(mx.', N2).';
Y2 = Y1 .* tw;
Y = fft(Y2, N1).';
Y = Y(:);
% Test:
% x = randn(1536,1);
% y1 = fft(x);
% y2 = fft_mixedradix(x, 3, 512);
% plot([y1-y2]);grid
If you have Matlab/octave you should be able to run and test the above and 
then convert
it to C. To get best performance don't use 2d-arrays, use a 1d-array instead 
and
index with appropriate stride.
Best rgds
-- 

On Thu, 25 Apr 2013 11:57:55 -0500, "coolboy03" <95038@dsprelated>
wrote:

>I just want to know how can we implement the FFT of size 1536. With reading
>the literature I came to know that we do it by splitting 1536 into three
>block of 512 and then take their fft. In the end we combine all the ffts
>and multiply with the respective twiddle factors to and apply the radix 3
>stage. Can anyone help me with the C coding regarding it. Suppose that I
>have done the coding for three 512 sub transforms . Now I want to go to the
>radix 3 stage.
>

Hello coolboy03,
  I don't know if it would be of any use 
to you but you might take a look at:

http://www.dsprelated.com/showarticle/63.php

It might help.  Ya' never know.

[-Rick-]

On 4/25/2013 12:49 PM, glen herrmannsfeldt wrote:
> Vladimir Vassilevsky <nospam@nowhere.com> wrote:
>> On 4/25/2013 11:57 AM, coolboy03 wrote:
>>> I just want to know how can we implement the FFT of size 1536.
>
>> "how can _we_ implement..."
>>   India ?
>
>>> With reading
>>> the literature I came to know that we do it by splitting 1536 into three
>>> block of 512 and then take their fft. In the end we combine all the ffts
>>> and multiply with the respective twiddle factors to and apply the radix 3
>>> stage. Can anyone help me with the C coding regarding it. Suppose that I
>>> have done the coding for three 512 sub transforms .
>>> Now I want to go to the radix 3 stage.
>
>> For any purpose other then homework, use FFT size of 2048 and pad data
>> with zeroes.
>
> Unless the data is periodic in 1536 samples.

Then resample 1536 into 4096

VLV

Vladimir Vassilevsky <nospam@nowhere.com> wrote:
> On 4/25/2013 12:49 PM, glen herrmannsfeldt wrote:
>> Vladimir Vassilevsky <nospam@nowhere.com> wrote:
>>> On 4/25/2013 11:57 AM, coolboy03 wrote:
>>>> I just want to know how can we implement the FFT of size 1536.

(snip)
>>>> With reading
>>>> the literature I came to know that we do it by splitting 1536 into three
>>>> block of 512 and then take their fft. In the end we combine all the ffts
>>>> and multiply with the respective twiddle factors to and apply the radix 3
>>>> stage. Can anyone help me with the C coding regarding it. Suppose that I
>>>> have done the coding for three 512 sub transforms .
>>>> Now I want to go to the radix 3 stage.

>>> For any purpose other then homework, use FFT size of 2048 and pad data
>>> with zeroes.

>> Unless the data is periodic in 1536 samples.
 
> Then resample 1536 into 4096

Hmm. Easier than resampling to 2048 I suppose. 

But the radix 3 step isn't that hard to do, is it? 

-- glen

On 4/27/2013 3:24 PM, glen herrmannsfeldt wrote:
> Vladimir Vassilevsky <nospam@nowhere.com> wrote:
>> On 4/25/2013 12:49 PM, glen herrmannsfeldt wrote:
>>> Vladimir Vassilevsky <nospam@nowhere.com> wrote:
>>>> On 4/25/2013 11:57 AM, coolboy03 wrote:
>>>>> I just want to know how can we implement the FFT of size 1536.
>
> (snip)
>>>>> With reading
>>>>> the literature I came to know that we do it by splitting 1536 into three
>>>>> block of 512 and then take their fft. In the end we combine all the ffts
>>>>> and multiply with the respective twiddle factors to and apply the radix 3
>>>>> stage. Can anyone help me with the C coding regarding it. Suppose that I
>>>>> have done the coding for three 512 sub transforms .
>>>>> Now I want to go to the radix 3 stage.
>
>>>> For any purpose other then homework, use FFT size of 2048 and pad data
>>>> with zeroes.
>
>>> Unless the data is periodic in 1536 samples.
>
>> Then resample 1536 into 4096
>
> Hmm. Easier than resampling to 2048 I suppose.

The 2048 would require heavy antialiasing.

> But the radix 3 step isn't that hard to do, is it?

Yes, but I doubt efficiency would be any better.

VLV