A scheme of parallel arithmetic coding

This paper presents a parallel arithmetic coding scheme in which supports a large degree of parallelism with a marginal cost in terms of the coding efficiency. The parallelism is brought by coding the bits using multiple arithmetic coders. We identify two types of losses in coding efficiency by breaking the dependency among the data: the loss by breaking the probability prediction process and the loss by breaking the information for context decision at the starting of each slice. We further analyze these losses quantitatively and find that the loss by breaking probability adaptation process takes the most of losses. A coding method is proposed in this paper to compensate such a loss by sending additional data. Experimental results show that our proposed method can compensate the loss well, especially for large scale parallel, whereas the overhead is moderate.