How do apply window in the Frequency Domain for a signal that was zero padded before FFT?

I can window in the frequency domain without zero padding by following this article here:

http://www.embedded.com/design/configurable-systems/4008835/DSP-Tricks-Frequency-Domain-Windowing

However I need to Zero pad the input signal for a particular size but I'm not sure how to then do frequency domain windowing on this signal.

On Monday, February 10, 2014 4:57:29 AM UTC-5, martin.m...@gmail.com wrote:
> I can window in the frequency domain without zero padding by following this article here: http://www.embedded.com/design/configurable-systems/4008835/DSP-Tricks-Frequency-Domain-Windowing However I need to Zero pad the input signal for a particular size but I'm not sure how to then do frequency domain windowing on this signal.

Zero-padding in the time domain interpolates in the frequency domain.  You can easily see this by setting up some test code to zero pad some function by different amounts and then take the FFT.

You can think this through as follows: 1) get, say, 32 points of an input signal, 2) window it with a 32 point window, 3) zero pad the result to 64 points, 4) transform it.  You might ask: "where's the application of the window in the frequency domain via convolution?"  Well, there wasn't any - and that's the point. By doing it in the time domain first, you'll generate an answer that provides you with some ground truth (ie: this is what you should be getting, no matter what kind of convoluted approach you use).

Now if you decide to do the windowing in the frequency domain, you may run into several problems.  First, you've zero padded your input signal.  You probably should make sure that you have an equivalently zero padded transform of your window points: eg: 1) get 32 time domain points for the window, 2) zero pad it to 64 points, 3) transform it, 4) convolve those points with the transform of your zero padded signal.

