Analytic Signal Generation in the Frequency Domain

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

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

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?

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

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

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

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