Method and apparatus for arithmetic coding, including probability estimation state table creation
First Claim
1. A method for creating a state machine for probability estimation, the method comprising:
- assigning probabilities to states of a look up table (LUT), including setting a probability for each state i of the states equal to the highest probability of the LPS multiplied by the adaptation rate to the power i, where i is a number for a given state and the adaptation rate is smaller than 1;
generating state transitions for states in the LUT to be transitioned to upon observing an MPS and an LPS, wherein the next state to which the state machine transitions from a current state when an MPS is observed is a next state higher than the current state if the current state is not the highest state and is the current state if the current state is the highest state, and further wherein the next state to which the state machine transitions from a current state when an LPS is observed for a plurality of states is a rounded version of a result of calculating;
number of current state+log((probability of the current state*the adaptation rate+(1−
the adaptation rate))/probability of the current state)/log(the adaptation rate).
2 Assignments
0 Petitions
Accused Products
Abstract
Methods and apparatuses for performing arithmetic encoding and/or decoding are disclosed. In one embodiment, the method for creating a state machine for probability estimation comprises assigning probabilities to states of a look up table (LUT), including setting a probability for each state i of the states equal to the highest probability of the LPS multiplied by the adaptation rate to the power i, where i is a number for a given state and the adaptation rate is smaller than 1. The method also comprises generating state transitions for states in the LUT to be transitioned to upon observing an MPS and an LPS, wherein the next state to which the state machine transitions from a current state when an MPS is observed is a next state higher than the current state if the current state is not the highest state and is the current state if the current state is the highest state. Furthermore, the next state to which the state machine transitions from a current state when an LPS is observed for a plurality of states is a rounded version of a result of calculating:
number of current state+log((probability of the current state*the adaptation rate+(1−the adaptation rate))/probability of the current state)/log(the adaptation rate).
45 Citations
25 Claims
-
1. A method for creating a state machine for probability estimation, the method comprising:
-
assigning probabilities to states of a look up table (LUT), including setting a probability for each state i of the states equal to the highest probability of the LPS multiplied by the adaptation rate to the power i, where i is a number for a given state and the adaptation rate is smaller than 1;
generating state transitions for states in the LUT to be transitioned to upon observing an MPS and an LPS, wherein the next state to which the state machine transitions from a current state when an MPS is observed is a next state higher than the current state if the current state is not the highest state and is the current state if the current state is the highest state, and further wherein the next state to which the state machine transitions from a current state when an LPS is observed for a plurality of states is a rounded version of a result of calculating; number of current state+log((probability of the current state*the adaptation rate+(1−
the adaptation rate))/probability of the current state)/log(the adaptation rate). - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. An arithmetic encoder comprising:
-
a probability estimator to generate a probability estimate that each event of an event sequence has a particular value, wherein the probability estimator generates the probability estimate in response to corresponding context information for said each event using a probability estimation state machine created by assigning probabilities to states of a look up table (LUT), including setting a probability for each state i of the states equal to the highest probability of the LPS multiplied by the adaptation rate to the power i, where i is a number for a given state and the adaptation rate is smaller than 1;
generating state transitions for states in the LUT to be transitioned to upon observing an MPS and an LPS, wherein the next state to which the state machine transitions from a current state when an MPS is observed is a next state higher than the current state if the current state is not the highest state and is the current state if the current state is the highest state, and further wherein the next state to which the state machine transitions from a current state when an LPS is observed for a plurality of states is a rounded version of a result of calculating; number of current state+log(probability of the current state*the adaptation rate+(1−
the adaptation rate))/probability of the current state)/log(the adaptation rate); anda coding engine coupled to the probability estimator to generate zero or more bits of an information sequence in response to each event and its corresponding probability estimate. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. An arithmetic decoder comprising:
-
a probability estimator to generate a probability estimate that an event of an event sequence has a particular value, wherein the probability estimator generates the probability estimate in response to corresponding context information for said event of the event sequence using a probability estimation state machine created by assigning probabilities to states of a look up table (LUT), including setting a probability for each state i of the states equal to the highest probability of the LPS multiplied by the adaptation rate to the power i, where i is a number for a given state and the adaptation rate is smaller than 1, and generating state transitions for states in the LUT to be transitioned to upon observing an MPS and an LPS, wherein the next state to which the state machine transitions from a current state when an MPS is observed is a next state higher than the current state if the current state is not the highest state and is the current state if the current state is the highest state, and further wherein the next state to which the state machine transitions from a current state when an LPS is observed for a plurality of states is a rounded version of a result of calculating; number of current state+log((probability of the current state*the adaptation rate+(1−
the adaptation rate))/probability of the current state)/log(the adaptation rate); anda decoding engine coupled to the probability estimator to generate an event of an event sequence in response to its corresponding probability estimate and an information sequence. - View Dependent Claims (18, 19, 20, 21, 22, 23, 24)
-
-
25. A decoding method comprising:
-
generating a probability estimate that an event of an event sequence has a particular value, the probability estimate being generated in response to corresponding context information for said each event of the event sequence using a probability estimation state machine created by assigning probabilities to states of a look up table (LUT), including setting a probability for each state i of the states equal to the highest probability of the LPS multiplied by the adaptation rate to the power i, where i is a number for a given state and the adaptation rate is smaller than 1, and generating state transitions for states in the LUT to be transitioned to upon observing an MPS and an LPS, wherein the next state to which the state machine transitions from a current state when an MPS is observed is a next state higher than the current state if the current state is not the highest state and is the current state if the current state is the highest state, and further wherein the next state to which the state machine transitions from a current state when an LPS is observed for a plurality of states is a rounded version of a result of calculating; number of current state+log((probability of the current state*the adaptation rate+(1−
the adaptation rate))/probability of the current state)/log(the adaptation rate); andgenerating an event of an event sequence in response to its corresponding probability estimate and an information sequence.
-
Specification