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

Как посчитать FFT используя Cooley-Tukey алгоритм ?

Хочу посчитать FFT используя Cooley-Tukey алгоритм.

 

Представляю отсчёты в виде квадратной матрицы, считаю дпф столбцов, умножаю на коэффициенты, потом дпф строк - получаю спектр.

Хочу поменять порядок расчёта (сначала дпф строк, потом столбцов) - не могу получить спектр.

Кто-то реализовывал расчёт иммено в таком порядке (сначала дпф строк, потом столбцов)?

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


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

Представляю отсчёты в виде квадратной матрицы, считаю дпф столбцов, умножаю на коэффициенты, потом дпф строк - получаю спектр.

Хочу поменять порядок расчёта (сначала дпф строк, потом столбцов) - не могу получить спектр.

 

Что значит «не можете получить спектр»? Поподробнее пожалуйста.

Ну и не забываем конечно об отличии между этими двумя способами: если в первом случае порядок выполнения: ДПФ столбцов - умножение на поворачивающие коэфф. - ДПФ строк, то во втором случае: умножение на поворачивающие коэфф. - ДПФ строк - ДПФ столбцов.

А вообще читайте Рабинера с Гоулдом, глава 6-я если точнее, там все очень хорошо расписано.

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


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

Что значит «не можете получить спектр»? Поподробнее пожалуйста.

Ну и не забываем конечно об отличии между этими двумя способами: если в первом случае порядок выполнения: ДПФ столбцов - умножение на поворачивающие коэфф. - ДПФ строк, то во втором случае: умножение на поворачивающие коэфф. - ДПФ строк - ДПФ столбцов.

А вообще читайте Рабинера с Гоулдом, глава 6-я если точнее, там все очень хорошо расписано.

Главу 6 читал. Порядок перемножения соблюдаю. В таком порядке вычисленния "умножение на поворачивающие коэфф. - ДПФ строк - ДПФ столбцов" не могу получить результаты идентичные методу "ДПФ столбцов - умножение на поворачивающие коэфф. - ДПФ строк". Не могу понять кто виноват. Или так в принципе нельзя посчитать?

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


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

Не могу понять кто виноват. Или так в принципе нельзя посчитать?

 

Как это нельзя? Математически это для ДПФ, очевидно, эквивалентно

Ищите непонятки в алгоритме. В коэффициентах вращения и порядке следования отсчётов

 

прорежение по времени/по частоте

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


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

Хочу посчитать FFT используя Cooley-Tukey алгоритм.

 

Представляю отсчёты в виде квадратной матрицы, считаю дпф столбцов, умножаю на коэффициенты, потом дпф строк - получаю спектр.

Хочу поменять порядок расчёта (сначала дпф строк, потом столбцов) - не могу получить спектр.

Кто-то реализовывал расчёт иммено в таком порядке (сначала дпф строк, потом столбцов)?

В таком порядке БПФ не работает. В Рабинере-Голде в этом месте ошибка.

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


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

В таком порядке БПФ не работает

Это почему еще?

X*W1*W2=(X*W1)*W2=(X*W2)*W1 - знаете такое?

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


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

Это почему еще?

X*W1*W2=(X*W1)*W2=(X*W2)*W1 - знаете такое?

 

Там, видимо, не двумерное преобразование, а вывод одномерного через двумерную факторизацию.

Типа того http://fpga.parallel.ru/fft/

 

Приколист говорит, что типа Рабинер дал маху и БПФ с прорежением по времени больше не работает :rolleyes:

Отменяется. Только по частоте. Это будет посильней "неверной" теоремы Котельникова :biggrin:

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


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

Там, видимо, не двумерное преобразование, а вывод одномерного через двумерную факторизацию.

Типа того http://fpga.parallel.ru/fft/

 

Приколист говорит, что типа Рабинер дал маху и БПФ с прорежением по времени больше не работает :rolleyes:

