FFT upsampling filter

Hi, all:

New member here. I did a search, but it seems there is no information
related to this topic.

What I am doing now is I am trying to upsample some data points to a much
higher sample rate, and to do that, I need a low pass filter after zero
stuffing.

There are 2 ways to reduce calculation complexity, AFAIK:
a. To use a polyphase filter at input sample rate, or
b. To use a FFT filter at output sample rate.

Is there any possibility that I can do FFT based FIR at input sample rate?
If so, this will reduce the calculation complexity by a whole LOT.






Thanks, 
Bo


---------------------------------------
Posted through http://www.DSPRelated.com

On 16.05.15 13.04, blueskull wrote:
> What I am doing now is I am trying to upsample some data points to a much
> higher sample rate, and to do that, I need a low pass filter after zero
> stuffing.
>
> There are 2 ways to reduce calculation complexity, AFAIK:
> a. To use a polyphase filter at input sample rate, or

??? The input samples contain all information that you want to keep. So 
what do you want to filter /before/ upsampling?

> b. To use a FFT filter at output sample rate.
>
> Is there any possibility that I can do FFT based FIR at input sample rate?

The same applies to the FIR filter.

> If so, this will reduce the calculation complexity by a whole LOT.

If you upsample by a higher factor your filter has much room for 
transistion. You do not need a very large filter kernel.

However, if you intend to use FFT anyway you simply can do the 
upsampling in the time domain. So only the inverse transformation needs 
to work at the target sample rate. Of course, I assume a power of two 
between the sampling rate here.


Marcel

>Hi, all:
>
>New member here. I did a search, but it seems there is no information
>related to this topic.
>
>What I am doing now is I am trying to upsample some data points to a
>much
>higher sample rate

[...snip...]

>b. To use a FFT filter at output sample rate.
>

[...snip...]

>
>Thanks, 
>Bo
>
>
>---------------------------------------
>Posted through http://www.DSPRelated.com

I am assuming you have a real valued signal.  The process using a FFT is
simple:

1) Take the FFT with a 1/N Normalization Factor

2) Zero out the top half of the FFT

3) Zero pad the FFT to the new size

4) Take an inverse DFT (or FFT) with a normalization factor of 2.

This works because DFT bin values are actually the coefficients of Fourier
series.  The top half of the bins don't represent frequencies at those
values, they are merely the conjugate mirrors of the bottom half.  That is
why you want to zero them out.

Filtering will cause you to lose information.  There are more efficient
techniques that can be done in the time domain.

You will also want to do slightly overlapping frames with sliding average
ends to smooth out any small discontinuities that can arise.

Ced
---------------------------------------
Posted through http://www.DSPRelated.com

Small correction.

5) Multiply the imaginary part of your output by i, and add it to the real
part.

Or, what's easier to understand, is treat the real values in your DFT as
the coefficients of cosine series and the imaginary part as real values
negative coefficients of sine series.

Ced
---------------------------------------
Posted through http://www.DSPRelated.com

On Sat, 16 May 2015 06:04:01 -0500, "blueskull" <105858@DSPRelated>
wrote:

>Hi, all:
>
>New member here. I did a search, but it seems there is no information
>related to this topic.
>
>What I am doing now is I am trying to upsample some data points to a much
>higher sample rate, and to do that, I need a low pass filter after zero
>stuffing.
>
>There are 2 ways to reduce calculation complexity, AFAIK:
>a. To use a polyphase filter at input sample rate, or

This works very well if you have a filter response that is suitable
for your system.   We do this in communication systems all the time
where the filter response is the pulse-shaping Nyquist filter, so that
we get pulse shaping and upsampling (to an arbitrary rate) with the
same filter..

>b. To use a FFT filter at output sample rate.
>
>Is there any possibility that I can do FFT based FIR at input sample rate?
>If so, this will reduce the calculation complexity by a whole LOT.

I'm not completely sure what you mean by this, but what you want to do
may be as simple as:

1. FFT
2. Zero pad to desired output length.
3. Inverse FFT at the longer vector length.

That's a very straightforward way to upsample a signal, but the
complexity is fairly high.   If that's not an issue then this may work
for you depending on your constraints.


>
>
>
>
>
>Thanks, 
>Bo
>
>
>---------------------------------------
>Posted through http://www.DSPRelated.com

Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

Depends if you are operating in real time or on a computer file. For real-time operation I would use the polyphase approach to avoid the latency. If it's just a file then the fft approach mentioned by Eric may work. But be careful about just applying a simple 1-0 mask in the frequency domain. 

Bob

[...snip...]

>I'm not completely sure what you mean by this, but what you want to do
>may be as simple as:
>
>1. FFT
>2. Zero pad to desired output length.
>3. Inverse FFT at the longer vector length.
>

