Entropy coding in video compression using probability interval partitioning

We present a novel approach to entropy coding, which provides the coding efficiency and simple probability modeling capability of arithmetic coding at the complexity level of Huffman coding. The key element of the proposed approach is a partitioning of the unit interval into a small set of probability intervals. An input sequence of discrete source symbols is mapped to a sequence of binary symbols and each of the binary symbols is assigned to one of the probability intervals. The binary symbols that are assigned to a particular probability interval are coded at a fixed probability using a simple code that maps a variable number of binary symbols to variable length codewords. The probability modeling is decoupled from the actual binary entropy coding. The coding efficiency of the probability interval partitioning entropy (PIPE) coding is comparable to that of arithmetic coding.