Distributed Arithmetic Coding for Sources with Hidden Markov Correlation

We consider the problem of Slepian-Wolf Coding (SWC) with decoder Side Information (SI). The encoder compresses discrete source $X=\{x_{t}\}_{t=1}^{N}$ in the absence of $Y=\{y_{t}\}_{t=1}^{N}$, discretely correlated SI. Slepian-Wolf theorem points out that lossless compression is achievable at rates $R\geq H(X|Y)$, the conditional entropy of $X$ given $Y$, where both $X$ and $Y$ are discrete random processes [1]. Conventionally, channel codes, such as turbo codes [2] or Low-Density Parity-Check (LDPC) codes [3], are used to deal with the SWC problem.

Recently, some SWC techniques based on entropy coding are proposed, such as Distributed Arithmetic Coding (DAC) [4, 5] and Overlapped Quasi-Arithmetic Coding (OQAC) [6]. These schemes can be seen as an extension of classic Arithmetic Coding (AC) whose principle is to encode source $X$ at rates $H(X|Y)\leq R<H(X)$ by allowing overlapped intervals. The overlapping leads to a larger final interval and hence a shorter codeword. However, ambiguous codewords are unavoidable at the same time. A soft joint decoder exploits SI $Y$ to decode $X$. Afterwards, the time-shared DAC (TS-DAC) [7] is proposed to deal with the symmetric SWC problem. To realize rate-incremental SWC, the rate-compatible DAC is proposed in [8].

In this paper, we research how to use the DAC to compress sources with hidden Markov correlation.

Let $p$ be the bias probability of binary source $X$, i.e., $p=P(x_{t}=1)$. In the classic AC, source symbol $x_{t}$ is iteratively mapped onto sub-intervals of $[0,1)$, whose lengths are proportional to $(1-p)$ and $p$. The resulting rate is $R\geq H(X)$. In the DAC [4], interval lengths are proportional to the modified probabilities $(1-p)^{\gamma}$ and $p^{\gamma}$, where

The resulting rate is $R\geq\gamma H(X)\geq H(X|Y)$. To fit the $[0,1)$ interval, the sub-intervals have to be partially overlapped. More specifically, symbols $x_{t}=0$ and $x_{t}=1$ correspond to intervals $[0,(1-p)^{\gamma})$ and $[1-p^{\gamma},1)$, respectively. It is just the overlapping that leads to a larger final interval, and hence a shorter codeword. However, as a cost, the decoder can not decode $X$ unambiguously without $Y$.

To describe the decoding process, we define a ternary symbol set $\{0,\chi,1\}$, where $\chi$ represents a decoding ambiguity. Let $C_{X}$ be the codeword and $\tilde{x}_{t}$ be the $t$-th decoded symbol, then

When the $t$-th symbol is decoded, if $\tilde{x}_{t}=\chi$, the decoder performs a branching: two candidate branches are generated, corresponding to two alternative symbols $x_{t}=0$ and $x_{t}=1$. For each new branch, its metric is updated and the corresponding interval is selected for next iteration. To reduce complexity, every time after decoding a symbol, the decoder uses the $M$-algorithm to keep at most $M$ branches with the best partial metric, and prunes others [4].

Note that the metric is not reliabe for the very last symbols of a finite length sequence $X$ [5]. This problem is solved by encoding the last $T$ symbols without interval overlapping [5]. It means that for $1\leq t\leq(N-T)$, $x_{t}$ is mapped onto $[0,(1-p)^{\gamma})$ and $[1-p^{\gamma},1)$; while for $(N-T+1)\leq t\leq N$, $x_{t}$ is mapped onto $[0,1-p)$ and $[1-p,1)$.

Therefore, a binary DAC system can be described by four parameters: $\{p,\gamma,M,T\}$.

Let $S=\{s_{t}\}_{t=1}^{N}$ be a sequence of states and $Z=\{z_{t}\}_{t=1}^{N}$ be a sequence of observations. A hidden Markov process is defined by $\lambda=(A,B,\pi)$:

$A=\{a_{ji}\}$: state transition probability matrix, where $a_{ji}=P(s_{t}=i|s_{t-1}=j)$;

$B=\{b_{i}(k)\}$: observation probability distribution, where $b_{i}(k)=P(z_{t}=k|s_{t}=i)$;

$\pi=\{\pi_{i}\}$: initial state distribution, where $\pi_{i}=P(s_{1}=i)$.

The aim of forward algorithm is to compute $P(z_{1},...,z_{t}|\lambda)$, given observation $\{z_{1},...,z_{t}\}$ and model $\lambda$. Let $\alpha_{t}(i)$ be the probability of observing the partial sequence $\{z_{1},...,z_{t}\}$ such that state $s_{t}$ is $i$, i.e.,

Initially, we have

For $t>1$, $\alpha_{t}(i)$ can be induced through iteration

Therefore,

In practice, $\alpha_{t}(i)$ is usually normalized by

where

In this case, we have

Assume that binary source $X$ and SI $Y$ are correlated by $Y=X\oplus Z$, where $Z$ is generated by a hidden Markov model with parameter $\lambda$. $X$ is encoded using a $\{p,\gamma,M,T\}$ DAC encoder. The decoding process is very similar to what described in [4]. The only difference is that the forward algorithm is embedded into the DAC decoder and the metric of each branch is replaced by $P(z_{1},...,z_{t}|\lambda)$, where $z_{t}=x_{t}\oplus y_{t}$.

We have implemented a 16-bit DAC codec system. The bias probability of $X$ is $p=0.5$. According to the recommendation of [5], we set $M=2048$ and $T=15$. The same 2-state (0 and 1) and 2-output (0 and 1) sources as in [9] are used in simulations (see Table I). The length of data block used in each test is $N=1024$.

To achieve lossless compression, each test starts from $\gamma=H(X|Y)$ (see Table II). If the decoding fails, we increase $\gamma$ with 0.01. Such process is iterated until the decoding succeeds. For each model, results are averaged over 100 trials. Experimental results are enlisted in Table II.

For comparison, also included in Table II are experimental results for the same settings from [9]. In each test of [9], $N=16384$ source symbols are encoded using an LDPC code. In addition, to synchronize the hidden Markov model, $N\alpha$ original source symbols are sent to the decoder directly without compression.

The results show that the DAC performs similarly to or slightly better than (for models 1 and 2) the LDPC-based approach [9]. Moreover, for hidden Markov correlation, the DAC outperforms the LDPC-based approach in two aspects:

1). The LDPC-based approach requires longer codes to achieve better performance, while the DAC is insensitive to code length [4].

2). For the LDPC-based approach, to synchronize the hidden Markov model, a certain proportion of original source symbols must be sent to the decoder as “seeds”. However, it is hard to determine $\alpha$, the optimal proportion of “seeds”. The results reported in [9] were obtained through an exhaustive search, which limits its application in practice.

This paper researches the compression of sources with hidden Markov correlation using the DAC. The forward algorithm is incorporated into the DAC decoder. The results are similar to that of the LPDC-based approach. Compared to the LDPC-based approach, the DAC is more suitable for practical applications.