Method and apparatus for fast digital signal decoding

Claim 1

A method for decompressing a compressed data bitstream, comprising the steps of: Huffman decoding a variable length string in said data bitstream to produce an output therefrom in the form of a fixed length set of symbols contained in a data block; classifying said data block for sparseness based upon data occupancy within said data block, wherein said classifying step further comprises: classifying said data blocks in accordance with a classification scheme wherein each data block is defined as a sparse matrix H, and where each of said data blocks is placed into one of the following classes based upon data occupancy within said data block: Type-0 -- only H[0,0] is nonzero; Type-1 -- only one of the H[i,j] is nonzero and H[0,0] is zero; Type-2 -- only an upper 2×2 submatrix of H has nonzero values, where some or all of H[0,0], H[0,1], H[1,0] and H[1,1] are non-zero; Type-3 -- only an upper 4×4 submatrix of H has nonzero values, where some or all of H[i,j], i=0, 1, . . . , 3, j=0, 1, . . . , 3 are nonzero; and Type-4 -- H is not a member of any of the above-mentioned classes, where the occupancy pattern in H is random; inverse quantizing to convert said symbols in said data block into a set of values adapted for an inverse discrete cosine transform calculation; and performing an inverse discrete cosine transform ("IDCT") operation based upon data block classification; wherein the overall number of calculations performed during said IDCT operation are a function of the data sparseness within said data block.

Claim 2

A method for decompressing a compressed data bitstream, comprising the steps of: Huffman decoding a variable length string in said data bitstream to produce an output therefrom in the form of a fixed length set of symbols contained in a data block; classifying said data block for sparseness based upon data occupancy within said data block, wherein said classifying step further comprises: classifying said data blocks in accordance with a classification scheme wherein each data block is defined as a sparse matrix H, and where each of said data blocks is placed into one of the following classes based upon data occupancy within said data block: Type-0 -- only H[0,0] is nonzero; Type-1 -- only one of the H[i,j] is nonzero and H[0,0] is zero; Type-2 -- only an upper 2×2 submatrix of H has nonzero values, where some or all of H[0,0], H[0,1], H[1,0] and H[1,1] are non-zero; Type-3 -- only an upper 4×4 submatrix of H has nonzero values, where some or all of H[i,j], i=0, 1, . . . , 3, j=0, 1, . . . , 3 are nonzero; and Type-4 -- H is not a member of any of the above-mentioned classes, where the occupancy pattern in H is random; inverse quantizing to convert said symbols in said data block into a set of values adapted for an inverse discrete cosine transform calculation; and performing an inverse discrete cosine transform ("IDCT") operation based upon data block classification; wherein the overall number of calculations performed during said IDCT operation are a function of the data sparseness within said data block.

Claim 9

An apparatus for decompressing a compressed data bitstream, comprising: a Huffman decoder for decoding a variable length string in said data bitstream and for providing an output in the form of a fixed length set of symbols contained in a data block; means for classifying each said data block for sparseness based upon data occupancy within said data block, said means for classifying further comprising; means for selecting data block type in accordance with a classification scheme where each data block is based upon a sparse matrix H, and where each of said data blocks is placed into one of the following classes based upon data occupancy within said data block: Type-0 -- only H[0,0] is nonzero; Type-1 -- only one of the H[i,j] is nonzero and H[0,0] is zero; Type-2 -- only an upper 2×2 submatrix of H has nonzero values, where some or all of H[0,0], H[0,1], H[1,0] and H[1,1] are non-zero; Type-3 -- only an upper 4×4 submatrix of H has nonzero values, where some or all of H[i,j], i=0, 1, . . . , 3, j=0, 1, . . . , 3 are nonzero; and Type-4 -- H is not a member of any of the above-mentioned classes, where the occupancy pattern in H is random; an inverse quantizer for converting said symbols in each data block into a set of values appropriate for an inverse discrete cosine transform calculation; and a processor for performing an inverse discrete cosine transform ("IDCT") operation based upon data block classification; wherein the overall number of calculations performed during said IDCT operation are a function of data sparseness within each of said data blocks.

Claim 10

An apparatus for decompressing a compressed data bitstream, comprising: a Huffman decoder for decoding a variable length string in said data bitstream and for providing an output in the form of a fixed length set of symbols contained in a data block; means for classifying each said data block for sparseness based upon data occupancy within said data block, said means for classifying further comprising; means for selecting data block type in accordance with a classification scheme where each data block is based upon a sparse matrix H, and where each of said data blocks is placed into one of the following classes based upon data occupancy within said data block: Type-0 -- only H[0,0] is nonzero; Type-1 -- only one of the H[i,j] is nonzero and H[0,0] is zero; Type-2 -- only an upper 2×2 submatrix of H has nonzero values, where some or all of H[0,0], H[0,1], H[1,0] and H[1,1] are non-zero; Type-3 -- only an upper 4×4 submatrix of H has nonzero values, where some or all of H[i,j], i=0, 1, . . . , 3, j=0, 1, . . . , 3 are nonzero; and Type-4 -- H is not a member of any of the above-mentioned classes, where the occupancy pattern in H is random; an inverse quantizer for converting said symbols in each data block into a set of values appropriate for an inverse discrete cosine transform calculation; and a processor for performing an inverse discrete cosine transform ("IDCT") operation based upon data block classification; wherein the overall number of calculations performed during said IDCT operation are a function of data sparseness within each of said data blocks.