Editing Orthogonal frequency-division multiplexing (section)

===Implementation using the FFT algorithm===
The orthogonality allows for efficient modulator and demodulator implementation using the [[fast Fourier transform|FFT]] algorithm on the receiver side, and inverse FFT on the sender side. Although the principles and some of the benefits have been known since the 1960s, OFDM is popular for wideband communications today by way of low-cost [[digital signal processing]] components that can efficiently calculate the FFT.

The time to compute the inverse-FFT or FFT has to take less than the time for each symbol,<ref name=ce883>{{cite thesis |type=B.E. |url=http://ce.sharif.ir/courses/85-86/2/ce883/resources/root/Lectures/About-OFDM.pdf |title=The suitability of OFDM as a modulation technique for wireless telecommunications, with a CDMA comparison |author=Eric Lawrey |date=October 1997 |access-date=2012-08-28 |archive-date=2012-09-14 |archive-url=https://web.archive.org/web/20120914014043/http://ce.sharif.ir/courses/85-86/2/ce883/resources/root/Lectures/About-OFDM.pdf |url-status=dead }}</ref>{{rp|84}} which for example for [[DVB-T]] {{nowrap|(FFT 8k)}} means the computation has to be done in {{nowrap|896 µs}} or less.

For an {{gaps|8192}}-point [[fast Fourier transform|FFT]] this may be approximated to:<ref name=ce883/><!-- extrapolated from the FFT 2048 example -->{{clarify|reason=Normally complexity is said to be proportional to N log2(N) per block for FFT; i.e., 8192×13 when N=8192.|date=September 2012}}

:<math>\begin{align}
  \mathrm{MIPS}
   &= \frac {\mathrm{computational\ complexity}}{T_\mathrm{symbol}} \times 1.3 \times 10^{-6} \\
   &= \frac{147\;456 \times 2}{896 \times 10^{-6}} \times 1.3 \times 10^{-6} \\
   &= 428
\end{align}</math>
* MIPS: [[Instructions per second#Million instructions per second|Million instructions per second]]

The computational demand approximately scales linearly with FFT size so a double size FFT needs double the amount of time and vice versa.<ref name=ce883/>{{rp|83}}<!--someone deduce this directly from n log(n) which needs ×4 to match ? --> As a comparison an [[Pentium III|Intel Pentium III]] CPU at 1.266&nbsp;GHz is able to calculate a {{nowrap|8192 point}} FFT in <!--$n=8192; $mflops=925; 5*$n*(log($n)/log(2))/$mflops=575.654054-->{{nowrap|576 µs}} using [[FFTW]].<!--double-precision complex, 1d transforms FFTW3 out-of-place--><ref>{{cite web |url=http://www.fftw.org/speed/Pentium3-1.266GHz/ |website=fftw.org |title=1.266 GHz Pentium 3 |date=2006-06-20}}</ref> [[Pentium M|Intel Pentium M]] at 1.6&nbsp;GHz does it in {{nowrap|387 µs.}}<ref>{{cite web |url=http://www.fftw.org/speed/PentiumM-1.6GHz-gcc/ |website=fftw.org |title=1.6 GHz Pentium M (Banias), GNU compilers |date=2006-06-20}}</ref> [[Core Duo|Intel Core Duo]] at 3.0&nbsp;GHz does it in {{nowrap|96.8 µs}}.<ref>{{cite web |url=http://www.fftw.org/speed/CoreDuo-3.0GHz-icc/ |website=fftw.org |title=3.0 GHz Intel Core Duo, Intel compilers, 32-bit mode |date=2006-10-09}}</ref>