11,640,626 members (60,567 online)
Tip/Trick

# Fast Fourier transform using DX11

, 14 Jan 2015 CPOL 20.8K 1.4K 39
 Rate this:
Please Sign up or sign in to vote.
FFT using DX11 compute shader

## Introduction

We introduce FFT (Fast Fourier transform) using DX11 GPGPU, also implement FT without DX11. FT is commonly used to transform function in time domain to a function in frequency domain, this further allows us to analyze signals in frequency space and add our own changes (digital equalizers), these changes are further reconverted to time domain using inverse FT.

We implement FT without DX11 to verify the output.

## Background

This article does not hope to introduce to the readers Fourier transform (FT), it only show cases use of GPU to perform FFTs, it would be a good idea to read up on FT. Also you would be required to go through my previous article http://www.codeproject.com/Articles/42612/DirectX-11-Compute-Shaders, since this article requires you to know about DX11 resource and views. Thankfully DX11 already provides FFT related functionality so we are not required to write a compute shader.

Advantage of running FT on GPU is to gain performance from the parallel stream processors.

## Using the code

As with my previous article, the attached code must be referred to at all times.

We must start by creating a DX11 device, remember that CS is not available on all hardware, for the purpose of this tutorial we will use the reference driver, this will force FFT to be computed on CPU.

`D3D11CreateDevice(NULL,D3D_DRIVER_TYPE_REFERENCE,0,0,0,0,D3D11_SDK_VERSION,&pDeviceOut,&flOut,&pContextOut);`

The next thing we need is the buffer on which we shall perform FT, remember what we perform here are strictly discrete FTs, so we work on buffer of fix size, please refer to http://en.wikipedia.org/wiki/Discrete_Fourier_transform

```for(int i=0;i<SIZE1;i++)
vBuf1.push_back(...)```

In our example, we create input of real numbers (no imaginary component is being used), but the outcome of an FT may contain an imaginary component.

FT always has a cosine (real) and sine (imaginary) component, we implement our own variation using an exp (e^x) function where e=2.7182818 refer: http://en.wikipedia.org/wiki/E_(mathematical_constant)

Now comes the best part

we need to create the buffer and fill it up with the data generated by the above code (please refer to my previous article related to compute shader), the difference between my previous article is that we use buffers that allow raw views as oppose to structured buffer. These buffers once created are made available to the GPU, the GPU can access them to perform the required computation.

`desc.MiscFlags = D3D11_RESOURCE_MISC_BUFFER_ALLOW_RAW_VIEWS;`

Lets create the FFT object

`HRESULT hr=D3DX11CreateFFT(pContextOut,&fftdesc,0 ,&fftbufferinfo,&pFFT)`

The variable fftbufferinfo returned will tell us the resource requirements to complete FFT, in the attached code ,we need 2 temporary buffers. We must create 2 temporary buffers and attach them, these temporary buffers are used internally to carry out the operation. Look up http://msdn.microsoft.com/en-us/library/windows/desktop/ff476847(v=vs.85).aspx

```<font face="Consolas" size="2"><font face="Consolas" size="2">std::vector<ID3D11Buffer *> ArrBufTemp;std::vector<ID3D11UnorderedAccessView *> ArrBufTemp_UAV;
</font></font>
<font face="Consolas" size="2"><font face="Consolas" size="2">std::vector<ID3D11Buffer *> ArrBufpreCompu;std::vector<ID3D11UnorderedAccessView *> ArrBufpreCompu_UAV;

//We must create the buffers

hr=pFFT->AttachBuffersAndPrecompute(fftbufferinfo.NumTempBufferSizes,fftbufferinfo.NumTempBufferSizes>0?&ArrBufTemp_UAV[0]:NULL,fftbufferinfo.NumPrecomputeBufferSizes,fftbufferinfo.NumPrecomputeBufferSizes>0?&ArrBufpreCompu_UAV[0]:NULL);</font></font>```

We must also set the forward scale, every FT point of output will be multiplied by this value.

`pFFT->SetForwardScale(1.0f);  // Set scaling to 1 unit only  (optional setting is 0, which means scaling is 1 unit)`

The next thing is to call

`hr=pFFT->ForwardTransform(pBufin1_UAV,&respBufin1_UAV);`

This will tell the DX11 runtime to perform FFT on the input data, it will return a resource view from which output data can be accessed. Further transforms and be performed on the output buffer.

Then pull out the output buffer, this is explained in my previous article on compute shader and in attached code. Remember the output will be twice the size of the input buffer since we get two outputs for every input point, one real and one imaginary value (as discussed earlier).

Now lets verify this by writing out own FT. The below code is straight from my college books

