Parallel entropy coding and decoding methods and devices
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.
1. A method for encoding of an input sequence of symbols using a processor, the symbols belonging to a finite alphabet, the method comprising:
for each symbol in the input sequence, assigning, with the processor, the symbol to one of N subsequences of symbols based on an estimated probability given by a context model;
merging, using the processor, a first subsequence of symbols with a second subsequence of symbols to create a merged subsequence, thereby reducing the N subsequences of symbols to d subsequences, wherein merging includes
determining an overhead associated with the first subsequence of symbols, wherein the first subsequence of symbols is associated with a first estimated probability,
calculating a ratio of the overhead to the number of symbols in the first subsequence and determining that the ratio is greater than a relative entropy between the first subsequence of symbols and the second subsequence of symbols, wherein the second subsequence of symbols is associated with a second estimated probability, and
associating the merged subsequence with the second estimated probability,
encoding the d subsequences in parallel by using d respective entropy coders to generate d respective encoded subsequences; and
outputting a bitstream, wherein the bitstream includes the d encoded subsequences and information for locating each of the d 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 1 , wherein the first estimated probability is p and the second estimated probability is q, and wherein the relative entropy between the first subsequence of symbols and the second subsequence of symbols is given by:
p *log( p/q )+(1 −p )log((1 −p )/(1 −q )).
5. The method claimed in claim 4 , wherein the first subsequence is k, and wherein determining the overhead OH(k) associated with the first subsequence of symbols is calculated as:
OH ( k )=8 *|C ( L ( k ))|−4*log(1 −p )+4,
where C(L(k)) is the number of bytes in a prefix portion of the bitstream for locating the first subsequence of symbols.
6. 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 d encoded subsequences.
7. The method claimed in claim 6 , wherein the information for locating comprises a length value for each of the d encoded subsequences.
8. 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 using the method claimed in claim 1 .
9. The encoder claimed in claim 8 , wherein the processor is configured to assign the 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.
10. The encoder claimed in claim 9 , wherein the context model comprises an adaptive context model, and wherein the processor is configured to assign the symbol to one of N subsequences by updating the adaptive context model after each appending operation.
11. The encoder claimed in claim 8 , wherein the first estimated probability is p and the second estimated probability is q, and wherein the relative entropy between the first subsequence of symbols and the second subsequence of symbols is given by:
p *log( p/q )+(1 −p )log((1 −p )/(1 −q )).
12. The encoder claimed in claim 11 , wherein the first subsequence is k, and wherein determining the overhead OH(k) associated with the first subsequence of symbols is calculated as:
OH ( k )=8 *|C ( L ( k ))|−4*log(1 −p )+4,
where C(L(k)) is the number of bytes in a prefix portion of the bitstream for locating the first subsequence of symbols.
13. The encoder claimed in claim 8 , wherein outputting the bitstream includes outputting a prefix and a payload, wherein the prefix contains the information for locating and the payload contains the d encoded subsequences.
14. The encoder claimed in claim 13 , wherein the information for locating comprises a length value for each of the d encoded subsequences.