System for compression and decompression of video data using discrete cosine transform and coding techniques

• US 5,270,832 A
• Filed: 04/14/1992
• Issued: 12/14/1993
• Est. Priority Date: 03/14/1990
• Status: Expired due to Term

• Current Assignee: LSI Logic Corporation (Broadcom, Inc.)
• Original Assignee: C-Cube Corporation (Broadcom, Inc.)
• Inventors: Balkanski, Alexandre, Kirkpatrick, James, Purcell, Steve
• Primary Examiner(s): Coles, Sr., Edward L.
• Assistant Examiner(s): GRANT II, JEROME
• Application Number:
  US07/870,122
• Time in Patent Office: 609 Days
• Field of Search: 358/400, 358/401, 358/426, 358/261.1, 358/261.2, 358/261.3, 358/261.4, 358/426, 358/427, 358/262.1, 358/432, 358/433, 358/435, 358/479, 382/56
• US Class Current: 382/246
• CPC Class Codes: H04N 19/13 Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC]
• CPC Class Codes: H04N 19/42 characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation H04N19/635 takes precedence
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/91 Entropy coding, e.g. variable length coding [VLC] or arithmetic coding

Abstract

A digital video compression system and an apparatus implementing this system are disclosed. Specifically, matrices of pixels in the RGB signal format are converted into YUV representation, including a step of selectively sampling the chrominance components. The signals are then subjected to a discrete cosine transform (DCT). A circuitry implementing the DCT in a pipelined architecture is provided. A quantization step eliminates DCT coefficients having amplitude below a set of preset thresholds. The video signal is further compressed by coding the elements of the quantized matrices in a zig-zag manner. This representation is further compressed by Huffman codes. Decompression of the signal is substantially the reverse of compression steps. The inverse discrete cosine transform (IDCT) may be implemented by the DCT circuit. Circuits for implementing RGB to YUV conversion, DCT, quantization, coding and their decompression counterparts are disclosed. The circuits may be implemented in the form an integrated circuit chip.

Claims

1. A system for compression and decompression of video images constituted by a stream of composite pixels, each pixel being represented by data of a plurality of luminance and chrominance component types, comprising:

block memory means for, during compression, sorting and storing said stream of composite pixels into single-component type data blocks and for providing in predetermined order said single-component type data blocks and for, during decompression, receiving and storing said single-component type data blocks and for reconstituting said stream of composite pixels; and

means for compressing and decompressing of said single-component type data blocks.

2. A method for compression and decompression of video images constituted by a stream of composite pixels, each pixel being represented by data of a plurality of luminance and chrominance component types, comprising the steps of:

providing block memory means for, during compression, sorting and sorting said stream of composite pixels into single-component type data blocks and for providing in predetermined order said single-component type data blocks and for, during decompression, receiving and storing said single-component type data blocks and for reconstituting said stream of composite pixels; and

providing compression and decompression of said single-component type data blocks.

3. A method for data compression and decompression, comprising:

providing a video interface means for receiving and transmitting digitized images as a stream of composite pixels, each composite pixel being represented by data of a plurality of chrominance and luminance types;

providing block memory means for receiving and sorting, during data compression, said stream of composite pixels from said video interface means into single-component type data blocks, and for receiving and reconstituting, during data decompression, single-component type data blocks into said stream of composite pixels;

providing a discrete cosine transform means for performing, during data compression, a 2-dimensional discrete cosine transform on single-component type data blocks received from said block memory means, and providing coefficients of said 2-dimensional discrete cosine transform, and for performing, during data decompression, a 2-dimensional inverse discrete cosine transform, and providing as output data said coefficients of said 2-dimensional inverse discrete cosine transform to said block memory means as single-component type data blocks;

providing a quantization means for attenuating, during data compression, higher frequency coefficients of said 2-dimensional discrete cosine transform, and for partially restoring, during data decompression, said higher frequency coefficients of said 2-dimensional discrete cosine transform, in preparation for said 2-dimensional inverse discrete cosine transform;

