Обратное быстрое преобразование Фурье, Граф алгоритма первого прореживания Опции

[maxqwe]

Здравствуйте, уважаемые форумчане.
Изучаю теорию БПФ(быстрое преобразование Фурье), а именно - граф первого деления алгоритма прореживания по времени БПФ по основанию 2.
Выглядит он так:

У меня возник вопрос, как будет выглядеть граф первого деления алгоритма прореживания по времени ОБПФ(обратного БПФ) по основанию 2?

Теоретически, для ОБПФ нужно применить операцию комплексного сопряжения вначале к входным данным, а затем к результату, полученному после прямого преобразования Фурье), и окончательный результат поделить на N.
Но как это изобразить на графе?Кто может подсказать?Или, если это возможно, графически продемонстрировать, заранее спасибо.

[petrov]

Теоретически, для ОБПФ нужно применить операцию комплексного сопряжения вначале к входным данным, а затем к результату, полученному после прямого преобразования Фурье)...

Ещё проще представлять DFT как произведение матрицы преобразования на вектор-столбец данных, а iDFT произведение комплексно-сопряжённой матрицы на вектор данных. Разница между DFT и iDFT только в порядке данных на выходе, положительные частоты меняются местами с соответствующими отрицательными частотами. Граф останется тот же самый, а порядок на выходе будет:
X(0)
X(N-1)
.
.
.
X(N/2+1)
X(N/2)
X(N/2-1)
.
.
.
X(1)

[blackfin]

Разница между DFT и iDFT только в порядке данных на выходе, положительные частоты меняются местами с соответствующими отрицательными частотами.
Граф останется тот же самый, а порядок на выходе будет:

Что-то вы тут сочиняете, КМК..

Если уж заикнулись про положительные и отрицательные частоты, то следуйте своей логике до конца:

Разница между DFT и iDFT в том, что вектор на входе DFT зависит от времени, а вектор на выходе DFT зависит от частоты.
В то же время вектор на входе iDFT зависит от частоты, а вектор на выходе iDFT зависит от времени.

Порядок следования семплов на входе и выходе в обоих случаях остается одним и тем же:

на входе: x[0],x[1],x[2],.., x[N-1],

и на выходе: X[0],X[1],X[2],.., X[N-1].

Что касается графа для FFT, то следует различать две формы: с децимацией по частоте (DIF) и с децимацией по времени (DIT).

Обе схемы являются зеркальным отражением друг друга относительно "вертикальной" оси графа.

Для графа FFT Radix-2 DIF данные на выходе графа следуют в бит-реверсном порядке.

Точно так же для графа FFT Radix-2 DIT данные на входе графа следуют в бит-реверсном порядке.

Любую из форм графа FFT можно преобразовать в iFFT.

Для этого нужно каждый поворачивающий множитель W^k заменить на комплексно-сопряженный (то есть, изменить знак у каждого sin[k] на противоположный) и заменить в каждой бабочке (для Radix-2): +1 <-> -1

Как-то так..

[petrov]

Что-то вы тут сочиняете, КМК..

>> w=exp(-j*2*pi/4)

w =

0.0000 - 1.0000i

Матрица DFT:

