Бързо преобразуване на Фурие

FFT технология

Това ръководство съдържа изходния код на операционния софтуер за изчисляване на FFT, подробно обяснение за това как работи и теоретична основа. Всичко това може да се намери и в други сайтове, но е трудно да се намери в този набор: програмата и обяснения и теория, и на руски език.

Ако не разполагате с време или желание да се занимава с теорията, можете директно да копирате текста на програмата в C ++. Ето заглавната част на файла, а fft.h fft.cpp източник за бързо преобразуване на Фурие на броя на броя на равни степен на две. Необходимо е да се предизвика функция FFT. Ето заглавната част на файла и изходния код на всеки (!) Брой на пробите. Той е малко по-бавно, но скоростта е там, също за Nlog2 Н. Calling необходимо universal_fft функция.

дефинира

определение 1

Предвид ограничен последователност x0. x1. x2. Xn-1 (в общ комплекс). В дискретна трансформация на Фурие (DFT) е за търсене на други последователности Х0. X1. X2. XN-1 чиито елементи се изчислява по формулата:

определение 2

Предвид ограничен последователност Х0. X1. X2. XN-1 (в общ комплекс). Обратното дискретна трансформация на Фурие (DFT) е за търсене на други последователности x0. x1. x2. Xn-1 чиито елементи се изчислява по формулата:

Главната особеност на тези трансформации (които могат да бъдат доказани в съответните секции на математиката) е този на серия от завои (за пряко преобразуване) последователност, и ако след това се прилага обратната трансформация, ние отново се оригиналната последователност.

определение 3

върти се нарича множител.

Помислете за броя имоти въртя фактори, които ние ще трябва в бъдеще.

Най-горната фигура в превръщането на множителя не е ли индекс - степен. Ето защо, когато тя е равна на единство, ние няма да го напиша:

Директно преобразуване на Фурие може да се изрази по отношение на превръщането фактори. Като резултат от формула (1) е:

Тези фактори са наистина оправдани името му. Равенство в комплексната равнина, всяко комплексно число като вектор, произхождащ от произхода. Ние представляваме комплексно число в експоненциална форма: повторното й # 966;. където г - на модула, и # 966; - аргумент. Модулът съответства на дължината на вектора, и аргумента - ъгълът на въртене:

Сега отнеме известно завъртане фактор. Неговият дял е равна на единство и фаза - 2π / Н. Както е известно, в размножаването на комплексни числа, представени в експоненциална форма, те се умножават модули и аргументи са обобщени. След това умножете първоначалния брой на фактора на отклонение от курса, не се променя дължината на вектора, но променя ъгъла му. Това означава, че векторът ще се завърти чрез 2π ъгъл / N (вж. Предишната фигура).

Ако сега разгледаме формула (3), става ясно, геометричен смисъл на трансформацията на Фурие: е да представляват комплексни числа N, векторите от комплекта, всеки като сума от вектори от комплекта завърта в кратни на 2π / N.

Новини
Knights етер теория