Using the convolution of two rectangular signals to test a block convolver.

To test a convolver, a rectangular train of pulses can be convolved with 
( a copy of ) itself to produce a triangular pulse.

So suppose I have two quantities related to rectangular pulses:

- Buffer size - number of pulses possible. The "10" in "float 
pulse1[10]" is the buffer size. Call this BufferSize.

- The length of the rectangular pulse. This much be <= the buffer size.
Call this PulseTrainLength.

What I find is that for a block convolver, there must be some "room"
left at the end. PulseTrainLength must be some n less than BufferSize or
you get spurious results.

This seems to be some function of the # of samples per block convolution
and the length of the FFT used by the block convolution. I have not 
quite nailed the relationship down.

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.

Obviously, two continuous streams of 1s to a block convolver would 
overflow after a while.

So I wonder of the real test should not be to have a sequence of
rectangular pulses convolved with itself but with enough spans of
zeros to prevent overflow. This would be done in a DAW, with prepared
.wav files for the signal and the convolution kernel.

I am trying to figure out if the bug is in the test, or in the code 
being tested.

Thanks in advance.

-- 
Les Cargill

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

Does that clear anything up?

-Ethan
 

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.

> -Ethan
>
>

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

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

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

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 think it's time to let this one lie fallow for a while.

-- 
Les Cargill

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


---
This email has been checked for viruses by Avast antivirus software.
https://www.avast.com/antivirus

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

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