Optimized bitstream encoding for compression

• US 8,791,843 B2
• Filed: 10/15/2012
• Issued: 07/29/2014
• Est. Priority Date: 10/15/2012
• Status: Active Grant

• Current Assignee: Seagate Technology LLC (Seagate Technology Holdings Plc)
• Original Assignee: LSI Corporation (Broadcom, Inc.)
• Inventors: Cohen, Earl T.
• Primary Examiner(s): JEAN PIERRE, PEGUY
• Application Number:
  US13/651,627
• Publication Number:
  US 20140104084A1
• Time in Patent Office: 652 Days
• Field of Search: 341/50, 341/51, 341/59, 341/67, 341/65, 341/87
• US Class Current: 341/51
• CPC Class Codes: H03M 7/3079 Context modeling
• CPC Class Codes: H03M 7/3084 using adaptive string matching, e.g. the Lempel-Ziv method

Abstract

An apparatus includes a first circuit and a second circuit. The first circuit may be configured to generate (i) a compressed representation of an input sequence of characters and (ii) statistics regarding one or more types of information in the compressed representation of the input sequence of characters. The second circuit may be configured to generate a compressed bitstream representation of the input sequence of characters in response to the compressed representation of the input sequence of characters and one or more of the statistics regarding the one or more types of information in the compressed representation of the input sequence of characters. The bitstream values encoding the one or more types of information are generally determined based upon a frequency of occurrence of the one or more types of information in the compressed representation of the input sequence of characters.

Claims

1. An apparatus comprising:

a first circuit configured to generate (i) a compressed representation of an input sequence of characters and (ii) statistics regarding one or more types of information in the compressed representation of the input sequence of characters, wherein the statistics comprise a histogram representation of values of a particular type of said one or more types of information; and

a second circuit configured to generate a compressed bitstream representation of the input sequence of characters in response to the compressed representation of the input sequence of characters and one or more of the statistics regarding the one or more types of information in the compressed representation of the input sequence of characters, wherein bitstream values encoding the one or more types of information are determined based upon a frequency of occurrence of the one or more types of information in the compressed representation of the input sequence of characters and using the histogram representation.

2. The apparatus according to claim 1, wherein said first circuit is configured to perform Lempel-Ziv (LZ) compression on said input sequence of characters.

3. The apparatus according to claim 1, wherein said first circuit is configured to perform a modified Lempel-Ziv (LZ) compression that generates said compressed representation of said input sequence of characters based upon a reduced representation of said input sequence of characters containing one or more codes representing repetitions of a sequence of one or more characters.

4. The apparatus according to claim 1, wherein the one or more types of information comprises a copy instruction length information.

5. The apparatus according to claim 1, wherein the one or more types of information comprises one or more of a length value, an offset value, and a flag value.

6. The apparatus according to claim 1, wherein the compressed bitstream is a loss-less representation of the input sequence of characters.

7. The apparatus according to claim 1, wherein said first circuit and said second circuit are part of a compression unit.

8. The apparatus according to claim 1, wherein said first circuit comprises one or more compression engines.

9. The apparatus according to claim 1, wherein said first circuit comprises a plurality of compression engines arranged in parallel.

10. The apparatus according to claim 1, wherein said second circuit is configured to find a first position in the histogram representation where an accumulated sum of the values of the particular type of information up through the first position is greater than or equal to one-half of a total of the values of the particular type of information.

11. The apparatus according to claim 10, wherein determining the bitstream values encoding the one or more types of information comprises encoding the positions in the histogram representation up through the first position in a minimal number of bits sufficient to distinguish each of the positions in the histogram representation up through the first position and at least one additional alternative.

12. The apparatus according to claim 11, wherein determining the bitstream values encoding the one or more types of information further comprises finding a second position in the histogram representation subsequent to the first position where the accumulated sum of the values of the type of information after the first position and up through the second position is greater than or equal to one-half of the total of the remaining values of the type of information after subtracting the values of the type of information up through the first position.

13. The apparatus according to claim 12, wherein determining the bitstream values encoding the one or more types of information further comprises encoding the positions in the histogram after the first position and up through the second position as a concatenation of the encoding of the at least one additional alternative and a minimal number of bits sufficient to distinguish each of the positions in the histogram representation after the first position and up through the second position and at least one still further alternative.

14. An apparatus comprising:

means for generating (i) a compressed representation of an input sequence of characters and (ii) statistics regarding one or more types of information in the compressed representation of the input sequence of characters, wherein the statistics comprise a histogram representation of values of a particular type of said one or more types of information; and

means for generating a compressed bitstream representation of the input sequence of characters in response to the compressed representation of the input sequence of characters and one or more of the statistics regarding the one or more types of information in the compressed representation of the input sequence of characters, wherein bitstream values encoding the one or more types of information are determined based upon a frequency of occurrence of the one or more types of information in the compressed representation of the input sequence of characters and using the histogram representation.

15. A method of optimizing bitstream encoding for compression comprising:

generating (i) a compressed representation of an input sequence of characters and (ii) statistics regarding one or more types of information in the compressed representation of the input sequence of characters, wherein the statistics comprise a histogram representation of values of a particular type of said one or more types of information; and

generating a compressed bitstream representation of the input sequence of characters in response to the compressed representation of the input sequence of characters and one or more of the statistics regarding the one or more types of information in the compressed representation of the input sequence of characters, wherein bitstream values encoding the one or more types of information are determined based upon a frequency of occurrence of the one or more types of information in the compressed representation of the input sequence of characters and using the histogram representation.