The problem with this approach is it assumes the bins at the top half of
the original DFT represent frequencies higher than the Nyquist frequency,
so these will be introduced in the reconstruction because there they are
lower than the new Nyquist frequency (assuming at least a doubling of
samples).
 
Assume there are N samples input and M samples output per frame.  If you
treat your bins as a "signed interpretation" and shift the upper half bin
values up so bin N-1 becomes bin M-1, and so on, this won't happen and a
graph of the output signal will look just like a graph of the input
signal.  The Nyquist bin can be shifted or left where it is, the effect is
the same since it will always be real valued and the cosine of an angle is
the same as the cosine of the negative angle.  Of course you want to zero
all the other bins.

Ced
---------------------------------------
Posted through http://www.DSPRelated.com

On Sat, 16 May 2015 13:52:11 -0500, "Cedron" <103185@DSPRelated>
wrote:

>[...snip...]
>
>>I'm not completely sure what you mean by this, but what you want to do
>>may be as simple as:
>>
>>1. FFT
>>2. Zero pad to desired output length.
>>3. Inverse FFT at the longer vector length.
>>
>
>The problem with this approach is it assumes the bins at the top half of
>the original DFT represent frequencies higher than the Nyquist frequency,
>so these will be introduced in the reconstruction because there they are
>lower than the new Nyquist frequency (assuming at least a doubling of
>samples).

Wait, what?    I think the only real assumption is that one needs to
know what they're doing.   Whether the FFT output is folded or not, or
whether the input is real or complex, or all the other things that
need to be handled, need to be handled. 

I don't think what you're assuming is assumed is really assumed.

>Assume there are N samples input and M samples output per frame.  If you
>treat your bins as a "signed interpretation" and shift the upper half bin
>values up so bin N-1 becomes bin M-1, and so on, this won't happen and a
>graph of the output signal will look just like a graph of the input
>signal.  The Nyquist bin can be shifted or left where it is, the effect is
>the same since it will always be real valued and the cosine of an angle is
>the same as the cosine of the negative angle.  Of course you want to zero
>all the other bins.

I'm not sure what you're trying to describe, unless, perhaps, you're
assuming that the FFT output is not folded?   In that case, then, yes,
pad in the middle.   Otherwise, pad at the ends.   Don't assume.
Don't even assume that something is assumed.

Or so I assume.  ;)

>Ced
>---------------------------------------
>Posted through http://www.DSPRelated.com

Eric Jacobsen
Anchor Hill Communications
http://www.anchorhill.com

[...snip...]

>
>Wait, what?    I think the only real assumption is that one needs to
>know what they're doing.   Whether the FFT output is folded or not, or
>whether the input is real or complex, or all the other things that
>need to be handled, need to be handled. 

No argument there.  It always helps to know what you are doing.

>
>I don't think what you're assuming is assumed is really assumed.
>


[...snip...]
>Don't even assume that something is assumed.
>
>Or so I assume.  ;)
>
>>Ced
>>---------------------------------------
>>Posted through http://www.DSPRelated.com
>
>Eric Jacobsen
>Anchor Hill Communications
>http://www.anchorhill.com

I guess I'll have to assume that 'assume' is the wrong word.  Maybe if I
had said 'acts as if' it would have been clearer.

Let me illustrate by point by a simple concrete example.  Suppose the
signal is

S_k = cos( k 2pi/16 )   0 <= k < 16 

N=16 and M=100.  When you take the FFT, bin number one will be one half
and bin 15 will be one half.  All other bins will be zero.  Now if you end
pad and take the inverse DFT the output signal will be

S_k = 1/2 cos( k 2pi/100 ) + 1/2 cos( 15k 2pi/100 ) 
0 <= k < 100

The latter being the alias frequency within the original context, but
renderable within the output context.

If you slide the one half up from bin 15 to bin 99 before you do the
inverse DFT, you will get the desired results:
 
S_k = 1/2 cos( k 2pi/100 ) + 1/2 cos( 99k 2pi/100 ) 
S_k = 1/2 cos( k 2pi/100 ) + 1/2 cos( (100-1)k 2pi/100 ) 
S_k = 1/2 cos( k 2pi/100 ) + 1/2 cos( -k 2pi/100 ) 
S_k = 1/2 cos( k 2pi/100 ) + 1/2 cos( k 2pi/100 ) 
S_k = cos( k 2pi/100 )

See what I mean?

Ced
---------------------------------------
Posted through http://www.DSPRelated.com

>Or so I assume.  ;)

Upon rereading my previous replies, I suppose I did say assume a lot.

I assume that is supposedly bad.

Sigh.

Ced
---------------------------------------
Posted through http://www.DSPRelated.com