.png){kind=icon}
.png){kind=icon}
Return
Fast Weighted Transforms for Linear Convolution
.png){kind=icon}
PRE
AI
DOI：10.1109/TSP.2025.3637157.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Convolution is fundamental in digital signal processing across many applications. Existing works enable <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ N $</tex-math> </inline-formula>-point linear convolution via <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$ N $</tex-math> </inline-formula>-point right-angle circular convolution (RCC) based on weighted transforms, effectively removing the need for zero padding. However, these methods are constrained by their choice of weights, which impacts the complexity of weight-related multiplications at the start of the transform and the end of the inverse transform. This limitation leads to either reduced accuracy or increased complexity in weighted Fourier transform (WFT)-based convolution, as well as restricted transform lengths in weighted Fermat number transform (WFNT)-based convolution. In this work, we address these challenges by merging the multiplications by weights into the butterfly structures with arbitrary power-of-2 radix for both WFT and WFNT. We also propose an extraction method to accommodate negative and complex numbers. Our work ensures that weights do not increase complexity, thereby improving accuracy and reducing complexity in WFT-based convolution, while allowing for a broader range of transform lengths in WFNT-based convolution.
Keywords:
Linear convolution
discrete Fourier transform
number theoretic transform
fast weighted transform
weighted Fourier transform
weighted Fermat number transform
Journal
I
IF:
5.8
Papers:
276
Citations:
0