FFTW

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

FFTW (ang. Fastest Fourier Transform in the West) – biblioteka do obliczania dyskretnych transformat Fouriera.

FFTW jest najszybszą niezależną od sprzętu biblioteką tego typu. Inne biblioteki o porównywalnych osiągach składają się z ręcznie optymalizowanego kodu asemblera, natomiast większość kodu FFTW jest generowana z zapisu w języku OCaml. Ponadto FFTW w czasie wykonania w fazie zwanej „planowaniem” dostosowuje się do właściwości danej maszyny – nie tylko procesora, ale również wykorzystuje cechy pamięci cache. Wykorzystuje do tego optymalizator, który stara się zdekomponować problem na prostsze podproblemy. FFTW wykorzystuje poza standardowymi wariantami algorytmu FFT Cooley-Tukey'a (dobry dla potęg 2), również algorytmy przydatne dla potęg dużych liczb pierwszych – takie jak algorytm FFT Radera oraz algorytm FFT Bluesteina.

FFTW jest biblioteką języka C, ale można jej używać także z Fortrana, C++ oraz D. Istnieją wersje tej biblioteki dla architektury SMP, a także dla obliczeń rozproszonych. FFTW od wersji 1.3 jest dostępna na licencji GPL (wcześniej była darmowa dla użytku niekomercyjnego); autorzy umożliwiają również uzyskania jej na innej, niewolnej licencji. Programy używające FFTW to m.in. GNU Octave i MATLAB.

Przykład użycia[edytuj | edytuj kod]

Przykładowy kod (dla wersji 2 FFTW):

#include <fftw.h>
#include <math.h>

int main()
{
	fftw_plan pl1,pl2;
	fftw_complex in[128], mid[128], out[128];
	int i;

	for (i=0; i<128; i++)
	{
		in[i].re = sin (M_PI*i/16);
		in[i].im = sin (M_PI*i/24);
	}

	pl1 = fftw_create_plan (128, FFTW_FORWARD, FFTW_ESTIMATE);
	pl2 = fftw_create_plan (128, FFTW_BACKWARD, FFTW_ESTIMATE);

	fftw_one (pl1, in, mid);
	fftw_one (pl2, mid, out);
	for (i=0; i<128; i++)
	{
		out[i].re /= 128;
		out[i].im /= 128;
	}

	fftw_destroy_plan (pl2);
	fftw_destroy_plan (pl1);

	for (i=0; i<128; i++)
		printf ("%d: in=(%f,%f), out=(%f,%f), d=(%f,%f)\n", i, in[i].re, in[i].im,
			out[i].re, out[i].im, out[i].re - in[i].re, out[i].im - in[i].im);

	return 0;
}

Zobacz też[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]