Chase-Like Decoding of Arithmetic Codes with Applications

Introduction

Joint Source Channel coding and decoding have become an area of strong interest because the separation between source and channel coding has turned out to be unjustified in practical systems due to limited block lengths and the residual redundancies in the data bits which remain after suboptimal source encoding.

Since Arithmetic Coding (AC) (Rissanen & Langdon, 1979) is applied in many emerging data compression standards, extensive work has been done recently to improve the robustness of these codes against channel errors. In fact, arithmetic-encoded data are very vulnerable to transmission errors (poor resynchronization properties). The first contributions, classified as robust entropy encoding techniques, tend to prevent error propagation by using proper synchronization markers (Sodagar et al., 2000) or considering some packetization techniques (Redmill & Kingsbury, 1996).

In Boyd et al. (1997), authors proposed a scheme reserving a space for an extra symbol (called forbidden symbol) that is in the source alphabet but never encoded. The technique provides excellent error detection but results in additional redundancy in the compressed bit-stream. However, this extra rate is small considering the error detection capability. The forbidden symbol technique was then integrated in different decoding schemes to provide AC error correction. Associated to an automatic repeat request (ARQ) protocol, the technique was used for error correction (Chou & Ramchandran; 2000, Anand et al., 2001).

More recent work tends to apply soft input sequence estimation algorithms for arithmetic decoding instead of hard input classical decoding. The proposed schemes consider different finite state representations for the arithmetic decoding machine and apply well known algorithms used in channel decoding such as Viterbi, List-Viterbi. In Elmasry and Shi (1999), the authors embeds channel coding in AC to enforce a minimum Hamming distance between compressed bit-streams and used the maximum a posteriori (MAP) estimator for soft input decoding. In Pettijohn et al. (2001) and Grangetto et al. (2005), sequential decoding schemes were applied on binary trees and path pruning technique was used based on the forbidden symbol error detection to improve decoding performance. Sayir (1999) used an arithmetic encoder adding redundancy in the compressed bit-stream by introducing gaps (equivalent to many forbidden symbols) in the coding space, and performs sequential decoding. In Guionnet and Guillemot (2003), authors used Bayesian networks to model the quasi-arithmetic encoder, and considered adding redundancy by introducing synchronization markers. A new 3-dimensional bit-synchronized trellis representing finite precision AC was recently proposed in Dongsheng et al. (2006) and provided to apply List-Viterbi soft input arithmetic decoding. A similar trellis was used in Ben-jamaa et al. (2008) to compute bounds on the error probability obtained with AC using different configurations of the forbidden symbol technique.