providing a zig-zag means for rearranging, during data compression, said coefficients of said 2-dimensional discrete cosine transform from "sequential" order into "zig-zag" order, and for rearranging, during data decompression, said zig-zag ordered coefficients of said 2-dimensional discrete cosine transforms from a "zig-zag" order to a "sequential" order;

providing a data packing and unpacking means for packing, during data compression, said "zig-zag" ordered coefficients of said 2-dimensional discrete cosine transform as run length-represented coefficients of said 2-dimensional discrete cosine transform, said run length-represented coefficients of said 2-dimensional discrete cosine transform represent runs of zero coefficients as run lengths of zero coefficients, and for unpacking, during data decompression, said run length-represented coefficients of said 2-dimensional discrete cosine transform to said "zig-zag" ordered coefficients of said 2-dimensional discrete cosine transform;

providing a Huffman coding/decoding means for coding, during data compression, said run length-represented coefficients of said 2-dimensional discrete cosine transform into Huffman codes, and for decoding, during data decompression, said Huffman codes into said run length-represented coefficients of said 2-dimensional discrete cosine transform;

providing a host interface means for transmitting, during data compression, said Huffman codes to a host computer, and for retrieving, during data decompression, said Huffman codes from a host computer.

4. A system for data compression and decompression, comprising:

video interface means for receiving and transmitting digitized images as a stream of composite pixels, each composite pixel being represented by data of a plurality of chrominance and luminance component types;

block memory means for receiving and sorting, during data compression, said stream of composite pixels from said video interface means into single-component type data blocks, and for receiving and reconstituting, during data decompression, single-component type data blocks into said stream of composite pixels;

discrete cosine transform means for performing, during data compression, a 2-dimensional discrete cosine transform on single-component type data blocks received from said block-memory means, and providing coefficients of said 2-dimensional discrete cosine transform, and for performing, during data decompression, a 2-dimensional inverse discrete cosine transform, and providing as output data said coefficients of said 2-dimensional inverse discrete cosine transform to said block memory means as single-component type data blocks;

quantization means for attenuating, during data compression, higher frequency coefficients of said 2-dimensional discrete cosine transform, and for partially restoring, during data decompression, said higher frequency coefficients of said 2-dimensional discrete cosine transform, in preparation for said 2-dimensional inverse discrete cosine transform;

zig-zag means for rearranging, during data compression, said coefficients of said 2-dimensional discrete cosine transform from "sequential" order into "zig-zag" order, and for rearranging, during data decompression, said zig-zag ordered coefficients of said 2-dimensional discrete cosine transform from a "zig-zag" order to a "sequential" order;

data packing and unpacking means for packing, during data compression, said "zig-zag" ordered coefficients of said 2-dimensional discrete cosine transform as run length-represented coefficients of said 2-dimensional discrete cosine transform, and for unpacking, during data decompression, said run length-represented coefficients of said 2-dimensional discrete cosine transform to said "zig-zag" ordered coefficients of said 2-dimensional cosine transform;

Huffman coding/decoding means for coding, during data compression, said run length-represented coefficients of said 2-dimensional discrete cosine transform into Huffman codes, and for decoding, during data decompression, said Huffman codes into said run length-represented coefficients of said 2-dimensional discrete cosine transform;

host interface means for transmitting, during data compression, said Huffman codes to a host computer, and for retrieving, during data decompression, said Huffman codes from a host computer.

5. A system as in claim 4, for data compression and decompression, wherein said video interface means comprises:

RGB-to-YUV means for translating video data from RGB representation to YUV representation, and vice versa; and

data synchronization means for providing synchronization signals during data decompression.

6. A system as in claim 5, for data compression and decompression, wherein said video interface means further comprises external buffer memory address generation means for generating external buffer memory address for storing video data in an external video memory buffer.

7. A system as in claim 4 for data compression and decompression, wherein said Huffman coding/decoding means comprises:

