On 18 Jan 2007 10:25:12 -0800, "robert bristow-johnson"
<rbj@audioimagination.com> wrote:
>
>Rick Lyons wrote:
>>
>> SOOooo, ... I'm sure leaning in the direction of
>> thinking that "fast-convolution analytic
>> signal-generation" can't be performed in an
>> efficient way and still achieve the performance
>> of exactly zero-ing out some signal's neg-freq
>> FFT samples
>
>but that's the same problem with any FIR implementation. the frequency
>response (DFT of FIR) does not exactly meet the design constraints and
>you learn to live with it. if you can implement a Hilbert transformer
>(or an approximation of it) withan FIR, you can do it with fast
>convolution. if throughput delay is not an issue, the optimal size of
>the FFT (to do this fast convolution with the minimum of operations per
>sample) is a function of FIR length L and the relative costs of
>different parts of your FFT, etc.
>
>> (as is possible with a single block
>> of time-domain signal data).
>
>but that OLA and OLS is meant for continuing filtering, not for this
>single block stuff. for that single block analysis, you *still* have
>to keep in mind that you're doing circular convolution.
>
>> Hope that made sense.
>
>as always.
>
>> R B-J & Ron, thanks for your advice.
>
>FWIW.
>r b-j
Hi,
we're in total agreement (I think.).
What I was tryin' to say was that for
a single (finite-length) block of time samples,
their neg-freq components can be made exactly zero.
For real-time signals (infinite-length sequences
of time samples), it doesn't look to me like
fast convolution can *perfectly* zero-out the
infinite-length time signal's neg-freq components.
See Ya',
[-Rick-]
Reply by Jerry Avins●January 18, 20072007-01-18
robert bristow-johnson wrote:
...
> Bob, assuming you understand "linear" convolution (with your impulse
> response on on little slip of paper and your input data drawn on
> another and you slide this impulse response alongside the input), think
> of this FFT convolution as having both slips of paper cut to the same
> length, and then wrapped around and taped (cylinderically). it's when
> the non-zero part of one straddles the splice of the other that you get
> edge problems.
Bob may be seeing another edge effect: the filter's start-up and
tail-off transients. Plug a steady stream on 1s into an LPF, and you
expect to see a steady stream of 1s coming out. That's not what you'll
see when the signal starts up, though.
Jerry
--
Engineering is the art of making what you want from things you can get.
¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯
Reply by Ron N.●January 18, 20072007-01-18
robert bristow-johnson wrote:
> BobM wrote:
> > robert bristow-johnson wrote:
> > > > (as is possible with a single block
> > > > of time-domain signal data).
> > >
> > > but that OLA and OLS is meant for continuing filtering, not for this
> > > single block stuff. for that single block analysis, you *still* have
> > > to keep in mind that you're doing circular convolution.
> >
> > So would it be accurate to say that the frequency domain method _seems_
> > to work for a large block size (large N, where input block size and FFT
> > size = N) only because the negative effects of circular convolution are
> > being masked?
Yes.
> i don't think anything is getting masked. if you don't want the
> "negative effects", you have to make sure that the impulse response
> length L is quite a bit smaller than N and then your input data (of
> total length N) must have at least L-1 zeros padded on it somewhere
> (either at the start or at the end) to prevent errors resulting from
> the impulse response "straddling the seam" of the originally linear
> data that was made to wrap around.
Actually, you might not need the impulse response to be shorter
than N as long as the total energy in the tail beyond N is lower
than your desired noise floor for the result. That's why the transform
seems to work for large N. Large N puts you farther out on the tail,
and the larger rectangle results in a narrower sinc-like filter which
decays faster.
IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M
Reply by robert bristow-johnson●January 18, 20072007-01-18
BobM wrote:
> robert bristow-johnson wrote:
> > > (as is possible with a single block
> > > of time-domain signal data).
> >
> > but that OLA and OLS is meant for continuing filtering, not for this
> > single block stuff. for that single block analysis, you *still* have
> > to keep in mind that you're doing circular convolution.
>
> So would it be accurate to say that the frequency domain method _seems_
> to work for a large block size (large N, where input block size and FFT
> size = N) only because the negative effects of circular convolution are
> being masked?
i don't think anything is getting masked. if you don't want the
"negative effects", you have to make sure that the impulse response
length L is quite a bit smaller than N and then your input data (of
total length N) must have at least L-1 zeros padded on it somewhere
(either at the start or at the end) to prevent errors resulting from
the impulse response "straddling the seam" of the originally linear
data that was made to wrap around.
> I say this because I notice problems at the edges of a
> large block when using this method.
if you didn't zero pad your input block with at least L-1 zeros, you
will have problems.
> I'm having trouble gaining an understanding of the nature of this
> method in the time domain.
...
> Does any of this make sense?
i didn't understand the arcane detail, but i *do* understand that the
time-domain behavior has to be understood.
Bob, assuming you understand "linear" convolution (with your impulse
response on on little slip of paper and your input data drawn on
another and you slide this impulse response alongside the input), think
of this FFT convolution as having both slips of paper cut to the same
length, and then wrapped around and taped (cylinderically). it's when
the non-zero part of one straddles the splice of the other that you get
edge problems.
r b-j
Reply by BobM●January 18, 20072007-01-18
robert bristow-johnson wrote:
> > (as is possible with a single block
> > of time-domain signal data).
>
> but that OLA and OLS is meant for continuing filtering, not for this
> single block stuff. for that single block analysis, you *still* have
> to keep in mind that you're doing circular convolution.
So would it be accurate to say that the frequency domain method _seems_
to work for a large block size (large N, where input block size and FFT
size = N) only because the negative effects of circular convolution are
being masked? I say this because I notice problems at the edges of a
large block when using this method.
I'm having trouble gaining an understanding of the nature of this
method in the time domain. What I see is that the real part is a single
impulse followed by 0's. The imaginary part looks like coefficients for
a bandpass filter, except that it is offset by half the block size. In
other words, the peak of the impulse response lies at the edges and
diminishes in amplitude from the edges to the center of the block. It
looks to me like if this were to be windowed it would need to be
windowed so that the highest part of the window lies at the edges of
the block, and only the imaginary part would be windowed (since the
real part is only a single impulse).
Does any of this make sense?
Reply by robert bristow-johnson●January 18, 20072007-01-18
Rick Lyons wrote:
>
> SOOooo, ... I'm sure leaning in the direction of
> thinking that "fast-convolution analytic
> signal-generation" can't be performed in an
> efficient way and still achieve the performance
> of exactly zero-ing out some signal's neg-freq
> FFT samples
but that's the same problem with any FIR implementation. the frequency
response (DFT of FIR) does not exactly meet the design constraints and
you learn to live with it. if you can implement a Hilbert transformer
(or an approximation of it) withan FIR, you can do it with fast
convolution. if throughput delay is not an issue, the optimal size of
the FFT (to do this fast convolution with the minimum of operations per
sample) is a function of FIR length L and the relative costs of
different parts of your FFT, etc.
> (as is possible with a single block
> of time-domain signal data).
but that OLA and OLS is meant for continuing filtering, not for this
single block stuff. for that single block analysis, you *still* have
to keep in mind that you're doing circular convolution.
> Hope that made sense.
as always.
> R B-J & Ron, thanks for your advice.
FWIW.
r b-j
Reply by Rick Lyons●January 18, 20072007-01-18
On 17 Jan 2007 16:19:38 -0800, "robert bristow-johnson"
<rbj@audioimagination.com> wrote:
>
>Ron N. wrote:
(snipped by Lyons)
>>
>> If you take the iDFT of your sequence, you will find that the
>> resulting impulse response was not padded. Therefore
>> calculations based on your assumption that the sequence
>> was the DFT of a padded imp response will likely fail.
>
>this is the salient thing, Rick and Bob. Ron and i are on exactly the
>same page.
>
>fast-convolution using OLA or OLS implements an FIR. the length of
>that FIR must be shorter than N (the FFT length) and, given a fixed N,
>there is a trade off between the length of the FIR (call it L) and the
>hop distance between adjacent frames (call that M) of input and output.
> N = M+L-1 . so you have to do something (perhaps window) to your
>impulse response to make L enough shorter than N, that you can actually
>get some usable samples to come out each frame.
>
>r b-j
Yea, I certainly understand what you and Ron
are saying. Actually, the length of the FIR
does not *have* to be shorter than N. I can make
this "fast-convolution analytic signal-generation"
work like a charm when the length of the FIR
is equal to N (L = N). However, in this case
what you call the "hop distance" is equal to
one and this means we have to perform a forward
and inverse FFT for *each* filter output
sample. (Sounds like a bad idea to me!!)
SOOooo, ... I'm sure leaning in the direction of
thinking that "fast-convolution analytic
signal-generation" can't be performed in an
efficient way and still achieve the performance
of exactly zero-ing out some signal's neg-freq
FFT samples (as is possible with a single block
of time-domain signal data).
Hope that made sense.
R B-J & Ron, thanks for your advice.
See Ya',
[-Rick-]
Reply by Rick Lyons●January 18, 20072007-01-18
On Wed, 17 Jan 2007 14:38:12 -0500, Mark Borgerding
<mark@borgerding.net> wrote:
>robert bristow-johnson wrote:
>[...]
>>i wonder if, for
>> numerical reasons with finite precision, if OA might "sound better".
>> the "discontinuity" between x[N-1] and x[0] gets in the math in OS and
>> sorta comes out in the wash (except for those L-1 samples that are not
>> saved), but i wonder if there is some numerical "lingering" of that
>> "click" if the word size is small enough even in the samples you keep.
>[..]
>
>I have not characterized the numerical differences between overlap-add
>vs. overlap-save with fixed point math. I suspect there are much bigger
>issues that would steer one away from either. Here's a link to a
>discussion we had on that topic a while back.
>http://tinyurl.com/ys5m4k
>
>-- Mark Borgerding
Hi Mark,
nice hearin' from you. Thanks for
joining the discussion here (and sharing
your thoughts). I'll have a look at that
"http://tinyurl.com/ys5m4k" thread as soon
as I am able.
Thanks again,
[-Rick-]
Reply by Rick Lyons●January 18, 20072007-01-18
On 17 Jan 2007 07:49:57 -0800, sampson164@gmail.com wrote:
>
>> Hi,
>> I can't argue with you on this issue. I don't recall
>> exactly why Mark Borgerding promotes OLS over OLA.
>> Maybe he'll chime in here and present his case.
>
>I'll go get Mark and tell him to quit working and get back to reading
>newsgroups.
>
>Stand by,
>John
Hi John,
Thanks. (I didn't know you
were Mark's Parole Officer. How
convenient for us!)
See Ya',
[-Rick-]
Reply by robert bristow-johnson●January 17, 20072007-01-17
Ron N. wrote:
> Rick Lyons wrote:
> > I'm not sure exactly how Bob's implementing his
> > scheme, but in my implementation there's no
> > impulse response to consider. Where in fast convolution
> > you zero pad the imp response to length N and then
> > takes its DFT, I'm strickly using the sequence
> >
> > 1,2,2,2,...2,2,2,1,0,0,0,0,...,0,0,0,0
> >
> > as if it were the DFT of the padded imp response.
>
> If you take the iDFT of your sequence, you will find that the
> resulting impulse response was not padded. Therefore
> calculations based on your assumption that the sequence
> was the DFT of a padded imp response will likely fail.
this is the salient thing, Rick and Bob. Ron and i are on exactly the
same page.
fast-convolution using OLA or OLS implements an FIR. the length of
that FIR must be shorter than N (the FFT length) and, given a fixed N,
there is a trade off between the length of the FIR (call it L) and the
hop distance between adjacent frames (call that M) of input and output.
N = M+L-1 . so you have to do something (perhaps window) to your
impulse response to make L enough shorter than N, that you can actually
get some usable samples to come out each frame.
r b-j