DSPRelated.com
Forums

Downsampling from an FFT

Started by tomb18 7 years ago13 replieslatest reply 7 years ago3068 views

I would like to down sample a signal from it's original sampling rate of 2,000,000 samples per second to 48,000 (or 44100) starting from the output of an #FFT.  This FFT delivers 16384 data points (8192 real and 8192 imaginary).  The data comes from a software defined radio as I and Q data.

I cannot do this in the time domain as I do not have the tools in my app to do so.  So I need to start from the FFT, drop the necessary data, then perform an iFFT.  These tools I have.

What I need help with, is determining how many samples to drop and how to arrange the data afterwards to be delivered to an inverse FFT.

Can someone help out please?

Thanks


[ - ]
Reply by kazAugust 24, 2017

Since your signal is at FFT output then pass it to IFFT directly then decimate by direct discarding. To avoid aliasing discard (by zeroing), when at FFT output stage, any frequencies that would alias later at decimation as this is in effect a brick wall low pass filter. To achieve the fraction you want take 3 samples out of 125.

[ - ]
Reply by tomb18August 24, 2017

Hi,

This seems real simple!  Let's see if I got this straight.

1) I zero out frequencies above the frequencies of interest.

2) I perform the iFFT.

3) I keep 3 samples out of each 125.  This gives 48000 per second.

So, does it matter which 3 I keep? For example in the first 125 I could keep the first, the 40th, the 80th and then start over at 125?  I guess it doesn't matter.  Am I correct?

Thanks!

[ - ]
Reply by kazAugust 24, 2017

1) correct, zero both +/- frequencies

2) correct

3) correct

as to which 3? it does affect phase of signal(delay) but otherwise I will discard regularly as you described. Remember you are dealing with frames rather than continuous signal so I don't know what could happen at boundaries

but you can deal with that

[ - ]
Reply by tomb18August 24, 2017

Ok.  But where are the negative frequencies?

When I run the FFT I receive as output an array of 16384 values. The values from bin 0 to 8191 are the frequencies above the bins 8192 to 16383.

This is what you get when you feed the I and Q signals into the complex FFT.  So to plot them you take 8192(lowest frequency) plot to 16383, then plot 0 to 8192 for the upper frequencies.  So I guess I just zero the higher frequencies as needed, then send the result.  In this case all of the bins from 0 to 8191 and a good part of the 8192 to 16384 will be zero.

Am I correct?

Thanks!!

[ - ]
Reply by kazAugust 24, 2017

Your fft produces Re/Im (complex output) so the bins for your signal at baseband would e symmetrical around dc. you need to zero on either side of dc away from your signal. since your fft is not centred on dc then you need to keep bins from first sample to say sample (n) for the +side of your signal then zero up to (end-n) i.e. keep mirror image of +ve side. Then apply ifft then discard samples

[ - ]
Reply by kazAugust 24, 2017

note that your fft output is 8192 complex samples and not as 16384.

Each Re/Im pair represents one sample 

[ - ]
Reply by tomb18August 24, 2017

Ok.  You are right of course!  I was thinking of what the result was after further processing when converting the output for plotting.

Perfect!  Much thanks here. I will code this up over the next couple of days and post the results!

Much thanks to all who helped out here.

Thank you

[ - ]
Reply by Fred MarshallAugust 24, 2017

It's a bit easier to answer in concept than to get into all the intricacies of the steps to take.  So here is a quick answer:

You currently have FFT samples that are on a circular periodicity of 2,000,000 Hz. 

You have 8192 samples in time at this rate.

You want to have FFT samples that are on a circular periodicity of 48,000Hz.  I will use 50,kHz just to keep things rounded off and simple.

That's a sample rate reduction of 2,000,000/50,000 or 40 times.

It appears that without any frequency interpolation, the result will have around 200 samples.  8192/40 ~ 200.  If that's OK then good.  That's about 4msec worth of data.

Given this, it's reasonable to assume that the bandwidth of the data is less than 24kHz.

You have to make sure that this is a reasonable assumption OR you have to assure that it's met.  Generally this is done with a low pass filter - and, at that, often in stages so the filter being used doesn't have to be too "good" and, thus, too long re: unit sample response.

So, conceptually you could use the FFT of a half-band filter to decrease the bandwidth by 2 using multiplication in frequency.  Given that (theoretically) the bandwidth is approaching 1,000,000 Hz, the filter will get it down to 500,000 Hz and leave a more or less zero-valued space of 1,000,000 Hz centered on fs/2.  That's 500,000 plus 1,000,000 plus 500,000.  Then you remove 1,000,000 from the center leaving a sample rate of 1,000,000.  Then 500,000,.... etc. until you get down to 50,000.  You can use the same filter each time - properly scaled in frequency. 

A "trick" is this:  If you can be reasonably sure that the data bandwidth doesn't exceed 25kHz in the first place then you can just drop all the frequency samples above 25kHz and attach the ends from 25kHz and from 1,975kHz because zeroing zeros has no effect. What you'd really like is for the data to have a flat spot (like a double zero) at 25kHz and at 1,975kHz so there are no transients introduced by doing this.  It's quite a leap but it's worth trying as it's very efficient.  Then you can compute the IFFT of the result.

Whether this all works well has to do with how you combine the sequences thereafter.  And, I'm not suggesting either that your numbers make any real sense in your intended application.  Somehow I worry about that but haven't analyzed it.


[ - ]
Reply by tomb18August 24, 2017

Thanks.  

My understanding is that I can do the "trick".  This is where I am having issues.

