|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 20 Nov 2002 22:50:50
To : €«мп Љ в®а
Subject : Пpеобpазование Хаpтли
--------------------------------------------------------------------------------
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, то
ИК> получается одинаково...
Hу так не надо добиваться "наместности". Используем вспомогательный буфер.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
