2-D discrete cosine transforms on a fine grain array processor

The 2-D DCT has been an industry standard in image data compression. Since its first introduction, a number of fast algorithms and technique have been introduced. Most of them were implemented using specialized VLSI chips. In this paper we present an efficient systolic 2-D DCT algorithm on a 2-D mesh fine-grained array processor. Our algorithm reads non-skewed input subimages and generates the output in non-skewed form with only a small amount of extra processors. It uses the minimum number of multiplications by employing modified small n algorithms. Our implementation of the 2-D DCT on the Micro Grained Array Processor (MGAP), which is a fine-grained and mesh-connected array processor being developed at the Penn State University, exploits massive parallelism. As a result the 2-D DCT of size 8×8 and 16×16 pixels for 256×256 pixel images can be computed at real time processing rates.