基于广义傅里叶变换的线性卷积算法（英文）
|
摘要
线性卷积可以转化为循环卷积,循环卷积可以转化为频域的乘法,从而线性卷积可以采用基于FFT (快速Fourier变换)的方法进行计算.本文给出了一种基于广义离散Fourier变换的线性卷积计算方法.本文首先分析了线性卷积和循环卷积的关系.然后,线性卷积的计算转化成一个特殊的Toeplitz矩阵与向量的乘积.然后,通过利用信号和滤波器的广义离散Fourier变换以及反变换,推导了这个乘积的快速算法.另外,本文推导方法还可以得到基于参数为-1的广义离散Fourier变换计算线性卷积的方法.
Linear convolutions can be converted to circular convolutions so that a fast transform with a convolution property can be used to implement the computation, which method is known as the FFT-based fast algorithm of linear convolution. In this paper, a novel proof of the computation of linear convolution based on Generalized Discrete Fourier Transform(GDFT) is constructed. Firstly, a relationship of linear convolution and circular convolution is thoroughly analyzed. Secondly, the computation of the linear convolution is translated to the multiplication of a special Toeplitz matrix and the signal. Lastly, this multiplication is accomplished by the inverse GDFT of the product of the GDFTs of the signal and the filter. Furthermore, a new method about the computation of complex linear convolution is constructed by using the GDFT with parameter-1, which is not considered in the previous literatures.
Linear convolutions can be converted to circular convolutions so that a fast transform with a convolution property can be used to implement the computation, which method is known as the FFT-based fast algorithm of linear convolution. In this paper, a novel proof of the computation of linear convolution based on Generalized Discrete Fourier Transform(GDFT) is constructed. Firstly, a relationship of linear convolution and circular convolution is thoroughly analyzed. Secondly, the computation of the linear convolution is translated to the multiplication of a special Toeplitz matrix and the signal. Lastly, this multiplication is accomplished by the inverse GDFT of the product of the GDFTs of the signal and the filter. Furthermore, a new method about the computation of complex linear convolution is constructed by using the GDFT with parameter-1, which is not considered in the previous literatures.
引文
[1] Yi H, Chen Z Q, Cao Y H. High precision computation of Morlet wavelet transform for multi-period analysis of climate data[J]. Journal of Information and Computational Science, 2014, 11(17):6369-6385
[2] Fu¨rer M. Faster integer multiplication[J]. SIAM Journal on Computing, 2009, 39(3):979-1005
[3] Martinez J, Heusdens R, Hendriks R C. A generalized poisson summation formula and its application to fast linear convolution[J]. Signal Processing Letters, IEEE, 2011, 18(9):501-504
[4] Martinez J, Heusdens R, Hendriks R C. A generalized fourier domain:signal processing framework and applications[J]. Signal Processing, 2013, 93(5):1259-1267
[5] Burrus C S S, Parks T W. DFT/FFT and Convolution Algorithms:Theory and Implementation[M]. New York:John Wiley&Sons, 1991
[6] Jin X Q. Preconditioning Techniques for Toeplitz Systems[M]. Beijing:Higher Education Press, 2010
[7] Nagy J G, Plemmons R J, Torgersen T C. Iterative image restoration using approximate inverse preconditioning[J]. IEEE Transactions on Image Processing, 1996, 5(7):1151-1162
[8] Yi H, Xin S X, Yin J F. A class of algorithms for continuous wavelet transform based on the circulant matrix[J]. Algorithms, 2018, 11(3):1-17
[2] Fu¨rer M. Faster integer multiplication[J]. SIAM Journal on Computing, 2009, 39(3):979-1005
[3] Martinez J, Heusdens R, Hendriks R C. A generalized poisson summation formula and its application to fast linear convolution[J]. Signal Processing Letters, IEEE, 2011, 18(9):501-504
[4] Martinez J, Heusdens R, Hendriks R C. A generalized fourier domain:signal processing framework and applications[J]. Signal Processing, 2013, 93(5):1259-1267
[5] Burrus C S S, Parks T W. DFT/FFT and Convolution Algorithms:Theory and Implementation[M]. New York:John Wiley&Sons, 1991
[6] Jin X Q. Preconditioning Techniques for Toeplitz Systems[M]. Beijing:Higher Education Press, 2010
[7] Nagy J G, Plemmons R J, Torgersen T C. Iterative image restoration using approximate inverse preconditioning[J]. IEEE Transactions on Image Processing, 1996, 5(7):1151-1162
[8] Yi H, Xin S X, Yin J F. A class of algorithms for continuous wavelet transform based on the circulant matrix[J]. Algorithms, 2018, 11(3):1-17