Отправлено -=ВН=- 02 июля 2004 г. 15:03 В ответ на: Но.. бабочки!? отправлено persol 02 июля 2004 г. 14:46

Что бабочки в БПФ делают? Дело в графическом изображении базовой операции в БПФ. В общем это конечно не совсем операция (как сложение, умножение и т.п.), ну пусть будет все-таки операция.
Для прореживания по времени она такая:
X(K)=XE(K)+W[K]*XO[K];
X[K+N/2]=XE[K]-W[K]*XO[K];
X - Фурье длины N; XE,XO - Фурье длины N/2 четных, нечетных соответственно.
Так вот графически эту операцию изображают в виде кружочка, с одной стороны в который входят входные (пардон) данные, а с другой выходят выходные (еще один пардон) данные. Чтобы уж слишком не углубляться, не буду объяснять почему, но входные данные, используюя географическую аналогию, входят с северо-запада и юго-запада, а выходные идут на северо-восток и юго-восток. Ну вот и получается графически отдаленно напоминающее бабочку. Batterfly, по ихнему. При других основаниях еще более отдаленно, но уж тут исторически. БПФ с прореж. по времени по основ. 2 первым придумали. В общем это стандартный термин в алгоритмах БПФ и не только.

• Бабочки, виноград, — persol   (02.07.2004 15:10, 52 байт)
  • Не надо там ничего образно мыслить. Это просто граф и не более того (+) — SM   (02.07.2004 15:17, 79 байт)
  • Виноград это фамилия. Он предложил свой алгоритм БПФ. — -=ВН=-   (02.07.2004 15:13, пустое)