Hi,
I was wondering if it is possible produce a sliding DFT, but also to
keep the effects of a zero padded spectrum.
For example, for a non zero padded signal the sliding DFT complex
frequnecy spectrum is calculated as follows
Xk(n) = [Xk(n-1)-x(n-N) + x(n)] *exp^(j2pik/N)
which is the same as moving a window on by one sample and taking the
FFT again.
but when zero padding in the follwing way (numbers indicating whre
information would be in the time domain):
[signal 0-511][ zeros 512 -1023]
the signal is only changing in the 0-511 samples, the number of zeros
always stays constant. Is it therfore possible to produce a sliding
DFT with zero padding?
Any help really appreciated.
J
Zero Padding and Sliding DFT
Started by ●August 16, 2008
Reply by ●August 17, 20082008-08-17
> Subject: Zero Padding and Sliding DFT
> Posted by: "sandwich_20082001" j...@york.ac.uk sandwich_20082001
> Date: Sat Aug 16, 2008 7:23 am ((PDT))
>
> Hi,
>
> I was wondering if it is possible produce a sliding DFT, but also to
> keep the effects of a zero padded spectrum.
>
> For example, for a non zero padded signal the sliding DFT complex
> frequnecy spectrum is calculated as follows
>
> Xk(n) = [Xk(n-1)-x(n-N) + x(n)] *exp^(j2pik/N)
>
> which is the same as moving a window on by one sample and taking the
> FFT again.
>
> but when zero padding in the follwing way (numbers indicating whre
> information would be in the time domain):
>
> [signal 0-511][ zeros 512 -1023]
>
> the signal is only changing in the 0-511 samples, the number of zeros
> always stays constant. Is it therfore possible to produce a sliding
> DFT with zero padding?
>
> Any help really appreciated.
>
> J
Hi J,
Yes it is possible to slide the spectrum. It should be taken into
considerations that since the update formula references spectral data
from the previous iteration Xk(n-1), and the length of the spectrum
after padding initial signal data is N = L(signal) + L(padding),
the indices in the update expression run from 0 through N-1. Which
essentially means that no matter what was the initial length of
the signal N(signal) then after N-L(padding) updates the further updates
do not use padding.
The above is very close to to starting with all zero spectrum and update it
using the above formula.
It is also follows that the effect of padding the signal data with zeros (that
results in an interpolated spectrum) would fade away with the updates.
As I can see it, the main point is that the spectrum length is a sum of
the signal's length and padding length.
Regards,
Andrew
> Posted by: "sandwich_20082001" j...@york.ac.uk sandwich_20082001
> Date: Sat Aug 16, 2008 7:23 am ((PDT))
>
> Hi,
>
> I was wondering if it is possible produce a sliding DFT, but also to
> keep the effects of a zero padded spectrum.
>
> For example, for a non zero padded signal the sliding DFT complex
> frequnecy spectrum is calculated as follows
>
> Xk(n) = [Xk(n-1)-x(n-N) + x(n)] *exp^(j2pik/N)
>
> which is the same as moving a window on by one sample and taking the
> FFT again.
>
> but when zero padding in the follwing way (numbers indicating whre
> information would be in the time domain):
>
> [signal 0-511][ zeros 512 -1023]
>
> the signal is only changing in the 0-511 samples, the number of zeros
> always stays constant. Is it therfore possible to produce a sliding
> DFT with zero padding?
>
> Any help really appreciated.
>
> J
Hi J,
Yes it is possible to slide the spectrum. It should be taken into
considerations that since the update formula references spectral data
from the previous iteration Xk(n-1), and the length of the spectrum
after padding initial signal data is N = L(signal) + L(padding),
the indices in the update expression run from 0 through N-1. Which
essentially means that no matter what was the initial length of
the signal N(signal) then after N-L(padding) updates the further updates
do not use padding.
The above is very close to to starting with all zero spectrum and update it
using the above formula.
It is also follows that the effect of padding the signal data with zeros (that
results in an interpolated spectrum) would fade away with the updates.
As I can see it, the main point is that the spectrum length is a sum of
the signal's length and padding length.
Regards,
Andrew
Reply by ●August 17, 20082008-08-17
Hi
So how would the following spectrum be calculated from the previous
spectrum with the effect of zero padding maintained?
I have tried in Matlab padding a spectrum and then using the sliding
equation for the size of the signal+padding but this does not produce
the correct result.
Thanks
J
Andrew Nesterov wrote:
>> Subject: Zero Padding and Sliding DFT
>> Posted by: "sandwich_20082001" j...@york.ac.uk sandwich_20082001
>> Date: Sat Aug 16, 2008 7:23 am ((PDT))
>>
>> Hi,
>>
>> I was wondering if it is possible produce a sliding DFT, but also to
>> keep the effects of a zero padded spectrum.
>>
>> For example, for a non zero padded signal the sliding DFT complex
>> frequnecy spectrum is calculated as follows
>>
>> Xk(n) = [Xk(n-1)-x(n-N) + x(n)] *exp^(j2pik/N)
>>
>> which is the same as moving a window on by one sample and taking the
>> FFT again.
>>
>> but when zero padding in the follwing way (numbers indicating whre
>> information would be in the time domain):
>>
>> [signal 0-511][ zeros 512 -1023]
>>
>> the signal is only changing in the 0-511 samples, the number of zeros
>> always stays constant. Is it therfore possible to produce a sliding
>> DFT with zero padding?
>>
>> Any help really appreciated.
>>
>> J
>
> Hi J,
>
> Yes it is possible to slide the spectrum. It should be taken into
> considerations that since the update formula references spectral data
> from the previous iteration Xk(n-1), and the length of the spectrum
> after padding initial signal data is N = L(signal) + L(padding),
> the indices in the update expression run from 0 through N-1. Which
> essentially means that no matter what was the initial length of
> the signal N(signal) then after N-L(padding) updates the further updates
> do not use padding.
>
> The above is very close to to starting with all zero spectrum and
> update it using the above formula.
>
> It is also follows that the effect of padding the signal data with
> zeros (that results in an interpolated spectrum) would fade away with
> the updates.
>
> As I can see it, the main point is that the spectrum length is a sum of
> the signal's length and padding length.
>
> Regards,
>
> Andrew
>
So how would the following spectrum be calculated from the previous
spectrum with the effect of zero padding maintained?
I have tried in Matlab padding a spectrum and then using the sliding
equation for the size of the signal+padding but this does not produce
the correct result.
Thanks
J
Andrew Nesterov wrote:
>> Subject: Zero Padding and Sliding DFT
>> Posted by: "sandwich_20082001" j...@york.ac.uk sandwich_20082001
>> Date: Sat Aug 16, 2008 7:23 am ((PDT))
>>
>> Hi,
>>
>> I was wondering if it is possible produce a sliding DFT, but also to
>> keep the effects of a zero padded spectrum.
>>
>> For example, for a non zero padded signal the sliding DFT complex
>> frequnecy spectrum is calculated as follows
>>
>> Xk(n) = [Xk(n-1)-x(n-N) + x(n)] *exp^(j2pik/N)
>>
>> which is the same as moving a window on by one sample and taking the
>> FFT again.
>>
>> but when zero padding in the follwing way (numbers indicating whre
>> information would be in the time domain):
>>
>> [signal 0-511][ zeros 512 -1023]
>>
>> the signal is only changing in the 0-511 samples, the number of zeros
>> always stays constant. Is it therfore possible to produce a sliding
>> DFT with zero padding?
>>
>> Any help really appreciated.
>>
>> J
>
> Hi J,
>
> Yes it is possible to slide the spectrum. It should be taken into
> considerations that since the update formula references spectral data
> from the previous iteration Xk(n-1), and the length of the spectrum
> after padding initial signal data is N = L(signal) + L(padding),
> the indices in the update expression run from 0 through N-1. Which
> essentially means that no matter what was the initial length of
> the signal N(signal) then after N-L(padding) updates the further updates
> do not use padding.
>
> The above is very close to to starting with all zero spectrum and
> update it using the above formula.
>
> It is also follows that the effect of padding the signal data with
> zeros (that results in an interpolated spectrum) would fade away with
> the updates.
>
> As I can see it, the main point is that the spectrum length is a sum of
> the signal's length and padding length.
>
> Regards,
>
> Andrew
>
Reply by ●August 18, 20082008-08-18
> Date: 17-Aug-2008 05:25:28 -0700
> From: James Hayward Hi
>
> So how would the following spectrum be calculated from the previous spectrum
> with the effect of zero padding maintained?
>
> I have tried in Matlab padding a spectrum and then using the sliding equation
> for the size of the signal+padding but this does not produce the correct
> result.
>
> Thanks
>
> J
Hi James,
I've been thinking a little more about the question. So far, one of the
implementations of the sliding algorithm could be as follows. The initial
array of signal and padding is (Ls is the length of the discrete signal,
Lp is the length of padding, N = Ls + Lp, P(k) are padding values, i.e.
zeroes)
x(0),x(1),...,x(Ls-1),P(0),...,P(Lp-1) - of N elements total
First, a DFT of the above array is performed; if N is right for a fast
transform, then an FFT could be used. The transform produced the spectrum
of the zero padded array.
After this phase, the sliding equation is used to update the spectrum for
each new incoming data sample. As the equation suggest, the input data array
is to be processed as a circular buffer, where the incoming sample replaces the
most obsolete sample, that is after the DFT would be x(0). The iterations
continue with x(1),...,P(lp-1) because spectrum length is the sum of initial
data and padding. On the Ls iteration the incoming sample replaces the first
padding entry P(0), et caetera until all zeroes are replaced with signal data.
As it is now clear, there is no means to keep padding in the sliding update
algorithm. This happens because the spectrum is updated on a sample by
sample basis, while zero padding is used in a window algorithm to interpolate
spectral components. The sliding approach does not involve spectral
interpolation, due to its array length is N, not Ls for both the data and the
spectrum.
Another approach to start sliding is to begin with both data and spectrum
arrays filled with zeroes. On zeroth iteration, x(0) enters the data array,
and the array may be considered as padded with N-1 zeros, et caetera, while
on the N-1 iteration the whole data array contain signal samples. On the
next iteration, x(N) replaces x(0), but apparently there will be no zero
padding anymore.
It is interesting to check yet another method, to fill in the next sample
into P(0)-th location after the initial DFT as in the first method I mentioned.
It will be a correct update of the initial interpolated spectrum, but as the
iterations progress, the interpolated spectral components would become more
close to the actual spectral components of the "instant" spectrum, and on
the Lp-1 iteration, the components should be just the same as if a DFT of
the signal array of length N (that is Ls+Lp) were calculated using a DFT or
an FFT.
I just cannot see the way to keep the effect of padding, because zeroes are
gone with time progressing.
A small note on your sliding equation, perhaps due to the notation chosen,
I am not sure about it. Routinely I use for the updated spectral components
X'(k), where k runs from 0 to N-1 the following:
X'(k) = (X(k) - x(-1) + x(N-1) * exp (j*2*pi*k/N)
The x(-1) sample leaves the array, the x(N-1) enters the array, but their
actual positions are determined on each iteration using circular buffer
pointer.
I hope this helps.
Regards,
Andrew
> Andrew Nesterov wrote:
>>> Subject: Zero Padding and Sliding DFT
>>> Posted by: "sandwich_20082001" j...@york.ac.uk sandwich_20082001
>>> Date: Sat Aug 16, 2008 7:23 am ((PDT))
>>>
>>> Hi,
>>>
>>> I was wondering if it is possible produce a sliding DFT, but also to
>>> keep the effects of a zero padded spectrum.
>>>
>>> For example, for a non zero padded signal the sliding DFT complex
>>> frequnecy spectrum is calculated as follows
>>>
>>> Xk(n) = [Xk(n-1)-x(n-N) + x(n)] *exp^(j2pik/N)
>>>
>>> which is the same as moving a window on by one sample and taking the
>>> FFT again.
>>>
>>> but when zero padding in the follwing way (numbers indicating whre
>>> information would be in the time domain):
>>>
>>> [signal 0-511][ zeros 512 -1023]
>>>
>>> the signal is only changing in the 0-511 samples, the number of zeros
>>> always stays constant. Is it therfore possible to produce a sliding
>>> DFT with zero padding?
>>>
>>> Any help really appreciated.
>>>
>>> J
>>
>> Hi J,
>>
>> Yes it is possible to slide the spectrum. It should be taken into
>> considerations that since the update formula references spectral data
>> from the previous iteration Xk(n-1), and the length of the spectrum
>> after padding initial signal data is N = L(signal) + L(padding),
>> the indices in the update expression run from 0 through N-1. Which
>> essentially means that no matter what was the initial length of
>> the signal N(signal) then after N-L(padding) updates the further updates
>> do not use padding.
>>
>> The above is very close to to starting with all zero spectrum and update it
>> using the above formula.
>>
>> It is also follows that the effect of padding the signal data with zeros
>> (that results in an interpolated spectrum) would fade away with the
>> updates.
>>
>> As I can see it, the main point is that the spectrum length is a sum of
>> the signal's length and padding length.
>>
>> Regards,
>>
>> Andrew
>
> From: James Hayward Hi
>
> So how would the following spectrum be calculated from the previous spectrum
> with the effect of zero padding maintained?
>
> I have tried in Matlab padding a spectrum and then using the sliding equation
> for the size of the signal+padding but this does not produce the correct
> result.
>
> Thanks
>
> J
Hi James,
I've been thinking a little more about the question. So far, one of the
implementations of the sliding algorithm could be as follows. The initial
array of signal and padding is (Ls is the length of the discrete signal,
Lp is the length of padding, N = Ls + Lp, P(k) are padding values, i.e.
zeroes)
x(0),x(1),...,x(Ls-1),P(0),...,P(Lp-1) - of N elements total
First, a DFT of the above array is performed; if N is right for a fast
transform, then an FFT could be used. The transform produced the spectrum
of the zero padded array.
After this phase, the sliding equation is used to update the spectrum for
each new incoming data sample. As the equation suggest, the input data array
is to be processed as a circular buffer, where the incoming sample replaces the
most obsolete sample, that is after the DFT would be x(0). The iterations
continue with x(1),...,P(lp-1) because spectrum length is the sum of initial
data and padding. On the Ls iteration the incoming sample replaces the first
padding entry P(0), et caetera until all zeroes are replaced with signal data.
As it is now clear, there is no means to keep padding in the sliding update
algorithm. This happens because the spectrum is updated on a sample by
sample basis, while zero padding is used in a window algorithm to interpolate
spectral components. The sliding approach does not involve spectral
interpolation, due to its array length is N, not Ls for both the data and the
spectrum.
Another approach to start sliding is to begin with both data and spectrum
arrays filled with zeroes. On zeroth iteration, x(0) enters the data array,
and the array may be considered as padded with N-1 zeros, et caetera, while
on the N-1 iteration the whole data array contain signal samples. On the
next iteration, x(N) replaces x(0), but apparently there will be no zero
padding anymore.
It is interesting to check yet another method, to fill in the next sample
into P(0)-th location after the initial DFT as in the first method I mentioned.
It will be a correct update of the initial interpolated spectrum, but as the
iterations progress, the interpolated spectral components would become more
close to the actual spectral components of the "instant" spectrum, and on
the Lp-1 iteration, the components should be just the same as if a DFT of
the signal array of length N (that is Ls+Lp) were calculated using a DFT or
an FFT.
I just cannot see the way to keep the effect of padding, because zeroes are
gone with time progressing.
A small note on your sliding equation, perhaps due to the notation chosen,
I am not sure about it. Routinely I use for the updated spectral components
X'(k), where k runs from 0 to N-1 the following:
X'(k) = (X(k) - x(-1) + x(N-1) * exp (j*2*pi*k/N)
The x(-1) sample leaves the array, the x(N-1) enters the array, but their
actual positions are determined on each iteration using circular buffer
pointer.
I hope this helps.
Regards,
Andrew
> Andrew Nesterov wrote:
>>> Subject: Zero Padding and Sliding DFT
>>> Posted by: "sandwich_20082001" j...@york.ac.uk sandwich_20082001
>>> Date: Sat Aug 16, 2008 7:23 am ((PDT))
>>>
>>> Hi,
>>>
>>> I was wondering if it is possible produce a sliding DFT, but also to
>>> keep the effects of a zero padded spectrum.
>>>
>>> For example, for a non zero padded signal the sliding DFT complex
>>> frequnecy spectrum is calculated as follows
>>>
>>> Xk(n) = [Xk(n-1)-x(n-N) + x(n)] *exp^(j2pik/N)
>>>
>>> which is the same as moving a window on by one sample and taking the
>>> FFT again.
>>>
>>> but when zero padding in the follwing way (numbers indicating whre
>>> information would be in the time domain):
>>>
>>> [signal 0-511][ zeros 512 -1023]
>>>
>>> the signal is only changing in the 0-511 samples, the number of zeros
>>> always stays constant. Is it therfore possible to produce a sliding
>>> DFT with zero padding?
>>>
>>> Any help really appreciated.
>>>
>>> J
>>
>> Hi J,
>>
>> Yes it is possible to slide the spectrum. It should be taken into
>> considerations that since the update formula references spectral data
>> from the previous iteration Xk(n-1), and the length of the spectrum
>> after padding initial signal data is N = L(signal) + L(padding),
>> the indices in the update expression run from 0 through N-1. Which
>> essentially means that no matter what was the initial length of
>> the signal N(signal) then after N-L(padding) updates the further updates
>> do not use padding.
>>
>> The above is very close to to starting with all zero spectrum and update it
>> using the above formula.
>>
>> It is also follows that the effect of padding the signal data with zeros
>> (that results in an interpolated spectrum) would fade away with the
>> updates.
>>
>> As I can see it, the main point is that the spectrum length is a sum of
>> the signal's length and padding length.
>>
>> Regards,
>>
>> Andrew
>
