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

From

Илья Кантор (2:5020/175.2)

To

Evgenij Masherov

Date

2002-11-20T21:35:12Z

Area

RU.ALGORITHMS

From: "Илья Кантор" <ilia@manual.ru>

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

 ИК>> За счет чего он 2кратный может получится ? Вроде, говорили уже об этом..
 ИК>> Могу перепостить сообщение с оценками, хотя на твоем сайте я его вижу..

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

Ок. Вот подробно расписанные оценки. Здесь доказывается, что количество
операций почти одинаково, за исключением 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)