Abstract: Linear convolutions can be converted to circular convolutions so that a fast trans-form 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.

Key words: generalized discrete Fourier transform, linear convolution, circular convolution, FFT