Inter-node compression with LDPC joint source–channel coding for highly correlated sources

Abstract

This paper investigates a new communication system where two nodes want to disseminate highly correlated contents to a single destination and can be applied for densely deployed wireless sensors networks applications. Motivated by their capacity-achieving performance and existing practical implementations, the proposed communication scheme is fully based on Low-Density Parity-Check (LDPC) codes for data compression and channel coding. More specifically, we consider a network of two correlated binary sources with two orthogonal communication phases. Data are encoded at the first source with an LDPC channel code and broadcast in the first phase. Based on the first source received data, the second source computes the correlation vector and applies a Joint Source–Channel (JSC) LDPC code, which output is communicated in the second phase. At the receiver, the whole network is mapped on a joint factor graph over which an iterative message-passing joint decoder is proposed. The aim of the joint decoder is to exploit the residual correlation between the sources for better estimation. Simulation results are investigated and compared to the theoretical limits and to an LDPC-based distributed coding system where no inter-node compression is applied.

KEYWORDS:

• Data compression
• distributed system
• correlated sources
• LDPC codes
• joint source/channel coding

1. Introduction

In densely deployed wireless sensor or internet of things networks, several nodes disseminate physical information to a central node for decision-making. Due to the redundant nature of the collected data, these nodes of information are generally correlated in space (different camera views, temperature or pressures samples from different sensors, etc.). In several cases, many nodes measure the same target phenomenon; hence, the correlation of the data is very high, which dominates the transmission bandwidth and can cause uplink congestion.

In the information and coding theory community, the problem of sending correlated data, with no communicating sources, to a unique destination is called distributed source coding, where the uncompressed correlation is exploited at the destination. The information theoretical lossless compression bounds on distributed source coding of two correlated sources are defined by the Slepian-Wolf (SW) theorem [1]. In fact, the latter states that two independent and identically distributed (i.i.d) sources can be compressed to a source rate $R_s=H(U_1,U_2)$, where $H(U_1,U_2)$ is the joint entropy of the sources $U_1$ and $U_2$ [1]. The result is also combined with the well-known Shannon theorem for the case of the transmission of correlated sources over noisy channels [2].

In this framework, several studies proposed practical joint source–channel coding and decoding techniques for the transmission of correlated sources [3–6]. In Ref. [3], the authors proposed Turbo-based JSC decoding that exploits the inter-source dependence to perform channel error-control for Additive White Gaussian Noise (AWGN) channels. Also, a similar system was investigated in [4] to transmit correlated sources over fading multiple access channels with three different source coding strategies. Besides, the authors in Ref. [5] proposed a hybrid digital/analog coding scheme to send correlated sources over discrete-memoryless two-way channels. Other contributions used channel codes to exploit the inter-sources correlation in the framework of distributed source coding [7–11]. LDPC-based iterative joint decoding schemes were proposed in [7, 9, 10], and the contributions were utilizing two types of iterations, named local and global iterations, to this aim. In the local iterations, the LDPC decoding process performs the Sum-Product (SP) algorithm independently for the two sources, then the estimation of the source’s correlation is performed at the global iterations. It was also demonstrated in [12] that Turbo Codes could reach the SW limit for distributed lossless source encoding.

All the presented contributions assume no inter-node communication. Hence, all the correlation is transmitted and then exploited by adequate JSC decoding. However, in wireless communications with orthogonal signalling, if the first source transmits its data, the latter is naturally broadcasted and received by the second source, and the correlation can be evaluated and compressed before transmission in the second phase. This remark motivates the current work where, unlike the described solutions, inter-node compression is used based on source LDPC codes, and JSC decoding is applied to exploit the residual correlation that remains after compression.

The proposed system aims to transmit two correlated binary sources to a destination over two independent AWGN channels. At the first source, an LDPC channel code is used. At the second source, based on the received data from the first source, we apply a JSC LDPC [13] coding to compress and protect the correlation vector. The main contributions behind this work are: First, inter-node compression coding system is introduced to transmit correlated binary sources based on JSC LDPC codes. Second, a global network Tanner graph is presented and used to apply a message-passing iterative joint decoding, that exploits the residual correlation of the two sources after compression. Simulation results are investigated and compared to Shannon-SW limits and to an equivalent LDPC-based system with distributed source coding.

This paper is organized as follows. Section 2 gives a detailed overview of the system model. Section 3 provides the message transfer decoding process. Investigation of the system efficiency based on simulation is emphasized in Section 4.

