Накапливается ошибка в fft

[guryev]

Source of the post
... даже если я правлю код по Вашему предложению, не меняется ровным счётом ничего.

А если бы даже и изменилось, получилось бы обратное преобразование (с точностью до множителя) вместо прямого - на качественную картинку это не влияет.

Но есть вот какая подозрительная штука:

Код: Выбрать все

 e = Re[step*cycle_W];
 f = Im[step*cycle_W];


, где увеличивается на 1 в теле самого внутреннего цикла, а уменьшается на 1 в самом внешнем цикле. Это приведёт к тому, что шаг выборки значений будет сначала 7 (фактически - не будет, поскольку выход из цикла произойдёт раньше), затем, после уменьшения на единицу: 6, затем 5, и т.д. Это едва ли правильно, так как значения (вроде бы!) должны выбираться с шагом, равным степени двойки.

[alexandr.krupnov]

Source of the post

Source of the post
... даже если я правлю код по Вашему предложению, не меняется ровным счётом ничего.

А если бы даже и изменилось, получилось бы обратное преобразование (с точностью до множителя) вместо прямого - на качественную картинку это не влияет.

Но есть вот какая подозрительная штука:

Код: Выбрать все

 e = Re[step*cycle_W];
 f = Im[step*cycle_W];


, где увеличивается на 1 в теле самого внутреннего цикла, а уменьшается на 1 в самом внешнем цикле. Это приведёт к тому, что шаг выборки значений будет сначала 7 (фактически - не будет, поскольку выход из цикла произойдёт раньше), затем, после уменьшения на единицу: 6, затем 5, и т.д. Это едва ли правильно, так как значения (вроде бы!) должны выбираться с шагом, равным степени двойки.

Мне кажется здесь всё нормально. Судите сами:
Шаг 7 Цикл всегда 0, в итоге берём поворачивающий коэффициент 7*0 = 0.
Шаг 6 Цикл равен 0 и 1. В итоге поворачивающий коэффициент 6*0 = 0 и 6*1 = 6
Шаг 5 5*0=0, 5*1=5, 5*2 = 10, 5*3 = 15
На шаге 4 имеем 0,4,8,12,16,20,24,28,32
и так далее

[alexandr.krupnov]

Номер шага_____Шаг 7___Шаг 6___Шаг 5___Шаг 4___Шаг 3___Шаг 2___Шаг 1

Номер ПМ______ W[0]___W[0]_____W[0]___ W[0]____ W[0]___W[0]____ W[0]
_______________________W[6]____W[5]____W[4]____W[3]___W[2]____ W[1]
_______________________________ W[10]___W[8]____W[6]___W[4]____W[2]
________________________________W[15]___W[12]___W[9]___W[6]____W[3]
________________________________________ W[16]___W[12]__W[8]____W[4]


и таг далее. На каждом шаге есть несколько блоков. На 7 шаге - 64 блока. На 6 - 32 блокак. На 5 - 16 блоков и так далее.
В каждом блоке - циклы. На 7 шаге в блоке 1 цикл, на 6 шаге в блоке - 2 цикла, на 5 шаге в блоке 4 цикла, на 4 шаге в блоке 8 циклов и так далее. На 1 шаге в блоке 64 цикла. На 1 шаге всего один блок.

[guryev]

Ох, лень объяснять... Короче, в процедуре coeff_func() меняйте оператор

Код: Выбрать все

for (step=7;step>0;step--)

на

Код: Выбрать все

for ( step = 64; step > 0; step >>= 1 )

и всё должно заработать.

И ещё одно - когда вычисляете образец сигнала (процедура calc_sin()), начинайте с аргумента 0, а не 1/s_rate, а то сигнал получается сдвинутый, ну и спектр тоже с болтанкой.

[alexandr.krupnov]

Source of the post
Ох, лень объяснять... Короче, в процедуре coeff_func() меняйте оператор

Код: Выбрать все

for (step=7;step>0;step--)

на

Код: Выбрать все

for ( step = 64; step > 0; step >>= 1 )

и всё должно заработать.

И ещё одно - когда вычисляете образец сигнала (процедура calc_sin()), начинайте с аргумента 0, а не 1/s_rate, а то сигнал получается сдвинутый, ну и спектр тоже с болтанкой.

Да, Вы правы. Огромное Вам спасибо. От всей души, я пару месяцев мучался с данной ошибкой. Перечитал Кестлера, Солонину, Юкио Сато, статей и форумов.
Если честно так и не понял почему именно так реализуется бпф а не какизначально я написал.
Если переписать на
for ( step = 64; step > 0; step >>= 1 )
то будет ли соблюдаться формула P = N*log2 (N)
как я понял, то нет, так как у меня получится 64 шага, в каждом шаге по 64 вложенных цикла (блок на цикл).
Если кому то не сложно, поясните, почему я так напутал с вложенными циклами и какова всё таки сложность программы (я про N*log2(N))
Спасибо в любом случае за помощь

ААА оператор Си >>= сдвигает же
И мы имеем 64, 32,16,8,4,2,1
То есть всё таки шагов 7 но они - есть показатели степени 2.
Всё, я понял. Я всё понял. Огромное Вам спасибо. Всё таки в учебниках где в качестве входного массива беруться 8 выборок и получают три шага c номерами ПМ [0], [0,2], [0,1,2,3] не проясняют момент о том что шаг обязательно есть показатель степени 2 с исходным значением N/2
СПАСИБО!