Method of context based adaptive binary arithmetic decoding with two part symbol decoding

Abstract

This invention is method of decoding a context based adaptive binary arithmetic encoded bit stream. The invention determines a maximum number of iterations for decoding a next symbol. This preferably employs a left most bit detect command. The invention considers the bit stream bit by bit until detection of a bit having a first digital state of the maximum number of iterations. If the maximum number of iterations occurs first, the invention decodes the considered bits. If a bit having the first digital state occurs first, the invention selects a number of next bits from the bit stream dependent upon the determined position within the coding table and decodes a symbol corresponding to the maximum number of bits and the selected number of next bits. The invention preferably pre-calculates an order symbol contexts corresponding to an order of determination of a code tree encompassing all possible codes and decodes symbols dependent upon a current context within the pre-calculated.

1. A method of decoding a context based adaptive binary arithmetic encoded bit stream comprising the steps of:
 determining a maximum number of iterations for decoding a next symbol dependent upon a code tree corresponding to the encoded bit stream;  
 considering the bit stream bit by bit until detection of a bit having a first digital state of the maximum number of iterations;  
 if the maximum number of iterations occurs before detecting a bit having the first digital state, decoding the considered bits;  
 if a bit having the first digital state is detected before the maximum number of iterations, selecting a number of next bits from the bit stream dependent upon the determined position within the code tree; and  
 decoding a symbol corresponding to the determined position within the code tree and the selected number of next bits.  
 
   
   
     2. The method of  claim 1 , wherein:
 said step of considering the bit stream bit by bit for a maximum number of iterations for decoding a next symbol includes for each iteration 
 determining a left most one bit position of QUARTER,  
 determining a left most one bit position of a range,  
 determining the number of iterations by subtracting the left most one bit position of QUARTER from the left most one bit position of range.  
 
 
   
   
     3. The method of  claim 1 , further comprising:
 pre-calculating an order symbol contexts corresponding to an order of determination of a code tree encompassing all possible codes; and  
 each step of decoding a symbol decodes the symbol dependent upon a current context within the pre-calculated order of symbol contexts.