ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   23 Apr 2003  09:52:30
 To : Andrew Sovgir
 Subject : FFT
 -------------------------------------------------------------------------------- 
 

 Tue Apr 22 2003 17:30, Andrew Sovgir wrote to All:
  AS> В факе наткнулся на алгоpитм (а точнее, исходник) сабжа. Так вот, там
  AS> есть огpаничение, котоpое на пеpвый взгляд показалось мне довольно
  AS> стpанным. Дело в том, что число точек там должно быть степенью двойки.
  AS> Возможно, какие-то огpаничения накладываются самим алгоpитмом. Hо мне
  AS> интеpесно: а что, на пpактике такие задачи встpечаются чаще всего? Или
  AS> есть какие дpугие алгоpитмы для любого числа точек? Или в таких случаях
  AS> считают пpосто пpеобpазование Фуpье (не "быстpое")?
 
 Это ограничение одного определенного алгоритма БПФ (Кули-Тьюки), существуют
 алгоритмы и для другого числа точек (Винограда и пр.). Однако БПФ для
 произвольного числа точек не бывает. Дело в том, что экономия операций
 достигается, по сути, за счет того, что существует возможность объединить
 результаты двух преобразований Фурье для части данных в преобразование Фурье
 для всей их совокупности. Простейший и первым предложенный алгоритм - делит
 данные пополам (четные и нечетные точки) и объединяет результаты расчета. Один
 шаг такого деления вместо n^2 операций требует 2*(n/2)^2=n^2/2 операций
 расчета ПФ и порядка n операций на объединение результатов. Повторяя процедуру
 деления, получаем, что доходим до расчета ПФ по двум точкам, время которого
 пренебрежимо мало, и производим log2(n) шагов деления и объединения, каждый из
 которых требует порядка n операций, что и обеспечивает n log(n) операций для
 БПФ против n^2 для ПФ "в лоб". Выбирая другую схему деления и объединения
 совокупности, получаем иной алгоритм. Скажем, если n=m*k, можно считать ПФ от
 m точек k раз и от k точек m раз. Подробнее - к Блейхуту и другим. Если
 требуемое число точек не равно степени двум, и не подходит под иные доступные
 алгоритмы, отрезок дополняют нулями. Даже в худшем случае это оказывается
 быстрее прямого ПФ без дополнения (разумеется, число точек должно быть
 достаточно велико - в JPEG ДПФ считается "в лоб", хотя там 64=8*8 точек...)
 
  AS> И там еще упоминаются такие теpмины как "частота Hайквиста" и "частота
  AS> дискpетизации". Пpавильно я понимаю, что частота дискpетизации - это
  AS> кол-во точек в секунду? И чем отличается амплитудный спектp от фазового
  AS> (это все оттуда же)?
 
 Частота дискретизации - количество отсчетов в секунду, да. Частота Hайквиста
 (Котельникова, Hайквиста-Котельникова-Шеннона-Уиттекера...) -  половина ея.
 Сигнал, с частотой выше этой частоты, правильно зарегистрирован не может
 быть...
 Результат ПФ - комплексный вектор. В большинстве случаев мы можем пренебречь
 временнЫми сдвигами сигнала, они же сдвиги фазы, и ограничиться модулем этого
 вектора, что и есть амплитуда. А аргумент его - фаза.
 
 Евгений Машеров АКА СанитарЖеня
 
 --- ifmail v.2.15dev5
  * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    FFT   Andrew Sovgir   22 Apr 2003 17:30:52   FFT   Evgenij Masherov   23 Apr 2003 09:52:30   FFT   Nick Poroshin   23 Apr 2003 18:50:52   Re: FFT   Alexey   05 May 2003 21:53:51   FFT   Max Alekseyev   05 May 2003 11:25:10   Re: FFT   Evgenij Masherov   05 May 2003 22:51:07   Re: FFT   Trusov Alexey   08 May 2003 19:15:35   Re: FFT   Evgenij Masherov   08 May 2003 20:14:25