# [Newbie] 64-point complex FFT with 32 bit floating-point representation

• posted

Hi all.

I'm currently trying to understand whether or not it is possible to implement a 802.11a-compliant OFDM modulator/demodulator on an FPGA. As far as I understand, the critical part of the project is the

64-point complex FFT with 32 bit floating-point representation (each real or complex number is represented in 32-bit floating-point). The FFT block should perform this calculation in no more than 2.5 us. I'm not an expert in this field, can anyone help me to understand whether or not this performance is achievable with the FPGAs currently available on the market? If yes: can you address me to some specific FPGA model? If not: what is the critical part of my specifications? (I suppose the time delay and the floating point spec).

This is only one of my current doubts. I hope we can start a profitable discussion. :-)

Ciao, Franco

• posted

Yes it is possible, you need to choose an FPGA large enough.

The FFT is relatively easy, using fixed-point arithmetic. No reason to use floating point. Other parts of the system are more challenging.

Easily achievable without requiring a high clock rate.

The first thing you need to do is come up with an outline design for the complete implementation, not just the FFT. Then estimate the size of each block, and the total size of the design. Do this before you select the FPGA, and work out what clock rate is required and how much memory you need.

You can break each part of the design into small blocks and learn as you go. Start with the FFT if you want, but it will not be the most difficult part. There are many papers on different FFT architectures, google for 'r2sdf fft' for examples.

• posted

dal ha scritto:

Wonderful!

Can you explain this to me? This is a critical point! I had a look at a master thesis of a guy here at the university... He wrote that a floating point representation is required (but he didn't write why). It would be much easier to operate with fixed-point numbers, but I should understand why...

Do you mean the Viterbi decoder?

I think you mean with fixed-point numbers...

Thank you for your suggestions! The problem is that my boss told me: "Ok, we want to have an FPGA implementation of an 802.11a modem. Before starting with VHDL, we need to understand which are the critical blocks and find an appropriate FPGA for our project. You have 1 week for this task." We will have a meeting during the next days, I will explain him the approach you suggested me.

Ciao, Franco.

• posted

"Franco Tiratore" ha scritto nel messaggio news: snipped-for-privacy@j73g2000cwa.googlegroups.com...

We have developed an 802.11b baseband and MAC in an FPGA, and we are trying to implement an 802.11g/a baseband processor as well. The FFT module is one of the most simplest part of the design and can be accomodated even in a small size FPGA. But you have to implement it using fixed point! Floating point will be an overkill... Other parts are far more challenging to implement then the simple FFT module, and much more resources-consuming!

If you want, you can drop me an email (for replying remov the "h" from the address :-) )

Regards, Antonio

• posted

A floating point FFT is likely to produce more accurate results than a fixed point FFT. That said you can make a fixed point FFT as accurate as you wish.

For 802.11a, which I believe uses a maximum of 64QAM, I find it hard to believe that floating point is necessary. Basically a less accurate fft will add a little extra noise to your system. If it's small enough its not worth worrying about.

Viterbi is not such a hard thing to implement but it can be tricky to get it performing properly.

There's also the QAM/BPSK/QPSK modulator/demodulator and data formatting for the MAC.

The real magic in these modems, however, is the front end processing required to equalize the channel. Issues such as AGC, alignment and equalization are a real swine to get right and have a huge bearing on the quality of results (at least thats my take from implementing a couple of wireline modem standards).

• posted

Ok, you are the second person telling me to use a fixed-point representation, then it must be the way it has to be done... :o) Let's consider the problem from scratch. Let's suppose that I want to implement a 64-QAM symbol mapper. This means that every 6 input bits the mapper has to output the correspondent symbol, that consist af a real and an imaginary part. The problem is to choose the representation of each of these numbers. We know that each number can be one of the following: -7, -5, -3, -1, 1,

