Method and system for computing 8×8 DCT/IDCT and a VLSI implementation
AssigneeThe Trustees of the University of Pennsylvania
InventorFeng Pan
Life of this patent
Estimating the term…
Abstract
A method and system for computing 2-D DCT/IDCT which is easy to implement with VLSI technology to achieve high throughput to meet the requirements of high definition video processing in real time is described. A direct 2-D matrix factorization approach is utilized to compute the 2-D DCT/IDCT. The 8×8 DCT/IDCT is computed through four 4×4 matrix multiplication sub-blocks. Each sub-block is half the size of the original 8×8 size and therefore requires a much lower number of multiplications. Additionally, each sub-block can be implemented independently with localized interconnection so that parallelism can be exploited and a much higher DCT/IDCT throughput can be achieved.
Claims27
A system for computing a two-dimensional discrete cosine transform (2D-DCT) of input data, the input data including at least first through sixty-fourth input elements of an 8 row×8 column matrix X, comprising:
- a shuffler having four parallel inputs and four parallel outputs, each input receiving a respective group of sixteen rows of the first through 64th elements, wherein said shuffler processes each row of four parallel input elements (a,b,c,d) received on said four inputs in parallel and outputs four output elements (x++,x−+,x+−,x−−) in parallel for each processed input row, each output element representing a different linear combination of four corresponding input elements;
- and
- first through fourth sub-block operators (EE, EO, OE, OO) each coupled in parallel to a respective one of said four outputs of said shuffler;
- wherein said first through fourth sub-block operators each process a set of sixteen output elements from said shuffler independently, and generate respective first through fourth sets of sixteen matrix products, each set of matrix products representing a product of three independent 4×4 matrix multiplications of a respective set of said sixteen output elements output from said shuffler.
A system for computing a two-dimensional inverse discrete cosine transform (2D-IDCT) of input data, the input data including at least first through sixty-fourth input elements of an 8 row×8 column matrix Xij, where 0≦i,j≦3, comprising:
- a multiplexer that divides the input data into first to fourth 4×4 sub-matrices Xee, Xoe, Xeo, and Xoo based on whether each element has an even or odd row and column coefficient such that 16 elements having an even row and an even column are included in sub-matrix Xee, 16 elements having an odd row and even column are included in sub-matrix Xoe, 16 elements having an even row and odd column are included in sub-matrix Xeo, and 16 elements having an odd row and odd column are included in sub-matrix Xoo;
- and
- first through fourth sub-block operators (EE, EO, OE, OO) receiving said first to fourth 4×4 sub-matrices Xee, Xoe, Xeo, and Xoo, respectively, said sub-block operators processing said first to fourth 4×4 sub-matrices Xee, Xoe, Xeo, and Xoo independently and generating respective first through fourth sets of sixteen matrix products, each set of matrix products representing a product of three independent 4×4 matrix multiplications of a respective set of said sixteen input elements in said input data.
A hybrid 2D-DCT and IDCT system that receives DCT input data and IDCT input data comprising:
- a first input multiplexer having a first input that receives the DCT input data and four outputs;
- a shuffler having four inputs coupled to said four outputs of said first input multiplexer and an output;
- a second input multiplexer having a first input coupled to said output of said shuffler and four outputs;
- and
- four sub-block operators, each having an input coupled in parallel to a respective output of said second input multiplexer and each sub-block operator having sixteen outputs.
A method for switching between transforming 2D-DCT data and 2D-IDCT data, comprising the steps of:
- switching first and second multiplexers to pass the 2D-DCT input data through a shuffler then through four sub-block operators to obtain a matrix Z output data representing a 2D-DCT of the input 2D-DCT input data;
- and
- switching the first and the second multiplexers to pass the 2D-IDCT input data through the four sub-block operators and then the shuffler to obtain a matrix Z output data representing a 2D-IDCT of the input 2D-IDCT input data,
- wherein the input data comprises either video data or decoded video data, and wherein said first switching step is performed prior to encoding the video data and said second switching step is performed on the decoded video data after inverse scanning and quantization.
Dependencies are inferred from the claim text.