pазвеpнyть pекypсию

From

Nickita A Startcev (2:5030/1039.8)

To

Pavel Sheliakin

Date

2002-05-06T03:41:04Z

Area

RU.ALGORITHMS

Привет, Pavel !


 05 May 02 , 06:15  Pavel Sheliakin писал к Nickita A Startcev:

 NA>> Я брал из фака эхи сишную реализацию БПФ. При проверке была видна
 NA>> куча артефактов и прочих неадекватностей. Мне интересно, где
 NA>> именно в факе ошибка? Или там не обойтись 'косметической правкой'
 NA>> и надо перепахивать всю программу?

 PS> Мне показалось, что оно вообще неправильно работало, складывало не так
 PS> как должнобыть по графу

Я с теорией БПФ знаком плохо. :) Я взял функцию из FAQ'а и вставил в свой проект. На тестовых примерах данная функция давала кучу артефактов. :(

 PS> А в ФАК можно вставить что-то вроде такого:

 PS>       n/2 - 1                    n/2 - 1
 PS> -      ---          2il     l     ---             2il
 PS> A   =  >     A     W    +  W      >     A        W
 PS>   k    ---     2i   n       n     ---    2i + 1   n
 PS>       i = 0                      i = 0


 PS> Так выглядит граф Кули-Тьюки для 4-хточечного БПФ

 PS> A0   A0 \ / C0\   / C0
 PS>          *     \ /
 PS> A1   A2 / \ C1\ * / C1
 PS>                X X
 PS> A2   A1 \ / C2/ * \ C2
 PS>          *     / \
 PS> A3   A3 / \ C3/   \ C3


 PS> a \ / c              c = a + m*b
 PS>    *     - "бабочка"
 PS> b / \ d              d = a - m*b

 PS>          l
 PS> m - это W
 PS>          n

1) где можно почитать всю теорию про БПФ?
2) где именно ошибка в факе?


.                                                С уважением, Никита.
... Пусть расцветают _ВСЕ_ цветы.
--- GoldED+/LNX 1.1.4.7
 * Origin: Люди Билли не любили... (c) (2:5030/1039.8)