2007/10/10 by Ning Chen, Zhiyuan Yan, Chen, Ning +1 · 1 citation
Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Digital Filter Design and Implementation #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Low-power high-performance VLSI design #Numerical Methods and Algorithms #cs.CC #cs.IT #math.CO #math.IT
paper · pdf · doi:10.48550/arxiv.0710.1879
11 pages, submitted to IEEE Transactions on Signal Processing
openalex publication_date 2007/10/10 · arxiv created 2008/10/23 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we first propose a novel common subexpression elimination (CSE) algorithm for matrix-vector multiplications over characteristic-2 fields. As opposed to previously proposed CSE algorithms, which usually focus on complexity savings due to recurrences of subexpressions, our CSE algorithm achieves two types of complexity reductions, differential savings and recurrence savings, by taking advantage of the cancelation property of characteristic-2 fields. Using our CSE algorithm, we reduce the additive complexities of cyclotomic fast Fourier transforms (CFFTs). Using a weighted sum of the numbers of multiplications and additions as a metric, our CFFTs achieve smaller total complexities than previously proposed CFFTs and other FFTs, requiring both fewer multiplications and fewer additions in many cases.