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

From

Pavel Sheliakin ()

To

Nickita A Startcev

Date

2002-05-05T06:15:54Z

Area

RU.ALGORITHMS

Hello, Nickita!
You wrote to (Pavel Sheliakin) on Wed, 01 May 2002 21:46:54 +0400:

 PS>> IMHO, в матричной форме преобразование Фурье и Уолша понять трудно.
 PS>> Лучше привести формулы и граф Кули-Тьюки. а по графу Кули-Тьюки БПФ
 PS>> и
 PS>> БПУ реализовать довольно просто.

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

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

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

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


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

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


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

         l
m - это W
         n


With best regards, Pavel Sheliakin.


--- Tearline sample
 * Origin: -= Jurevetc OnLine InterNetNews Server =- (2:5024/50)