|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : €«мп Љ в®а 2:5020/175.2 20 Nov 2002 22:35:12
To : Evgenij Masherov
Subject : Пpеобpазование Хаpтли
--------------------------------------------------------------------------------
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