```for(k=0;k<n;k++)for(j=0;j<n;j++)
b[k]=b[k]+a[j]*exp(i*-1*k*j*2*3.1415926/n);```

b[k] will hold the FT output at point k

The first for loop does the summation, the next one moves ahead to find the FT of the next point. (This part is self explanatory to people who have worked on FTs)

The 2 for loops are used (hence a time complexity of n^2), not to mention exp function is added to work with complex numbers and is compute heavy, i =sqrt(-1), j,k are used in for loop. The output of our FT closely matches the output of DX11 FFT.

Since b[k] is calculated for every value of k, these operations can be carried out on every stream individually, hence FFT/FT implemented on GPU will greatly improve performance.

As an exercise, you may implement Inverse FT (IFT):

## Points of Interest

FFT are very computational intensive tasks, and to implement them on the GPU can highly optimize your code. You can try implementing your own version of a sound equalizer or a new winamp visualization using the attached code (may be my next project).

## License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

## About the Author

 Instructor / Trainer India
Hi,
I have been working with computers since my eight grade, programming the ZX Spectrum. I have always had an interest in assembly language and computer theory (and is still the reason for taking tons of online courses), actively code using C/C++ on Windows (using VS) and Linux (using QT).

I also provide training on data structures, algorithms, parallel patterns library , Graphics (DX11), GPGPUs (DX11-CS,AMP) and programming for performance on x86.
Feel free to call me at 0091-9823018914 (UTC +5:30)

(All views expressed here do not reflect the views of my employer).

## Comments and Discussions

 First Prev Next
 compiling on VS2013, d3dx11effect.h does not appear to be needed Jan Heckman17-Jan-15 23:52 Jan Heckman 17-Jan-15 23:52
 Thanks!! Sten Roar4-Jan-15 21:52 Sten Roar 4-Jan-15 21:52
 Re: Thanks!! Asif Bahrainwala5-Jan-15 21:26 Asif Bahrainwala 5-Jan-15 21:26
 Re: Thanks!! Sten Roar6-Jan-15 0:17 Sten Roar 6-Jan-15 0:17
 Re: Thanks!! Asif Bahrainwala6-Jan-15 1:36 Asif Bahrainwala 6-Jan-15 1:36
 Re: Thanks!! Sten Roar6-Jan-15 23:57 Sten Roar 6-Jan-15 23:57
 Re: Thanks!! Asif Bahrainwala7-Jan-15 17:54 Asif Bahrainwala 7-Jan-15 17:54
 Re: Thanks!! Sten Roar7-Jan-15 20:55 Sten Roar 7-Jan-15 20:55
 Re: Thanks!! Asif Bahrainwala8-Jan-15 17:59 Asif Bahrainwala 8-Jan-15 17:59
 Re: Thanks!! Asif Bahrainwala9-Jan-15 22:35 Asif Bahrainwala 9-Jan-15 22:35
 Re: Thanks!! Sten Roar11-Jan-15 22:19 Sten Roar 11-Jan-15 22:19
 Re: Thanks!! Asif Bahrainwala12-Jan-15 6:08 Asif Bahrainwala 12-Jan-15 6:08
 Re: Thanks!! Sten Roar13-Jan-15 23:41 Sten Roar 13-Jan-15 23:41
 Re: Thanks!! Asif Bahrainwala14-Jan-15 6:17 Asif Bahrainwala 14-Jan-15 6:17
 FFT via AMP Asif Bahrainwala19-Jul-13 9:04 Asif Bahrainwala 19-Jul-13 9:04
 Re: FFT via AMP Dewey20-Jul-13 2:00 Dewey 20-Jul-13 2:00
 Re: FFT via AMP Asif Bahrainwala21-Jul-13 0:12 Asif Bahrainwala 21-Jul-13 0:12
 Re: FFT via AMP Dewey24-Jul-13 0:43 Dewey 24-Jul-13 0:43
 Thank you!! are_all_nicks_taken_or_what4-Apr-12 3:01 are_all_nicks_taken_or_what 4-Apr-12 3:01
 Been trying to get this to work for several days. Your code helped me a lot! Maybe you should update your sample project to also handle 2D FFT?
 Re: Thank you!! Asif Bahrainwala1-Jun-12 3:55 Asif Bahrainwala 1-Jun-12 3:55
 Last Visit: 31-Dec-99 18:00     Last Update: 1-Aug-15 2:28 Refresh 1

General    News    Suggestion    Question    Bug    Answer    Joke    Rant    Admin

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150731.1 | Last Updated 15 Jan 2015
Article Copyright 2012 by Asif Bahrainwala
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid