I'd really like to understand how combining consecutive DFT's can work.
Let's say our input is x0,x1,...x7 and the DFT we want to compute is
X0,X1,...X7

We start by doing two half-size DFT's:

Y0 = x0 + x1 + x2 + x3
Y1 = x0 - i*x1 - x2 + i*x3
Y2 = x0 - x1 + x2 - x3
Y3 = x0 + i*x1 - x2 - i*x3

Z0 = x4 + x5 + x6 + x7
Z1 = x4 - i*x5 - x6 + i*x7
Z2 = x4 - x5 + x6 - x7
Z3 = x4 + i*x5 - x6 - i*x7

Now I agree because of periodicity we can compute all the even-numbered
bins easily: X0=Y0+Z0, X2=Y1+Z1, and so on.

But I don't see how we can get the odd bins easily from the Y's and Z's.
For instance we should have:

X1 = x0 + (r - r*i)*x1 - i*x2 + (-r - r*i)*x3 - x4 + (-r + r*i)*x5 + i*x6 +
(r + r*i)*x7

where r=sqrt(1/2)

Is it actually possible? It seems like the phase of the coefficients in the
Y's and Z's advance too quickly to be of any use.

-Ethan



On Mon, Nov 5, 2018 at 3:40 PM, Ethan Duni <ethan.d...@gmail.com> wrote:

> You can combine consecutive DFTs. Intuitively, the basis functions are
> periodic on the transform length. But it won't be as efficient as having
> done the big FFT (as you say, the decimation in time approach interleaves
> the inputs, so you gotta pay the piper to unwind that). Note that this is
> for naked transforms of successive blocks of inputs, not a WOLA filter
> bank.
>
> There are Dolby codecs that do similar with a suitable flavor of DCT (type
> II I think?) - you have your encoder going along at the usual frame rate,
> but if it detects a string of stationary inputs it can fold them together
> into one big high-res DCT and code that instead.
>
> On Mon, Nov 5, 2018 at 11:34 AM Ethan Fenn <et...@polyspectral.com> wrote:
>
>> I don't think that's correct -- DIF involves first doing a single stage
>> of butterfly operations over the input, and then doing two smaller DFTs on
>> that preprocessed data. I don't think there is any reasonable way to take
>> two "consecutive" DFTs of the raw input data and combine them into a longer
>> DFT.
>>
>> (And I don't know anything about the historical question!)
>>
>> -Ethan
>>
>>
>>
>> On Mon, Nov 5, 2018 at 2:18 PM, robert bristow-johnson <
>> r...@audioimagination.com> wrote:
>>
>>>
>>>
>>> Ethan, that's just the difference between Decimation-in-Frequency FFT
>>> and Decimation-in-Time FFT.
>>>
>>> i guess i am not entirely certainly of the history, but i credited both
>>> the DIT and DIF FFT to Cooley and Tukey.  that might be an incorrect
>>> historical impression.
>>>
>>>
>>>
>>> ---------------------------- Original Message
>>> ----------------------------
>>> Subject: Re: [music-dsp] 2-point DFT Matrix for subbands Re: FFT for
>>> realtime synthesis?
>>> From: "Ethan Fenn" <et...@polyspectral.com>
>>> Date: Mon, November 5, 2018 10:17 am
>>> To: music-dsp@music.columbia.edu
>>> ------------------------------------------------------------
>>> --------------
>>>
>>> > It's not exactly Cooley-Tukey. In Cooley-Tukey you take two
>>> _interleaved_
>>> > DFT's (that is, the DFT of the even-numbered samples and the DFT of the
>>> > odd-numbered samples) and combine them into one longer DFT. But here
>>> you're
>>> > talking about taking two _consecutive_ DFT's. I don't think there's any
>>> > cheap way to combine these to exactly recover an individual bin of the
>>> > longer DFT.
>>> >
>>> > Of course it's possible you'll be able to come up with a clever
>>> frequency
>>> > estimator using this information. I'm just saying it won't be exact in
>>> the
>>> > way Cooley-Tukey is.
>>> >
>>> > -Ethan
>>> >
>>> >
>>>
>>>
>>>
>>> --
>>>
>>> r b-j                         r...@audioimagination.com
>>>
>>> "Imagination is more important than knowledge."
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>>
>>> _______________________________________________
>>> dupswapdrop: music-dsp mailing list
>>> music-dsp@music.columbia.edu
>>> https://lists.columbia.edu/mailman/listinfo/music-dsp
>>>
>>
>> _______________________________________________
>> dupswapdrop: music-dsp mailing list
>> music-dsp@music.columbia.edu
>> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
>
> _______________________________________________
> dupswapdrop: music-dsp mailing list
> music-dsp@music.columbia.edu
> https://lists.columbia.edu/mailman/listinfo/music-dsp
>
_______________________________________________
dupswapdrop: music-dsp mailing list
music-dsp@music.columbia.edu
https://lists.columbia.edu/mailman/listinfo/music-dsp

Reply via email to