2. The proposed communication system with inter-node compression based on JSC LDPC codes

As mentioned, we study a joint coding system composed of two memoryless binary sources $S_1,S_2$ and one single destination. Each source communicates its own data to the destination through an independent AWGN channel, based on LDPC codes. As shown in Figure 1, the source $S_1$ generates a binary i.i.d sequence ${\mathbf{b}}_1$. We assume that the sequence ${\mathbf{b}}_1$ is $n_1$ bits length, and is encoded by an LDPC channel code providing a codeword ${\mathbf{c}}_1$, such as (1) $\begin{array}{r}{\mathbf{c}}_1={\mathbf{G}}_{\mathbf{c}{\mathbf{c}}_1}^{\mathbf{T}}\times {\mathbf{b}}_1\end{array}$(1) with the generator matrix ${\mathbf{G}}_{\mathbf{c}{\mathbf{c}}_1}$ of size ($n_1\times m_1$). Then, the encoded bit-stream ${\mathbf{c}}_1$ is broadcasted over AWGN channels by means of BPSK modulation. We denote by $R_{c{c}_1}=n_1/m_1$ the first source LDPC channel coding rate. Besides, the second source $S_2$ generates a binary data ${\mathbf{b}}_2$, which is supposed to be correlated with ${\mathbf{b}}_1$ by means of a crossover probability p. Otherwise, ${\mathbf{b}}_2={\mathbf{b}}_1\oplus \mathbf{z}$, where z is a random variable with a probability $\text{Pr}(z=1)=p$ and $\text{Pr}(z=0)=1-p$. The probability (1-p) also denoted by $\rho$ is defined as the correlation ratio between the two sources. The small the p is, the more correlated the sources are.

Figure 1. System model for inter-node correlation compression using LDPC codes.

At the second source, we can recover a noisy version of ${\mathbf{b}}_1$, after the wireless broadcast transmits phase of $S_1$. The received version will then be decoded at the second source to reconstruct an estimate of ${\mathbf{b}}_1$ called $\widehat{{\mathbf{b}}_1}$. The latter is obtained after a BP iterative decoding on the LDPC channel coding 1 Tanner graph constructed based on the $((m_1-n_1)\times m_1)$ parity check matrix ${\mathbf{H}}_{\mathbf{c}{\mathbf{c}}_1}$. Then, we construct the correlation vector as $\mathbf{e}=\widehat{{\mathbf{b}}_1}\oplus {\mathbf{b}}_2$ being the XOR of the vectors $\widehat{{\mathbf{b}}_1}$ and ${\mathbf{b}}_2$. The obtained vector e is very redundant, which motivated the use of an LDPC source encoder [13] with an ($l$×$n_2$) parity check matrix ${\mathbf{H}}_{\mathbf{s}\mathbf{c}}$ providing a compressed sequence as (2) $\begin{array}{r}\mathbf{d}={\mathbf{H}}_{\mathbf{s}\mathbf{c}}\times \mathbf{e}\end{array}$(2) The compressed sequence d is then encoded by a second LDPC channel code using the generator matrix ${\mathbf{G}}_{\mathbf{c}{\mathbf{c}}_2}$ with $(l\times m_2)$ dimensions as (3) $\begin{array}{r}{\mathbf{c}}_2={\mathbf{G}}_{\mathbf{c}{\mathbf{c}}_2}^{\mathbf{T}}\times \mathbf{d}\end{array}$(3)

The codeword ${\mathbf{c}}_2$ is modulated by BPSK and transmitted to the destination over an AWGN channel. $R_{sc}=l/n_2$ denotes the source coding rate of $S_2$ and $R_{c{c}_2}=l/m_2$ is the corresponding channel coding rate. Since we consider orthogonal signalling, the overall rate of the proposed system is $R=\frac{2R_{c{c}_1}{R}_{c{c}_2}}{R_{c{c}_2}+R_{c{c}_1}{R}_{sc}}$.

3. The joint network-mapped iterative decoder

The aim of the joint decoder, applied at the receiver, is to generate the best estimates of original sources data based on error-correcting LDPC decoding, while exploiting the residual correlation between the two sources after LDPC correlation compression.