>> F=w.^([0:3].'*[0:3])

F =

1.0000 + 0.0000i 1.0000 + 0.0000i 1.0000 + 0.0000i 1.0000 + 0.0000i
1.0000 + 0.0000i 0.0000 - 1.0000i -1.0000 - 0.0000i -0.0000 + 1.0000i
1.0000 + 0.0000i -1.0000 - 0.0000i 1.0000 + 0.0000i -1.0000 - 0.0000i
1.0000 + 0.0000i -0.0000 + 1.0000i -1.0000 - 0.0000i 0.0000 - 1.0000i


Матрица iDFT:

>> iF=conj(F)

iF =

1.0000 + 0.0000i 1.0000 + 0.0000i 1.0000 + 0.0000i 1.0000 + 0.0000i
1.0000 + 0.0000i 0.0000 + 1.0000i -1.0000 + 0.0000i -0.0000 - 1.0000i
1.0000 + 0.0000i -1.0000 + 0.0000i 1.0000 - 0.0000i -1.0000 + 0.0000i
1.0000 + 0.0000i -0.0000 - 1.0000i -1.0000 + 0.0000i 0.0000 + 1.0000i

Единичная матрица:

>> iF*F/4

ans =

1.0000 + 0.0000i -0.0000 - 0.0000i 0.0000 - 0.0000i 0.0000 - 0.0000i
-0.0000 + 0.0000i 1.0000 + 0.0000i -0.0000 - 0.0000i 0.0000 - 0.0000i
0.0000 + 0.0000i -0.0000 + 0.0000i 1.0000 + 0.0000i -0.0000 - 0.0000i
0.0000 + 0.0000i 0.0000 + 0.0000i -0.0000 + 0.0000i 1.0000 + 0.0000i

Та же самая единичная, только порядок строк другой:

>> F*F/4

ans =

1.0000 + 0.0000i -0.0000 - 0.0000i 0.0000 - 0.0000i 0.0000 - 0.0000i
-0.0000 - 0.0000i 0.0000 - 0.0000i 0.0000 - 0.0000i 1.0000 + 0.0000i
0.0000 - 0.0000i 0.0000 - 0.0000i 1.0000 + 0.0000i -0.0000 - 0.0000i
0.0000 - 0.0000i 1.0000 + 0.0000i -0.0000 - 0.0000i 0.0000 - 0.0000i

Т. е. мы можем вычислять iDFT тем же графом что и DFT, в iF матрице те же самые фильтры в строчках, что и в F, только в другом порядке, комплексное сопряжение меняет местами положительные и отрицательные частоты.

[blackfin]

Т. е. мы можем вычислять iDFT тем же графом, что и DFT...

Для DFT/iDFT не существует графа в общепринятом значении этого слова. Граф существует для FFT/iFFT.

PS. Что касается численных примеров, то в математике они за доказательства не считаются.

... только в другом порядке, комплексное сопряжение меняет местами положительные и отрицательные частоты.

Не нужно путать "порядок следования" частот и "положительные и отрицательные частоты"..

Комплексное сопряжение действительно эквивалентно изменению "порядка следования" частот на выходе DFT, но только для вещественных входных векторов.

В общем случае это не верно..

[petrov]

Комплексное сопряжение действительно эквивалентно изменению "порядка следования" частот на выходе DFT, но только для вещественных входных векторов.

В общем случае это не верно..

Тогда достаточно простейший пример привести такого комплексного вектора.

[blackfin]

Тогда достаточно простейший пример привести такого комплексного вектора.

[attachment=113084:iFFT.jpg]

[petrov]

St =

Columns 1 through 6

1.0000 + 0.0000i -0.9239 + 0.3827i 0.7071 - 0.7071i -0.3827 + 0.9239i -0.0000 - 1.0000i 0.3827 + 0.9239i

Columns 7 through 8

-0.7071 - 0.7071i 0.9239 + 0.3827i

>> DFT=fft(St)

DFT =

Columns 1 through 6

1.0000 + 0.1989i 1.0000 + 0.6682i 1.0000 + 1.4966i 1.0000 + 5.0273i 1.0000 - 5.0273i 1.0000 - 1.4966i

Columns 7 through 8

1.0000 - 0.6682i 1.0000 - 0.1989i

>> fft(DFT)/8

ans =

Columns 1 through 6

1.0000 + 0.0000i 0.9239 + 0.3827i -0.7071 - 0.7071i 0.3827 + 0.9239i -0.0000 - 1.0000i -0.3827 + 0.9239i

Columns 7 through 8

0.7071 - 0.7071i -0.9239 + 0.3827i

Как видим результат равен St с точностью до перестановки отрицательных и положительных частот.

[blackfin]

OK. Сдаюсь.