Abstract
This paper presents the lowest multiplication complexity, self-recursive, radix-2 DCT II/III algorithms for any n = 2t (t ≥ 1) with implementations in signal-flow graphs and image compression. These algorithms are derived mainly using a matrix factorization technique to factor DCT II/III matrices into sparse and scaled orthogonal matrices. Although there are small length DCT II algorithms available only for n = 8 and n = 16, there is no existing self-recursive fast radix-2 DCT II/III algorithms for any n. To fill this gap, this paper presents the lowest multiplication complexity radix-2 self-recursive DCT II/III algorithms. We also attain the lowest theoretical multiplication bound for n = 8 with the new DCT II algorithm and establish new lowest bounds for DCT III for any n and for DCT II for any n ≥ 32. The paper also establishes a novel relationship between DCT II an DCT IV having sparse factors. This enables one to see the connection of most traditional factorization of DCT II/III matrices with the proposed DCT II/III matrices.
Original language | American English |
---|---|
Journal | SIAM Journal on Matrix Analysis and Applications |
Volume | 39 |
DOIs | |
State | Published - Jan 1 2018 |
Keywords
- discrete cosine transforms
- radix-2 algorithms
- self-recursive algorithms
- lowest multiplication complexity
- sparse and orthogonal factors
- signal flow graphs
- image compression
Disciplines
- Signal Processing
- Control Theory
- Numerical Analysis and Computation
- Numerical Analysis and Scientific Computing
- Theory and Algorithms