First of all, there are 16384 samples since this is a complex FFT and I am using an IQ stream which is two channels.

The resulting FFT output puts the upper frequencies into the lower 0-8192 bins so to display the spectrum you need to plot 8192-16383 and then 0-8191.

Now if I want to drop samples the question is how do I deal with the fact that there will be 393.216 packets.  Do I take 392 or 394 and what do I do with the missing data?

Next assuming this is OK, I need to recreate the I (real) and Q(imaginary) signals. Do I just feed this into a complex inverse FFT?  What is real?  What is imaginary? Do I just zero out the imaginary?

At the very least this is something I should try I think.

Thanks

[ - ]
Reply by Fred MarshallAugust 24, 2017

Well, you can multiply the number of samples that I used by 2X as I was referring to complex or I/Q frequency samples.  I think it's fair to say this:

I and Q samples are both real values in time.  And, I assume they are coincident in time but this may not be the case for you.  Or, the way you're carrying them may introduce a delay on one vs. the other - so a linear phase component to deal with.

So, you would have two real sequences to FT. 
And, the results will each be complex in general.
Their IFTs will be real again if all is done properly.
But maybe you mean that you are using a complex FT and since the imaginary values are zero, you are filling those locations with real data as well?  That's a common practice but it makes things more complicated for you.

You may want to consider some identities to help think things through:

- The FT of a real, even function is real.

- The FT of an even function is even.

- The FT of a real, odd function is imaginary.  So, the FT of an imaginary, odd function is real.

- The FT of an odd function is odd.

The inverse is the same.

So, in the end, you will not want the input to the IFTs to have components that cause the IFT output be complex..... and so on.

Displaying the spectrum and dealing with where the outputs show up is only a matter of setting pointers (addresses).  Necessary but not so challenging.

As above, without using any tricks that may well be available (I don't know them), just assume that you have two sequences that result from your real I and real Q channels.  Now you have two complex sequences in frequency.
Treat them separately as if each were a single sequence.
Then IFT each sequence back to a real sequence.
DON'T zero out the imaginary any more than the real!
In frequency: what is real is real and, what is imaginary is imaginary.
In time: the results should be purely real but still I and Q channels.

I don't understand how there can possibly be fractional numbers of packets. But, yes, I understand that the ratio would suggest that.  It likely doesn't matter the exact number as long as there's consistency in the transformations.   You are effectively choosing the ending temporal sample rate (the total frequency span) in making this determination.  Does that matter in this application?







[ - ]
Reply by tomb18August 24, 2017

I am not that knowledgeable in DSP but trying to learn.

Perhaps knowing how my tools work will help. My iFFT tool will take an array of complex numbers.

For example, instead of using the 2MHz input, I can use a sound card connected to the IQ output of an SDR at 192kHz.  I can then convert the I and Q audio channels into a complex signal and feed it into my complex FFT(16384).  The output is 16384 frequencies. I can then feed this as is into my iFFT tool and the output is is a complex array which I can then split into two arrays composed of I and Q.  These then go to the output sound card at 192KHz and it works fine.  I recover my data.

So I want to do the same but instead starting from 2MHz and ending at 48kHz.

So starting from the FFT output, I can drop all frequencies greater than 48000 khz from these 16384 frequencies.  So the question is do I just drop these into the complex inverse FFT?  I would have thought that the lower half would go into the imaginary input and the positive half would go into the real input.   Or do I just treat all the remaining frequencies as complex and then  send them to the iFFT?

And yes, the output has to be 48kHz since it is fed to a sound card.

This is where I am confused.  Also how do I get exactly 48KHz?

Thanks, this is pretty new to me.



[ - ]
Reply by Fred MarshallAugust 24, 2017

What you want to do is reduce the sample rate.  This means that the FT domain has to repeat more frequently (view the output as a single period of a continuous, periodic set of samples).  You start with 2MHz period in frequency. You need to reduce to 50kHz in frequency.  The reciprocal of the span in one domain is the distance between samples in the other domain.  So 50kHz corresponds to

1) zero all the data in all the sequences from 25kHz to 1,975kHz. This may be OK to do and it may not be OK to do.  But it's surely what you WANT to do.

2) Now actually remove the samples that have been zeroed.  This effectively shifts what was 2MHz down to 50kHz and the new period is 50kHz and reduces the number of samples by 40.  Here, as is the typical case, I have zero frequency at the beginning and the sample rate as the highest frequency.  If it's not arranged that way then at least visualize it this way and treat it this way.  And now, what was at 1,975kHz is at 25kHz and the total frequency range is 50kHz - corresponding to the sample interval.

3) Now you have a sequence (or sequences) which you would put into the inverse transform.

You say: "I can then convert the I and Q audio channels into a complex signal"  I don't think that's correct.  I think what you mean is that you put the REAL I samples into the REAL addresses for the input to the FFT and you put the REAL Q samples into what would be the IMAGINARY addresses for the input to the FFT. This is only a trick and makes things complicated for you it seems.  So, just don't do it. Save the algorithmic tricks for later.  Better, put the REAL Q samples into the FFT and get the Q result.  Then put the REAL I samples into the FFT and get the I result.  Both will be complex.  Now treat each sequence separately as above so they are shorter.  Then IFFT each sequence separately to get your REAL I and REAL Q sequences out.  Then proceed as you might with REAL I and Q time samples thereafter.

If there are tricks that blend I and Q with REAL and Imaginary then save those for further work.  I believe this is good advice.  Others might chime in.



[ - ]
Reply by tomb18August 24, 2017

Great. That explains a lot! 

Now, the next question is interesting. 

Thanks, Tom