• 0
donwazonesko

FFT / iFFT / RS - Basys3

Question

Hello, 

A while ago i've managed to receive data from XADC using my board Basys3 and now i need to use FFT, iFFT and proceed the output from these to via RS to my computer. Could you please show me examples of FFT / iFFT and RS connection? I've been trying to find something online, but there is nothing as simple as that.

 

Best Regards,

Michael

Share this post


Link to post
Share on other sites

25 answers to this question

Recommended Posts

  • 0

Hi,

if you aren't required to do it on the FPGA, you'll save yourselves a lot of implementation and debugging effort if you do the FFT offline.

An Octave script for the job can be found here. It's basically this

        b = b .* blackmanharris(numel(b));
        
        % calculate spectrum
        mag = abs(fft(b.')) .^ 2;
        
        f_Hz = fd_freqbase(numel(mag)) * rAdc_Hz;    
        
        % === keep only positive frequencies ===
        mask = (f_Hz >= 0) & (f_Hz < rAdc_Hz / 2);
        mag = mag(mask);
        f_Hz = f_Hz(mask);

        % === convert to dB ===
        mag = 10*log10(mag/max(mag)+eps);
		h = plot(f_Hz/1e3, mag); %set(h, 'lineWidth', 2);
        xlabel('f/kHz'); ylabel('dB');

  with those two functions

function fb = fd_freqbase(n)
    fb = 0:(n - 1);
    fb = fb + floor(n / 2);
    fb = mod(fb, n);
    fb = fb - floor(n / 2);
    
    fb = fb / n; % now [0..0.5[, [-0.5..0[
end

function win = blackmanharris(n)
    a0 = 0.35875;
    a1 = 0.48829;
    a2 = 0.14128;
    a3 = 0.01168;
    N = n-1;
    n = [0:N]';
    win = a0 - a1.*cos(2.*pi.*n./N) + a2.*cos(4.*pi.*n./N) - a3.*cos(6.*pi.*n./N);
end

There's many ways to skin a cat... this one has regulatory approval 🙂

This is just about postprocessing. You still need to transfer the data e.g. via a UART. I'd recommend 16 bit binary format. ASCII or hex will be very slow in comparison.

Share this post


Link to post
Share on other sites
  • 0

Unfortunately i need to use FFT inside of an FPGA. I need to save data received from 2 XADC ports - use FFT on one and iFFT on the second one and multiply each other. Then proceed the data via RS to PC.

Share this post


Link to post
Share on other sites
  • 0

Maybe your description of the algorithm is incomplete, but intuitively this does not sound like it would produce any "meaningful" results (e.g. usually IFFT is applied to a complex-valued signal).

Share this post


Link to post
Share on other sites
  • 0

@xc6lx45

about signal processing - if you multiply fft of one signal and multiply it with inversed fft of second one - the answer is the peak from xcor. In my case its the location of microphones. I need to implement FFT / iFFT - multiply both and proceed the output data with RS to my PC. 

Share this post


Link to post
Share on other sites
  • 0

@donwazonesko,

Hopefully you know to do more than just multiply the FFT of one channel by the iFFT of another.  There's a touch more to it, mostly to avoid circular convolution.

I'm not sure what you mean by an "RS" connection, so I'll ignore that and offer an window+FFT example for you instead.  (Includes dB mapping as well, although I'm tempted to create an option to do linear mapping.)  This follows from @xc6lx45's outline above as well, although I use a Hann window rather than a Blackman window.  (Neither are my preferred window.)

The design is currently a simulation only design that draws a scrolling raster a simulated VGA screen (i.e. GTK window on your desktop).  It's simulation only primarily because few FPGAs have the block RAM necessary to do the frame buffer that this one requires.  My plan is to adjust the demo to handle DDR3 SDRAM + HDMI in the future.  Indeed, the simulation of that is complete--I just need to prove that it works on the hardware now.

Dan

Share this post


Link to post
Share on other sites
  • 0

 

1 hour ago, donwazonesko said:

@xc6lx45

about signal processing - if you multiply fft of one signal and multiply it with inversed fft of second one - the answer is the peak from xcor. In my case its the location of microphones. I need to implement FFT / iFFT - multiply both and proceed the output data with RS to my PC. 

OK that starts to make more sense. So one channel is reference signal e.g. transmitted signal, one channel the received reflection.

Capture both, FFT, multiply (don't forget the conjugate), iFFT. On the bright side, in this specific case you can solve the circularity issues mentioned above with sufficient zero padding on the transmit signal (rule of thumb: Add enough zeros until all reflections have died down to negligible level). This may be easier said than done with a hardware FFT, though...

Resolution is limited to the sample rate. If you want to do better, you can interpolate by stealing lines 315..345 here . Needless to say, this calculation needs to be done on a microcontroller or the like. In double precision it's usually accurate to 1 % of a sample.

For a reference algorithm, have a look here (this is more complex and somewhat heuristic but has proven itself over the years). With noise-free data this can be accurate to about one nanosample.

Share this post


Link to post
Share on other sites
  • 0

dear @jpeyron
May i ask about 5 things connected to fft and to signal processing?

    - "Number of Channels" - what is it used for? I've gone through "FFT v9.0" from xilinx but the only information 
about that is that can be selected is from 1 to 12.
    - "Transform Length" - is it the lenght of the input data to FFT core? is there any rule like sampling rate must be 2x max. freq.? 
    - "Target Clock Frequency" - Can i go for 450MHz if my board (basys3) has Internal clock speeds exceeding 450MHz? What are the limits. It's good to know (i think) that The Basys3 board includes a single 100MHz oscillator connected to pin W5
    - "Target Data Throughput" - How to know what Throughput should be set? 
  

 

Edit: To create ifft using vivado you've got to change the sign of imaginary part and then proceed with fft. 

Edited by donwazonesko

Share this post


Link to post
Share on other sites
  • 0
1 hour ago, donwazonesko said:

Edit: To create ifft using vivado you've got to change the sign of imaginary part and then proceed with fft.  

I suspect your "ifft" is in reality a conjugated fft

Mathematical background (behind this theory and conventional fft-based crosscorrelation):

In an FFT-less world, you'd use a so-called "matched filter" as optimal detector that convolves with a time-reversed replica of the known signal (see first line here. Never mind "conjugated" since you have real-valued data).
FFT does the convolution. Conjugation in the frequency domain is equivalent to time reversal in the time domain.

Edited by xc6lx45
Wikipedia reference

Share this post


Link to post
Share on other sites
  • 0

@donwazonesko

4 hours ago, donwazonesko said:

May i ask about 5 things connected to fft and to signal processing?

    - "Number of Channels" - what is it used for? I've gone through "FFT v9.0" from xilinx but the only information 
about that is that can be selected is from 1 to 12.
    - "Transform Length" - is it the lenght of the input data to FFT core? is there any rule like sampling rate must be 2x max. freq.? 
    - "Target Clock Frequency" - Can i go for 450MHz if my board (basys3) has Internal clock speeds exceeding 450MHz? What are the limits. It's good to know (i think) that The Basys3 board includes a single 100MHz oscillator connected to pin W5
    - "Target Data Throughput" - How to know what Throughput should be set?

  1. If you are collecting from multiple audio sources , it would make sense to make each source a separate "channel" within the FFT. While this isn't strictly required, the "cost" of the FFT in terms of logic usage may go down if you do this.
  2. Yes, the transform length should be the size of the FFT
  3. If you are processing audio, I doubt you will need 450MHz.  100MHz will be a comfortable speed to achieve.  If you elect for higher speeds, you may find that you need to spend more time finding and fixing timing problems within your design.  For example, I'm not sure just how fast Xilinx's FFT can or will run.  I've only personally created logic that will run at 100MHz (or below) and up to 200MHz.  Getting the 200MHz logic to work was annoying, since I had to retool a lot of my 100MHz logic to do it.
  4. I'm not familiar with the target data throughput parameter.  I would imagine that would just be the number of channels times the data rate of your incoming signal.

As for the RS232  (UART) piece of this problem, I've done that before.  I use what I call a UART to WB bridge, which gives me control access to things going on within the FPGA as well as an ability to stream data in or out using the UART.  It's not terribly efficient or high speed, but it works and it is easy to attach other peripherals to that can be controlled.  This was how I went about testing my own FFT applications.  A more common approach here on Digilent's site/forum is to instead use a microblaze processor with an AXI interconnect to access your FFT results and your serial port.   I haven't tried this second approach myself, but you'll find many others on this forum have.

Dan

Share this post


Link to post
Share on other sites
  • 0

@D@n

Is it better to create 8x fft or 1 fft with 8 channels? 

Also to create inverted FFT (like @xc6lx45 said - conjugated  fft) - you've got to invert the imaginary part of the output. How do i invert imaginary part of the (fft) output vector and leave the rest ?

Edited by donwazonesko

Share this post


Link to post
Share on other sites
  • 0

@donwazonesko,

44 minutes ago, donwazonesko said:

Is it better to create 8x fft or 1 fft with 8 channels?

I'm not sure.  It might be.  I know that you can often do two real FFT's at once for the cost of one complex FFT, but I'm not sure about how Xilinx's implementation handles this.  My own implementation ... doesn't get that far.

44 minutes ago, donwazonesko said:

Also to create inverted FFT (like @xc6lx45 said - conjugated  fft) - you've got to invert the imaginary part of the output. How do i invert imaginary part of the (fft) output vector and leave the rest ?

Let's work through this.  An FFT is SUM x[n] e^{-j 2pi kn/N}, right?  The inverse FFT is SUM X[k]e^{j2pi kn/N}.  That means that if we give the fft x^ by conjugating the input values, we should get the conjugation of the entire FFT: [SUM X^{*}[k] e^{-j2pi kn/N}] = SUM x[n] e^{j2pi kn/N}.  So if you conjugate both inputs and outputs, you should get the inverse FFT.  If you just conjugate the outputs, you should get an FFT appropriate for use in a correlation as discussed above.

By "invert the imaginary part" I think he means to conjugate the input and thus negate the imaginary part of it.

Dan

Share this post


Link to post
Share on other sites
  • 0

@D@n

That's correct. But since the data comming out of XADC is std_logic_vector(15 downto 0), how do i seperate img part from bits? You are able to seperate the imaginary parts after FFT not before, and still the question is how to implement it into VHDL.

Michael

Share this post


Link to post
Share on other sites
  • 0

@donwazonesko,

Conjugating a real value with no imaginary component is a no-op.  I think this also answers how to implement it within VHDL.  (i.e. leave it as is, and just call it conjugated)

Dan

Share this post


Link to post
Share on other sites
  • 0

Dear @jpeyron

Could you please tell me if you attached capacitor C33 -  C36 to your board (while working on  Nexys 4 DDR Spectral Sources Demo? If yes,  what capacity have you used? 

 

I need to lower the noice..  

Edited by donwazonesko

Share this post


Link to post
Share on other sites
  • 0

Hi @donwazonesko,

I did not create the Nexys 4 DDR Spectral Sources Demo. I have used it and did not need to add additional noise filtering circuit to the project.  Beyond the FFT's noise reducing quality you can add an additional  filter like the one you pointed to in this forum here without concern as long as you wire it correctly..

cheers,

Jon

Share this post


Link to post
Share on other sites
  • 0

@gummadi Teja,

What you are asking for is not the common approach to building FFTs, therefore let me take this moment to invite you to build an FFT that uses the CORDIC algorithm without any multiplies.

Let me also share with you what I think you will discover.  While CORDIC algorithms do not use multiplies, they aren't necessarily logic efficient by any stretch of the imagination.  Worse, CORDICs apply a gain to the incoming signal.  Before you think this gain might be easily factored out since it applies to all incoming samples, let me remind you that there are two paths through each butterfly--one that would get the gain and one that would not. That brings you back to needing a multiply again.

The FFT algorithm I linked to above does have an option that doesn't require hard multiplies (DSPs).  Be aware, though, if you use this option the generator will build your multiplies from shifts and adds and this will cost you a lot of logic resources.  Yes, I am aware of an alternative multiplication algorithm that I've come across that is very light on logic resources, but it also requires a delay equal to the number of bits in the multiply.  That would slow the FFT processing down to (roughly) one sample every 54 clocks or so.  Yes, the algorithm is similar to a shift-add multiplication algorithm, although about 2x less the area.  While I've thought of integrating this into my own FFT design, no one has been paying for this upgrade so ... it may take a long while before I get to it.

All that said, there's a saying in English that "Beggar's can't be choosers."  If you really want a specific type of FFT implementation, you might be stuck with needing to build it yourself.

Perhaps if you share more about why you are so interested in such an algorithm, and what engineering problem you are trying to solve, it might be easier to actually recommend a solution to your design problem.  So far, you've been asking for an implementation, when I think what you need is a solution.  The two are very different.

Dan

Share this post


Link to post
Share on other sites
  • 0

thank you sir, iam already complete my code for fft but i have one error is there...that is in last butterfly it could not give the correct solution.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now