maxqwe 0 17 июня, 2018 Опубликовано 17 июня, 2018 · Жалоба Здравствуйте, уважаемые форумчане. Изучаю теорию БПФ(быстрое преобразование Фурье), а именно - граф первого деления алгоритма прореживания по времени БПФ по основанию 2. Выглядит он так: У меня возник вопрос, как будет выглядеть граф первого деления алгоритма прореживания по времени ОБПФ(обратного БПФ) по основанию 2? Теоретически, для ОБПФ нужно применить операцию комплексного сопряжения вначале к входным данным, а затем к результату, полученному после прямого преобразования Фурье), и окончательный результат поделить на N. Но как это изобразить на графе?Кто может подсказать?Или, если это возможно, графически продемонстрировать, заранее спасибо. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
petrov 7 18 июня, 2018 Опубликовано 18 июня, 2018 · Жалоба Теоретически, для ОБПФ нужно применить операцию комплексного сопряжения вначале к входным данным, а затем к результату, полученному после прямого преобразования Фурье)... Ещё проще представлять DFT как произведение матрицы преобразования на вектор-столбец данных, а iDFT произведение комплексно-сопряжённой матрицы на вектор данных. Разница между DFT и iDFT только в порядке данных на выходе, положительные частоты меняются местами с соответствующими отрицательными частотами. Граф останется тот же самый, а порядок на выходе будет: X(0) X(N-1) . . . X(N/2+1) X(N/2) X(N/2-1) . . . X(1) Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
blackfin 25 18 июня, 2018 Опубликовано 18 июня, 2018 · Жалоба Разница между 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: Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
petrov 7 18 июня, 2018 Опубликовано 18 июня, 2018 · Жалоба Что-то вы тут сочиняете, КМК.. >> 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 25 18 июня, 2018 Опубликовано 18 июня, 2018 · Жалоба Т. е. мы можем вычислять iDFT тем же графом, что и DFT... Для DFT/iDFT не существует графа в общепринятом значении этого слова. Граф существует для FFT/iFFT. PS. Что касается численных примеров, то в математике они за доказательства не считаются. ;) ... только в другом порядке, комплексное сопряжение меняет местами положительные и отрицательные частоты. Не нужно путать "порядок следования" частот и "положительные и отрицательные частоты".. Комплексное сопряжение действительно эквивалентно изменению "порядка следования" частот на выходе DFT, но только для вещественных входных векторов. В общем случае это не верно.. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
petrov 7 18 июня, 2018 Опубликовано 18 июня, 2018 · Жалоба Комплексное сопряжение действительно эквивалентно изменению "порядка следования" частот на выходе DFT, но только для вещественных входных векторов. В общем случае это не верно.. Тогда достаточно простейший пример привести такого комплексного вектора. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
blackfin 25 18 июня, 2018 Опубликовано 18 июня, 2018 · Жалоба Тогда достаточно простейший пример привести такого комплексного вектора. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
petrov 7 18 июня, 2018 Опубликовано 18 июня, 2018 · Жалоба 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 25 18 июня, 2018 Опубликовано 18 июня, 2018 · Жалоба OK. Сдаюсь. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться