Перейти к содержанию

Обратное быстрое преобразование Фурье

Здравствуйте, уважаемые форумчане.

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

Выглядит он так:

123456.jpg

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

 

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

Но как это изобразить на графе?Кто может подсказать?Или, если это возможно, графически продемонстрировать, заранее спасибо.

Поделиться сообщением


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

 

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

X(0)

X(N-1)

.

.

.

X(N/2+1)

X(N/2)

X(N/2-1)

.

.

.

X(1)

 

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
Разница между 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.

 

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

 

Как-то так.. :biggrin:

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
Что-то вы тут сочиняете, КМК..

 

>> 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, только в другом порядке, комплексное сопряжение меняет местами положительные и отрицательные частоты.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
Т. е. мы можем вычислять iDFT тем же графом, что и DFT...

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

 

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

 

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

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

 

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

 

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

Поделиться сообщением


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

 

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

 

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

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты
Тогда достаточно простейший пример привести такого комплексного вектора.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

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 с точностью до перестановки отрицательных и положительных частот.

 

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Для публикации сообщений создайте учётную запись или авторизуйтесь

Вы должны быть пользователем, чтобы оставить комментарий

Создать учетную запись

Зарегистрируйте новую учётную запись в нашем сообществе. Это очень просто!

Регистрация нового пользователя

Войти

Уже есть аккаунт? Войти в систему.

Войти
Авторизация