Overlapped Arithmetic Codes for Binary Asymmetric Sources

Arithmetic codes are the most important method for lossless source coding. By allowing overlapped intervals, arithmetic codes can also implement lossless distributed source coding, i.e., the so-called Slepian-Wolf coding. It had been thought that the overlapped arithmetic code of binary symmetric sources is a many-to-one mapping from source space to codeword space, so every source block can be decoded from only one codeword. Surprisingly, this paper finds that this thought is incorrect because it is possible to decode a source block from a codeword differing from its own codeword. To explain this weird phenomenon, this paper proposes to describe arithmetic codes with a directed bipartite graph. If a source block can be decoded from a codeword differing from its own codeword, there will be a unidirectional edge from the codeword to the source block in the directed bipartite graph. It is found that, compared with binary symmetric sources, there are many more unidirectional edges for binary asymmetric sources due to interval nesting. The existence of unidirectional edges is harmful because it may cause decoding failure. To solve this problem, this paper proposes the Local Encoder at Decoder (LED) structure, which can remove all unidirectional edges. This paper also proposes the roundup symbol-interval mapping to remove sub-bit rate loss. After applying these two techniques, the performance of overlapped arithmetic codes for binary asymmetric sources is significantly improved. Other contributions of this paper include: (a) find that Rissanen's method fails to generate prefix overlapped arithmetic code, which tells us that the length of overlapped arithmetic code should always be sent to the decoder; (b) refine Witten's method to generate the shortest prefix arithmetic code with finite precision.