Nyquist and the Complex-Real FFT

I've heard that there is a way to essentially double the sampling rate of a
complex input signal into a real FFT by alternating the real and imaginary
signals in time (given that the I and Q are sampled independently)?  Does
this really work?  If it does, are there only certain conditions
(relationships between sample time and frequency) where it does? 

Thanks Much!

On Wed, 28 Nov 2007 10:20:58 -0600, vanlansl wrote:

> I've heard that there is a way to essentially double the sampling rate of a
> 
> complex input signal into a real FFT by alternating the real and imaginary
> 
> signals in time (given that the I and Q are sampled independently)?  Does
> 
> this really work?  If it does, are there only certain conditions
> 
> (relationships between sample time and frequency) where it does? 
> 
> Thanks Much!

You could, if I'm not mistaken, use a real FFT that way, then peel out
what would be the result of a complex FFT from the result.

But I suspect that you'd use up just as much or more computation time than
doing a complex FFT.

You should also be able to do a real FFT on the real part, then a real FFT
on the imaginary part, and combine the answers.  No, I'm not sure what's
the right way to do this off the top of my head, but if you start with the
properties of the Fourier transform you can figure it out.

-- 
Tim Wescott
Control systems and communications consulting
http://www.wescottdesign.com

Need to learn how to apply control theory in your embedded system?
"Applied Control Theory for Embedded Systems" by Tim Wescott
Elsevier/Newnes, http://www.wescottdesign.com/actfes/actfes.html

On Nov 28, 12:55 pm, Tim Wescott <t...@seemywebsite.com> wrote:
> On Wed, 28 Nov 2007 10:20:58 -0600, vanlansl wrote:
> > I've heard that there is a way to essentially double the sampling rate of a
>
> > complex input signal into a real FFT by alternating the real and imaginary
>
> > signals in time (given that the I and Q are sampled independently)?  Does
>
> > this really work?  If it does, are there only certain conditions
>
> > (relationships between sample time and frequency) where it does?
>
> > Thanks Much!
>
> You could, if I'm not mistaken, use a real FFT that way, then peel out
> what would be the result of a complex FFT from the result.
>
> But I suspect that you'd use up just as much or more computation time than
> doing a complex FFT.

there *are* real to complex FFTs that take N *real* samples going in
and return N/2 complex values (where the Hermitian symmetry is
implied) and i thought they were meant to be more efficient than an N
point complex FFT where you started with all of the imaginary parts
zeroed and ended up with that conjugate symmetry explicit (thus a
little redundancy).  for the first case, since the DC and Nyquist
components *have* to be purely real, what they usually do is put the
real part of the Nyquist component in the imaginary part of X[0]
(which would otherwise be known to be zero) so they can pack all of
the information into N/2 complex values.

>
> You should also be able to do a real FFT on the real part, then a real FFT
> on the imaginary part, and combine the answers.  No, I'm not sure what's
> the right way to do this off the top of my head,

i've gone through it once here on comp.dsp.  it was laborious and long
ago.

imagine a regular old N/2 point complex-in, complex-out DFT.  define
the input signal such that the real parts of the input are the even
samples of an N point real sequence and that the imaginary parts are
the odd samples of the N point real sequence and "go to town" with
it.  then see what you have to do to untangle the results you want
from it.  have fun.

r b-j

"vanlansl" <svan2@excite.com> writes:

> I've heard that there is a way to essentially double the sampling rate of a
> complex input signal [...]

So you'd like to interpolate a complex signal by two?

I'm sorry - I'm not sure what your question is, and I'm not sure Tim's or
Robert's answer addresses it.
-- 
%  Randy Yates                  % "How's life on earth? 
%% Fuquay-Varina, NC            %  ... What is it worth?" 
%%% 919-577-9882                % 'Mission (A World Record)', 
%%%% <yates@ieee.org>           % *A New World Record*, ELO
http://www.digitalsignallabs.com

On Nov 28, 2:28 pm, Randy Yates <ya...@ieee.org> wrote:
> "vanlansl" <sv...@excite.com> writes:
> > I've heard that there is a way to essentially double the sampling rate of a
> > complex input signal [...]
>
> So you'd like to interpolate a complex signal by two?
>
> I'm sorry - I'm not sure what your question is, and I'm not sure Tim's or
> Robert's answer addresses it.
> --
> %  Randy Yates                  % "How's life on earth?
> %% Fuquay-Varina, NC            %  ... What is it worth?"
> %%% 919-577-9882                % 'Mission (A World Record)',
> %%%% <ya...@ieee.org>           % *A New World Record*, ELOhttp://www.digitalsignallabs.com

I've seen this more often the other way, from real to half frequency
complex by making even samples real, odd samples imaginary. Adjacent
input samples become a complex sample and alternate complex samples
are multiplied by -1.

This is based on complex demodulation by one forth the sample
frequency where the cosine terms are 1 0 -1 0... and the sine terms
are 0 1 0 -1... and the adjacent samples are summed as a crude
desampling filter. The signal should be prefiltered to a bandpass that
is much narrower than the Nyquist limit.

Try this process in reverse.

Dale B. Dalrymple
http://dbdimages.com
http://stores.lulu.com/dbd

On Nov 28, 10:50 pm, dbd <d...@ieee.org> wrote:
...
>  The signal should be prefiltered to a bandpass that
> is much narrower than the Nyquist limit.

hmmmm.  the thing i was thinking about was "merely" using an N/2
complex-in, complex-out DFT to perform an N-point DFT with real input
and where the output only contains half of the conjugate symmetric
output that you would get with a regular N-point DFT.  now, to do the
"untangling", you would need an addition N/4 twiddle factors that the
N/2 point complex DFT did not use (but a regular N-point *does* use),
but there was no restriction of the bandwidth or frequency content of
the input data.  the only restriction was that the imaginary part of
each sample is assumed zero (and not granted any space).

r b-j

vanlansl wrote:
> I've heard that there is a way to essentially double the sampling rate of a
> complex input signal into a real FFT by alternating the real and imaginary
> signals in time (given that the I and Q are sampled independently)?  Does
> this really work?  If it does, are there only certain conditions
> (relationships between sample time and frequency) where it does? 
> 
> Thanks Much!
> 
> 


Sure. The only tool you need to understand this trick is linear 
superposition.

i.e.

f + K*g     <==>    F + K*G
^^^^                ^^^^^
time domain         frequency domain



Split the complex vector into the real part and the imaginary part
( in the above nomenclature: f==real part, g=image part, K=j )

so FFT(real + j*imag) == FFT(real) + j*FFT(imag)



One caveat:  most real FFTs return only the half-spectrum, since the 
other half is conjugate symmetric.  You'll need both halves.


-- Mark