# Re: [music-dsp] 2-point DFT Matrix for subbands Re: FFT for realtime synthesis?

```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```