Отменяется. Только по частоте. Это будет посильней "неверной" теоремы Котельникова :biggrin:

 

Прореживание по времени работает, что оно не работает никто не писал.

Не работает формула, по которой БПФ вычисляется как умножение на поворачивающие множители - ДПФ столбцов - ДПФ строк.

И она никакого отношения к прореживанию по времени не имеет.

А Рабинер действительно дал маху, сначала напутав с индексами при выводе формулы, а затем назвав это прореживанием по времени.

 

Прореживания по времени и по частоте отличаются тем, что вы разбиваете массив на 2 строки и n/2 столбцов в одном случае, и n/2 строк и 2 столбца в другом (см., например, книгу Блейхута).

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


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

Прореживание по времени работает, что оно не работает никто не писал.

Не работает формула, по которой БПФ вычисляется как умножение на поворачивающие множители - ДПФ столбцов - ДПФ строк.

И она никакого отношения к прореживанию по времени не имеет.

А Рабинер действительно дал маху, сначала напутав с индексами при выводе формулы, а затем назвав это прореживанием по времени.

 

Прореживания по времени и по частоте отличаются тем, что вы разбиваете массив на 2 строки и n/2 столбцов в одном случае, и n/2 строк и 2 столбца в другом (см., например, книгу Блейхута).

 

 

И что просчитав ДПФ по строкам, умножив на некую прорежённую матрицу и сделав ДПФ по столбцам нельзя получить результат?

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

Не верю, хоть и не проверял )) Мне кажется этих алгоритмов факторизации было придумано на любой вкус миллион.

 

Что в формулах возможны ошибки - это не вопрос. Они во всех книгах есть

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


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

Вроде разобрались...

 

И что просчитав ДПФ по строкам, умножив на некую прорежённую матрицу и сделав ДПФ по столбцам нельзя получить результат?

Нельзя. Если данные расположены в виде:

x_0 x1 ... x_n-1

x_n x_n+1 ... x_2n-1

то вначале нужно делать ДПФ-столбцов, потом умножение на матрицу, потом ДПФ-строк.

 

Если в обратном порядке (ДПФ-строк, потом умножение на матрицу, потом ДПФ-столбцов),

то надо делать не одно умножение на матрицу (для вычисления каждого элемента вертикального ДПФ матрица разная), то есть два.

Шо и выходит из формулы в Рабинере и Голде. А формула, как это ни удивительно, правильная. Только объём вычислений возрастает, а они это не учитывают и ничего не говорят об этом. Так шо немного, но обманули. И к типам прореживания это не имеет отношения, и по-времени и по-частоте вначале считают ДПФ-столбцов, просто разбиение, как выше сказали, разное (2xN или Nx2)

 

По типу алгоритма Гуда-Томаса (для взаимно простых множителей декомпозиции, где вообще нет вращений и вычисления производятся в любом

порядке), но с вращениями для Кули -Тьюки.

Тут переставляют данные в хитром порядке. Можна как хочешь расставить, и построкам начинать, и по столбцам.

 

 

 

Смысл был в том, чтоб без переставления начать с ДПФ-последовательного блока данных(x0,x1,...,xN-1) как написано в книге, а нельзя. Вот так.

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


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

Исходники вашей телеги к БПФ в студию. Т.к. написали Вы уже много, но с увеличением количества букв смысл все дальше и дальше.

 

Лично я сначала алгоритмы проверяю в Matlabe, а затем уже пихаю в MC.

Так вот, не считая погрешности вычисления, то ДПФ=БПФ(строки-столбцы)=БПФ(столбцы-строки).

xPLOIRi9OX.gif

Значит, дело явно не в бобине.

 

