Вопрос по быстрому преобразованию Фурье

← →
Yuri Btr © (2004-10-07 15:12) [0]

Ув. мастера, мне действительно нужно очень срочно разобраться с применением БПФ в моей программе, я нарыл много теоретической и практической информации по этому вопросу, попробовал вспомнить курс вышки из вуза. Нормальную практическую реализацию алгоритма БПФ я смог найти только в компоненте DSXFastFourier (на www.torry.net). Там есть такая ф-ия:
procedure TDSXFastFourier.FourierTransform(AngleNumerator: double); var NumBits, i, j, k, n, BlockSize, BlockEnd: word; delta_angle, delta_ar: double; alpha, beta: double; tr, ti, ar, ai: double; begin NumBits := NumberOfBitsNeeded (FNumSamples); for i := 0 to FNumSamples-1 do begin j := ReverseBits ( i, NumBits ); FOnGetData(i,FInBuffer[i]); FOutBuffer[j] := FInBuffer[i]; end; BlockEnd := 1; BlockSize := 2; while BlockSize <= FNumSamples do begin delta_angle := AngleNumerator / BlockSize; alpha := sin ( 0.5 * delta_angle ); alpha := 2.0 * alpha * alpha; beta := sin ( delta_angle ); i := 0; while i < FNumSamples do begin ar := 1.0; (* cos(0) *) ai := 0.0; (* sin(0) *) j := i; for n := 0 to BlockEnd-1 do begin k := j + BlockEnd; tr := ar*FOutBuffer[k].Real - ai*FOutBuffer[k].Imag; ti := ar*FOutBuffer[k].Imag + ai*FOutBuffer[k].Real; FOutBuffer[k].Real := FOutBuffer[j].Real - tr; FOutBuffer[k].Imag := FOutBuffer[j].Imag - ti; FOutBuffer[j].Real := FOutBuffer[j].Real + tr; FOutBuffer[j].Imag := FOutBuffer[j].Imag + ti; delta_ar := alpha*ar + beta*ai; ai := ai - (alpha*ai - beta*ar); ar := ar - delta_ar; INC(j); end; i := i + BlockSize; end; BlockEnd := BlockSize; BlockSize := BlockSize SHL 1; end; end;
эта ф-ия использует FOutBuffer и FInBuffer типа
type TComplex = Record Real : double; imag : double; end; TComplexArray = array [0..0] of TComplex; PComplexArray = ^TComplexArray; FInBuffer : PComplexArray; FOutBuffer : PComplexArray;
У меня же есть данные функции, которые представляют собой массив значений SmallInt (вообще то это формат Windows PCM, получаемый с пом. Bass.dll при вызове callback ф-ии указанной в BASS_RecordStart)
Как мне можно преобразовать значение типа SmallInt в значение типа TComplex (для дальнейшей записи в FInBuffer и вызова функции FourierTransform) ???
Заранее благодарен за любую помощь.

← →
Digitman © (2004-10-07 15:30) [1]

> нарыл много теоретической и практической информации по этому
> вопросу

проще было скачать бил-ку IntelSPL (Signak Processing Library) и не мучаться - БПФ в ней. поверь, реализован для х86-процессоров гораздо эффективней, нежели подобные примеры

и мне непонятно, для чего в подобного рода "примерах" при прямом быстром Фурье-преобразовании требуется представление вх.значений именно в компл.виде ... если существует исх.массив smallint-значений, требующий БПФ-обработки ...
вот результат прямого преобразования - это да, это еще можно как-то интерпретировать в виде массива комплексных значений !

← →
Ozone © (2004-10-07 15:41) [2]

Забивай просто дествительную часть значениями.

← →
Ozone © (2004-10-07 15:43) [3]

Вот на каком-то курсе делал http://www.rsdn.ru/Forum/Message.aspx?mid=566437&only=1

Мож пригодиться.

← →
Digitman © (2004-10-07 15:53) [4]

для прямого БПФ пользуй простейшие и понятнейшие расчеты по известным же формулам :

1. Амлитуда k-й гармоники спектра анализируемого сигнала

Hk = Sqrt(Ak^2 + Bk^2)

где
Ak - т.н. "действительная", а Bk - "комплексная" часть представления значения k-й спектральной составляющей

2.
P = 2Pi / m
Ak = 2/m * СУМ(от r=1 до r=m)Tr * cos(k * P * r)
Bk = 2/m * СУМ(от r=1 до r=m)Tr * sin(k * P * r)