Based on the factor graph representation available for source and channel LDPC codes, the network joint decoder of correlated sources can be described by two elementary connected decoders as shown in Figure 2. The global graph components are the channel decoder graph of source 1 and the joint source–channel decoder graph of source 2. The decoding process uses message transfer based on the Belief Propagation (BP) algorithm and is composed of two types of iterations: local iterations l and global iterations g. First, a local processing is applied where the LDPC channel decoder 1 of source 1 and the joint source–channel decoder 2 of source 2 apply the BP algorithm with a maximum number of local iterations, denoted by $l_{max}$. After these $l_{max}$ iterations, the outputs of the elementary decoders provide the estimates of ${\mathbf{b}}_1$ and e, denoted respectively by $\widehat{{\mathbf{b}}_1}$ and $\hat{\mathit{e}}$, which are inherently related to the second source original source sequence ${\mathbf{b}}_2$. We propose at a second decoding stage to compute an estimate of the source’s correlation using global iterations to enhance the performance of the joint decoders by providing extra a priori information. The latter is provided by the correlation update process depicted in Figure 3, where $\widehat{{\mathbf{b}}_2}$ vector is estimated as (4) $\begin{array}{r}\widehat{{\mathbf{b}}_2}=\widehat{{\mathbf{b}}_1}\oplus \hat{\mathit{e}}\end{array}$(4) As shown in Figure 2, the correlation estimate applied by updating the log-likelihood ratios (LLRs) during global iterations provides messages $L_{est}^{(g)}$($\widehat{{\mathbf{b}}_1}$) and $L_{est}^{(g)}$($\hat{\mathit{e}}$), passed respectively to the channel decoder graph 1 and the joint source–channel LDPC decoder 2 for further local iterations. We note that at the first global iteration g = 0, $L_{est}^{(g)}$($\widehat{{\mathbf{b}}_1}$) and $L_{est}^{(g)}$($\hat{\mathit{e}}$) are initialized to zero, and for the next iterations, they will be appended to the systematic variable nodes of each corresponding decoder. The joint global decoder messages transfer is described in more detail as follows for a specific l-th local and g-th global iteration.

Figure 2. The proposed joint decoder factor graph for $S_1$ and $S_2$ sources reconstruction.

Figure 3. The global iteration joint decoder block diagram with correlation exploitation and LLRs updating.

For the elementary LDPC channel decoder 1, the messages of the variable nodes $v=1,\dots ,m_1$ sent to a check nodes c are (5) $\begin{array}{r}{m}_{v,c}^{c{\text{c}}_1,(l)}=Z_v^{c{\text{c}}_1}+\sum _{c^{\mathrm{\prime }}\ne c}{m}_{c^{\mathrm{\prime }},v}^{c{\text{c}}_1,(l-1)}+L_{est}^{(g-1)}(\widehat{{\mathbf{b}}_1})\end{array}$(5) where $Z_v^{c{\text{c}}_1}=\frac{2r_v}{{\sigma }_n^2}$ are the channel observations LLRs used to initialize the variable nodes. $L_{est}^{(g-1)}(\widehat{{\mathbf{b}}_1})$ are the LLRs corresponding to the estimates of the vector $\widehat{{\mathbf{b}}_1}$ components at the global iteration g. $L_{est}^{(g)}(\widehat{{\mathbf{b}}_1})$ expression is (6) $\begin{array}{rl}{L}_{est}^{(g)}(\widehat{{\mathit{b}}_1})& =2tan{h}^{-1}\\ & \times \left(\text{tanh}\left(\frac{L^{(g)}(\widehat{{\mathbf{b}}_2})}{2}\right)\times tanh\left(\frac{L^{(g)}(\hat{\mathit{e}})}{2}\right)\right)\end{array}$(6) where $L^{(g)}(\widehat{{\mathbf{b}}_2})$ are the LLRs corresponding to the vector ${\mathbf{b}}_2$ components estimated as [9] (7) $\begin{array}{r}{L}^{(g)}(\widehat{{\mathbf{b}}_2})=log\left(\frac{k-w_H}{w_H}\right)\end{array}$(7) with k and $w_H$ being respectively the length and the Hamming weight of sequence $\widehat{{\mathbf{b}}_2}$.