Или я не понимаю, о чем Вы говорите. :(

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


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

Только объём вычислений возрастает, а они это не учитывают и ничего не говорят об этом. Так шо немного, но обманули.

 

Ну хорошо, что хоть немного. Факторизация-то есть.

 

Или я не понимаю, о чем Вы говорите. :(

 

Они не делают двумерного FFT.

Они говорят о факторизации одномерного FFT длиной N через как-бы двумерное размерностью пусть sqrt(N) * sqrt(N)

Не совсем двумерное, там внутри ещё умножать на что-то надо, но типа - сначала sqrt(N) преобразований длиной sqrt(N)

по одному измерению, потом умножения на какие-то поворачисающие множители, потом sqrt(N) преобразований длиной sqrt(N) по другому. Как Кули-Тьюки выводится рекурсией по N

 

Неважно, забудьте. Рабинер частично реабилитирован :biggrin:

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


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

Исходники вашей телеги к БПФ в студию. Т.к. написали Вы уже много, но с увеличением количества букв смысл все дальше и дальше.

 

Лично я сначала алгоритмы проверяю в Matlabe, а затем уже пихаю в MC.

Так вот, не считая погрешности вычисления, то ДПФ=БПФ(строки-столбцы)=БПФ(столбцы-строки).

xPLOIRi9OX.gif

Значит, дело явно не в бобине.

 

Или я не понимаю, о чем Вы говорите. :(

Я говорю, что если у нас есть массив x0,x1,x2,x3 и мы хотим посчитать его ДПФ,

для этого представляем его в виде:

x0 x1

x2 x3,

 

то такая последовательность действий: ДПФ(x0,x1)+ДПФ(x2,x3)+умножение на матрицу поворачивающих коеффициентов+ДПФ(x0,x2)+ДПФ(x1,x3) правильного результата не даст. Исходников есстественно нет, т.к. не смог это сделать.

 

П.с. это не двумерное ДПФ, а вычисление одномерного большого ДПФ через комбинацию малых.

 

Неважно, забудьте. Рабинер частично реабилитирован :biggrin:

 

Только частично. )

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


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

Хочу посчитать FFT используя Cooley-Tukey алгоритм.

 

Представляю отсчёты в виде квадратной матрицы, считаю дпф столбцов, умножаю на коэффициенты, потом дпф строк - получаю спектр.

Хочу поменять порядок расчёта (сначала дпф строк, потом столбцов) - не могу получить спектр.

Кто-то реализовывал расчёт иммено в таком порядке (сначала дпф строк, потом столбцов)?

http://www.dspsystem.narod.ru/content/fft/...e/thintime.html написано что и как есть пример программной реализации. Там и про поворачивающие коэффициенты подробно расписано

Изменено пользователем bahurin

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


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

Я говорю, что если у нас есть массив x0,x1,x2,x3 и мы хотим посчитать его ДПФ,

для этого представляем его в виде:

x0 x1

x2 x3,

 

то такая последовательность действий: ДПФ(x0,x1)+ДПФ(x2,x3)+умножение на матрицу поворачивающих коеффициентов+ДПФ(x0,x2)+ДПФ(x1,x3) правильного результата не даст. Исходников есстественно нет, т.к. не смог это сделать.

Специально почитал соответствующий раздел Рабинера/Голда.

Алгоритм №1: БПФ столбцов+умножение на поворачивающие множители+БПФ строк - это работает. Об этом Вы уже писали.

Чтобы работал Алгоритм №2: БПФ строк+умножение на поворачивающие множители+БПФ столбцов - необходима другая сортировка массива.

 

Если для Алгоритма №1 данные записываются в массив по строкам, т.е. в Вашем примере

х0 х1

х2 х3

то для Алгоритма №2 необходимо записывать по столбцам:

х0 х2

х1 х3

 

Ответ почему теперь будет работать, очевиден, и, думаю, не требует доказательств

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


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

Присоединяйтесь к обсуждению

Вы можете написать сейчас и зарегистрироваться позже. Если у вас есть аккаунт, авторизуйтесь, чтобы опубликовать от имени своего аккаунта.

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...