Fast and numerically stable algorithms for discrete cosine transforms

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 2, butterfly operations, and plane rotations/rotation-reflections. 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.