Method and device for compression of binary sequences by grouping multiple symbols
View Patent ↗A method for encoding an input sequence of symbols to produce a bitstream and a method of decoding the bitstream to generate a reconstructed binary sequence. Encoding employs 2 L -ary encoding trees having codewords associated with leaf nodes. A context model is used to select an encoding tree corresponding to an estimated probability at the encoder. The same context model is used by the decoder to select a decoding tree. The decoder interleaves bits from decoded sequences of length-L strings associated with different estimated probabilities, based on the context model.
1. A method for encoding an input sequence of binary symbols using a context model having a set of context states and a respective 2 L -ary encoding tree associated with each context state, the method comprising:
for a length-L string of consecutive symbols,
determining the context state for a first symbol of the length-L string, and selecting the 2 L -ary encoding tree associated with that context state;
appending subsequent length-L strings of consecutive symbols to the length-L string of consecutive symbols to form a sequence of strings and encoding that sequence of strings as a codeword using the selected 2 L -ary encoding tree; and
updating the context state based on the symbols in that sequence of strings and the context model.
2. The method claimed in claim 1 , wherein appending and encoding comprise traversing one level of the selected 2 L -ary encoding tree based on each L-length string of consecutive symbols in the sequence of strings.
3. The method claimed in claim 2 , wherein traversing includes determining that one of the subsequent length-L strings completes the sequence of strings by reaching a leaf node in the selected encoding tree, and wherein encoding includes outputting the codeword corresponding to the leaf node.
4. The method claimed in claim 1 , wherein the symbols in the length-L string of consecutive symbols and the symbols in the subsequent length-L string of consecutive symbols all have a common context.
5. The method claimed in claim 1 , wherein the updating is performed after each length-L string of consecutive symbols.
6. The method claimed in claim 1 , wherein the updating is performed only after encoding the sequence of strings as a codeword.
7. An encoder for encoding an input sequence of symbols, 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 .
8. The encoder claimed in claim 7 , wherein the processor is configured to append and encode by traversing one level of the selected 2 L -ary encoding tree based on each L-length string of consecutive symbols in the sequence of strings.
9. The encoder claimed in claim 8 , wherein the processor is configured to traverse by determining that one of the subsequent length-L strings completes the sequence of strings by reaching a leaf node in the selected encoding tree, and wherein the processor is configured to encode by outputting the codeword corresponding to the leaf node.
10. The encoder claimed in claim 7 , wherein the symbols in the length-L string of consecutive symbols and the symbols in the subsequent length-L string of consecutive symbols all have a common context.
11. The encoder claimed in claim 7 , wherein the processor is configured to update the context state after each length-L string of consecutive symbols.
12. The encoder claimed in claim 7 , wherein the processor is configured to update the context state after encoding the sequence of strings as a codeword.
13. A method for decoding a bitstream of encoded data to generate a reconstructed binary sequence, the bitstream containing a plurality of codewords, the method comprising:
determining a context associated with a next bit of the reconstructed binary sequence based on a context model; and
determining whether a decoded bit associated with that context is available from a previously decoded codeword and,
if so, adding that decoded bit to the reconstructed binary sequence, and,
if not then
parsing the bitstream to extract a next codeword,
decoding the next codeword using a decoding table selected based upon a context state to obtain a new bit sequence associated with that context, and
adding a first decoded bit from the new bit sequence to the reconstructed binary sequence.
14. The method claimed in claim 13 , wherein the decoding comprises matching the next codeword from the bitstream to an entry in the decoding table.
15. The method claimed in claim 13 , wherein the determining a context and the determining whether a decoded bit is available are repeated cyclically.
16. A decoder for decoding a bitstream of encoded data to generate a reconstructed binary sequence, the decoder comprising:
a processor;
a memory;
a decoding application stored in memory and containing instructions for configuring the processor to decode the bitstream using the method claimed in claim 13 .
17. The decoder claimed in claim 16 , wherein the processor is configured to decode by matching the next codeword from the bitstream to an entry in the decoding table.
18. The decoder claimed in claim 16 , wherein the processor is configured to determine a context and determine whether a decoded bit is available cyclically.