Отправлено ВН 15 сентября 2003 г. 14:31 В ответ на: Вопрос теоретикам: отправлено msize 15 сентября 2003 г. 12:29

Да формулы для всех отсчетов результирующего FFT получаются из:
1. для действительного сигнала отсчеты FFT для отрицательных частот комплексно сопряжены с отсчетами для соотв. полож. частот, т.е. X[N-k=X'[k];
2. использования бабочки по основанию 2 с прореживанием по времени.
Один из вариантов вычисления БПФ длиной N через пару БПФ половинной длины это прореживание по времени.
Т.е.:
X[k]=XE[k]+exp(-j*2*pi/N)*XO[k]
X[k+N/2]=XE[k]-exp(-j*2*pi/N)*XO[k]
k=0...N/2-1. XE[k], XO[k] - БПФ размера N/2 над четными и нечетными элементами исходного массива, соответственно, т.е. над xe[n]=x[2*n] и
xo[n]=x[2*n+1].
При используемом Вами методе, БПФ вычисляется над комплексным сигналом z[n]=xe[n]+j*xo[n]. БПФ половинной длины.
Z[k]=XE[k]+j*XO[k]=Re(XE[k])+j*Im(XE[k])+j*Re(XO[k]-Im(XO[k])=
Re(Z[k])+j*Im(Z[k]). Re(Z[k])=Re(XE[k])-Im(XO[k]); Im(Z[k])=Im(XE[k])+Re(XO[k]).
Нужно из Z[k] выделить XE[k] и XO[k] и подставить их в бабочку, чтобы получить X[K], т.е. БПФ полной длины над x[n].
Пусть размер Z равен M=N/2.
Используется комплексная сопряженность отсчетов БПФ действ. сигнала для отриц. частот, именно XE[M-k]=XE'[k], XO[M-k]=XO'[k]. k=1...M/2.
Или Z[M-k]=XE'[k]+j*XO'[k]. Или Re(Z[M-k])=Re(XE[k])+Im(XO[k]),
Im(Z[M-k])=-Im(XE[k])+Re(XO[k]).
Из этих выражений и выражений для Re(Z[k]),Im(Z[k]) получаются выражения для XE[k],XO[k] при k=1...M/2, а отсчеты для M-k просто комплексно сопряжены с найденными. k=0 - особая точка, но для нее тоже все просто.
Для k=0 и Im(XE[k]) и Im(XO[k])=0 - для действит. сигнала отсчет на 0 ч-те всегда действительный, прямо из формулы для ПФ следует, базовая функция для 0 частоты это косинус 0 частоты.
Т.е. Re(Z[0])=Re(XE[0]), Im(Z[0])=Re(XO[0]).
Теперь только подставить XE[k],XO[k], k=0...M-1=0...N/2-1 в бабочку.