Reply by glen herrmannsfeldt●October 6, 20082008-10-06
Rick Lyons wrote:
> On Wed, 1 Oct 2008 11:17:26 -0700 (PDT), SYL <syanli@gmail.com> wrote:
>>Suppose I have N samples and I want to do one N point FFT and a 4N
>>point FFT with zeros padding. Can do get the 4N-FFT by interpolating
>>the N-FFT? Is there a formula? Is the interpolation fast than just do
>>a zero-padded 4N-FFT?
(snip)
> I say that for the following reason. Say our
> N-point time sequence was a pure tone whose
> frequency was exactly at a N-point FFT's bin center.
> The N-point FFT's positive-freq mag results would
> be a single non-zero sample (an impulse sample).
> Interpolating that would yield an interpolated
> sequence whose samples are proportional to the
> impulse response of the interpolation filter.
> The 4N-point FFT magnitude results (of a zero-padded
> time sequence) will be a sin(x)/x sequence.
> So there's no guarantee that the impulse response
> of the interpolation filter will be equal to a
> sin(x)/x sequence.
But once you know N it isn't hard to figure out the response
of sin(x)/x for all N. (With the complication of circular
boundary conditions, so hopefully N isn't too small.)
Then it is just matrix multiply, so hopefully N isn't too big.
-- glen
Reply by glen herrmannsfeldt●October 6, 20082008-10-06
Ron N wrote:
> On Oct 1, 11:17 am, SYL <sya...@gmail.com> wrote:
>>Suppose I have N samples and I want to do one N point FFT and a 4N
>>point FFT with zeros padding. Can do get the 4N-FFT by interpolating
>>the N-FFT? Is there a formula? Is the interpolation fast than just do
>>a zero-padded 4N-FFT?
A 4N point FFT should take about 4*log2(4)=8 times as
long as an N point FFT.
> A zero-padded FFT is the same as a rectangular window in the
> frequency domain which is identical to sin(x)/x or Sinc (actually
> Dirichlet kernel for finite length FFTs) interpolation in the time
> domain. However, most interpolation is done with much shorter
> kernels, which results in a loss of filter quality. If you need the
> quality and a rectangular filter response, a zero-padded FFT might
> be a faster way to get the interpolated results than a sufficiently
> wide interpolation kernel (windowed Sinc, or similar). Or a shorter
> interpolation kernel (or other interpolation method, such as
> bidirectional IIR filtering) may fit your quality requirements.
I would say it depends a lot on why you want the interpolation.
You could do a linear or cubic spline interpolation fairly fast,
which might be good enough for some cases. Maybe even a higher
order spline. If the spectrum is fairly smooth the spline will
likely be pretty close. If it isn't, then, will, why are you
doing this? (It likely matters.)
-- glen
Reply by Ron N●October 6, 20082008-10-06
On Oct 1, 11:17�am, SYL <sya...@gmail.com> wrote:
> Hi,
>
> Suppose I have N samples and I want to do one N point FFT and a 4N
> point FFT with zeros padding. Can do get the 4N-FFT by interpolating
> the N-FFT? Is there a formula? Is the interpolation fast than just do
> a zero-padded 4N-FFT?
A zero-padded FFT is the same as a rectangular window in the
frequency domain which is identical to sin(x)/x or Sinc (actually
Dirichlet kernel for finite length FFTs) interpolation in the time
domain. However, most interpolation is done with much shorter
kernels, which results in a loss of filter quality. If you need the
quality and a rectangular filter response, a zero-padded FFT might
be a faster way to get the interpolated results than a sufficiently
wide interpolation kernel (windowed Sinc, or similar). Or a shorter
interpolation kernel (or other interpolation method, such as
bidirectional IIR filtering) may fit your quality requirements.
.
IMHO. YMMV.
--
rhn A.T nicholson d.0.t C-o-M
Reply by Rick Lyons●October 5, 20082008-10-05
On Wed, 1 Oct 2008 11:17:26 -0700 (PDT), SYL <syanli@gmail.com> wrote:
>Hi,
>
>Suppose I have N samples and I want to do one N point FFT and a 4N
>point FFT with zeros padding. Can do get the 4N-FFT by interpolating
>the N-FFT? Is there a formula? Is the interpolation fast than just do
>a zero-padded 4N-FFT?
>
>Thanks
Hi (again),
Thinking more about this, perhaps
an interpolation filter of the proper shape and
duration can be used to make this "interpolate a
N-point FFT" process work in an acceptable manner.
And maybe we can be clever in performing the convolutional
filtering to minimize its computational workload.
Humm, ... I need to put some additional thought into
this idea.
[-Rick-]
Reply by Rick Lyons●October 5, 20082008-10-05
On Wed, 1 Oct 2008 11:17:26 -0700 (PDT), SYL <syanli@gmail.com> wrote:
>Hi,
>
>Suppose I have N samples and I want to do one N point FFT and a 4N
>point FFT with zeros padding. Can do get the 4N-FFT by interpolating
>the N-FFT? Is there a formula? Is the interpolation fast than just do
>a zero-padded 4N-FFT?
>
>Thanks
Hi,
I'm not sure why no one has replied to
your interesting questions. In any case,
here are my "two cents."
Off the top of my head: even when we account for
the gain loss due to interpolation, I'm willing to
bet a bottle of Pilsner Urquell that interpolating
the N-point FFT results (by a factor
of four) will NOT give the same results as a
4N-point FFT performed on a zero padded
time-domain sequence.
I say that for the following reason. Say our
N-point time sequence was a pure tone whose
frequency was exactly at a N-point FFT's bin center.
The N-point FFT's positive-freq mag results would
be a single non-zero sample (an impulse sample).
Interpolating that would yield an interpolated
sequence whose samples are proportional to the
impulse response of the interpolation filter.
The 4N-point FFT magnitude results (of a zero-padded
time sequence) will be a sin(x)/x sequence.
So there's no guarantee that the impulse response
of the interpolation filter will be equal to a
sin(x)/x sequence.
You should be able to model these two processes
fairly quickly with some software (MathCAD,
MATLAB, etc.).
Good Luck,
[-Rick-]
Reply by SYL●October 1, 20082008-10-01
Hi,
Suppose I have N samples and I want to do one N point FFT and a 4N
point FFT with zeros padding. Can do get the 4N-FFT by interpolating
the N-FFT? Is there a formula? Is the interpolation fast than just do
a zero-padded 4N-FFT?
Thanks