# Frequency interpolation

Started by June 23, 2004
```Hai,

I am in need of a frequency interpolator algorithm, which can find the
arbitrary points "beteween the frequency bins".  When I was going
through the discussions in this group, I found few mails related to
that but many of them are related to finding a particular peak
frequency in the Spectrum.  But my interest is representing a
"N-point" spectrum as a "M-point" spectrum so that when taken IFFT of
it I get back a resampled signal.  Is this possible?

Balaji
```
```"balaji" <subscribemehere@yahoo.co.in> wrote in message
> Hai,
>
> I am in need of a frequency interpolator algorithm, which can find the
> arbitrary points "beteween the frequency bins".  When I was going
> through the discussions in this group, I found few mails related to
> that but many of them are related to finding a particular peak
> frequency in the Spectrum.  But my interest is representing a
> "N-point" spectrum as a "M-point" spectrum so that when taken IFFT of
> it I get back a resampled signal.  Is this possible?
>
> Balaji

Your question isn't completely clear to me, but zero-padding of the time
domain data before peforming the FFT might give you the additional
interpolated points you are looking for. Note that you will not get
increased frequency 'resolution' using this method.

Cheers

```
```"balaji" <subscribemehere@yahoo.co.in> wrote in message
> Hai,
>
> I am in need of a frequency interpolator algorithm, which can find the
> arbitrary points "beteween the frequency bins".  When I was going
> through the discussions in this group, I found few mails related to
> that but many of them are related to finding a particular peak
> frequency in the Spectrum.  But my interest is representing a
> "N-point" spectrum as a "M-point" spectrum so that when taken IFFT of
> it I get back a resampled signal.  Is this possible?

Balaji,

It appears you're confusing two concepts:
- interpolation in frequency
and
- interpolation in time.
So, you need to have that straight.....

To interpolate in frequency, you can do this:
FFT this sequence for reference purposes.
Now, append zeros to the original time sequence so there are now M samples;
N generally nonzero samples and M-N zeros at the end.
FFT this new sequence of M samples.
The comparison of the first FFT and the second FFT is that the length N
frequency sequence is interpolated into a length M frequency sequence.

If you IFFT the length M sequence, you will get the original time sequence
of N samples with M-N zeros appended.  So, there is no resampling to be had
by interpolating in frequency in this manner.

If what you really want to do is increase the temporal sample rate then you
can do this:

Repeat those samples until there are M frequency samples.  That's a repeat
of M/N - so M/N has to be an integer.
This is a periodic spectrum with period N samples but we are now going to
treat it as if it is periodic with period M samples.
Multiply by the frequency response of a lowpass filter so that the bandwidth
remains no greater than the original fs/2 which is now normalized to Mfs/2N.
After lowpass filtering, IFFT.
The result will be a time-interpolated sequence.

If you really want to do both then:

Add zeros to the original time sequence in order to interpolate in
frequency.  This does nothing to the temporal sample rate.
FFT
Repeat the frequency samples as above.  This increases the temporal sample
rate.
Lowpass filter by multiplying.
IFFT
The result is a time sequence with a higher sample rate with a corresponding
interpolated transform.
It still has the zeros that were appended however..... probably perturbed by
the filtering but perhaps not by much.  (er... I think)

There are some good articles at DSPGuru on interpolation.

Fred

```
```In article <abbb46cb.0406230558.17501f20@posting.google.com>,
balaji <subscribemehere@yahoo.co.in> wrote:
>I am in need of a frequency interpolator algorithm, which can find the
>arbitrary points "beteween the frequency bins".  When I was going
>through the discussions in this group, I found few mails related to
>that but many of them are related to finding a particular peak
>frequency in the Spectrum.  But my interest is representing a
>"N-point" spectrum as a "M-point" spectrum so that when taken IFFT of
>it I get back a resampled signal.  Is this possible?

Convolving the output of the N-point FFT with a Sinc function will
interpolate a curve between the sample points related to the frequency
bins.  Of course, quantization and S/N ratio of the original data will
limit the resolution of the interpolation.  You will have to adjust the
width of the Sinc function so that both N-point and M-point signal end up
filtered to meet Nyquist criteria (different cases for M < N and M >= N).

IMHO. YMMV.
--
Ron Nicholson   rhn AT nicholson DOT com   http://www.nicholson.com/rhn/
#include <canonical.disclaimer>        // only my own opinions, etc.
```
```Hai,

I think I did not put my question clearly.  Aim of this exercise is
resampling the signal.  I can do this in time domain, by adding zeros
followed by filtering.  Can I bring about the same effect of
resampling "in the frequency domain".  That is
1. Take a block of input signals
2. Apply DFT to the above
3. Now if you have taken N points of DFT interpolate these N points to
M points
4. Apply IDFT and get back the signal.
Is the above process possible?

You have nearly answered my question like this:
> Repeat those samples until there are M frequency samples.  That's a repeat
> of M/N - so M/N has to be an integer.
> This is a periodic spectrum with period N samples but we are now going to
> treat it as if it is periodic with period M samples.
> Multiply by the frequency response of a lowpass filter so that the bandwidth
> remains no greater than the original fs/2 which is now normalized to Mfs/2N.
> After lowpass filtering, IDFT.
> The result will be a time-interpolated sequence.

Problem is that M/N is not an interger.  For instance, for a
conversion from 44.1kHz to 48kHz the ratio is 160/147.  In fact, for
an oversampling by 2 I am presently using what you have told above.
For ratios like 160/147, I have to know or interpolate the points
between the DFT points. i.e I have to get values corresponding to
points 0.91875, 1.8375, 2.75625 ...
If this is a normal data, I can use polynomial interpolators.  But my
doubt is for a Spectal data(DFT), are there any special algorithms
which will do this job?

Thanks,
Balaji

"Fred Marshall" <fmarshallx@remove_the_x.acm.org> wrote in message
news:<Vf6dnSO4KfJVLETd4p2dnA@centurytel.net>...
> "balaji" <subscribemehere@yahoo.co.in> wrote in message
> > Hai,
> >
> > I am in need of a frequency interpolator algorithm, which can find the
> > arbitrary points "beteween the frequency bins".  When I was going
> > through the discussions in this group, I found few mails related to
> > that but many of them are related to finding a particular peak
> > frequency in the Spectrum.  But my interest is representing a
> > "N-point" spectrum as a "M-point" spectrum so that when taken IFFT of
> > it I get back a resampled signal.  Is this possible?
>
> Balaji,
>
> It appears you're confusing two concepts:
> - interpolation in frequency
> and
> - interpolation in time.
> So, you need to have that straight.....
>
> To interpolate in frequency, you can do this:
> FFT this sequence for reference purposes.
> Now, append zeros to the original time sequence so there are now M samples;
> N generally nonzero samples and M-N zeros at the end.
> FFT this new sequence of M samples.
> The comparison of the first FFT and the second FFT is that the length N
> frequency sequence is interpolated into a length M frequency sequence.
>
> If you IFFT the length M sequence, you will get the original time sequence
> of N samples with M-N zeros appended.  So, there is no resampling to be had
> by interpolating in frequency in this manner.
>
> If what you really want to do is increase the temporal sample rate then you
> can do this:
>
> Repeat those samples until there are M frequency samples.  That's a repeat
> of M/N - so M/N has to be an integer.
> This is a periodic spectrum with period N samples but we are now going to
> treat it as if it is periodic with period M samples.
> Multiply by the frequency response of a lowpass filter so that the bandwidth
> remains no greater than the original fs/2 which is now normalized to Mfs/2N.
> After lowpass filtering, IFFT.
> The result will be a time-interpolated sequence.
>
> If you really want to do both then:
>
> Add zeros to the original time sequence in order to interpolate in
> frequency.  This does nothing to the temporal sample rate.
> FFT
> Repeat the frequency samples as above.  This increases the temporal sample
> rate.
> Lowpass filter by multiplying.
> IFFT
> The result is a time sequence with a higher sample rate with a corresponding
> interpolated transform.
> It still has the zeros that were appended however..... probably perturbed by
> the filtering but perhaps not by much.  (er... I think)
>
> There are some good articles at DSPGuru on interpolation.
>
> Fred
```
```subscribemehere@yahoo.co.in (balaji) wrote in message
> Hai,
>
> I think I did not put my question clearly.  Aim of this exercise is
> resampling the signal.  I can do this in time domain, by adding zeros
> followed by filtering.  Can I bring about the same effect of
> resampling "in the frequency domain".  That is
> 1. Take a block of input signals
> 2. Apply DFT to the above
> 3. Now if you have taken N points of DFT interpolate these N points to
> M points
> 4. Apply IDFT and get back the signal.
> Is the above process possible?

Yes it is. Fred Marshall gave a very clear explanation in his reply to
your first post. In fact, you quote his recipe here so I am sure

> You have nearly answered my question like this:
> > Repeat those samples until there are M frequency samples.  That's a repeat
> > of M/N - so M/N has to be an integer.
> > This is a periodic spectrum with period N samples but we are now going to
> > treat it as if it is periodic with period M samples.
> > Multiply by the frequency response of a lowpass filter so that the bandwidth
> > remains no greater than the original fs/2 which is now normalized to Mfs/2N.
> > After lowpass filtering, IDFT.
> > The result will be a time-interpolated sequence.
>
> Problem is that M/N is not an interger. For instance, for a
> conversion from 44.1kHz to 48kHz the ratio is 160/147.  In fact, for
> an oversampling by 2 I am presently using what you have told above.
> For ratios like 160/147, I have to know or interpolate the points
> between the DFT points. i.e I have to get values corresponding to
> points 0.91875, 1.8375, 2.75625 ...
> If this is a normal data, I can use polynomial interpolators.  But my
> doubt is for a Spectal data(DFT), are there any special algorithms
> which will do this job?

I am sure there are people out there who know this better than me,
but I can vaguely remember hearing that the 44.1/48 ratio was
deliberately chosen so as to make conversions between the CD and DAT
digital formats particularily difficult.

Rune
```
```"balaji" <subscribemehere@yahoo.co.in> wrote in message
> Hai,
>
> I think I did not put my question clearly.  Aim of this exercise is
> resampling the signal.  I can do this in time domain, by adding zeros
> followed by filtering.  Can I bring about the same effect of
> resampling "in the frequency domain".  That is
> 1. Take a block of input signals
> 2. Apply DFT to the above
> 3. Now if you have taken N points of DFT interpolate these N points to
> M points
> 4. Apply IDFT and get back the signal.
> Is the above process possible?

Balaji,

Yes. You can do something in the frequency domain.  It might look like this:

Instead of interpolating in frequency, you need to *extend* in frequency.
(This is exactly the same type of operation as extending in time with zeros
in order to interpolate in frequency while keeping the sample rate
unchanged.  That's what I explained before).
Now the operations are flipped from time to frequency and from frequency to
time and the zeros are put in the middle instead of at one end.

So, add a sequence of zeros in the frequency domain that are equally
distributed around fs/2 - that is, add them in the middle of the sequence.

For example, if there are N samples, add N zeros from the N/2th sample.
The new sample rate is at 2N.

Then IFFT.
The sample rate will be 2x higher than before.  More zeros, higher temporal
sample rate.  The temporal epoch will remain unchanged because you have not
changed the frequency resolution.....

Fred

```
```balaji wrote:

> Hai,
>
> I think I did not put my question clearly.  Aim of this exercise is
> resampling the signal.  I can do this in time domain, by adding zeros
> followed by filtering.  Can I bring about the same effect of
> resampling "in the frequency domain".  That is
> 1. Take a block of input signals
> 2. Apply DFT to the above
> 3. Now if you have taken N points of DFT interpolate these N points to
> M points
> 4. Apply IDFT and get back the signal.
> Is the above process possible?
>

I don't see why not. I did something similar by adding zeros in the freq
domain when going up in fs. The problem is that you probably want to do
this using 2^n length fft's (instead of prime fft's).  Also use
overlap-add if you're processing blocks of data but my guess is that I
don't need to tell you.
```
```Rune wrote:
...
> I am sure there are people out there who know this better than me,
> but I can vaguely remember hearing that the 44.1/48 ratio was
> deliberately chosen so as to make conversions between the CD and DAT
> digital formats particularily difficult.

When you look at the lowest common multiples of 44100 and 44100 +
k*100, for k in {0,1,...,50 } you'll see that 48000 is not at either
extreme (best case is 49000, worst case is 49100, worst case below
48000 is 47900).

I don't know the exact reason either. It would be interesting to hear
this from somebody who knows.

Regards,
Andor
```
```hai,

> Convolving the output of the N-point FFT with a Sinc function will
> interpolate a curve between the sample points related to the frequency
> bins.  Of course, quantization and S/N ratio of the original data will
> limit the resolution of the interpolation.  You will have to adjust the
> width of the Sinc function so that both N-point and M-point signal end up
> filtered to meet Nyquist criteria (different cases for M < N and M >= N).

Can you elaborate this idea a bit more?  I didnot get the essence of
this sync convolution yet.

balaji

rhn@mauve.rahul.net (Ronald H. Nicholson Jr.) wrote in message
news:<cbcn2h\$5pl\$2@blue.rahul.net>...
> balaji <subscribemehere@yahoo.co.in> wrote:
> >I am in need of a frequency interpolator algorithm, which can find the
> >arbitrary points "beteween the frequency bins".  When I was going
> >through the discussions in this group, I found few mails related to
> >that but many of them are related to finding a particular peak
> >frequency in the Spectrum.  But my interest is representing a
> >"N-point" spectrum as a "M-point" spectrum so that when taken IFFT of
> >it I get back a resampled signal.  Is this possible?
>
> Convolving the output of the N-point FFT with a Sinc function will
> interpolate a curve between the sample points related to the frequency
> bins.  Of course, quantization and S/N ratio of the original data will
> limit the resolution of the interpolation.  You will have to adjust the
> width of the Sinc function so that both N-point and M-point signal end up
> filtered to meet Nyquist criteria (different cases for M < N and M >= N).
>
>
> IMHO. YMMV.
```