The messages $L^{(g)}(\hat{\mathit{e}})$ are computed after $l_{max}$ local iterations at the second source joint graph by (8) $\begin{array}{r}{L}^{(g)}(\hat{\mathit{e}})=Z_v^{sc}+\sum _{c^{\mathrm{\prime }}}{m}_{c^{\mathrm{\prime }},v}^{sc(l_{max}-1)}\end{array}$(8) The messages delivered by the check nodes $c=1,\dots ,n_1$ of the channel decoder 1 to the connected variable nodes are evaluated as (9) $\begin{array}{r}{m}_{c,v}^{c{c}_1,(l)}=2tan{h}^{-1}\left(\prod _{v^{\mathrm{\prime }}\ne v}\tanh \left(\frac{m_{v^{\mathrm{\prime }},c}^{c{c}_1,(l)}}{2}\right)\right)\end{array}$(9)

The joint source–channel LDPC decoding process message transfer for the second source elementary decoder behaves the same [13]. However, in this proposed system, we append the correlation update messages to the variable nodes of the LDPC source decoding part. Hence, after a fixed number of local iterations, the updating LLR for the variable nodes of the LDPC source decoder is calculated as (10) $\begin{array}{r}{m}_{v,c}^{sc,(l)}=Z_v^{sc}+\sum _{c^{\mathrm{\prime }}\ne c}{m}_{c^{\mathrm{\prime }},v}^{sc,(l-1)}+L_{est}^{(g-1)}(\hat{\mathit{e}})\end{array}$(10) where $L_{est}^{(g-1)}$($\hat{\mathit{e}}$) are the LLRs associated to a vector $\hat{\mathit{e}}$. The LLRs $L_{est}^{(g)}$($\hat{\mathit{e}}$) are evaluated as (11) $\begin{array}{rl}{L}_{est}^{(g)}(\hat{\mathit{e}})& =2tan{h}^{-1}(\text{tanh}\left(\frac{L^{(g)}(\widehat{{\mathbf{b}}_2})}{2}\right)\\ & \times tanh\left(\frac{L^{(g)}(\widehat{{\mathbf{b}}_1})}{2}\right))\end{array}$(11) and $L^{(g)}(\widehat{{\mathbf{b}}_1})$ is given by (12) $\begin{array}{r}{L}^{(g)}(\widehat{{\mathbf{b}}_1})=Z_v^{c{\text{c}}_1}+\sum _{c^{\mathrm{\prime }}}{m}_{c^{\mathrm{\prime }},v}^{c{\text{c}}_1,(l_{max}-1)}\end{array}$(12) After a fixed number of global iterations of the joint global decoder, the sequence $\widehat{{\mathbf{b}}_1}$ is estimated based on the following a posteriori LLR (13) $\begin{array}{rl}L(\widehat{{\mathbf{b}}_1})& =Z_v^{c{\text{c}}_1}+\sum _{c^{\mathrm{\prime }}}{m}_{c^{\mathrm{\prime }},v}^{c{\text{c}}_1,(l_{max})}\\ & +L_{est}^{(g)}(\widehat{{\mathbf{b}}_1})\text{ for }v=1,\dots ,n_1\end{array}$(13)

Also, the information vector $\widehat{{\mathbf{b}}_2}$ is estimated based on the correlation vector, LLRs calculated by (14) $\begin{array}{r}L(\hat{\mathit{e}})=Z_v^{sc}+\sum _{c^{\mathrm{\prime }}}{m}_{c^{\mathrm{\prime }},v}^{sc,(l_{max})}+L_{est}^{(g)}(\hat{\mathit{e}})\text{ for }v=1,\dots ,n_2\end{array}$(14)

4. Simulation results

In this section, we investigate the performance of the proposed inter-node compression scheme with JSC LDPC codes. Also, we compare the performance of our proposed system to a distributed coding system [11] where no communication is allowed between the two sources, and the correlation is fully exploited at the decoder (not compressed). The distributed coding system is composed of two binary sources, where data are encoded independently by LDPC channel codes and then sent to the destination through AWGN channels.

We consider a binary i.i.d sequence with information length $n_1$ = 1800 bits, a regular LDPC channel code with a code rate $R_{c{c}_1}=1/2$, and degrees defined by ($d_v$ = 3, $d_c$ = 6) at source $S_1$. At the second source, we assume $n_2=1800$ bits and apply a JSC source and channel LDPC regular codes with respective rates $R_{sc}=1/2$ and $R_{c{c}_2}=1/2$ with (3, 6) degrees. The overall rate of the system is R = 2/3. At the decoder, we apply the described message passing algorithm with a maximum number of local iterations equal to $l_{max}=100$ and different number of global iterations denoted by GI. Also, we assume that the two sources have the same distance to the destination, and consequently the same signal-to-noise ratio. However, we suppose that the $S_1$is too close to $S_2$ and the inter-nodes link suffers from no communication errors $\widehat{({\mathbf{b}}_1}={\mathbf{b}}_1)$. We studied in [14] the case where wireless link between sources is noisy with a bit error probability pe. This case can be tackled by applying an LLR updating function [14] and is omitted in this paper. For the reference distributed system, we consider channel coding rates $R_{c{c}_1}=2/3$ and $R_{c{c}_2}=2/3$ with constant degrees (3, 9), which means a global rate equal to 2/3.