3, 5, 7. The 802.11a standard says that we must consider a correction factor of 1/sqrt(42) that is approximately 0.154. Then we have to multiply all the above mentioned numbers for this factor. Then, we are not dealing with integer numbers! After this, to make it simple, we have to apply the 64-point fft to 64 complex numbers (made up of two real numbers of the type described above). The problem is now to understand how to represent these numbers. I had a look at a master thesis (not so good thesis, I must say). It considers all these numbers represented in 32 floating-point format. That means, for example in the 64-QAM mapper, we have a ROM that outputs the correspondent 32 floating point symbols (32+32 for real and imaginary part) according to the 6 input bits. With a floating-point representation the ROM outputs exactly the calculated values. If I want to use a fixed-point representation, how should I convert the non-integer numbers to fixed-point numbers? And furthermore, what about the output of the IFFT block, how should I interpret the fixed-point output numbers?

It's clear that I have few ideas but well-confused... :o) But that's why I started this post.... :o)))

Can you go more in detail? I think the Viterbi decoder is another critical part.

I WANT, I WANT! :o))))))) But probably other people are interested and can contribute on the newsgroup...

Ciao, Franco

• posted

Hi Andy!

Andy Ray ha scritto:

Perfect. Then it's only a matter of studying the FFT theory. The important thing is to understand that this block is not so critical as it appeared. And of course, if you can suggest some documentation it would be really useful.

This is a really interesting point. Can you suggest some text/documentation in order to understand a systematic way to evaluate the noise due to the fixed-point representation? Of course this noise must be somehow affected by the number of bits we dedicate to the foxed-point representation. I think an in-depth theory must be available in some book...

And another critical point... Even the DAC (after the ofdm modulator, before the RF part of the transmitter) introduces noise, due to the number of bits of its resolution. How can we quantify its effects? Also here, this problem must have been already studied.

I think we will consider these problems at a later stage. As you have probably understood, we are really at the beginning of this work and for the moment we are mostly acquiring information. The complete project (a 802.11a transceiver) will take several months (several years?). Unfortunately the people involved in my group lack of the necessary expertise (but we are of course working to build it up).

Ciao, Franco

• posted

Pretty much any of the current FPGA offerings are capable of 64 point FFTs in 2.5 us. For OFDM, there really isn't any need to use floating point. Floating point trades accuracy for dynamic range. In the case of OFDM, you have 64 point FFT, so at most you'll have a growth of 6 bits in your data. Presumably, the data is coming from a DAC through some filters, so the dynamic range of the data coming into the FFT is also not that large. A single precision floating point FFt is going to have a 24 bit data path plus an 8 bit exponent. A 24 bit fixed point data path with no exponents is more than enough for this application.

There are FFT cores in the cores offered by the major FPGA vendors. These are not bad considering the price (free). You can obtain considerably higher performance and smaller size from third party IP providers, but it is not free.

In any event, you need to look at the entire OFDM receiver, as the FFT is only one block of it, and can be readily found off-the-shelf.

• posted

Hi, Ray. Thanks for your suggestions. What do you mean with the following two phrases?

and

Ciao, Franco

• posted

Floating point is a numeric representation to fit a larger dynamic range into a fixed number of bits. 32 bits can represent 2^32 unique values regardless of the format. For fixed point representation, those 2^32 values are equally spaced between 0 and 2^32-1 for unsigned. Floating point reserves some of the bits to indicate a scale factor to extend the range of values that can be represented, but that comes at the price of minimum resolution that varies depending on the scale. IEEE single precision floating point gives you 24 bits of accuracy (instead of 32), but that is scaled so that the msb of the 24 bit field is always significant.

The FFT conserves energy, it can be looked at as redistributing the input signal in time. If you have a full scale input that is at a single frequency that has a period that is an integer sub-multiple of the FFT size, all the energy from that signal will fall into a single FFT bin. For an N point FFT, the output at that bin will be N times the input signal amplitude. Since the input is at full scale already, there is nothing you can do to the signal to increase the output at that bin more than N* the full scale input. Adding any other frequency content will move some of that energy to another FFT bin, diminishing the spectral content in that bin. What I am saying, is the maximum output value from an N point FFT is N times the maximum input value. For a 64 point FFT, the maximum output is no more than 64 times the maximum input. For a fixed point representation, that would require the output to have at most six more bits than the input to represent all possible outputs without either overflowing or truncating the lsbs.

• posted

Ray Andraka ha scritto:

[cut]

More than clear! Anyway, after my question I started to write down some formulas and I found exactly what you have just explained me. :o)

Ciao, Franco

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.