Parallel arithmetic coding techniques

Patent metadata

Field	Value
Publication number	US-10419772-B2
Application number	US-201514925761-A
Country	US
Kind code	B2
Filing date	Oct 28, 2015
Priority date	Oct 28, 2015
Publication date	Sep 17, 2019
Grant date	Sep 17, 2019

Abstract

Systems and methods for decoding compressed data are described herein. A memory may receive a data stream comprising a string of encoded symbols encoded using an arithmetic coding based coding technique. The string of encoded symbols represents a series of one or more decoded symbols. Each of the one or more decoded symbols comprises one of a most probable symbol and a least probable symbol. A processor may determine a number of consecutive most probable symbols in the series of one or more decoded symbols by performing a plurality of parallel mathematical comparisons based on one or more of the encoded symbols. The processor may further decode a group of symbols of the series of one or more decoded symbols based on the plurality of parallel mathematical comparisons. The group of symbols comprises the number of consecutive most probable symbols.

First claim

What is claimed is:

1. A method for decoding compressed video data, the method comprising:
receiving a video data stream comprising a string of encoded symbols, the string of encoded symbols representing an encoding of a binary sequence, wherein, in the binary sequence, a first symbol appears more frequently than a second symbol, and wherein the string of encoded symbols encodes probabilities of successive occurrences of the first symbol in the binary sequence;
receiving, with the video data stream, a length of the binary sequence and a count of occurrences of the first symbol in the binary sequence;
performing multiple comparisons in parallel, wherein each of the multiple comparisons compare a current value of a subset of the string of encoded symbols against a first probability of the current value encoding only the first symbol and a second probability of the current value encoding an occurrence of the second symbol, wherein the first probability and the second probability are based on the length of the binary sequence and the count of occurrences of the first symbol, and wherein the first probability is adjusted for successive comparisons of the multiple comparisons to include more occurrences of the first symbol;
determining a count of consecutive occurrences of the first symbol in the subset of the string of encoded symbols based on a particular comparison from the multiple comparisons being invalid; and
outputting a sequence of the first symbol followed by an instance of the second symbol, wherein a number of the first symbol in the sequence is equal to the count of consecutive occurrences of the first symbol.

2. The method of claim 1 , wherein performing the multiple comparisons and outputting the sequence completes in a single clock cycle.

3. The method of claim 1 , wherein the string of encoded symbols is encoded without using bit-stuffing techniques.

4. The method of claim 1 , wherein the string of encoded symbols is encoded based on one of arithmetic coding or Q-coding.

5. The method of claim 1 , wherein the string of encoded symbols is encoded based on a multiplier based coding technique.

6. The method of claim 1 , wherein the sequence is indicative of one or more syntax elements defining at least a portion of a sequence of pictures.

7. A system for decoding compressed video data, the system comprising:
a memory configured to receive a video data stream comprising a string of encoded symbols, the string of encoded symbols represents an encoding of a binary sequence, wherein, in the binary sequence, a first symbol appears more frequently than a second symbol, and wherein the string of encoded symbols encodes probabilities of successive occurrences of the first symbol in the binary sequence; and
a processor configured to:
receive, with the video data stream, a length of the binary sequence and a count of occurrences of the first symbol in the binary sequence;
perform multiple comparisons in parallel, wherein each of the multiple comparisons compare a current value of a subset of the string of encoded symbols against a first probability of the current value encoding only the first symbol and a second probability of the current value encoding an occurrence of the second symbol, wherein the first probability and the second probability are based on the length of the binary sequence and the count of occurrences of the first symbol, and wherein the first probability is adjusted for successive comparisons of the multiple comparisons to include more occurrences of the first symbol;
determine a count of consecutive occurrences of the first symbol in the subset of the string of encoded symbols based on a particular comparison from the multiple comparisons being invalid; and
output a sequence of the first symbol followed by an instance of the second symbol, wherein a number of the first symbol in the sequence is equal to the count of consecutive occurrences of the first symbol.

8. The system of claim 7 , wherein performing the multiple comparisons and outputting the sequence completes in a single clock cycle.

9. The system of claim 7 , wherein the string of encoded symbols is encoded without using bit-stuffing techniques.

10. The system of claim 7 , wherein the string of encoded symbols is encoded based on one of the following: arithmetic coding or Q-coding.

11. The system of claim 7 , wherein the string of encoded symbols is encoded based on a multiplier based coding technique.

12. The system of claim 7 , wherein the sequence is indicative of one or more syntax elements defining at least a portion of a sequence of pictures.

13. A non-transitory computer-readable medium having stored thereon instructions that, when executed, cause a processor of a device for decoding data to perform operations including:
receiving a video data stream comprising a string of encoded symbols, the string of encoded symbols representing an encoding of a binary sequence, wherein, in the binary sequence, a first symbol appears more frequently than a second symbol, and wherein the string of encoded symbols encodes probabilities of successive occurrences of the first symbol in the binary sequence;
receiving, with the video data stream, a length of the binary sequence and a count of occurrences of the first symbol in the binary sequence;
performing multiple comparisons in parallel, wherein each of the multiple comparisons compare a current value of a subset of the string of encoded symbols against a first probability of the current value encoding only the first symbol and a second probability of the current value encoding an occurrence of the second symbol, wherein the first probability and the second probability are based on the length of the binary sequence and the count of occurrences of the first symbol, and wherein the first probability is adjusted for successive comparisons of the multiple comparisons to include more occurrences of the first symbol;
determining a count of consecutive occurrences of the first symbol in the subset of the string of encoded symbols based on a particular comparison from the multiple comparisons being invalid; and
outputting a sequence of the first symbol followed by an instance of the second symbol, wherein a number of the first symbol in the sequence is equal to the count of consecutive occurrences of the first symbol.

14. The non-transitory computer-readable medium of claim 13 , wherein performing the multiple comparisons and outputting the sequence completes in a single clock cycle.

15. The non-transitory computer-readable medium of claim 14 , wherein the string of encoded symbols is encoded without using bit-stuffing techniques.

16. The non-transitory computer-readable medium of claim 14 , wherein the string of encoded symbols is encoded based on one of arithmetic coding and Q-coding.

17. The non-transitory computer-readable medium of claim 14 , wherein the string of encoded symbols is encoded based on a multiplier based coding technique.

18. A system for decoding compressed video data, the system comprising:
means for receiving a video data stream comprising a string of encoded symbols, the string of encoded symbols representing an encoding of a binary sequence, wherein, in the binary sequence, a first symbol appears more frequently than a second symbol, and wherein the string of encoded symbols encodes probabilities of successive occurrences of the first symbol in the binary sequence;
means for receiving, with the video data stream, a length of the binary sequence and a count of occurrences of the first symbol in the binary sequence;

Assignees

• Qualcomm Inc

Inventors

• Sinha Pavel
• Todorovich Mark

Classifications

• H04N19/91

  Entropy coding, e.g. variable length coding [VLC] or arithmetic coding · CPC title

• H04N19/13

  Adaptive entropy coding, e.g. adaptive variable length coding [AVLC] or context adaptive binary arithmetic coding [CABAC] · CPC title

• H04N19/436 Primary

  using parallelised computational arrangements · CPC title

• H04N19/43

  Hardware specially adapted for motion estimation or compensation · CPC title

• H04N19/177

  the unit being a group of pictures [GOP] · CPC title