Probability Interval Partitioning Entropy (PIPE) Coding

The probability interval partitioning entropy (PIPE) coding concept is a technique for coding binary data. Similar to binary arithmetic coding, it closely approaches the entropy limit of a source while for the actual encoding and decoding process, only simple variable-length codes are needed. The key element of the concept is a partitioning of the model probabilities into a small set of probability intervals and thus a categorization of the source symbols according to their model probability. Symbols of one interval are then coded using a so-called bin coder that is optimized for a single representative probability. This introduces a new layer of abstraction because bins of an interval are all treated in the same way, which allows a simple design of the bin coders. Furthermore, bin coders can operate independently and thus in parallel. The impact of the probability interval partitioning on the bit rate is depicted in the following chart together with the entropy limit for an exemplary setup of four bin coders. Note that the bit-rate overhead can be made arbitrarily low by increasing the number of probability intervals.

The PIPE coding concept can be applied to the context-based adaptive binary arithmetic coding (CABAC) scheme as used in the video coding standard H.264/AVC and the emerging video coding standard HEVC. It replaces the (binary arithmetic) M coder of CABAC with the probability quantizer, a set of bin coders and a multiplexer as shown in the figure below. Coding symbols as, e.g., motion vectors and transform coefficient levels are first converted into a stream of so-called bins (which are binary decisions to be coded) and the context modeler assigns a model probability to each bin. The probability quantizer distributes the bins to the bin encoders, which encode the bins independently and in parallel. Finally, the encoded representations of the bins are multiplexed into a single bit stream. With an appropriately designed set of V2V codes, only a negligible averaged bit-rate increase of less than 0.5% is observed in comparison to binary arithmetic coding.