Z-Coder: a fast adaptive binary arithmetic coder

Abstract

A binary arithmetic coder and decoder provides improved coding accuracy due to improved probability estimation and adaptation. They also provide improved decoding speed through a “fast path” design wherein decoding of a most probable symbol requires few computational steps. Coded data represents data that is populated by more probable symbols (“MPS”) and less probable symbols (“LPS”). In an embodiment, a decoder receives a segment of the coded data as a binary fraction C. It defines a coding interval of possible values of C, the interval extending from a variable lower bound A to a constant upper bound 1. For each position in the decoded symbol string, the decoder computes a test value Z that subdivides the coding interval into sub-intervals according to the relative probabilities that an MPS or an LPS occurs in the position. A first sub-interval extends from the lower bound A to the test value Z; the second sub-interval extending from the test value Z to 1. If C is greater than Z, the decoder emits an MPS for the current position in the decoded symbol string and sets the lower bound A to the test variable Z for use during decoding of the next position in the decoded symbol string. If C is less than Z, the decoder emits an LPS and computes a new lower bound A and a new binary fraction C for use during decoding of the next position in the decoded symbol string. The encoder operates according to analogous techniques to compose coded data from original data.

We claim:  
     
         1 . A method for decoding coded data into a decoded symbol string populated by more probable symbols (“MPS”) and less probable symbols (“LPS”), the method comprising the steps of: 
 receiving a segment of coded data interpreted as a binary fraction C;  
 defining a coding interval of possible values of C, the interval extending from a variable lower bound A to a constant upper bound 1;  
 for each position in the decoded symbol string:  
 computing a test value Z subdividing the coding interval into sub-intervals in accordance with the relative probabilities that an MPS and an LPS occurs in the position, a first sub-interval extending from the lower bound A to the test value Z, the second sub-interval extending from the test value Z to 1;  
 if C is greater than Z: 
 placing an MPS at the current position in the decoded symbol string, and  
 setting the lower bound A to the test variable Z for use in decoding of a next position in the decoded symbol string; and  
 
 if C is less than Z: 
 placing an LPS at the current position in the decoded symbol string, and  
 computing a new lower bound A and a new binary fraction C for use in decoding of the next position in the decoded symbol string.  
 
 
     
     
         2 . The method of  claim 1 , wherein the computation of the test value Z comprises the steps of: 
 computing a first test value Z1 derived from the lower bound A and from a current estimate P of the probability of the LPS symbol,    computing a second test value Z2 derived the lower bound A and from the current estimate P of the probability of the LPS symbol,    setting the test value Z to the lesser of Z1 and Z2.    
     
     
         3 . The method of  claim 2 , wherein Z1 and Z2 are computed according to:  
         Z 1= A+P/R 1, and  Z 2=½ +A/ 2−(½ −P )/ R 2,  wherein R1 and R2 are powers of two.    
     
     
         4 . The method of  claim 3 , wherein R2 is twice R1.  
     
     
         5 . The method of  claim 3 , wherein R2 is four times R1.  
     
     
         6 . The method of  claim 2 , comprising the additional step of: 
 defining a fence variable F;    if the first test value Z1 is smaller than the fence variable F; 
 placing an MPS at the current position in the decoded symbol string,  
 setting the lower bound A to the test variable Z1 for use in decoding of a next position in the decoded symbol string, and  
 immediately proceeding decoding of next position in the decoded symbol string; and  
   whenever the binary fraction C is modified by the decoding process, redefining the fence variable F to be less than the binary fraction C.    
     
     
         7 . The method of  claim 1 , further comprising, when a predefined criterion is met, updating both the binary fraction C and the new lower bound A in order to accommodate a new segment of coded data.  
     
     
         8 . The method of  claim 7 , wherein the predetermined criterion is met when a symbol within C is consumed.  
     
     
         9 . The method of  claim 1 , wherein the computation of the test value Z depends on the value of a parameter P approximating a probability of the occurrence of LPS symbols in the decoded symbol string, said method comprising the additional steps of: 
 if the decoded symbol is a LPS, setting the parameter P to a value representing an increased estimated probability for the LPS symbol; and    if the decoded symbol is a MPS;    comparing the lower bound A with a threshold value M depending on P, and    if the lower bound A is greater than the threshold value M, setting the parameter P to a value representing a decreased estimated probability for the LPS symbol.    
     
     
         10 . The method of  claim 9 , wherein the parameter P is indirectly represented by an integer index for accessing table entries specifying: 
 the actual value of the parameter P,    the value of the threshold M,    the new value of the index used for representing an increased estimated probability for the LPS symbol and    the new value of the index used for representing a decreased estimated probability for the LPS symbol.    
     
     
         11 . The method of  claim 1 , wherein the computation of the test value Z depends on the value of a parameter P representing the estimated probability of the LPS symbols, said method comprising the additional step of: 
 if the decoded symbol is an LPS, setting the parameter P to a value representing an increased estimated probability for the LPS symbol.    if the decoded symbol is a MPS, 
 comparing the test value Z with a threshold value M depending on P, and  
 if the test value Z is greater than the threshold value M, setting the parameter P to a value representing a decreased estimated probability for the LPS symbol.  
   
     
     
         12 . The method of  claim 10 , wherein the parameter P is indirectly represented by an integer index for accessing table entries specifying: 
 the actual value of the parameter P,    the value of the threshold M,    the new value of the index used for representing an increased estimated probability for the LPS symbol and    the new value of the index used for representing a decreased estimated probability for the LPS symbol.    
     
     
         13 . A method for encoding data, the data represented by a symbol string populated by more probable symbols (“MPS”) and less probable symbols (“LPS”), the method comprising the steps of: 
 initializing a code accumulator S;  
 defining a coding interval extending from a variable lower bound A to a constant upper bound 1;  
 for each position in the symbol string: 
 computing a test value Z subdividing the coding interval into sub-intervals in accordance with the relative probabilities of an MPS and an LPS occur in the position, a first sub-interval extending from the lower bound A to the test value Z, the second sub-interval extending from the test value Z to 1;  
 if the symbol located at the current position in the symbol string is a MPS, setting the lower bound A to the test variable Z for use in encoding of a next position in the decoded symbol string;  
 if the symbol located at the current position in the symbol string is an LPS,  
 adding the length of the second sub-interval to the accumulator S, and  
 computing a new lower bound A for use in encoding of a next position in the decoded symbol string; and  
 when a predefined criterion is met, outputting a segment of coded data and computing new values for both the accumulator S and the lower bound A.  
 
 
     
     
         14 . The method of  claim 13 , wherein the computation of the test value Z comprises the steps of: 
 computing a first test value Z1 derived from the lower bound A and from a current estimate P of the probability of the LPS symbol,    computing a second test value Z2 derived the lower bound A and from the current estimate P of the probability of the LPS symbol,    setting the test value Z to the lesser of Z1 and Z2.    
     
     
         15 . The method of  claim 14 , wherein Z 1  and Z 2  are computed according to:  
         Z 1= A+P/R 1, and  Z 2=½ +A/ 2−(½ −P )/ R 2,  wherein R1 and R2 are powers of two.    
     
     
         16 . The method of  claim 15 , wherein R2 is twice R1.  
     
     
         17 . The method of  claim 15 ,. wherein R2 is four times R1.  
     
     
         18 . The method of  claim 13 , wherein the computation of the test value Z depends on the value of a parameter P approximating a probability of the occurrence of LPS symbols in the decoded symbol string, said method comprising the additional steps of: 
 if the decoded symbol is a LPS, setting the parameter P to a value representing an increased estimated probability for the LPS symbol; and    if the decoded symbol is a MPS; 
 comparing the lower bound A with a threshold value M depending on P, and  
 if the lower bound A is greater than the threshold value M, setting the parameter P to a value representing a decreased estimated probability for the LPS symbol.  
   
     
     
         19 . The method of  claim 18 , wherein the parameter P is indirectly represented by an integer index for accessing table entries specifying: 
 the actual value of the parameter P,    the value of the threshold M,    the new value of the index used for representing an increased estimated probability for the LPS symbol and the new value of the index used for representing a decreased estimated probability for the LPS symbol.    
     
     
         20 . The method of  claim 13 , wherein the computation of the test value Z depends on the value of a parameter P representing the estimated probability of the LPS symbols, said method comprising the additional step of: 
 if the decoded symbol is an LPS, setting the parameter P to a value representing an increased estimated probability for the LPS symbol.    if the decoded symbol is a MPS, 
 comparing the test value Z with a threshold value M depending on P, and  
 if the test value Z is greater than the threshold value M, setting the parameter P to a value representing a decreased estimated probability for the LPS symbol.  
   
     
     
         21 . The method of  claim 20 , wherein the parameter P is indirectly represented by an integer index for accessing table entries specifying: 
 the actual value of the parameter P,    the value of the threshold M,    the new value of the index used for representing an increased estimated probability for the LPS symbol and    the new value of the index used for representing a decreased estimated probability for the LPS symbol.    
     
     
         22 . A method of decoding coded data into decoded data, the decoded data represented by a symbol string of more probable symbols (“MPS”) and less probable symbols (“LPS”), the method comprising: 
 receiving a segment of coded data as a binary fraction,  
 for a position in the decoded symbol string, 
 defining an interval of possible values of the coded data, the interval bounded by 1 and a lower bound,  
 computing a test variable that divides the interval into two sub-intervals according to relative probabilities that the symbol should be occupied by the MPS or the LPS, a first sub-interval extending from 1 to the test variable and associated with the MPS, a second sub-interval extending from the test variable to the lower bound and associated with the LPS,  
 when the coded data segment occupies the first sub-interval, placing an MPS in the position, and  
 
 when the coded data segment occupies the second sub-interval, placing an LPS in the position.  
 
     
     
         23 . The method of  claim 1 , further comprising a step of, when an MPS is placed in the position, setting the lower bound to the test variable for use in decoding of a next position in the decoded symbol string.  
     
     
         24 . The method of  claim 1 , further comprising a step of, when an LPS is placed in the position, incrementing both the lower bound and the coded data segment by an amount representing a difference between  1  and the test variable for use in decoding of a next position in the decoded symbol string.  
     
     
         25 . The method of  claim 1 , further comprising a step of renormalizing the values of the coded data segment and the lower bound when a bit in the coded data segment has been consumed.  
     
     
         26 . The method of  claim 25 , wherein the renormalizing step causes data of the coded data segment and the lower bound to be shifted one bit to the left.  
     
     
         27 . The method of  claim 25 , wherein the renormalizing step includes a step of testing a most significant bit position of the lower bound and determining that the bit in the coded data segment has been consumed when the most significant bit position of the lower bound is a 1.  
     
     
         28 . The method of  claim 1 , wherein the test variable is computed according to the formula Z=A+p, wherein Z represents the value of the test variable, A represents a value of the lower bound and p represents an approximation of the probability of the occurrence of the LPS.  
     
     
         29 . A method of decoding coded data into decoded data, the decoded data represented by a symbol string of more probable symbols (“MPS”) and less probable symbols (“LPS”), the method comprising: 
 receiving a segment of coded data as a binary fraction,  
 for a position in the decoded symbol string, 
 defining an interval of possible values of the coded data, the interval bounded by 1 and a lower bound,  
 computing a test variable that divides the interval into two sub-intervals according to relative probabilities that the symbol should be occupied by the MPS or the LPS, a first sub-interval extending from 1 to the test variable and associated with the MPS, a second sub-interval extending from the test variable to the lower bound and associated with the LPS,  
 computing a fence variable to be the lesser of the coded data segment and ½, and  
 when the test variable is less than the fence variable, placing an MPS in the position.  
 
 
     
     
         30 . The method of  claim 29 , further comprising steps of, when the test variable is greater than the fence variable, determining whether the test variable is greater than the coded data segment and, if so, placing an MPS in the position.  
     
     
         31 . The method of  claim 30 , further comprising a step of, when an MPS is placed in the position, setting the lower bound to the test variable for use in decoding of a next position in the decoded symbol string.  
     
     
         32 . The method of  claim 29 , further comprising step of, when the test variable is greater than the fence variable, determining whether the test variable is less than the coded data segment and, if so, placing an LPS in the position.  
     
     
         33 . The method of  claim 32 , further comprising a step of, when an LPS is placed in the position, incrementing both the lower bound and the coded data segment by an amount representing a difference between 1 and the test variable for use in decoding of a next position in the decoded symbol string.  
     
     
         34 . A method of decoding coded data into decoded data, comprising the steps of: 
 receiving a segment of coded data as a binary fraction,    for a position in the decoded symbol string, 
 defining an interval of possible values of the coded data, the interval bounded by 1 and a lower bound,  
 computing a test variable that divides the interval into two sub-intervals according to relative probabilities that the symbol should be occupied by the MPS or the LPS, a first sub-interval extending from 1 to the test variable and associated with the MPS, a second sub-interval extending from the test variable to the lower bound and associated with the LPS,  
   computing a fence variable to be the lesser of the coded data segment and ½, 
 decoding an MPS for the position when either of the following conditions occur: the test variable is less than the fence variable, and the when the test variable is less than the segment of coded data, and  
 decoding an LPS for the position and performing LPS adaptation when neither of the conditions occur.  
   
     
     
         35 . The method of  claim 34 , further comprising, when an MPS is decoded, determining whether the test variable is greater than an MPS adaptation test variable and, if so, performing MPS adaptation.  
     
     
         36 . A method of decoding coded data, the coded data representing a sequence of symbols including a most probable symbol (“MPS”) and a least probable symbol (“LPS”), the method comprising: 
 receiving a segment of the coded data as a fractional value;  
 initializing a variable representing a lower limit on possible values of the segment of coded data to equal zero; and  
 iteratively, 
 calculating a test variable that divides an interval from the lower limit to one according to relative probabilities that a next symbol to be decoded is an LPS or an MPS,  
 calculating a fence variable representing the lesser of one half and the value of segment of coded data,  
 decoding the next symbol to be an MPS when the test variable is less than the fence variable,  
 otherwise, decoding the next symbol to be an MPS when the test variable is less than the value of segment of coded data,  
 otherwise, decoding the next symbol to be an LPS,  
 when an MPS is decoded, setting the lower limit for a next iteration equal to the test variable, and  
 when an LPS is decoded, setting the lower limit and the segment of coded data equal to their respective values for the instant iteration added by an amount equal to the difference between the test variable and 1.  
 
 
     
     
         37 . The method of  claim 36 , further comprising, when an MPS is decoded, determining whether the test variable is greater than an MPS adaptation threshold and, if so, performing MPS adaptation.  
     
     
         38 . The method of  claim 36 , further comprising, when an LPS is decoded, performing LPS adaptation.  
     
     
         39 . A decoder adapted to perform the following functions: 
 receive a segment of the coded data as a fractional value;    initialize a variable representing a lower limit on possible values of the segment of coded data to equal zero; and    iteratively, 
 calculate a test variable that divides an interval from the lower limit to one according to relative probabilities that a next symbol to be decoded is an LPS or an MPS,  
 calculate a fence variable representing the lesser of one half and the value of segment of coded data,  
 decode the next symbol to be an MPS when the test variable is less than the fence variable,  
 otherwise, decode the next symbol to be an MPS when the test variable is less than the value of segment of coded data,  
 otherwise, decode the next symbol to be an LPS,  
 when an MPS is decoded, set the lower limit for a next iteration equal to the test variable, and  
 when an LPS is decoded, set the lower limit and the segment of coded data equal to their respective values for the instant iteration added by an amount equal to the difference between the test variable and 1.  
   
     
     
         40 . The decoder of  claim 39 , wherein the decoder, when an MPS is decoded, determines whether the test variable is greater than an MPS adaptation threshold and, if so, performs MPS adaptation.  
     
     
         41 . The decoder of  claim 39 , wherein the decoder, when an LPS is decoded, performs LPS adaptation.