A fast 2-D DCT algorithm via distributed arithmetic optimization

The complexity of the Discrete Cosine Transform (DCT) is a concern in portable video compression devices, where multiplications are typically much more costly than additions and binary shifts. Since most conventional fast DCT algorithms exploit the algebraic structure of the DCT, their multiplicative complexity has been shown to have lower bounds. In this paper, we take advantage of the distributed arithmetic (DA) structure of the 2-D DCT. We introduce a novel fast DA-DCT algorithm based on DA optimization, which reduces the number of additions by a factor of 22, through recursive pairwise matching. On average, only 1 multiplication, 40 additions as well as 16 binary shifts are required for each DCT coefficient. The overall multiplicative complexity is 28% lower than the theoretical lower bound. Our DA-DCT is numerically equivalent to the exact, double precision floating-point 2-D DCT.