Contraining the FFT bins used to represent a signal.

Is it possible to constrain the frequencies that are used to represent a
sampled time domain signal? For example, is it possible to constrain a
signal to be represented by only odd-numbered or even-numbered frequency
bins? 

Presumably the error will be larger but is it even possible to accomplish?
My gut feeling says yes because if we take an example of a 2K point FFT it
certainly seems possible that we should be able to represent the function
with the 1K even or odd bins that are available. Can�t seem to get there
with the math though� or find an algorithm.

As an example of what doesn't work (and I didn't expect it to), is to do
an FFT of an audio signal, pick only the odd (or even) bins and then do an
IFFT. The end result sounds like the person is in a barrel. 

Any ideas?

Thx.

edie wrote:
> Is it possible to constrain the frequencies that are used to represent a
> sampled time domain signal? For example, is it possible to constrain a
> signal to be represented by only odd-numbered or even-numbered frequency
> bins?
>
> Presumably the error will be larger but is it even possible to accomplish?
> My gut feeling says yes because if we take an example of a 2K point FFT it
> certainly seems possible that we should be able to represent the function
> with the 1K even or odd bins that are available. Can't seem to get there
> with the math though... or find an algorithm.
>
> As an example of what doesn't work (and I didn't expect it to), is to do
> an FFT of an audio signal, pick only the odd (or even) bins and then do an
> IFFT. The end result sounds like the person is in a barrel.

One property of a DFT/FFT is that the bins are orthogonal.
That means that if a portion of your signal is in any bin,
that portion will not appear in any other bin.  So if you
remove that bin, you remove the portion of the signal that
was in that bin.  This could be your entire signal, if it
just happened to be completely within the bin you deleted.
So even the removal of one bin, much worse every even or odd
bin, could render your signal unrepresented.

Now you could use a window or non-linear process to spread
portions of your signal into adjacent bins before the DFT,
so that no sinusoid would be lost by throwing away a single
bin, but this would still be only partially representative
of the altered "spread" signal, not necessarily the original
signal.


IMHO. YMMV.
-- 
rhn A.T nicholson d.0.t C-o-M

edie wrote:
> Is it possible to constrain the frequencies that are used to represent a
> sampled time domain signal? For example, is it possible to constrain a
> signal to be represented by only odd-numbered or even-numbered frequency
> bins? 
> 
> Presumably the error will be larger but is it even possible to accomplish?
> My gut feeling says yes because if we take an example of a 2K point FFT it
> certainly seems possible that we should be able to represent the function
> with the 1K even or odd bins that are available. Can�t seem to get there
> with the math though� or find an algorithm.
> 
> As an example of what doesn't work (and I didn't expect it to), is to do
> an FFT of an audio signal, pick only the odd (or even) bins and then do an
> IFFT. The end result sounds like the person is in a barrel. 

You can construct signals that consist only of odd harmonics of some 
fundamental, and others that contain only even harmonics. Those, and 
only those, can be represented by only odd or even bins. A square wave 
is an example of the first kind.

Jerry
-- 
        "The rights of the best of men are secured only as the
        rights of the vilest and most abhorrent are protected."
            - Chief Justice Charles Evans Hughes, 1927
���������������������������������������������������������������������

What about oversampling then decimating (taking the odd or even
samples) ?

On Nov 6, 12:11 pm, "edie" <j...@etymonic.com> wrote:
> Is it possible to constrain the frequencies that are used to represent a
> sampled time domain signal? For example, is it possible to constrain a
> signal to be represented by only odd-numbered or even-numbered frequency
> bins?
>
> Presumably the error will be larger but is it even possible to accomplish?
> My gut feeling says yes because if we take an example of a 2K point FFT it
> certainly seems possible that we should be able to represent the function
> with the 1K even or odd bins that are available. Can't seem to get there
> with the math though... or find an algorithm.
>
> As an example of what doesn't work (and I didn't expect it to), is to do
> an FFT of an audio signal, pick only the odd (or even) bins and then do an
> IFFT. The end result sounds like the person is in a barrel.
> 
> Any ideas?
> 
> Thx.

dp wrote:
> What about oversampling then decimating (taking the odd or even
> samples) ?

I don't think that first doubling the number of bins and taking half of 
those is what edie had in mind, but that would work.

Jerry
-- 
        "The rights of the best of men are secured only as the
        rights of the vilest and most abhorrent are protected."
            - Chief Justice Charles Evans Hughes, 1927
���������������������������������������������������������������������

"Jerry Avins" <jya@ieee.org> wrote in message 
news:arqdnY9mELWxYtLYnZ2dnUVZ_oGdnZ2d@rcn.net...
> dp wrote:
>> What about oversampling then decimating (taking the odd or even
>> samples) ?
>
> I don't think that first doubling the number of bins and taking half of 
> those is what edie had in mind, but that would work.
>
> Jerry
> -- 

