PARALLEL ENTROPY CODING AND DECODING METHODS AND DEVICES

• US 20110200104A1
• Filed: 02/18/2010
• Published: 08/18/2011
• Est. Priority Date: 02/18/2010
• Status: Active Grant

• Current Assignee: Malikie Innovations Limited (Key Patent Innovations Limited)
• Original Assignee: Blackberry Limited
• Inventors: KORODI, Gergely Ferenc, Yang, En-Hui, He, Dake
• Granted Patent: US 8,487,791 B2
• Time in Patent Office: Days
• US Class Current: 375/240.12
• CPC Class Codes: H03M 7/40 Conversion to or from variable length codes, e.g. Shannon-Fano code, Huffman code, Morse code
• 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/436 using parallelised computational arrangements
• CPC Class Codes: H04N 19/44 Decoders specially adapted therefor, e.g. video decoders which are asymmetric with respect to the encoder
• CPC Class Codes: H04N 19/46 Embedding additional information in the video signal during the compression process H04N19/517, H04N19/68, H04N19/70 take precedence
• CPC Class Codes: H04N 19/61 in combination with predictive coding

Abstract

A method for entropy coding data using parallel entropy coders to encode an input sequence as a plurality of encoded subsequences, which are then combined to form an output bitstream. The input sequence is separated into subsequences on the basis of a context model. A method for entropy decoding a bitstream of encoded data by extracting a plurality of encoded subsequences from the bitstream and entropy decoding the encoded subsequences in parallel to generate a plurality of decoded subsequences, which are then interleaved based on a context model to produce a reconstructed sequence.

Claims

1. A method for encoding of an input sequence of symbols, the symbols belonging to a finite alphabet, the method comprising:

for each symbol in the input sequence, assigning the symbol to one of N subsequences of symbols, based on an estimated probability given by a context model;

encoding the N subsequences in parallel by using N respective entropy coders to generate N respective encoded subsequences; and

outputting a bitstream, wherein the bitstream includes the N encoded subsequences and information for locating each of the N encoded subsequences.

2. The method claimed in claim 1, wherein assigning the symbol to one of N subsequences comprises:

determining the estimated probability associated with that symbol based on the context model, and

appending that symbol to symbols for said one of N subsequences.

3. The method claimed in claim 2, wherein the context model comprises an adaptive context model, and wherein assigning the symbol to one of N subsequences further comprises updating the adaptive context model after each appending operation.

4. The method claimed in claim 2, further comprising detecting a flush event, and wherein the encoding the N subsequences is performed in response to detecting the flush event.

5. The method claimed in claim 4, wherein the input sequence of symbols comprises video data, and wherein the flush event comprises an end-of-frame or end-of-slice.

6. The method claimed in claim 2, further comprising allocating a storage element for each of the N subsequences, and wherein each of the storage elements stores its respective subsequence of symbols.

7. The method claimed in claim 1, wherein outputting the bitstream includes outputting a prefix and a payload, wherein the prefix contains the information for locating and the payload contains the N encoded subsequences.

8. The method claimed in claim 7, wherein the information for locating comprises a length value for each of the N encoded subsequences.

9. An encoder for encoding an input sequence of symbols, the symbols belonging to a finite alphabet, the encoder comprising:

a processor;

a memory; and

an encoding application stored in memory and containing instructions for configuring the processor to encode the input sequence by

for each symbol in the input sequence, assigning the symbol to one of N subsequences of symbols, based on an estimated probability given by a context model;

encoding the said N subsequences in parallel by using N respective entropy coders to generate N respective encoded subsequences; and

outputting a bitstream, wherein the bitstream includes the N encoded subsequences and information for locating each of the N encoded subsequences.

10. The encoder claimed in claim 9, wherein the encoding application and processor comprise:

a context modeling component and demultiplexer configured to separate the input sequence into the N subsequences of symbols,

N entropy coders configured to encode the N respective subsequences of symbols in parallel and to output the N respective encoded subsequences, and

a multiplexer configured to generate the bitstream.

11. The encoder claimed in claim 9, wherein the encoding application contains instructions for configuring the processor to assign each symbol to one of N subsequences by

determining the estimated probability associated with that symbol based on the context model, and

appending that symbol to symbols for said one of N subsequences.

12. The encoder claimed in claim 11, wherein the encoding application is configured to allocate a storage element in the memory for each of the N subsequences, and wherein each of the storage elements stores its respective subsequence of symbols.

13. A method for decoding a bitstream of encoded data to reconstruct a sequence of symbols, the symbols belonging to a finite alphabet, the method comprising:

extracting from the bitstream N encoded subsequences;

for each of the N encoded subsequences, entropy decoding that encoded subsequence to produce a respective decoded subsequence containing symbols, wherein at least two of the encoded subsequences are entropy decoded in parallel; and

interleaving symbols from the N decoded subsequences, based on a context model, to generate the reconstructed sequence of symbols.

14. The method claimed in claim 13, wherein entropy decoding comprises inputting two or more encoded subsequences to respective parallel entropy decoders each configured to decode its encoded subsequence and to produce the respective decoded subsequence.

15. The method claimed in claim 13, wherein the bitstream further includes information for locating each of the N encoded subsequences, and wherein extracting includes extracting the information and locating the N encoded subsequences based on the information.

16. The method claimed in claim 15, wherein the bitstream includes a prefix field containing the information and a payload field containing the N encoded subsequences.

17. The method claimed in claim 16, wherein the N encoded subsequences are concatenated within the payload field, and wherein the information includes length information for each of the N encoded subsequences.

18. The method claimed in claim 13, wherein interleaving includes, for each symbol of the reconstructed sequence,

determining an estimated probability based on the context model,

selecting a symbol from one of the N encoded subsequences, based on the estimated probability, and

adding the selected symbol to the reconstructed sequence.

19. The method claimed in claim 18, wherein interleaving further includes, for each symbol of the reconstructed sequence, updating the context model.

20. The method claimed in claim 13, further comprising:

dequantizing and inverse transforming the sequence of symbols to generate residual data,

applying a prediction operation to the residual data to generate pixel data, and

outputting the pixel data.

21. A decoder for decoding encoded data for decoding a bitstream of encoded data to reconstruct a sequence of symbols, the symbols belonging to a finite alphabet, 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 from the bitstream N encoded subsequences,

for each of the N encoded subsequences, entropy decoding that encoded subsequence to produce a respective decoded subsequence containing symbols, wherein at least two of the encoded subsequences are entropy decoded in parallel, and

interleaving symbols from the N decoded subsequences, based on a context model, to generate the reconstructed sequence of symbols.

22. The decoder claimed in claim 21, wherein the decoding application and processor comprise:

a demultiplexer configured to extract the N encoded subsequences from the bitstream,

two or more entropy decoders configured to decode the N encoded subsequences in parallel and to output the N decoded subsequences of symbols, and

a context modeling component and multiplexer configured to interleave the N decoded subsequences into the reconstructed sequence.

23. The decoder claimed in claim 21, further comprising two or more parallel entropy decoders each configured to decode respective encoded subsequences and to produce the respective decoded subsequence.

24. The decoder claimed in claim 21, wherein the decoding application contains instructions for configuring the processor to interleave symbols by, for each symbol of the reconstructed sequence:

determining an estimated probability based on the context model,

selecting a symbol from one of the N encoded subsequences, based on the estimated probability, and

adding the selected symbol to the reconstructed sequence.