>>
>> Exactly- the block convolution seems to just provide the ...
>> illusion of not being circular, or of a "circle" with a...
>> different ( smaller? larger? ) "radius". Interesting.
>>
>
> Yes, FFT->multiply->IFFT is equivalent to a circular convolution, not a linear one.
Right! We knew that; I knew that.
What was not clear was the relationship ( which holds ) between block
and a "you have all of both sample-sets in memory and convolve them" case.
> This is why you have to pad out with zeros in the overlap-add method > -- it makes sure the result of the single-block convolution is short > enough to fit in the buffer without looping around the end.
>
You only have to pad out FFTSIZE-SIGNAL_QUANTUM[1] samples, at the end,
for a block convolution, and only for the case where you're convolving a
fixed quantity of samples. I hope that last thing
becomes clearer down the page.
[1] say SIGNAL_QUANTUM=89 ( for 2msec @ 44100 ksamples/sec ) and FFTSIZE
= 1024 - leaving 935 or 936.
>>
>> For a 64 sample FFT, with 18 signal-samples per processing iteration,
>> 46 zeros behaves badly, 45 produces the expected result.
>>
>
> I don't understand what you mean here. If you're using a 64 sample
> FFT, you need to provide an array of 64 numbers as input. If 18 of
> them are signal samples, aren't there then going to be exactly 46
> zeros? How could you have a different number of zeros?
>
Neat question!
This is for a VST plugin that uses block convolution of a continuous
stream of input. But part of it is a generic block convolver,
implemented as a C++ class with a minimal API.
I needed to test the convolver seperate from the VST plugin stuff. It's
difficult to create a test case using a DAW because samples written to
a .wav file are constrained to the range -1...1. I actually did this
with samples where 1 => 0.01 or 0.001 , and got the correct output.
Still, I wanted the classic test.
So the test case was to convolve a fixed buffer of all-ones ( a
rectangular pulse ) with another fixed block of the same number of all
ones - because that was easy to test for. You expect a triangular pulse
as output. A small state machines checks for a triangular pulse well.
So I chose:
- A variable number of samples in the rectangular pulse. The C program
used accepted as a command line argument the number of samples.
- An FFT size of 64.
- An "input quantum" - how many new, signal-to-be-convolved samples
per iteration through the block convolver.
- A buffer size, >= the number of samples in the rectangular pulse.
This means I could drive the program with a script. It would basically
print "BAD" or "GOOD". The script could salami-slice the parameters
until we found the edge case between good and bad.
What I found was - regardless of all the other parameters, if I added
the right number of zeros[1], it did not go circular. If I didn't, it did.
[1] to both the signal *and the impulse*, because they are constrained
as being the same for this test.
For a 64 sized FFT with 19 input samples per block, the dividing line
was between 46 and 45. 45 zeros bad, 46 good. The conclusion is
that for block convolutions, you must add enough zeros ( to the impulse
) or it'll become a circular convolution.
Which makes perfect sense.
I am sure I messed this up, and please, ask again if you have
questions.
> -Ethan
>
--
Les Cargill
Reply by ●March 21, 20172017-03-21
>
> Exactly- the block convolution seems to just provide the ...
> illusion of not being circular, or of a "circle" with a...
> different ( smaller? larger? ) "radius". Interesting.
>
Yes, FFT->multiply->IFFT is equivalent to a circular convolution, not a linear one. This is why you have to pad out with zeros in the overlap-add method -- it makes sure the result of the single-block convolution is short enough to fit in the buffer without looping around the end.
>
> For a 64 sample FFT, with 18 signal-samples per processing iteration,
> 46 zeros behaves badly, 45 produces the expected result.
>
I don't understand what you mean here. If you're using a 64 sample FFT, you need to provide an array of 64 numbers as input. If 18 of them are signal samples, aren't there then going to be exactly 46 zeros? How could you have a different number of zeros?
-Ethan
Reply by Les Cargill●March 20, 20172017-03-20
eric.jacobsen@ieee.org wrote:
> On Sun, 19 Mar 2017 20:09:15 -0500, Les Cargill
> <lcargill99@comcast.com> wrote:
>
>> eric.jacobsen@ieee.org wrote:
>>> On Sun, 19 Mar 2017 15:14:23 -0500, Les Cargill
>>> <lcargill99@comcast.com> wrote:
>>>
>>>> Update:
>>>>
>>>> I was able to "put my test driver in a test driver".
>>>>
>>>> It's still a 512x512 convolution.
>>>>
>>>> Defining quantities:
>>>> FFTSIZE - the size of the FFT
>>>> SIGNALBLOCKSIZE - the number of signal samples per FFT
>>>> KERNELBLOCKSIZE - the number of kernel samples per FFT
>>>>
>>>> So FFTSIZE == 64, SIGNALBLOCKSIZE = 13 and therefore
>>>> KERNELBLOCKSIZE == 51.
>>>>
>>>> If I leave less than 51 zero samples to be processed, it doesn't work.
>>>> So it's really a 461 x 461 test.
>>>>
>>>>
>>>> What I remain unsure of is whether this is a defect in the thing being
>>>> tested, or the test itself. It *reminds* me of the "2N-1" nature of
>>>> using convolution to morph equal rectangular pulses into triangular
>>>> pulses, but I'm not sure I can say I know that's the case.
>>>>
>>>> So I have to go over the "last block" processing with a fine tooth comb.
>>>>
>>>> I also tried the "in the DAW" version of this ( that just meant
>>>> peparing test vectors ) and that seems to have worked, although
>>>> there were even more zeros there.
>>>>
>>>> --
>>>> Les Cargill
>>>
>>> Are you sure you're not just seeing the difference between linear and
>>> circular convolution?
>>
>> I'm pretty sure there's no circular convolution going on here, but I'll
>> double check that assumption. I believe what I have is linear
>> convolution via the overlap-add method, using the FFT.
>
> Fast convolution via FFT is always circular at the FFT length. The
> overlap-add or overlap-save methods are attempts to make it appear
> linear in the aggregate. At the edges it may take some additional
> care to make sure things don't get wonky.
>
>
Exactly- the block convolution seems to just provide the ...
illusion of not being circular, or of a "circle" with a...
different ( smaller? larger? ) "radius". Interesting.
The Bad Thing happens when there are less-or-equal zeros at the end
than there are *kernel* samples in an FFT. Since I was able to get
an exact figure for the number of zeros needed, I can say that with
more confidence now.
For a 64 sample FFT, with 18 signal-samples per processing iteration,
46 zeros behaves badly, 45 produces the expected result.
64-18 = 46. 46 bad, 45 good.
>>> I'm not sure I get all the details of what
>>> you're doing,
>>
>> Yeah, it's pretty hard to tell. It should be just an iterated block
>> convolution using overlap-add.
>>
>>> but it sounds like maybe this is part of it?
>>>
>>>
>>>
>>> ---
>>> This email has been checked for viruses by Avast antivirus software.
>>> https://www.avast.com/antivirus
>>>
>>
>> --
>> Les Cargill
>
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
>
--
Les Cargill
Reply by ●March 19, 20172017-03-19
On Sun, 19 Mar 2017 20:20:46 -0500, Les Cargill
<lcargill99@comcast.com> wrote:
>eric.jacobsen@ieee.org wrote:
>> On Sun, 19 Mar 2017 15:14:23 -0500, Les Cargill
>> <lcargill99@comcast.com> wrote:
>>
>>> Update:
>>>
>>> I was able to "put my test driver in a test driver".
>>>
>>> It's still a 512x512 convolution.
>>>
>>> Defining quantities:
>>> FFTSIZE - the size of the FFT
>>> SIGNALBLOCKSIZE - the number of signal samples per FFT
>>> KERNELBLOCKSIZE - the number of kernel samples per FFT
>>>
>>> So FFTSIZE == 64, SIGNALBLOCKSIZE = 13 and therefore
>>> KERNELBLOCKSIZE == 51.
>>>
>>> If I leave less than 51 zero samples to be processed, it doesn't work.
>>> So it's really a 461 x 461 test.
>>>
>>>
>>> What I remain unsure of is whether this is a defect in the thing being
>>> tested, or the test itself. It *reminds* me of the "2N-1" nature of
>>> using convolution to morph equal rectangular pulses into triangular
>>> pulses, but I'm not sure I can say I know that's the case.
>>>
>>> So I have to go over the "last block" processing with a fine tooth comb.
>>>
>>> I also tried the "in the DAW" version of this ( that just meant
>>> peparing test vectors ) and that seems to have worked, although
>>> there were even more zeros there.
>>>
>>> --
>>> Les Cargill
>>
>> Are you sure you're not just seeing the difference between linear and
>> circular convolution? I'm not sure I get all the details of what
>> you're doing, but it sounds like maybe this is part of it?
>>
>>
>>
>> ---
>> This email has been checked for viruses by Avast antivirus software.
>> https://www.avast.com/antivirus
>>
>
>
>I'm not sure you're not right here - and I believe the defect would then
>be in my test setup because I'd need to add enough zeros for it to not
>be a circular convolution.
>
>That fits what I see.
>
>I'm just a bit confused because it's a *block* convolution, so it's not
>like the simple examples you see online. I'm not sure what conceptual
>leaps to make and which to avoid.
>
>Thanks, Eric. And I apologize for how messy the thread's been. This is a
>fairly involved algorithm. Its not complex in itself, but there's a lot
>of offset-accounting to do.
I responded to your previous post before I saw this one. No worries
on details, that's kind of the nature of discussions here; there's
always a tradeoff between brevity or putting people to sleep with too
much detail.
>I think it's time to let this one lie fallow for a while.
Sometimes that clears things up for me...walk away from it for a
while. ;)
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
Reply by ●March 19, 20172017-03-19
On Sun, 19 Mar 2017 20:09:15 -0500, Les Cargill
<lcargill99@comcast.com> wrote:
>eric.jacobsen@ieee.org wrote:
>> On Sun, 19 Mar 2017 15:14:23 -0500, Les Cargill
>> <lcargill99@comcast.com> wrote:
>>
>>> Update:
>>>
>>> I was able to "put my test driver in a test driver".
>>>
>>> It's still a 512x512 convolution.
>>>
>>> Defining quantities:
>>> FFTSIZE - the size of the FFT
>>> SIGNALBLOCKSIZE - the number of signal samples per FFT
>>> KERNELBLOCKSIZE - the number of kernel samples per FFT
>>>
>>> So FFTSIZE == 64, SIGNALBLOCKSIZE = 13 and therefore
>>> KERNELBLOCKSIZE == 51.
>>>
>>> If I leave less than 51 zero samples to be processed, it doesn't work.
>>> So it's really a 461 x 461 test.
>>>
>>>
>>> What I remain unsure of is whether this is a defect in the thing being
>>> tested, or the test itself. It *reminds* me of the "2N-1" nature of
>>> using convolution to morph equal rectangular pulses into triangular
>>> pulses, but I'm not sure I can say I know that's the case.
>>>
>>> So I have to go over the "last block" processing with a fine tooth comb.
>>>
>>> I also tried the "in the DAW" version of this ( that just meant
>>> peparing test vectors ) and that seems to have worked, although
>>> there were even more zeros there.
>>>
>>> --
>>> Les Cargill
>>
>> Are you sure you're not just seeing the difference between linear and
>> circular convolution?
>
>I'm pretty sure there's no circular convolution going on here, but I'll
>double check that assumption. I believe what I have is linear
>convolution via the overlap-add method, using the FFT.
Fast convolution via FFT is always circular at the FFT length. The
overlap-add or overlap-save methods are attempts to make it appear
linear in the aggregate. At the edges it may take some additional
care to make sure things don't get wonky.
>> I'm not sure I get all the details of what
>> you're doing,
>
>Yeah, it's pretty hard to tell. It should be just an iterated block
>convolution using overlap-add.
>
>> but it sounds like maybe this is part of it?
>>
>>
>>
>> ---
>> This email has been checked for viruses by Avast antivirus software.
>> https://www.avast.com/antivirus
>>
>
>--
>Les Cargill
> On Sun, 19 Mar 2017 15:14:23 -0500, Les Cargill
> <lcargill99@comcast.com> wrote:
>
>> Update:
>>
>> I was able to "put my test driver in a test driver".
>>
>> It's still a 512x512 convolution.
>>
>> Defining quantities:
>> FFTSIZE - the size of the FFT
>> SIGNALBLOCKSIZE - the number of signal samples per FFT
>> KERNELBLOCKSIZE - the number of kernel samples per FFT
>>
>> So FFTSIZE == 64, SIGNALBLOCKSIZE = 13 and therefore
>> KERNELBLOCKSIZE == 51.
>>
>> If I leave less than 51 zero samples to be processed, it doesn't work.
>> So it's really a 461 x 461 test.
>>
>>
>> What I remain unsure of is whether this is a defect in the thing being
>> tested, or the test itself. It *reminds* me of the "2N-1" nature of
>> using convolution to morph equal rectangular pulses into triangular
>> pulses, but I'm not sure I can say I know that's the case.
>>
>> So I have to go over the "last block" processing with a fine tooth comb.
>>
>> I also tried the "in the DAW" version of this ( that just meant
>> peparing test vectors ) and that seems to have worked, although
>> there were even more zeros there.
>>
>> --
>> Les Cargill
>
> Are you sure you're not just seeing the difference between linear and
> circular convolution? I'm not sure I get all the details of what
> you're doing, but it sounds like maybe this is part of it?
>
>
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
>
I'm not sure you're not right here - and I believe the defect would then
be in my test setup because I'd need to add enough zeros for it to not
be a circular convolution.
That fits what I see.
I'm just a bit confused because it's a *block* convolution, so it's not
like the simple examples you see online. I'm not sure what conceptual
leaps to make and which to avoid.
Thanks, Eric. And I apologize for how messy the thread's been. This is a
fairly involved algorithm. Its not complex in itself, but there's a lot
of offset-accounting to do.
I think it's time to let this one lie fallow for a while.
--
Les Cargill
Reply by Les Cargill●March 19, 20172017-03-19
eric.jacobsen@ieee.org wrote:
> On Sun, 19 Mar 2017 15:14:23 -0500, Les Cargill
> <lcargill99@comcast.com> wrote:
>
>> Update:
>>
>> I was able to "put my test driver in a test driver".
>>
>> It's still a 512x512 convolution.
>>
>> Defining quantities:
>> FFTSIZE - the size of the FFT
>> SIGNALBLOCKSIZE - the number of signal samples per FFT
>> KERNELBLOCKSIZE - the number of kernel samples per FFT
>>
>> So FFTSIZE == 64, SIGNALBLOCKSIZE = 13 and therefore
>> KERNELBLOCKSIZE == 51.
>>
>> If I leave less than 51 zero samples to be processed, it doesn't work.
>> So it's really a 461 x 461 test.
>>
>>
>> What I remain unsure of is whether this is a defect in the thing being
>> tested, or the test itself. It *reminds* me of the "2N-1" nature of
>> using convolution to morph equal rectangular pulses into triangular
>> pulses, but I'm not sure I can say I know that's the case.
>>
>> So I have to go over the "last block" processing with a fine tooth comb.
>>
>> I also tried the "in the DAW" version of this ( that just meant
>> peparing test vectors ) and that seems to have worked, although
>> there were even more zeros there.
>>
>> --
>> Les Cargill
>
> Are you sure you're not just seeing the difference between linear and
> circular convolution?
I'm pretty sure there's no circular convolution going on here, but I'll
double check that assumption. I believe what I have is linear
convolution via the overlap-add method, using the FFT.
> I'm not sure I get all the details of what
> you're doing,
Yeah, it's pretty hard to tell. It should be just an iterated block
convolution using overlap-add.
> but it sounds like maybe this is part of it?
>
>
>
> ---
> This email has been checked for viruses by Avast antivirus software.
> https://www.avast.com/antivirus
>
--
Les Cargill
Reply by ●March 19, 20172017-03-19
On Sun, 19 Mar 2017 15:14:23 -0500, Les Cargill
<lcargill99@comcast.com> wrote:
>Update:
>
>I was able to "put my test driver in a test driver".
>
>It's still a 512x512 convolution.
>
>Defining quantities:
>FFTSIZE - the size of the FFT
>SIGNALBLOCKSIZE - the number of signal samples per FFT
>KERNELBLOCKSIZE - the number of kernel samples per FFT
>
>So FFTSIZE == 64, SIGNALBLOCKSIZE = 13 and therefore
>KERNELBLOCKSIZE == 51.
>
>If I leave less than 51 zero samples to be processed, it doesn't work.
>So it's really a 461 x 461 test.
>
>
>What I remain unsure of is whether this is a defect in the thing being
>tested, or the test itself. It *reminds* me of the "2N-1" nature of
>using convolution to morph equal rectangular pulses into triangular
>pulses, but I'm not sure I can say I know that's the case.
>
>So I have to go over the "last block" processing with a fine tooth comb.
>
>I also tried the "in the DAW" version of this ( that just meant
>peparing test vectors ) and that seems to have worked, although
>there were even more zeros there.
>
>--
>Les Cargill
Are you sure you're not just seeing the difference between linear and
circular convolution? I'm not sure I get all the details of what
you're doing, but it sounds like maybe this is part of it?
---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus
Reply by Les Cargill●March 19, 20172017-03-19
Update:
I was able to "put my test driver in a test driver".
It's still a 512x512 convolution.
Defining quantities:
FFTSIZE - the size of the FFT
SIGNALBLOCKSIZE - the number of signal samples per FFT
KERNELBLOCKSIZE - the number of kernel samples per FFT
So FFTSIZE == 64, SIGNALBLOCKSIZE = 13 and therefore
KERNELBLOCKSIZE == 51.
If I leave less than 51 zero samples to be processed, it doesn't work.
So it's really a 461 x 461 test.
What I remain unsure of is whether this is a defect in the thing being
tested, or the test itself. It *reminds* me of the "2N-1" nature of
using convolution to morph equal rectangular pulses into triangular
pulses, but I'm not sure I can say I know that's the case.
So I have to go over the "last block" processing with a fine tooth comb.
I also tried the "in the DAW" version of this ( that just meant
peparing test vectors ) and that seems to have worked, although
there were even more zeros there.
--
Les Cargill
Reply by Les Cargill●March 19, 20172017-03-19
Thanks, Ethan - I am obviously somewhat confused :)
I apologize if I can't quite get the thing asked properly,
and thank you for your patience.
ethan@polyspectral.com wrote:
>>
>> Now, for a non-block, all-at-one-time convolution using FFT, the
>> output must be of size greater than or equal to
>> (2*PulseTrainLength)-1. So I think what I am seeing is a ...
>> corollary of this.
>>
>
> I think you're on the right track here. To make it concrete, let's
> suppose your FFT size is 256.
>
> The usual approach is to break both input signals into chunks of 128
> samples, to make sure we don't go past the end of the buffer, and pad
> them out to length 256. Then we do the FFT->multiply->IFFT operation
> and end up with 256 output samples (technically 255, the last one
> will always be zero).
>
> If our input signals were only 128 samples long or less, we're done.
> If not, we have to make sure we mix our 256 output samples into the
> output at the correct place. The result of convolving the m-th chunk
> of signal A and the n-th chunk of signal B should show up in the
> output starting at time 128*(m + n). So there's some tricky
> bookkeeping and overlapping to do there.
>
I *believe* I have that covered. Er, at least I've managed to put in
instrumentation which enforces what I believe to be all the invariants
for that. I will revisit that again, after this is finished.
Yes, the number of kernel samples per FFT must be calculated to be
FFT size - input samples per block, all that. You have to handle "last
blocks" properly.
This is more sinister.
There are actually 5 parameters:
A - # samples per input iteration. [1]
[1] consider a DAW running @ 44100, 2msec service period - 89
samples.
B - FFT size
C,D - # of samples in each pulse train. C == D for this case
E - # of samples in each buffer, including zeros at the end.
Obviously, some permutations there do not work at all.
But I have found cases where when C == E and D == E I get
spurious results. But it always works when E == 2 * C and
E == 2 * D
"2" is just what I have observed; it's less than that but I can't
say I've completely analyzed what the minimum is.
I think I have to have enough zeros as input to meet some constraint
on "using convolution to make triangles" that goes unmet, even though
it's a block convolution.
> Does that clear anything up?
>
It helps refine the direction of the thread. I don't think I've gotten
the question right yet.