Analytic Signal Generation in the Frequency Domain

> I have some MATLAB code that implements OS that I wrote.
> (That's because I've been convinced by our DSP pal
> Mark Borgerding that OS is more efficient than OA.)
> Anyway, using my OS software and trying implement
> the "freq-domain analytic sig generation" scheme
> on contiguous blocks of time samples has yielded
> results that sound similar to your results.
>
> The real part of my desired analytic signal seems
> like it might be correct, but the imaginary
> part of my time sequence exhibits gross
> discontinuities.  My gut tells me that the OS
> process should work, but I've done a bit of experimenting
> and darn-it I can't get the process to work.
> This "bugs" me to no end.  I've been scratching
> my head for some time today, but that hasn't helped
> any.

That's the same thing I am seeing. The real part looks good to me, but
the imaginary part is showing discontinuities. But more than just
discontinuities between frames, it looks "distorted."

>
> Bob, if we can't figure this out, we can always
> "wave the white flag" and post another message here
> asking for help.  Surely you and I aren't the first
> guys who've tried to solve this problem.  It
> seems so "straightforward"!!

Thanks again Rick. I would imagine somebody has tried to implement this
as a block process.

This also makes me wonder if the process as stated currently is
"flawed." To be more clear, I also see oddities in the imaginary output
for a very large FFT size (say, for a few seconds of audio). In my
understanding Matlab is calculating the Hilbert transformation using
this method, and we may be seeing the same issue here.

> The errata has been updated since we last exchanged
> E-mails.
> Bob, do you still have your "...@yahoo.com" E-mail
> address that you used back in May of 2005?

Ok, I'd be happy to receive it! Yes, I still have the yahoo address.

Regards,
Bob

On 16 Jan 2007 14:52:34 -0800, "robert bristow-johnson"
<rbj@audioimagination.com> wrote:

>
>BobM wrote:
>> >
>> >    1,2,2,2,...2,2,2,1,0,0,0,0,...,0,0,0,0
>> >
>> > I'd guess the time-domain impulse response would
>> > some sort of complex sequence whose magnitude response
>> > would be very similar to a sinx(x) sequence.
>>
>> Based on R B-J's question I took an IFFT of the above sequence, and it
>> looks as you describe.
>
>so what you need to do is window it or something so that it is of
>length shorter than your FFT.  that's what you *must* do to use the FFT
>and OLA to do convolution.
>
>...
>>
>> I'm not absolutely certain that OLA is needed. It
>> appears to be necessary though.
>
>you can do direct convolution to implement a (delayed) Hilbert
>Transformer.
>
>
>but if you want to do "fast convolution" (by use of the FFT), you need
>to insure that your circular convolution does not straddle this nasty
>boundary between x[N-1] and x[0] where both are non-zero.  this is why
>zero padding is needed. at least for OLA, if it's overlap-save (OLS),
>there is another way to do it so that you only save the samples that
>weren't contaminated by the bad wrap-around or straddling.  either way
>(OLS or OLA) you have to have your frequency response of the FIR filter
>be such that the impulse response attached to it is shorter than the
>FFT length by enough that you can get some decent quantity of output
>samples for each overlapping FFT frame.
>
>> Thanks to both of you for your time and your help.
>
>FWIW.

Hi R B-J,
  yep, I'm sure you're right about all the above 
precautions necessary about implementing "fast convolution."

[-Rick-]

On 16 Jan 2007 21:21:00 -0800, "robert bristow-johnson"
<rbj@audioimagination.com> wrote:

>
>Rick Lyons wrote:
>> (That's because I've been convinced by our DSP pal
>> Mark Borgerding that OS is more efficient than OA.)
>
>i dunno why it wouldn't.  OS and OA have the same computation for the
>FFT, applying frequency response, and iFFT.  and they both advance your
>input pointer the same amount per frame.  and the OA requires padding
>the input frame with zeros and adding the overlapped output frames.  OS
>requires copying some samples over from the previous frame instead of
>padding and then just picking the segment of samples that is not
>contaminated from the impulse response straddling the wrap around point
>between x[N-1] and x[0].  copying samples is maybe a little slower than
>stuffing zero but i would not expect the cost of those extra reads to
>be as much as a the same number of reads, adds, and write.  actually OA
>would be twice the number of reads (twice the overlap length) than OS.
> i'm convinced, too (but i always thunk it).  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.
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.
>
>> Anyway, using my OS software and trying implement
>> the "freq-domain analytic sig generation" scheme
>> on contiguous blocks of time samples has yielded
>> results that sound similar to your results.
>
>even if the impulse response is no longer than N-M+1 where N is the FFT
>length and M is your hop size (the number of samples you keep each
>frame)? 

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.

I'll keep playin' around with this as time 
permits.

See Ya',
[-Rick-]

> 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

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
> 


I dunno if I "promote OLS over OLA".  I would say there is a slight
speed advantage to using overlap-save because it skips the additions of
the transient responses in overlap-add.  All other things being equal,
that would make OLS slightly preferable.  ... But all other things are
rarely equal.

Here are some reasons to prefer OLA:

1.) Some memory layouts may lend themselves better to OLA.

2.) Spectra are to be recovered from the output FFT data.  In OLS, this
would be stymied by the presence of the "wraparound transient" in the
frequency domain data.

3.) The implementer understands OLA better.


There are many tools for many purposes.


-- Mark Borgerding

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.

See my post about the impulse response being close to
a sinc with inversly proportional lobe width.  The shorter
sequences produce a wider sinc with perhaps too much
energy wrapping around the edges of the fft aperature.
This puts a lower limit on N for a given result "quality"
(s/n or whatever).


IMHO. YMMV.
-- 
rhn A.T nicholson d.0.t C-o-M

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

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

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

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