|
|
Сортировку, если ее вообще делают, делают раз. Либо до БПФ, либо после БПФ. После каждой ступени ее не делают.
Сортировки после каждой ступени ничему не противоречат, они просто приведут к какому-то порядку данных в окончательном результате.Но Вам, мне кажется, нужно начать с самого начала.
X[k]=sum(x[n]*exp(-j*2pi*n*k/N)).
Сумма по n, n и k от 0 до N-1.
Это формУла 1.
Далее ускоряете вычисления, путем взятия преобразований меньшего размера и их сшивки.
Делаете из x[n] 2 массива в 2 раза меньшей длины.
Один, x0, образован из четных элементов x, т.е. x0[n]=x[2n],
второй, x1, из нечетных, x1[n]=x[2n+1]. n от 0 до (N/2)-1.В результате получите:
X[k]=sum(x[2n]*exp(-j*2pi*2n*k/N))+sum(x[2n+1]*exp(-j*2pi*(2n+1)*k/N))=
=sum(x0[n]*exp(-j*2pi*n*k/(N/2)))+exp(-j*2pi*k/N)*sum(x1[n]*exp(-j*2pi*n*k/(N/2))).
В этих выражениях суммы по n ,n от 0 до N/2-1; k от 0 до N-1
Обозначив через X0[k],X1[k] преобразования Ф. длиной N/2 над x0[n],x1[n] и учтя, что они, X0,X1, будут периодичны
с периодом N/2, получим:
X[k]=X0[k]+exp(-j*2pi*k/N)*X1[k]
X[k+N/2]=X0[k]-exp(-j*2pi*k/N)*X1[k]
k от 0 до N/2-1.
Это группа формул 2 :-))
И образует она бабочку по осн. 2 с прореж. по времени.
И в ней X0[k],X1[k] -преобразования Ф. длиной N/2 над x0[n],x1[n].
X0[k]=sum(x0[n]*exp(-j*2pi*n*k/(N/2)));
X1[k]=sum(x1[n]*exp(-j*2pi*n*k/(N/2)));
суммы по n, n и k от 0 до N/2-1.
Пусть это будет группа формул 3:-)
Далее все вышеописанное применяется уже к x0, для вычисления X0, и к x1, для вычисления X1.
Здесь как раз важно все правильно обозначить:-)
Делим x0 на четные и нечетные отсчеты. Четные обозначим x00, нечетные x10.
Аналогично делим x1, но его четные обозначим x01, нечетные x11.
Т.е. вторая цифра в обозначении указывает, из какого массива, x0 или x1, получен соответствующий массив, а первая - четная или нечетная
часть. В более общем случае - первая показывает чет-нечет, а следующие цифры - номер массива на предыдущем разбиении, из которого этот чет-нечет
берется.X00,X10,X01,X11 - преобразования Ф. длиной N/4 над x00,x10,x01,x11:
X00[k]=sum(x00[n]*exp(-j*2pi*n*k/(N/4)));
X10[k]=sum(x10[n]*exp(-j*2pi*n*k/(N/4)));
X01[k]=sum(x01[n]*exp(-j*2pi*n*k/(N/4)));
X11[k]=sum(x11[n]*exp(-j*2pi*n*k/(N/4)));
суммы по n, n и k от 0 до N/4-1.
Тогда, по аналогии с X[k]:
X0[k]=X00[k]+exp(-j*2pi*k/(N/2))*X10[k]
X0[k+N/4]=X00[k]-exp(-j*2pi*k/(N/2))*X10[k]
X1[k]=X01[k]+exp(-j*2pi*k/(N/2))*X11[k]
X1[k+N/4]=X01[k]-exp(-j*2pi*k/(N/2))*X11[k]
k - от 0 до N/4-1.И подставив все это в выражения для X[k],X[k+N/2]:
X[k]=X00[k]+exp(-j*2pi*k/N)*X01[k]+exp(-j*2pi*2*k/N)*X10[k]+exp(-j*2pi*3*k/N)*X11[k];
X[k+N/4]=X00[k]-j*exp(-j*2pi*k/N)*X01[k]-exp(-j*2pi*2*k/N)*X10[k]+j*exp(-j*2pi*3*k/N)*X11[k];
X[k+N/2]=X00[k]-exp(-j*2pi*k/N)*X01[k]+exp(-j*2pi*2*k/N)*X10[k]-exp(-j*2pi*3*k/N)*X11[k];
X[k+3*N/4]=X00[k]+j*exp(-j*2pi*k/N)*X01[k]-exp(-j*2pi*2*k/N)*X10[k]-j*exp(-j*2pi*3*k/N)*X11[k];
k - от 0 до N/4-1.
Это группа формул 4.
И образует эта группа формул бабочку по основанию 4 с прорежив. по времени.
Суммарное число бабочек для всего преобразования=(N/4)*log4(N), N - степень 4.
Причем log4(N) - число ступеней преобразования, N/4 - число бабочек на каждой ступени.У Вас N =16. Соответственно число ступеней=2, и на каждой ступени по 4 бабочки.
Первую ступень Вы сделали, будем надеяться, что правильно.
Ее результаты как раз и есть X00,X01,X10,X11
Вам осталось сделать вторую ступень. Как и какие там к-ты - показывает группа формул 4.Если хотите - распишите по аналогии сами для X00,X01,X10,X11. Как они получаются.
Получите готовый граф преобразования для 16.Ну или ниже. В предположении, что перед БПФ была проведена четвертично-инверсная перестановка,
первая ступень сделана правильно, используете Вы алгоритм с замещением,
Y[0..15] - массив результатов на выходе первой ступени.
X00[0..3]=Y[0..3]
X01[0..3]=Y[4..7]
X10[0..3]=Y[8..11]
X11[0..3]=Y[12..15].
Как их друг с другом соединить и к-ты - из группы формул 4.
Только проверьте написанное, это совсем несложно. Я просто мог где-то описаться.
|
|
E-mail: 
info@telesys.ru
