2D-DCT Part 1

The forward 2D-DCT is computed from the following equation:

In the previous equation N is the block size, in our situation our block size is 8x8 so N=8, x(i, j) is the input sample and X(m,n) is the dct transformed matrix.

A straightforward implementation of the previous equation requires N⁴ multiplications. However, the DCT is a separable transform and it can be expressed in matrix notation (the row-column decomposition) as two 1D-DCT as follows:

Z=A*X*A^T

The matrix A is a NxN (8x8) matrix whose basis vectors are sampled cosines defined as:

Each NxN (8x8) matrix-matrix multiply is separated into N (8) matrix-vector products. A standard block diagram of a 2D-DCT processor with the use of 1D-DCT units is shown in the following figure:

The first unit computes the Y = A*X and the second computes the Z= Y*A^T. Each 1D-DCT unit must be capable of computing N multiplies per input sample.

The first 1D-DCT unit operates on rows of A and columns of  X. However, in each cycle we have the values of the elements in each row instead of the elements in each columns. So it is wiser to compute first the product Y = A * X^T. Thus, in the second stage we have to perform 1D-DCT in order to compute the product Z = A*Y^T. It is obvious that Z = A * (A * X^T)^T equals to Z = A * X * A^T. 

I created a simple code in python to confirm that the matrices multiplications equals to the final 2D-DCT. I confirmed the results of the row-column decomposition approach with the results of the intergrated matlab dct() function using a test block. 

In the next part, I will describe in details my implementation of the 2D-DCT in MyHDL.

All the above pictures and equations were taken from the paper "A 100 mhz 2-d 8x8 DCT/IDCT Processor for HDTV Applications" link.