ifft с симметричным входом, оптимальный алгоритм Опции

[tocha]

Делая FFT для реального сигнала длиной 2*N, мы получаем комплексный результат, причём выход имеет complex-conjugate симметрию. И реализовать его можно через комплексное FFT длиной N + небольшие манипуляции и на этом сэкономить вычислительные ресурсы.
Нужно сделать обратное преобразовние IFFT для комплексного входа длиной 2*N, который имеет свойство complex-conjugate симметрии. Соответствено результат будет реальным.
Правильно то, шо если мы сделали RFFT длиной 2*N упрощённым методом(CFFT длиной N), то и complex conjugate IFFT длиной 2*N мы можем вычислить через FFT длиной N?

[Xenia]

Делая FFT для реального сигнала длиной 2*N, мы получаем комплексный результат, причём выход имеет complex-conjugate симметрию. И реализовать его можно через комплексное FFT длиной N + небольшие манипуляции и на этом сэкономить вычислительные ресурсы.
Нужно сделать обратное преобразовние IFFT для комплексного входа длиной 2*N, который имеет свойство complex-conjugate симметрии. Соответствено результат будет реальным.
Правильно то, шо если мы сделали RFFT длиной 2*N упрощённым методом(CFFT длиной N), то и complex conjugate IFFT длиной 2*N мы можем вычислить через FFT длиной N?

Не совсем поняла суть вашего вопроса в части употребления обозначений N и 2*N. Например, если реального сигнал у вас длиной 2*N, то что вы принимаете за N? Это осталось непонятным. Тем не менее, я постараюсь кратко описать эту ситуацию.

Если мы пользуемся обычным классическим FFT, которое является по своей сути комплексным, то мы заполняем своим реальным сигналом действительную часть комплексного массива длиной N, а мнимую заполняем нулями. После преобразования получим на этом же месте две зеркальные половинки, из которых для дела достаточно первых половин. Зеркальная же часть здесь содержит избыточную информацию из-за того, что число коэффициентов (или частот) в результате FFT вдвое меньше числа точек. Т.е. на середине отрезка (N/2) находится частота Найквиста, выше которой частоты определить теоретически невозможно.

Это метод избыточен по вычислениям, т.к. тем же методом мы могли бы сделать FFT сразу двум функциям, запихнув вторую в мнимую часть вместо нулей. Тогда бы зеркальность оказалась нарушена, но зная свойство симметрии (действительные части симметричны, а мнимые контрсимметричны) мы могли бы получить результаты для каждой из функций, складывая или вычитая зеркальные половинки. При сложении контрсимметричные вклады самоуничтожаются, а при вычитании самоуничтожаются уже симметричные вклады. Поэтому, складывая действительную часть преобразования с зеркальной, мы получаем действительную часть 1-ой функции, а ее мнимую часть получаем вычитанием зеркала в мнимой части. Для второй функции, наоборот - действительную получаем вычитанием, а мнимую сложением.

На практике же куда больший интерес представляет вычисление вдвое более длинной функции, чем двух отрезков разных функций обычной длины. И вот тут был сделан остроумный ход. Исходную функцию, длиной 2*N, режут пополам и получают FFT-преобразование ее обеих половин за один проход FFT так, как будто это были две разные функции. Потом восстанавливают результат для каждой из них сложением и вычитанием зеркальных половин. И, наконец, делают последнюю "бабочку" FFT-преобразования над этими половинками, получая FFT-результат на всю длину массива (2*N).

Частота Найквиста только не влезает, и ее приходится запихивать в пустующую мнимую часть при постоянной составляющей (частоты 0). Это всегда возможно сделать, поскольку частота Найквиста всегда действительна, т.к. мнимую/синусную части она никогда не содержит. Всю эту операцию обычно называют реальным FFT или RFFT. Но в книжках стараются не афишировать, как она вычисляется , ограничиваясь примерами комплексного FFT.

RFFT экономнее, чем CFFT, как по занимаемой памяти (не получаем зеркального мусора и не выделяем для него места в памяти), так и по времени, но зато код становится очень противным .

Обратное преобразование IRFFT устроено подобным же образом. Там тоже складывают пополам и прокручивают вместе на мясорубке за один проход . Самое простое - не вникать во все эти премудрости, а взять готовый код. А то мне вникать пришлось, когда была задача написать RFFT и IRFFT на ассемблере x87, чтобы все расчеты были на регистрах сопроцессора и никакого другого обращения к памяти, кроме массива, не было. Как вспомню, так вздрогну .