Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-10-29
2002-10-01
Morse, Gregory (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S400000, C708S402000
Reexamination Certificate
active
06460061
ABSTRACT:
FIELD OF THE INVENTION
The present invention generally relates to the 2-dimensional (2-D) discrete cosine transform (DCT), and more particularly to implementing the 2-D forward and inverse DCT on an FPGA using a polynomial transform.
BACKGROUND
The 2-D DCT is at the heart of many low-rate codecs for video compression. For example, the DCT is an integral part of the MPEG and H.261 standards. The DCT's time efficient computation is also of great interest in various communications and multi-media applications.
There are several strategies available to the digital signal processing (DSP) system engineer for realizing a DCT-based codec. One option is to use a software programmable DSP processor such as the TMS320C5x from Texas Instruments. This brings high flexibility to a design at the expense of performance. At the other end of the implementation spectrum is an ASIC solution, which provides high performance with little or no flexibility. A third option includes field programmable gate arrays (FPGAs).
FPGAs offer high-performance without sacrificing design flexibility The conventional technique for realizing a 2-D DCT is to exploit the transform separability and decompose the problem into a sequence of 1-D sub-problems. That is, first a 1-D DCT is performed on the rows, followed by a 1-D DCT on the, columns. For high-resolution N×N-pixel (N>=1024) color images, a parallel architecture that incorporates row and column, processors as well as a matrix transposition engine must be used to accommodate real-time data rates. Using distributed arithmetic (as described in U.S. Pat. No. 3,77,130 entitled, “Digital Filter for PCM Encoded Signals” to Croisier et al.) to implement a 1-D DCT on an FPGA can greatly reduce the number of configurable logic blocks (CLB s) used for the DCT.
While distributed arithmetic reduces the number of CLBs of an FPGA that are used to implement the 2-D DCT, it is desirable for economic reasons to further reduce the number of CLB used to implement the 2-D DCT.
SUMMARY OF THE INVENTION
The present invention includes a circuit arrangement that implements a 2-D forward and inverse DCT using a polynomial transform. In one embodiment, an input permutation processor reorders input sample data, wherein the reordered data samples logically form a matrix. A plurality of 1-D DCT processors are coupled to the input permutation processor. Extended diagonals passing through the matrix reference data that are provided as input to respective 1-D DCT processors, which operate in parallel. Output data from the 1-D DCT processors are provided as input data to a polynomial transform processor. The polynomial transform processor applies a polynomial transform to data from the 1-D DCTs, and output data from the polynomial transform processor are re-ordered in a prescribed order for 2-D DCT outputs.
In another embodiment the various processors and storage elements are implemented on FPGA function generators. Since the 1-D DCT processors and polynomial transform are multiplier free, usage of FPGA resources is minimized.
Various embodiments are set forth in the Detailed Description and Claims which follow.
REFERENCES:
patent: 3777130 (1973-12-01), Croisier et al.
patent: 4164023 (1979-08-01), Whitehouse et al.
patent: 5031038 (1991-07-01), Guillemot et al.
patent: 5181183 (1993-01-01), Miyazaki
patent: 5363096 (1994-11-01), Duhamel et al.
patent: 5408425 (1995-04-01), Hou
patent: 5566123 (1996-10-01), Freidin et al.
patent: 5758192 (1998-05-01), Alfke
patent: 6119080 (2000-09-01), Liu et al.
patent: 6343304 (2002-01-01), Yang et al.
H.J. Nussbaumer and P. Quandralle, “Computation of Convolutions and Discrete Fourier Transforms by Polynomial Transforms”, IBM Journal of Research and Development, vol. 22, No. 2, Mar. 1978, pp. 134-144.
James W. Cooley and John W. Tukey, “An Algorithm for the Machine Calculation of Complex Fourier Series”, Mathematics of Computation—A Quarterly Journal Edited by Harry Polachek, XIX, Nos. 89-92, 1965, pp. 297-301.
P. Duhamel and C. Guillemot, “Polynomial Transform Computation of the 2-D DCT”, IEEE International Conference on Acoustics, Speech and Signal Processing, vol. 3, ICASSP 90, Apr. 3-6, 1990, pp. 1515-1518.
S. C. Chan and K. L. Ho, “A New Two-Dimensional Fast Cosine Transform Algorithm”, IEEE Transactions on Signal Processing, formerly IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 39, No. 2, Feb. 1991, pp. 481-485.
H. R. Wu and F. J. Paoloni, “A Two-Dimensional Fast Cosine Transform Algorithm Based on Hou's Approach”, IEEE Transactions on Signal Processing, formerly IEEE Transactions on Acoustics, Speech, and Signal Processing, vol. 39, No. 2, Feb. 1991, pp. 544-546.
The Programmable Logic Data Book 1999, available from Xilinx, Inc., 2100 Logic Drive, San Jose, California 95124, pp. 3-7.
J. Prado and P. Duhamel, “A Polynomial Transform Based Computation of the 2-D DCT with Minumum Multplicative Complexity”, IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 1996, pp. 1347-1350.
Do Chat
Maunu LeRoy D.
Morse Gregory
Xilinx , Inc.
Young Edel M.
LandOfFree
2-dimensional discrete cosine transform using a polynomial... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with 2-dimensional discrete cosine transform using a polynomial..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and 2-dimensional discrete cosine transform using a polynomial... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2996444