Chase-Like Decoding of Arithmetic Codes with Applications

Chase-Like Decoding of Arithmetic Codes with Applications

Amin Zribi (Ecole Nationale des Ingénieurs de Tunis, Tunisia and Université Européenne de Bretagne, France), Sonia Zaibi (Ecole Nationale des Ingénieurs de Tunis, Tunisia), Ramesh Pyndiah (Université Européenne de Bretagne, France) and Ammar Bouallègue (Ecole Nationale des Ingénieurs de Tunis, Tunisia)
Copyright: © 2011 |Pages: 14
DOI: 10.4018/ijcvip.2011010103

Abstract

Motivated by recent results in Joint Source/ Channel (JSC) coding and decoding, this paper addresses the problem of soft input decoding of Arithmetic Codes (AC). A new length-constrained scheme for JSC decoding of these codes is proposed based on the Maximum a posteriori (MAP) sequence estimation criterion. The new decoder, called Chase-like arithmetic decoder is supposed to know the source symbol sequence and the compressed bit-stream lengths. First, Packet Error Rates (PER) in the case of transmission on an Additive White Gaussian Noise (AWGN) channel are investigated. Compared to classical arithmetic decoding, the Chase-like decoder shows significant improvements. Results are provided for Chase-like decoding for image compression and transmission on an AWGN channel. Both lossy and lossless image compression schemes were studied. As a final application, the serial concatenation of an AC with a convolutional code was considered. Iterative decoding, performed between the two decoders showed substantial performance improvement through iterations.
Article Preview

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 9: 4 Issues (2019): Forthcoming, Available for Pre-Order
Volume 8: 4 Issues (2018)
Volume 7: 4 Issues (2017)
Volume 6: 2 Issues (2016)
Volume 5: 2 Issues (2015)
Volume 4: 2 Issues (2014)
Volume 3: 4 Issues (2013)
Volume 2: 4 Issues (2012)
Volume 1: 4 Issues (2011)
View Complete Journal Contents Listing