Lowest Complexity Self-Recursive Radix-2 DCT II/III Algorithms

Sirani M. Perera, Jianhua Liu, Sirani K M. Perera

Research output: Contribution to journalArticlepeer-review

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 languageAmerican English
JournalSIAM Journal on Matrix Analysis and Applications
Volume39
DOIs
StatePublished - 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

Cite this