In Figure 4, we plot the BER performance as a function of the E_so/N₀ for the inter-node compression system (system 1) and distributed coding system (system 2). We note that the crossover probability p between the two sources, used in this experiment, is equal to 0.01. In our investigations, to analyze the efficiency of the proposed joint decoder, we also consider the theoretical SW/Shannon bound proposed in [15], where E_so/N₀ should be greater than (15) $\begin{array}{r}\frac{E_{so}}{N_0}{|}_{lim}=\frac{2^{H(S_1,S_2)R}-1}{2R}\end{array}$(15) where E_so is the energy per source bit, $N0=2{\sigma }_n^2$ is the noise power spectral density, $H(S_1,S_2)$ is the source’s joint entropy, and R is the overall coding rate. The joint entropy is given by $H(S_1,S_2)=H(S_1)+h(p)$ and depends on the first source entropy H(S1) (equal to 1 here) and on the crossover probability p.

Figure 4. BER performance for equivalent rates compression of inter-source correlations and distributed coding systems with crossover probability p = .01.

From the obtained results, we observe that the performance of the system 1 in the waterfall region is better than the system 2. The proposed system provides a gain of about 2.2 dB for BER equal to ${10}^{-2}$ and with no global iterations (GI = 0).

The gap of the proposed system with respect to the SW/Shannon theoretical limit is less than 1 dB. However, while it is clear that the performance of the distributed system 2 is substantially improved after exploiting the source’s correlation during the global iterations, the latter has no impact on the performance of our proposed system with inter-node compression. Indeed, this behaviour is explained by the fact that the compression scheme applied at the second source reduces drastically the correlation between the sources, hence there is no residual redundancy to exploit. Otherwise, if no extra computation is allowed at the destination node, the inter-node compression can be beneficial since we can reach fair performance with no need of global iterations. Finally, we also remark a higher error floor, justified by the compression loss, which depends on the source coding operation, applied at the second source and is specific to the joint LDPC source coding process.

We previously demonstrated in [16] that in the case of point-to-point communication, the joint LDPC system can reach better improvements as the source is highly correlated and provides less error floors. In the second set of experiments, we study, in Figure 5, the effect of the crossover probability p on the performance of the inter-node compression system in the waterfall and error floor regions.

Figure 5. BER performance for system 1 with different crossover probability p.

We propose three crossover probabilities p: p = .02 with $H(S_1,S_2)=1.14$, p = .01 and $H(S_1,S_2)=1.08$, and p = .003 with $H(S_1,S_2)=1.029$. Also, we use the theoretical limit of E_so/N₀ as benchmark for the different values of p. We recall that the number of global iterations is oversized especially for high values of p where no improvement is obtained, due to LDPC correlation compression. We can conclude from the results that having a lower parameter p involves better improvement in both waterfall and error floor regions. We observe a gain of about 0.3 dB with p = 0.003 compared to the case where p = .01 for a $\text{BER}={10}^{-2}$ with a reduced error floor. The practical system behaviour agrees also with the theoretical limits, and always a gap less than 1 dB is achieved.

5. Conclusion

In this paper, we study a joint source–channel coding system that compresses the inter-node correlations based on LDPC codes. First, we presented the system model, which is composed of two binary sources and one destination, and with two communication phases. Second, we developed a joint decoder with two stages of iterations to exploit the source correlation. Based on computer simulations, we demonstrated that the proposed system could provide slightly better results in the waterfall region compared to a distributed coding system exploiting the source correlation without applying any global iterations at the cost of a quality loss for high SNRs. The proposed system can be beneficial for downlink wireless sensor network systems, where computation cost is increased at the intermediate source with XORing and LDPC compression, but very low processing is needed at the destination by omitting global iterations.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work has received a French government support granted to the Cominlabs excellence laboratory and managed by the National Research Agency in the Investing for the Future program under reference ANR-10-LABX-07-01.