реклама на сайте
подробности

 
 
 
Reply to this topicStart new topic
> Обратное быстрое преобразование Фурье, Граф алгоритма первого прореживания
maxqwe
сообщение Jun 17 2018, 10:47
Сообщение #1





Группа: Новичок
Сообщений: 1
Регистрация: 17-06-18
Пользователь №: 105 127



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

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

Теоретически, для ОБПФ нужно применить операцию комплексного сопряжения вначале к входным данным, а затем к результату, полученному после прямого преобразования Фурье), и окончательный результат поделить на N.
Но как это изобразить на графе?Кто может подсказать?Или, если это возможно, графически продемонстрировать, заранее спасибо.
Go to the top of the page
 
+Quote Post
petrov
сообщение Jun 18 2018, 12:52
Сообщение #2


Гуру
******

Группа: Свой
Сообщений: 2 207
Регистрация: 21-10-04
Из: Balakhna
Пользователь №: 937



Цитата(maxqwe @ Jun 17 2018, 13:47) *
Теоретически, для ОБПФ нужно применить операцию комплексного сопряжения вначале к входным данным, а затем к результату, полученному после прямого преобразования Фурье)...


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

Go to the top of the page
 
+Quote Post
blackfin
сообщение Jun 18 2018, 13:55
Сообщение #3


Гуру
******

Группа: Свой
Сообщений: 2 970
Регистрация: 18-04-05
Пользователь №: 4 261



Цитата(petrov @ Jun 18 2018, 15:52) *
Разница между 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.gif
Go to the top of the page
 
+Quote Post
petrov
сообщение Jun 18 2018, 14:12
Сообщение #4


Гуру
******

Группа: Свой
Сообщений: 2 207
Регистрация: 21-10-04
Из: Balakhna
Пользователь №: 937



Цитата(blackfin @ Jun 18 2018, 16:55) *
Что-то вы тут сочиняете, КМК..


>> 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, только в другом порядке, комплексное сопряжение меняет местами положительные и отрицательные частоты.
Go to the top of the page
 
+Quote Post
blackfin
сообщение Jun 18 2018, 14:16
Сообщение #5


Гуру
******

Группа: Свой
Сообщений: 2 970
Регистрация: 18-04-05
Пользователь №: 4 261



Цитата(petrov @ Jun 18 2018, 17:12) *
Т. е. мы можем вычислять iDFT тем же графом, что и DFT...

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

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

Цитата(petrov @ Jun 18 2018, 17:12) *
... только в другом порядке, комплексное сопряжение меняет местами положительные и отрицательные частоты.

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

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

В общем случае это не верно..
Go to the top of the page
 
+Quote Post
petrov
сообщение Jun 18 2018, 15:50
Сообщение #6


Гуру
******

Группа: Свой
Сообщений: 2 207
Регистрация: 21-10-04
Из: Balakhna
Пользователь №: 937



Цитата(blackfin @ Jun 18 2018, 17:16) *
Комплексное сопряжение действительно эквивалентно изменению "порядка следования" частот на выходе DFT, но только для вещественных входных векторов.

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


Тогда достаточно простейший пример привести такого комплексного вектора.
Go to the top of the page
 
+Quote Post
blackfin
сообщение Jun 18 2018, 16:41
Сообщение #7


Гуру
******

Группа: Свой
Сообщений: 2 970
Регистрация: 18-04-05
Пользователь №: 4 261



Цитата(petrov @ Jun 18 2018, 18:50) *
Тогда достаточно простейший пример привести такого комплексного вектора.

Прикрепленное изображение
Go to the top of the page
 
+Quote Post
petrov
сообщение Jun 18 2018, 17:05
Сообщение #8


Гуру
******

Группа: Свой
Сообщений: 2 207
Регистрация: 21-10-04
Из: Balakhna
Пользователь №: 937



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 с точностью до перестановки отрицательных и положительных частот.
Go to the top of the page
 
+Quote Post
blackfin
сообщение Jun 18 2018, 17:16
Сообщение #9


Гуру
******

Группа: Свой
Сообщений: 2 970
Регистрация: 18-04-05
Пользователь №: 4 261



OK. Сдаюсь.
Go to the top of the page
 
+Quote Post

Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 16th July 2018 - 12:21
Рейтинг@Mail.ru


Страница сгенерированна за 0.01037 секунд с 7
ELECTRONIX ©2004-2016