Methods and devices for load balancing in parallel entropy coding and decoding

• US 8,174,414 B2
• Filed: 04/13/2010
• Issued: 05/08/2012
• Est. Priority Date: 04/13/2010
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: Korodi, Gergely Ferenc, He, Dake, Yang, En-Hui, Martin-Cocher, Gaelle Christine
• Primary Examiner(s): Nguyen, Khai M
• Application Number:
  US12/758,905
• Publication Number:
  US 20110248872A1
• Time in Patent Office: 756 Days
• Field of Search: 341/51, 341/107
• US Class Current: 341/107
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code

Abstract

Devices and methods for entropy decoding a bitstream of encoded data by extracting a plurality of encoded subsequences from a payload field of the bitstream for parallel decoding on a set of parallel entropy decoders. The method includes dividing the payload of concatenated encoded subsequences into segments using a distribution function and distributing the segments amongst the set of parallel entropy decoders to balance the computational load among the parallel entropy decoders. The received bitstream includes auxiliary information inserted by the encoder to enable the decoder to entropy decode segments that begin with a portion of an encoded subsequence.

Claims

1. A method of decoding a bitstream at a decoder having two or more parallel entropy decoders, the bitstream having a payload of concatenated encoded subsequences, the method comprising:

extracting length data for the encoded subsequences from the bitstream, wherein each of the encoded subsequences is associated with a respective estimated probability defined by a context model;

partitioning the payload into a plurality of segments for parallel decoding, wherein the partitioning divides at least one of the encoded subsequences into a first part within one of the plurality of segments and a second part within another of the plurality of segments;

reading auxiliary information from the bitstream; and

decoding the plurality of segments using the two or more parallel entropy decoders, wherein the auxiliary information enables decoding of the second part without first decoding the first part.

2. The method claimed in claim 1, wherein the encoded subsequences contain codewords, and wherein the auxiliary information comprises an offset value for modifying the partitioning that divides the at least one of the encoded subsequences based on the offset value.

3. The method claimed in claim 2, wherein the offset value is a number of bits, and wherein the method comprises modifying the partitioning that divides the at least one of the encoded subsequences by the number of bits so as to align the partitioning that divides the at least one of the encoded subsequences with a codeword boundary.

4. The method claimed in claim 1, wherein the encoded subsequences have been encoded using an arithmetic encoding scheme, and wherein the auxiliary information comprises state variables for initializing one of the parallel entropy decoders to enable it to decode the second part of the at least one of the encoded subsequences.

5. The method claimed in claim 1, wherein the partitioning divides the payload into the plurality of segments and the auxiliary information comprises auxiliary information for each division between segments.

6. The method claimed in claim 1, wherein the bitstream includes a header portion, and wherein the header portion includes a first header part containing the length data and a second header part containing the auxiliary information.

7. The method claimed in claim 1, wherein partitioning includes dividing the payload into the plurality of segments such that no segment has a length longer than any other by more than one bit.

8. The method claimed in claim 1, wherein partitioning includes calculating a weighted distribution function in which each encoded subsequence has an associated weighting factor and the weighted distribution function includes multiplying the bit length of each encoded subsequence by its associated weighting factor and summing the weighted bit lengths of all the encoded subsequences.

9. The method claimed in claim 1, wherein there are more segments than parallel entropy decoders, the method further comprising distributing the segments amongst the parallel entropy decoders for the decoding.

10. The method claimed in claim 9, wherein the number of segments is an integer multiple of the number of parallel entropy decoders, and wherein distributing includes distributing the integer number of segments to each parallel entropy decoder.

11. A computer-readable medium having stored thereon computer-executable instructions which, when executed by a processor, configure the processor to execute the method claimed in claim 1.

12. A method for encoding multiple sources to generate a bitstream, the method comprising:

entropy encoding the multiple sources to generate encoded subsequences, wherein each of the encoded subsequences is associated with a respective estimated probability defined by a context model, and concatenating the encoded subsequences;

calculating a partition of the concatenated encoded subsequences into a plurality of segments, wherein the partition would divide at least one of the encoded subsequences into a first part within one of the plurality of segments and a second part within another of the plurality of segments;

determining auxiliary information required by a decoder to enable the decoder to decode the second part without first decoding the first part; and

outputting the bitstream, wherein the bitstream includes the concatenated encoded subsequences and the auxiliary information.

13. The method claimed in claim 12, wherein the encoded subsequences contain codewords, and wherein the auxiliary information comprises an offset value for modifying the partition that divides the at least one of the encoded subsequences based on the offset value.

14. The method claimed in claim 13, wherein the offset value is a number of bits for modifying the partitioning that divides the at least one of the encoded subsequences so as to align the partition that divides the at least one of the encoded subsequences with a codeword boundary.

15. The method claimed in claim 12, wherein encoding comprises encoding using an arithmetic encoding scheme, and wherein the auxiliary information comprises state variables for an entropy decoder at a point between two adjacent segments.

16. The method claimed in claim 15, further comprising decoding the first part of the at least one encoded subsequence and determining the state variables after decoding the first part.

17. The method claimed in claim 12, wherein the partition would divide the concatenated encoded subsequences into the plurality of segments and wherein the auxiliary information comprises auxiliary information for each division between segments.

18. The method claimed in claim 12, wherein the bitstream includes a header portion, and wherein the header portion includes a first header part containing length data regarding the encoded subsequences and a second header part containing the auxiliary information.

19. The method claimed in claim 12, wherein calculating includes calculating the partition such that no segment has a length longer than any other by more than one bit.

20. The method claimed in claim 12, wherein calculating includes calculating a weighted distribution function in which each encoded subsequence has an associated weighting factor and the weighted distribution function includes multiplying the bit length of each encoded subsequence by its associated weighting factor and summing the weighted bit lengths of all the encoded subsequences.

21. A computer-readable medium having stored thereon computer-executable instructions which, when executed by a processor, configure the processor to execute the method claimed in claim 12.

22. A decoder for decoding a bitstream using two or more parallel entropy decoders, the bitstream having a payload of encoded subsequences, the decoder comprising:

a processor;

a memory; and

a decoding application stored in memory and containing instructions for configuring the processor to decode the bitstream by

extracting length data for the encoded subsequences from the bitstream, wherein each of the encoded subsequences is associated with a respective estimated probability defined by a context model;

partitioning the payload into a plurality of segments for parallel decoding, wherein the partitioning divides at least one of the encoded subsequences into a first part within one of the plurality of segments and a second part within another of the plurality of segments;

reading auxiliary information from the bitstream; and

decoding the plurality of segments using the two or more parallel entropy decoders, wherein the auxiliary information enables decoding of the second part without first decoding the first part.

23. An encoder for encoding multiple sources to generate a bitstream, the encoder comprising:

a processor;

a memory; and

an encoding application stored in memory and containing instructions for configuring the processor to generate the bitstream by

entropy encoding the multiple sources to generate encoded subsequences, wherein each of the encoded subsequences is associated with a respective estimated probability defined by a context model, and concatenating the encoded subsequences;

calculating a partition of the concatenated encoded subsequences into a plurality of segments, wherein the partition would divide at least one of the encoded subsequences into a first part within one of the plurality of segments and a second part within another of the plurality of segments;

determining auxiliary information required by a decoder to enable the decoder to decode the second part without first decoding the first part; and

outputting the bitstream, wherein the bitstream includes the concatenated encoded subsequences and the auxiliary information.