n-кратная свертка FFT и круговое перекрытие - PullRequest
Новая
       17

n-кратная свертка FFT и круговое перекрытие

1 голос
/ 14 февраля 2012

Описание проблемы

Я использовал теорему о свертке для эффективного вычисления свертки.Предположим, есть два реальных сигнала s1 и s2 длиной N каждый.Тогда я могу получить свертку из 

import numpy as np
import numpy.fft as fft

size = len(s1)
fft_size = int(2 ** np.ceil(np.log2(2 * size - 1))) #The size for the FFT algorithm

S1 = fft.rfft(s1, fft_size) #Take FTs
S2 = fft.rfft(s2, fft_size)

convolution = fft.irfft(S1 * S2) #Take IFT

Однако, если у меня есть k синглов, fft_size должен быть изменен, чтобы читать 

fft_size = int(2 ** np.ceil(np.log2(k * size - 1)))

, чтобы избежать кругового перекрытия.

К сожалению, я не знаю k априори.Один из вариантов - выбрать максимальное значение k_max, но я бы предпочел не использовать большие объемы памяти, если в этом нет крайней необходимости, и я бы предпочел не оценивать FT снова каждый раз при изменении k.

Вопрос

Можно ли выполнить одно из следующих действий:

  • Принимать БПФ сигнала для k=1 и "нулевую площадку в пространстве Фурье" при необходимости?
  • Предотвратить круговую упаковку в БПФ?

1 Ответ

1 голос
/ 16 февраля 2012

  1. Заполнение нулями в частотной области возможно, но требует гораздо большего вычислительного усилия (флопс), чем выполнение его во временной области.Скорее всего, IFFT, Zeropad и Re-FFT будут быстрее создавать «пространство» для каждой дополнительной быстрой свертки.

  2. Более длинный результат полной свертки должен идти куда-то, поэтомуНет, невозможно предотвратить круговую свертку при использовании БПФ.Даже заполнение нулями не мешает вычислению кругового перекрытия, оно просто гарантирует, что перекрытие в результате эквивалентно добавлению нуля.

...