Stable, recursive and fast algorithms for discrete sine transformations having orthogonal factors

In this paper we derive numerically stable, fast and recursive radix-2 algorithms for discrete sine transformations (DST) having sparse and orthogonal factors. These real radix-2 stable algorithms are completely recursive, fast, based on the simple orthogonal factors and solely depend on DST I–IV. Compared to most DST algorithms, our algorithms are easy to implement and use only permutations, scaling by constants, butterfly operations, and plane rotations/rotation-reflections. For a given vector x , we also analyze error bounds of computing y = Sx for the presented DST I–IV algorithms: S. A classification of these real radix-2 DST algorithms enables us to establish the excellent forward and backward stability based on the sparse and orthogonal factors. Finally we elaborate the signal flow graphs based on the presented orthogonal factorization of DST I–IV matrices.