first-in-first-out memory (FIFO) means for storing said run length-represented coefficients of said 2-dimensional discrete cosine transform;

Huffman table means for storing and providing Huffman code encoding tables during compression and Huffman code decoding tables during decompression;

coding means for translating said run length-represented coefficients of said 2-dimensional discrete cosine transform into Huffman codes using said Huffman code encoding tables; and

decoding means for translation of said Huffman codes to said run length-represented coefficients of said 2-dimensional discrete cosine transform using said Huffman code decoding tables.

8. A system as in claim 7 for data compression and decompression, wherein said coding means comprises:

read control means for requesting a run length represented coefficient of said 2-dimensional discrete cosine transform;

coding address means for providing an address constructed from said run length-represented coefficient of said 2-dimensional discrete cosine transform to said Huffman table means for requesting an entry in said Huffman code encoding tables; and

Huffman code output means for providing said entry in said Huffman code encoding tables as output Huffman code.

9. A system as in claim 7 for data compression and decompression, wherein said decoding means comprises:

Huffman code receiving means for receiving a Huffman code;

decoding address means for providing an address, constructed from either said Huffman code or a next address, to said Huffman table means for requesting an entry in said Huffman code decoding tables;

decoding control means for examining said entry of said Huffman code decoding tables to determine if said entry of said Huffman code decoding tables is a run-length represented coefficient of said 2-dimensional discrete cosine transform or comprises a next address, and for providing said next address to said decoding address means when said entry of said Huffman code decoding table comprises a next address; and

Huffman decode output means for providing said run-length represented coefficient of said 2-dimensional discrete cosine transform as an output Huffman decoded datum.

10. A system as in claim 4, for computing a 2-dimensional discrete cosine transform and a 2-dimensional inverse discrete cosine transform, wherein said discrete cosine transform means comprises:

discrete cosine transform processor means for selectably providing coefficients of a discrete cosine transform and coefficients of an inverse discrete cosine transform;

row storage means for temporarily storing intermediate data of said 2-dimensional discrete cosine transform, and intermediate data of said 2-dimensional inverse discrete cosine transform;

input selection means for alternatively receiving, during computation of said 2-dimensional discrete cosine transform, data from said block memory means and intermediate data of said 2-dimensional discrete cosine transform from said row storage means for transmitting to said discrete cosine transform processor means, and for alternatively receiving, during computation of said 2-dimensional inverse discrete cosine transform, input data and said intermediate data of said 2-dimensional inverse discrete cosine transform from said row storage means for transmitting to said discrete cosine transform processor means; and

row/column separation means for, during computation of said 2-dimensional discrete cosine transform, separating from said coefficients of said discrete cosine transform said coefficients of said 2-dimensional discrete cosine transform and said intermediate data of said 2-dimensional discrete cosine transform, for transmitting said coefficients of said 2-dimensional discrete cosine transform as output data and said intermediate data of said 2-dimensional discrete cosine transform to said row storage means, for, during computation of said 2-dimensional inverse discrete cosine transform, separating from said coefficients of said inverse discrete cosine transform said coefficients of said 2-dimensional inverse discrete cosine transform and said intermediate data of said 2-dimensional inverse discrete cosine transform, and for transmitting said coefficients of said 2-dimensional inverse discrete cosine transform to said block memory means, and for transmitting said intermediate data of said 2-dimensional inverse discrete cosine transform to said row storage means.

11. A system as in claim 10, wherein said row storage means comprises:

memory means for storing intermediate data of a 2-dimensional discrete cosine transform during data compression and for storing intermediate data for a 2-dimensional inverse discrete cosine transform during data decompression, said memory means allows reading and writing a pair of said intermediate data at a time; and

address generator means for generating addresses for read/write access reading and writing said pair of said intermediate data to said memory means.

12. A system as in claim 11, wherein said memory means comprises:

an odd plane of a plurality of memory cells, for storing a first datum of said pair of said intermediate data; and

an even plane of a plurality of memory cells, for storing a second datum of said pair of said intermediate data.

13. A system as in claim 12, wherein said memory means is accessed by a method comprising the steps of:

providing, in order, a first and a second square matrices of the same dimension, and each matrix with an even number of rows and column, said matrices are provided two entries at a time row-by-row;

writing said first matrix into said memory means two entries at a time, in an order such that, in the beginning of the writing the first row, the first of said two entries is written into said odd plane, and the second of said two entries is written into said even plane, and said order is maintained throughout said first row, and said order is reversed at the beginning of the second row, such that the first of said two entries is written into said even plane, and the second of said two entries is written into said odd plane, said order is reversed alternatively until said first matrix is completely written into said memory means; and

reading said first matrix two entries at a time column-by-column until the entire first matrix is read, and writing said second matrix two entries at a time row-by-row into the memory locations of said memory means previously occupied by each two entries of said first matrix read, and said writing of said second matrix is in an order substantially the same as described for writing said first matrix.

14. A system as in claim 10, for computing a 2-dimensional discrete cosine transform and a 2-dimensional inverse discrete cosine transform, wherein said discrete cosine transform processor means comprises:

a first plurality of latches for receiving a first, second, third and fourth data;

first summing means for selectably computing a first sum or a difference of said first and second data, and for selectably computing a second sum or difference for said third and fourth data;

a second plurality of latches for receiving, storing and transmitting as first result said first sum or difference and as a second result said second sum or difference;

first multiplication means for selectably performing a first multiplication of said first result with 2 cos (pi/8), 2 cos (pi/4), 2 cos (3pi/8) and 1;

a third plurality of latches for receiving, storing and transmitting result of said first multiplication and for receiving from said second plurality of latches, storing and transmitting said second result;

first multiplexor means for selecting a first multiplexed datum from said result of said first multiplication and said first result in said second plurality of latches;

second multiplexor means for selecting a second multiplexed datum form said result of said first multiplication and said second result in said third plurality of latches;

second summing means for computing a third sum or difference of said first multiplexed datum and said second result stored in said third plurality of of latches;

third multiplexor means for selecting a third multiplexed datum from said second result stored in said third plurality of of latches and said third sum or difference;

a fourth plurality of latches for receiving said second multiplexed datum and said third multiplexed datum;

a plurality of multiplexors for selecting from said fourth plurality of latches a fourth, fifth, sixth and seventh multiplexed data;

third summing means for selectably providing a fourth sum or difference of said fourth and fifth multiplexed data, and for selectably providing a fifth sum or difference of said sixth and seventh multiplexed data;

a fifth plurality of latches for receiving and storing said fourth sum or difference, and said fifth sum or difference;

a second multiplication means for selectably performing a second multiplication of said fourth sum and 2 cos (pi/8), 2 cos (pi/4), or 2 cos (3pi/8) or 1;

a sixth plurality of latches for receiving and storing the result of said second multiplication and said fifth sum or difference;

fourth multiplexor means for selecting an eighth multiplexed datum from said result of said second multiplication stored in said sixth plurality of latches and said fourth sum or difference;

fourth summing means for computing a sixth sum or difference of said eighth multiplexed datum and said fifth sum or difference stored in said sixth plurality of latches;

fifth multiplexor means for selecting a ninth multiplexed datum from said fifth sum or difference stored in said sixth plurality of latches;

sixth multiplexor means for selecting a tenth multiplexed datum from said sixth sum or difference and said fifth sum or difference stored in said sixth plurality of latches;

a seventh plurality of latches for receiving and storing said ninth multiplexed datum and said tenth multiplexed datum;

fifth summing means for providing a seventh sum of said ninth and tenth multiplexed data, and for selectably providing a eighth sum or difference of said ninth and tenth multiplexed data; and

an eighth plurality of latches for receiving and storing said seventh sum and said eighth sum.