Пpеобpазование Хаpтли

From

Evgenij Masherov (2:5020/175.2)

To

Илья Кантор

Date

2002-11-20T21:50:50Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

Wed Nov 20 2002 21:35, Илья Кантор wrote to Evgenij Masherov:

 EM>> Двукратный выигрыш получается из того, что БПФ по К точкам может быть
 EM>> применено для вычисления действительного преобразования Фурье по 2К
 EM>> точках.
 EM>> Оно же может быть вычислено при помощи БПФ по 2К точкам.
 EM>> Число элементарных операций для Фурье составляет C*(K*log K)+O(), для
 EM>> Хартли C*(2*K*log(2*K))+O(). Однако комплексное умножение-сложение
 EM>> требует вчетверо больше операций, чем действительное, что и дает
 EM>> (пренебрегая разницей между логарифмом К и 2*К) примерно двойной
 EM>> выигрыш.

 ИК> Ок. Вот подробно расписанные оценки. Здесь доказывается, что количество
 ИК> операций почти одинаково, за исключением O(N) с малой константой. Все
 ИК> данные по количеству операций относятся к действиям с действительными
 ИК> числами.

 ИК> В БПФ на каждом уровне рекурсии делается N/2 бабочек, каждая из 4
 ИК> умножений и 6 сложений, всего 2N* и 3N+ на уровень.

 ИК> В БПХ на каждом уровне делается N/4 спаренных бабочки (иначе не "на
 ИК> месте" выходит). Каждая спаренная бабочка - это 4 умножения и 6 сложений.
 ИК> #define FHT_T2Butterfly(N1,N2,C,S) {\ 
 ИК>         double Rx,Ri;                   \
 ИК>         int i1=N1,i2=N2;                        \
 ИК>         Rx=Right[i1];Ri=Right[i2];    \
 ИК>         {                                       \ 
 ИК>                 double cas1,Lx;         \
 ИК>                 cas1=Rx*(C)+Ri*(S);     \
 ИК>                 Lx=Left[i1];            \
 ИК>                 Left[i1]  = Lx+cas1;    \ 
 ИК>                 Right[i1] = Lx-cas1;    \
 ИК>         }                             \
 ИК>         {                                       \
 ИК>                 double cas2,Li;         \ 
 ИК>                 cas2=Rx*(S)-Ri*(C);     \ 
 ИК>                 Li=Left[i2];            \
 ИК>                 Left[i2]  = Li+cas2;    \
 ИК>                 Right[i2] = Li-cas2;    \
 ИК>         }                             \
 ИК> }
 ИК> Так что всего N умножений и 3N/2 сложений.

 ИК> Комплексный вектор в 2 раза короче действительного, поэтому БПФ
 ИК> действительного вектора состоит также из N умножений и 3N/2 сложений.

 ИК> Если не учитывать затраты O(N) с малой константой на FFT Real wrapper, то
 ИК> получается одинаково...

Ну так не надо добиваться "наместности". Используем вспомогательный буфер.

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)