I suppose I should mention that many window functions are calculated differently, depending on whether N is an odd or even number.  Also, you may think that you're going to save some big calculation time by using a Hanning (or, more properly, Hann) window and convolving it in the frequency domain - after all, it's only three non-zero points (I haven't transformed a zero-padded time domain Hann window to see if it still has only three non-zero frequency domain points, but I suspect it would - as long as you keep the amount of zero padding to some power of two factor).  But if you're using some weird number for your zero padding, I'm sure you could end up with more non-zero numbers.

All in all, I don't think you're going to save much calculation time by windowing via convolution in the frequency domain - but it might be useful as an exercise just to see how things are done, and it may come in handy for some specific cases.

Kevin McGee

Try transforming the zero-padded window itself.  If you get only a small number of non-zero terms then frequency- domain convolution may still be practical. If not then this technique is not going to work. If your original record length is not a power of 2 then it's pretty much gauranteed to fail. 

Bob

On Mon, 10 Feb 2014 01:57:29 -0800 (PST), martin.mullins942@gmail.com
wrote:

>I can window in the frequency domain without zero padding by following this article here:
>
>http://www.embedded.com/design/configurable-systems/4008835/DSP-Tricks-Frequency-Domain-Windowing
>
>However I need to Zero pad the input signal for a particular size but I'm not sure how to then do frequency >domain windowing on this signal.

Hi,
  Yu've asked a pretty interesting question.

Let's talk about a hanning window.  When you DFT an 
N-point time sequence, you will have three non-zero-
valued freq-domain hanning coefficients to convolve 
with your DFT samples.

When you zero-pad an N-point time sequence to a 
length of 2N, and perform a 2N-point DFT, you will 
have more that 2*3=6 non-zero-valued freq-domain 
hanning coefficients to convolve with your DFT samples.
That's because the DFT of the zero-padded hanning window 
sequence has been interpolated by the time-domain zero 
padding.

When you zero-pad an N-point time sequence to a 
length of 4N, and perform a 4N-point DFT, you will 
have more that 4*3=12 non-zero-valued freq-domain 
hanning coefficients to convolve with your DFT samples.

With zero-padding, the exact number of non-zero-valued 
freq-domain hanning coefficients used for the convolution 
will depend on how small the interpolated (zero-padded) 
hanning window's DFT sequence values are so small that 
you choose to ignore them.

Freq-domain windowing is possible for zero-padded sequences 
but the number of freq-domain window coefficients, needed 
for convolution, will be greater than three.

You'll have to do some software modeling of the process 
to see how many freq-domain window coefficients you need 
for the convolution.

Good Luck,
[-Rick-]
  

I was assuming that the OP had a length-N sequence where N was not necessarily a power of 2, and that he windowed it with an N-point
Hanning window, and then zero-stuffed to extend out to the nearest 2^n length. If that's the case then I think it's hopeless to do the same by frequency-domain convolution. 


Bob

On Tue, 11 Feb 2014 16:35:08 -0800 (PST), radams2000@gmail.com wrote:

>I was assuming that the OP had a length-N sequence where N was not necessarily a power of 2, and that he windowed it with an N-point
>Hanning window, and then zero-stuffed to extend out to the nearest 2^n length. If that's the case then I think it's hopeless to do the same by frequency-domain convolution. 
>
>
>Bob

Hi Bob,
  The OP's post was somewhat vague, wasn't it?

[-Rick-]

Yes it was. There are really 2 distinct non-2^n cases.  If the data is the impulse response of some filter, and you capture the whole response until it's decayed to some very small value , then it makes sense to zero- pad to the next 2^n length and use no window at all before the fft. On the other hand if you want to estimate the spectrum of an infinite-length signal based on a finite set of samples where the record length is not 2^n, then it makes sense to window first and then zero- pad before the fft. I'm having a hard time thinking of a case where you would want to zero- pad and then window and then take the fft (assuming non-2^n length)

Bob

On 2/15/14 11:49 AM, radams2000@gmail.com wrote:
> Yes it was. There are really 2 distinct non-2^n cases.  If the data is the impulse response of some filter, and you capture the whole response until it's decayed to some very small value , then it makes sense to zero- pad to the next 2^n length and use no window at all before the fft. On the other hand if you want to estimate the spectrum of an infinite-length signal based on a finite set of samples where the record length is not 2^n, then it makes sense to window first and then zero- pad before the fft. I'm having a hard time thinking of a case where you would want to zero- pad and then window and then take the fft (assuming non-2^n length)
>

it depends on the length of the window.  if you zero-pad from some 
length L to a longer length N and window that with a length-N window, 
that would be silly.  but if you zero-pad from length L to N, then 
window the non-pad portion with a decent window of length L, that's no 
different in result than windowing first and padding second.

-- 

r b-j                  rbj@audioimagination.com

"Imagination is more important than knowledge."

Yes I agree. 

Bob

On Sunday, February 16, 2014 1:28:48 AM UTC+10, Rick Lyons wrote:
> 
> Hi Bob,
> 
>   The OP's post was somewhat vague, wasn't it?
> 
> 
> 
> [-Rick-]

I'm zero padding from a 2^n to 2^n, say K=2048 window length and N = 8192 the fft length.

After the suggestions from this article it works but only for the case
of zero padding only after the original data rectangle window.
ie. x(n) = [data (len: K)][zeros (len: N-K)]                  -- (1)
If X(m) = FFT{x(n)}
Then X_window(m) = alpha*X(m) - beta/2 * X(m-N/K) - beta/2 * X(m+N/K)
So the only difference is that instead of X(m +/- 1) terms its X(m +/- N/K)
(Was determined by taking the FFT of the hanning window).

However I've tried the case where there is equal padding on both sides.
x(n) = [zeros (len: (N-K)/2)][data (len: K)][zeros (len:(N-K)/2)]        -- (2)
And the resulting windowed fft following the procedure above is wrong, it actually makes it worse.


It seems the only difference between case (1) and (2) is that in (2) by having
the rectangular windowed data shifted in the fft causes a phase shift for the 
dirichlet kernel. But the hanning window centered in the same spot requires the same shift for each of its three dirichlet kernels. Thus I can't see how there should be any difference between case (1) and (2)