我们知道\(FFT\)是一个循环卷积。
本质上的离散傅里叶变换满足的是这个性质:
\]
但是由于我们做的长度足够大(\(n\)足够大)所以这种循环卷积卷不回去。
这导致我们只能做特定长度的\(FFT,n=2^w\)
如果我们需要做任意长度循环卷积呢?
其实稍微推推式子就可以了。。。
只说\(DFT\),\(IDFT\)也类似。
其实我们要求的是这样一个多项式:
\]
也就是所谓的点值表达式。
那么也就是要求:
\]
这样就可以用我们的小\(trick\)个换成卷积形式了。
\]
这样可以拆了:
\]
卷积形式吧!
也就是说
我们做一次任意长度循环卷积需要\(FFT\)上9次。。。
常数还是蛮大的。
有一种神仙的办法就是把虚部压进去一起\(DFT\),我还没搞太明白。
晚上再去看吧。
本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:「笔记」多项式任意长度循环卷积 - Python技术站