The OP's objective is no different than the objective of time-domain 
decimation (sample rate reduction) except the domains are switched.  The 
rules (switched around in domains) are the same.  Use a "half band" or "half 
time" filter in frequency.

So, yes, some information is lost unless the real temporal epoch is actually 
shorter than implied by the original FFT.

If the f=0 sample has to remain then the even frequency samples are 
retained.  Then the fundamental in time is doubled in frequency - meaning 
that the resulting temporal sequence repeats one time.

If the f=0 sample isn't retained then the resulting temporal sequence is 
zero mean - and is an odd function of time.

So, the first one is really shorter by a factor of 2 and the second one is 
still the same length as originally but is antisymmetric - thus redundant in 
that sense.

Fred 

I have tried several different oversampling/decimating schemes in order to
generate a bin spacing in the frequency domain that is double the original
and then translating those bins to the correct location in the original
domain. When I do the IFFT I get the "barrel effect" plus some clicks and
pops. 

I think that the fundamental problem is that when using this scheme half
the original time domain information is getting thrown away and replaced
with an approximation via the IFFT. It's kind of interesting that the
signal (which is speech) is still quite understandable but it sounds
echo-y plus the clicks and pops are causing leakage into the empty bins
and I need to keep those clean to use for another signal. 

So... back to the original question. Is there some way to keep the time
domain block intact but constrain the Fourier approximation to only use
even or odd bins? I understand all the normal arguments about requiring
harmonics of a fundamental to approximate a signal. What I'm asking here
is why we can't approximate the same signal by using harmonics of double
the fundamental (for the case where we use only even bins). When you think
about it there are many harmonics (both odd and even) available of double
the fundamental so why can't force the FT to use only those?

I feel like I'm trying to sneak one past Mr. Fourier but at the same time
I can't come up with a fundamental reason why this shouldn't work. 

Thx.




>What about oversampling then decimating (taking the odd or even
>samples) ?
>
>On Nov 6, 12:11 pm, "edie" <j...@etymonic.com> wrote:
>> Is it possible to constrain the frequencies that are used to represent
a
>> sampled time domain signal? For example, is it possible to constrain a
>> signal to be represented by only odd-numbered or even-numbered
frequency
>> bins?
>>
>> Presumably the error will be larger but is it even possible to
accomplish?
>> My gut feeling says yes because if we take an example of a 2K point FFT
it
>> certainly seems possible that we should be able to represent the
function
>> with the 1K even or odd bins that are available. Can't seem to get
there
>> with the math though... or find an algorithm.
>>
>> As an example of what doesn't work (and I didn't expect it to), is to
do
>> an FFT of an audio signal, pick only the odd (or even) bins and then do
an
>> IFFT. The end result sounds like the person is in a barrel.
>> 
>> Any ideas?
>> 
>> Thx.
>
>

edie wrote:

> I have tried several different oversampling/decimating schemes in order to
> generate a bin spacing in the frequency domain that is double the original
> and then translating those bins to the correct location in the original
> domain. When I do the IFFT I get the "barrel effect" plus some clicks and
> pops.

Probably an implementation issue. Do you use overalp-add / save?


> I think that the fundamental problem is that when using this scheme half
> the original time domain information is getting thrown away and replaced
> with an approximation via the IFFT. It's kind of interesting that the
> signal (which is speech) is still quite understandable but it sounds
> echo-y plus the clicks and pops are causing leakage into the empty bins
> and I need to keep those clean to use for another signal.

If x[n] is a vector, one can show that X[k] = DFT[ x[n] ] has only odd
harmonics (ie. X[k] = 0 for k even) iff the x[n] satisfies

x[n + N/2] = - x[n]

and similarly X[k] has only even harmonics iff

x[n + N/2] = x[n],

for n = 0, 1, ... N/2 - 1.

So if you want to add two signals x1 and x2, such that x1 only occupies
the odd bins and x2 only occupies the even bins of X = DFT[ x1 + x2 ],
then just make sure that x1 and x2 satisfy the above two relations.

Regards,
Andor

edie wrote:
> So... back to the original question. Is there some way to keep the time
> domain block intact but constrain the Fourier approximation to only use
> even or odd bins?

Certainly.  Just throw away the odd or even bins.  But note
that this will completely represent the input only for certain
constrained types of input signals.  Others, it will distort.

> I understand all the normal arguments about requiring
> harmonics of a fundamental to approximate a signal. What I'm asking here
> is why we can't approximate the same signal by using harmonics of double
> the fundamental (for the case where we use only even bins).

Because your new vector basis is not complete.  An infinite
number of even signals cannot represent an odd signal.
Think of  an FFT/DFT as a vector transform, where the sinusoids
completely span the vector space.  If your new basis does
not span the space, then information will be lost after a
transform pair.


IMHO. YMMV.
-- 
rhn A.T nicholson d.0.t C-o-M

Did you read my response to Jerry Avins.

It may be somewhat cryptic but it says it all ....

Just details of implementation needed.

Fred