здесь
m - число выборок во вх.буфере
P - период дискретизации (период времени, с которым ассоциирован преобразуемый буфер, ассоциирован с 2Pi-интервалом)
r - индекс выбоки во вх.буфере
Tr - значение выборки с индексом r во вх.буфере
k - индекс гармоники в массиве, предст. рез.спектр

БПФ предполагает, что m кратно двойке

← →
Jeer © (2004-10-07 15:57) [5]

Здесь оно есть.
http://www.basegroup.ru/download/

IntelSPL давно уж нет:)
Теперь IPP и платная:(

← →
Digitman © (2004-10-07 15:58) [6]

> период времени, с которым ассоциирован преобразуемый буфер,
> ассоциирован с 2Pi-интервалом

ляп

P - период выборок , а не период буфера в целом ..

← →
Jeer © (2004-10-07 15:59) [7]

Еще не забыть бы о явлении Гиббса и использовать "оконное" преобразование (Хэмминг, Блэкман, Велч и тп)

← →
Yuri Btr © (2004-10-07 16:12) [8]

to Ozone ©
спасибо, большое за пример, хотя и на C

to Digitman ©
Огромное спасибо за ответы...
Мне нужно всего лишь разложить буффер записи на спектр, понимаете, для этого использовать всю библиотеку SPL наверно будет слишком много, там же наверняка исходников нет
Я понимаю, что опытные программисты в возрасте ( и не только) все знают математические выкладки наизусть.
Но я думаю, что у многих посетителей форума даже нет и понятия что такое БПФ. Поэтому, не могли ли бы мы поподробнее разобраться с практическим применением БПФ.

m - число выборок во вх.буфере - применительно к звуковым данным, это дискретизация (например 44100 кГц или же степень двойки - 512, 1024, 2048, 4096 и т.д ?)
P - период дискретизации (в каких единицах ?)
r - индекс выбоки во вх.буфере (понятно - номер текущей выборки)
Tr - значение выборки с индексом r во вх.буфере ( понятно)
k - индекс гармоники в массиве, предст. рез.спектр (k - от 0 до 44100 ?)

← →
Yuri Btr © (2004-10-07 16:17) [9]

to Jeer
Спасибо.
Я так понимаю - FilteringBase это то что мне нужно?
(Задача - разложить сигнал на спектр и определить наличие определённых частот в нём)

to Digitman ©
Правда, IntelSPL уже нет, я вчера смотрел.
И ещё наверное нужно использовать оконную функцию для уменьшения утечек как написал Jeer © (07.10.04 15:59) [7]

← →
Digitman © (2004-10-07 17:42) [10]

по-нашему по-папуасски говоря

m - число элеменов массива smallint-значений, представленых вх.буфером

P - подели окружность (2Pi) на число m, это и будет "период" (представь в голове график одного целого периода синусоиды, это будет время = 2Pi, рассеки синусоиду параллельными вертикальными прямыми на m равных отрезков, отрезок на оси абсцисс, образованный точками пересечения любых двух соседних прямых и осью абсцисс и будет периодом выборок)

k - это не частота, а именно номер гармоники, которая не может быть больше r ... вопрос о связи частоты дискретизации и номера гармоники в полученном спектре - вопрос отдельный, но и здесь нет ничего сложного ... сначала с этим разберись ...

>для прямого БПФ пользуй простейшие и понятнейшие расчеты по известным же формулам :
>Digitman © (07.10.04 15:53) [4]
> P = 2Pi / m
>Ak = 2/m * СУМ(от r=1 до r=m)Tr * cos(k * P * r)
>Bk = 2/m * СУМ(от r=1 до r=m)Tr * sin(k * P * r)
- это Дискретное ПФ, но отнюдь не Быстрое... Либо "прямое", либо "быстрое"(в простонародье - "бабочка") - а "быстрое" только через комплексные числа.

???

> Yuri Btr

han_malign прав.
быстрое (прямое) преобразование пытаешься реализовать именно ты, я же описал тебе "на огурцах" механику дискретного преобразования, которое так же имеет право на существование в ряде конечных применений

Yuri Btr © (08.10.04 11:37) [13]

БПФ это быстрые методы реализации ДПФ.
Наиболее распространен по основанию 2.
Более быстрыми могут оказаться в частном применении алгоритмы: Винограда, с взаимно-простыми множителями, на основе теоретико-числовых преобразования.

Вопрос по быстрому преобразованию Фурье Найти похожие ветки