Fast parsing of variable-to-fixed-length codes

• US 8,004,431 B2
• Filed: 12/04/2009
• Issued: 08/23/2011
• Est. Priority Date: 12/09/2008
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Reznik, Yuriy
• Primary Examiner(s): JeanPierre; Peguy
• Application Number:
  US12/631,215
• Publication Number:
  US 20100141489A1
• Time in Patent Office: 627 Days
• Field of Search: 341/67, 341/50, 341/51, 341/56
• US Class Current: 341/67
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

Methods and systems for parsing and decoding compressed data are provided. Random segments of the compressed data may be decompressed and positioned appropriately in the corresponding uncompressed data set. The methods and systems utilize variable to fixed length (VF) coding techniques. For some applications, the VF coding techniques may be implemented within media encoders, decoders, or combined encoder-decoders (CODECs).

Claims

1. A method comprising:

storing in memory a data structure that is representative of a list of base codewords in lexicographic order, wherein there is one base codeword for each level of a variable to fixed length code tree that includes a fixed length code;

selecting a fixed length code from a compressed data set comprising a plurality of fixed length codes;

determining the based codeword associated with the selected fixed length code; and

determining the length of a word represented by the selected fixed length code based on the base codeword associated with the selected fixed length code.

2. The method of claim 1, wherein the base codeword for each level of the variable to fixed length code tree that includes a fixed length code is representative of the smallest fixed length code at each level of the variable to fixed length code tree that includes a fixed length code.

3. The method of claim 1, wherein the data structure comprises an array.

4. The method of claim 1, wherein the data structure comprises a linked list.

5. The method of claim 1, wherein the data structure comprises a binary search tree.

6. The method of claim 1, wherein the data structure comprises a digital search tree.

7. The method of claim 1, further comprising determining a segment associated with the selected fixed length code.

8. The method of claim 1, wherein the compressed data set comprises a compressed video stream.

9. An apparatus comprising:

a memory configured to;

store a data structure that is representative of a list of base codewords in lexicographic order, wherein there is one base codeword for each level of a variable to fixed length code tree that includes a fixed length code;

a processor configured to;

select a fixed length code from a compressed data set comprising a plurality of fixed length codes;

determine the based codeword associate with the selected fixed length code; and

determine the length of a word represented by the selected fixed length code based on the base codeword associated with the selected fixed length code.

10. The apparatus of claim 9, wherein the base codeword for each level of the variable to fixed length code tree that includes a fixed length code is representative of the smallest fixed length code at each level of the variable to fixed length code tree that includes a fixed length code.

11. The apparatus of claim 9, wherein the data structure comprises an array.

12. The apparatus of claim 9, wherein the data structure comprises a linked list.

13. The apparatus of claim 9, wherein the data structure comprises a binary search tree.

14. The apparatus of claim 9, wherein the data structure comprises a digital search tree.

15. The apparatus of claim 9, wherein the processor is further configured to determine a segment associated with the selected fixed length code.

16. The apparatus of claim 9, wherein the compressed data set comprises a compressed video stream.

17. An apparatus comprising:

means for storing in memory a data structure that is representative of a list of base codewords in lexicographic order, wherein there is one base codeword for each level of a variable to fixed length code tree that includes a fixed length code;

means for selecting a fixed length code from a compressed data set comprising a plurality of fixed length codes;

means for determining the based codeword associated with the selected fixed length code; and

means for determining the length of a word represented by the selected fixed length code based on the base codeword associated with the selected fixed length code.

18. The apparatus of claim 17, wherein the base codeword for each level of the variable to fixed length code tree that includes a fixed length code is representative of the smallest fixed length code at each level of the variable to fixed length code tree that includes a fixed length code.

19. The apparatus of claim 17, wherein the data structure comprises an array.

20. The apparatus of claim 17, wherein the data structure comprises a linked list.

21. The apparatus of claim 17, wherein the data structure comprises a binary search tree.

22. The apparatus of claim 17, wherein the data structure comprises a digital search tree.

23. The apparatus of claim 17, further comprising means for determining a segment associated with the selected fixed length code.

24. The apparatus of claim 17, wherein the compressed data set comprises a compressed video stream.

25. A computer-readable medium, comprising instructions that when executed perform a method comprising:

storing in memory a data structure that is representative of a list of base codewords in lexicographic order, wherein there is one base codeword for each level of the variable to fixed length code tree that includes a fixed length code;

selecting a fixed length code from a compressed data set comprising a plurality of fixed length codes;

determining the based codeword associated with the selected fixed length code; and

determining the length of a word represented by the selected fixed length code based on the base codeword associated with the selected fixed length code.