Fast and numerically stable algorithms for discrete cosine transforms

详细信息    查看全文

• 作者：Plonka ; Gerlind ; Tasche ; Manfred
• 关键词：65T50 ; 65G50 ; 15A23 ; Discrete cosine transform ; Fast algorithm ; Stable algorithm ; Fast cosine transform ; Arithmetic cost ; Numerical stability ; Factorization of cosine matrix ; Direct sum decomposition ; Sparse orthogonal matrix factors
• 刊名：Linear Algebra and its Applications
• 出版年：2005
• 出版时间：January 1, 2005
• 年：2005
• 卷：394
• 期：Complete
• 页码：309-345
• 全文大小：477 K

文摘

In this paper, we derive fast and numerically stable algorithms for discrete cosine transforms (DCT) of radix-2 length which are based on real factorizations of the corresponding cosine matrices into products of sparse, (almost) orthogonal matrices of simple structure. These algorithms are completely recursive, are simple to implement and use only permutations, scaling with Formula Not Shown, butterfly operations, and plane rotations/rotationaaareflections. Our algorithms have low arithmetic costs which compare with known fast DCT algorithms. Further, a detailed analysis of the roundoff errors for the presented DCT algorithms shows their excellent numerical stability which outperforms a real fast DCT algorithm based on polynomial arithmetic.