LOWEST COMPLEXITY SELF-RECURSIVE RADIX-2 DCT II/III ALGORITHMS

This paper presents the lowest multiplication complexity, self-recursive, radix-2 DCT II/III algorithms for any n = 2(t) (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.