如何使用快速傅立叶变换计算数组元素的乘积之和？

Question

我有一些二进制数组。例如，让我的数组是：

int a[] = {1, 0, 0, 0, 1, 0, 1, 0, 1}

我想根据这个公式计算值：

如何使用快速傅里叶变换计算此函数？我有一个大数组，我必须多次计算这个函数。所以，我希望能够快速计算出这个函数。

Answer 1

void main()
{
    int i,k,sum=0; 
    for(i=0;i<9;i++)
    {
        for(k=0;k<2*i;k++) 
        {
            sum + =(a[k]*a[2*i-k]; // calculating B
        }
    }
    cout<<sum;
}

Answer 2

你所做的计算基本上是一个卷积，时域中的卷积只是频率的乘法 domain.So 只需得到 a 的 FFT 并将其与自身相乘，然后执行IFFT to return to the time domain.So 总之，可以通过

计算b

b(2*i) = IFFT( FFT(a[0:2*i)]).FFT(a[0:2*i]) )

如何使用快速傅立叶变换计算数组元素的乘积之和？

How to calculate a sum of products of array elements using a fast Fourier transform?

c++

arrays

c++11

sum

fft