在线咨询
中国工业与应用数学学会会刊
主管：中华人民共和国教育部
主办：西安交通大学
ISSN 1005-3085  CN 61-1269/O1
工程数学学报

工程数学学报 ›› 2019, Vol. 36 ›› Issue (1): 106-114.doi: 10.3969/j.issn.1005-3085.2019.01.009

• • 上一篇    下一篇

基于广义傅里叶变换的线性卷积算法（英）

戴银云,   易   华,   余   涛   

  1. 井冈山大学数理学院，江西  吉安  343009
  • 收稿日期:2017-04-18 接受日期:2018-06-13 出版日期:2019-02-15 发布日期:2019-04-15
  • 通讯作者: 易 华 E-mail address: 876145777@qq.com
  • 基金资助:
    江西省自然科学基金(20161BAB201017)；江西省教育厅科技项目(GJJ160758)；井冈山大学博士科研启动项目(JZB11002).

An Algorithm for Linear Convolution Based on Generalized Discrete Fourier Transform

DAI Yin-yun,   YI Hua,  YU Tao   

  1. Department of Mathematics, Jinggangshan University, Ji'an, Jiangxi 343009
  • Received:2017-04-18 Accepted:2018-06-13 Online:2019-02-15 Published:2019-04-15
  • Contact: H. Yi. E-mail address: 876145777@qq.com
  • Supported by:
    The Natural Science Foundation of Jiangxi Province (20161BAB201017); the Science and Technology Project of Department of Education of Jiangxi Province (GJJ160758); the Doctoral Research Startup Project of Jinggangshan University (JZB11002).

PDF (PC)

417

摘要： 线性卷积可以转化为循环卷积，循环卷积可以转化为频域的乘法，从而线性卷积可以采用基于FFT（(快速Fourier变换）的方法进行计算．本文给出了一种基于广义离散Fourier变换的线性卷积计算方法．本文首先分析了线性卷积和循环卷积的关系．然后，线性卷积的计算转化成一个特殊的Toeplitz矩阵与向量的乘积．然后，通过利用信号和滤波器的广义离散Fourier变换以及反变换，推导了这个乘积的快速算法．另外，本文推导方法还可以得到基于参数为$-1$的广义离散Fourier变换计算线性卷积的方法．

关键词: 广义离散傅里叶变换, 线性卷积, 循环卷积, FFT

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

中图分类号: