Complexity reduction, self/completely recursive, radix-2 DCT I/IV algorithms

Abstract This paper proposes fast, self/completely recursive, radix-2 Discrete Cosine Transform (DCT) of types I/IV algorithms. Implementations of these new algorithms are stated through signal-flow graphs. These algorithms are derived mainly using a matrix factorization technique to factor the DCT I/IV matrices into sparse and scaled orthogonal matrices. This paper fills the gap of addressing the remaining DCTs in connection to our former work in the lowest multiplication complexity, self recursive, radix-2 DCT II/III algorithms. There has been no radix-2 DCT-I algorithm which is self recursive and has sparse and scaled orthogonal factors as proposed in this paper. The paper also establishes a novel relationship between DCT-I and DCT-III matrices having sparse factors for any n = 2 t where t ≥ 1 . This enables one to observe all traditional completely recursive DCT-I algorithms as the self recursive DCT-I algorithm proposed in this paper. Apart from the novel DCT-I algorithm, we also establish a novel completely recursive DCT-IV algorithm which executes recursively with the lowest multiplication complexity, self recursive, radix-2 DCT-II algorithm which was derived in our former paper. The proposed DCT-IV algorithm attains the lowest possible multiplication counts.