Resynchronization properties of arithmetic coding

This paper considers decoding an arithmetic code stream when an initial portion of the code stream is unknown. Full resynchronization is hypothesized to have complexity that is exponential in the length of the initial portion. Experimental results specify the time complexity of determining the current arithmetic code interval, which is the important task in partial resynchronization.