Delayed Coding Scheme for Channels with Insertion, Deletion, and Substitution Errors

We consider the concatenation of a binary input–output ID channel with a binary symmetric channel, i.e., an IDS channel [6, 9]. Let $\bm{X}=(X_{1},X_{2},\ldots,X_{n})\in\{0,1\}^{n}$ denote the input sequence. In this channel, each input bit $X_{t}$, $t\in\{1,\ldots,n\}$, is deleted with probability $p_{\rm id}/2$, replaced by two random bits (i.e., insertion) with probability $p_{\rm id}/2$, or transmitted with probability $1-p_{\rm id}$. During transmission, $X_{t}$ is flipped with a probability of $p_{\rm s}$. Through this process, $\bm{X}$ is mapped to the output sequence $\bm{Y}=(Y_{1},Y_{2},\ldots,Y_{n^{\prime}})\in\{0,1\}^{n^{\prime}}$, where $n^{\prime}$ can be larger or smaller than $n$. For ID-type channels, the process $Y_{t}$ is typically formulated as the output of a hidden Markov model (HMM). Similar to [7, 8, 9], we adopt the channel state process $S_{t}$ given by a simple random walk in the presence of reflecting boundaries over the set $\{-D_{\rm max},...,+D_{\rm max}\}$, where $D_{\rm max}$ is the maximum allowed drift ($D_{\rm max}>0$). The state $S_{t}=i$ represents the timing drift at time $t$ (the difference between the number of transmitted and received bits is $i$). The maximum drift $D_{\rm max}=8$ is used in this study based on observations in [8].

For ID-type channels, instead of capacity, the SIR is generally used as an achievable information rate. The SIR is defined as

that is, the mutual information rates between the i.i.d. equiprobable inputs and corresponding outputs. The estimation of $C_{\rm SIR}$ was carried out in [10, 11] based on the Shannon–McMillan–Breiman theorem for discrete stationary ergodic random processes.

We now describe the proposed DC scheme for channels with ID errors. The main idea underlying our scheme is inspired by a synchronization marker [6] and recently proposed modulation technique called delayed bit interleaved coded modulation [12].

Let $\bm{c}_{t}=(c_{1},c_{2},\ldots,c_{n})\in\{0,1\}^{n}$ represent the interleaved codeword selected from a binary linear code $\mathcal{C}$ at time $t\in\{1,\ldots,L\}$, where $L$ is the number of transmitted codewords. Hereafter, no distinction is made between codewords and “interleaved” codewords. At the transmitter side, each codeword is divided into $m$ subblocks $\bm{c}_{t}^{(1)},\bm{c}_{t}^{(2)},\ldots,\bm{c}_{t}^{(m)}$ of $n/m$ bits (for simplicity, $n$ is assumed to be divisible by $m$). For $i\in\{1,\ldots,m\}$, each subblock $\bm{c}^{(i)}_{t}$ is associated with a delay $T_{i}\in\{0,\ldots,T_{\rm max}\}$, where $T_{\rm max}$ denotes the maximum allowed delay. We call $\bm{T}=(T_{1},T_{2},\ldots,T_{m})$ a delay scheme. While using a delay scheme $\bm{T}$, the $t$-th transmitted sequence $\bm{x}_{t}\in\{0,1\}^{n}$, $t\in\{1,\ldots,L+T_{\rm max}\}$, is obtained by interleaving $\bm{c}^{(1)}_{t-T_{1}},\bm{c}^{(2)}_{t-T_{2}},\ldots,\bm{c}^{(m)}_{t-T_{m}}$ as follows:

where $||$ denotes the interleaving operator. The sequence $\bm{x}_{t}$ is transmitted over an IDS channel, and the corresponding output $\bm{y}_{t}$ is observed at the receiver. Figure 1 shows the configuration of transmitted sequences for $\bm{T}=(0,1,2,3)$ and $L=5$, where $m=4$ and $T_{\rm max}=3$. As shown in the figure, to start and terminate the encoding process, known bits (white-colored blocks in Fig. 1) participate in some transmitted sequences. In this study, we set these known-bits to be independent and uniformly distributed (i.u.d.), and the delay scheme $\bm{T}=(0,1,\ldots,T_{\rm max})$ is employed for a given $T_{\rm max}$.

As explained in the following subsection, the delay and known bits lead to a performance improvement in detection (re-synchronization). However, they also incur a rate loss. Given a code rate $R$ of a component code $\mathcal{C}$, the transmission rate of the DC scheme is

We can see that, for large $L$ $(L\gg T_{\rm max})$, $R_{\rm DC}$ approaches $R$. Note that the DC scheme does not impose a constant rate-loss as required for the use of inner codes.

For future use, we introduce the sets $\mathcal{D}_{j}$ and $\mathcal{\tilde{D}}_{j}$ characterized by a given DC scheme. For $j\in\{0,\ldots,T_{\rm max}\}$, $\mathcal{D}_{j}=\{i\mid T_{i}=j\}$ and $\mathcal{\tilde{D}}_{j}=\{i\mid j<T_{i}\}$ denote the index sets of subblocks $i$ at delay equal to $j$ and larger than $j$, respectively.

We explain the chained detection and decoding algorithm used in the DC scheme in this section. This algorithm proceeds by successively estimating original codewords $\bm{c}_{t}$, $t\in\{1,\ldots,L\}$, one by one starting from $t=1$ to $L$, where priorly decoded codewords help to recover the current codeword in the detection. The MAP detector, implemented with the Bahl–Cocke–Jelinek–Raviv (BCJR) algorithm, is employed here.

For $i\in\{1,\ldots,L\}$, $\bm{q}_{i}=(\bm{q}_{i}^{(1)},\bm{q}_{i}^{(2)},\ldots,\bm{q}_{i}^{(m)})$ denotes the extrinsic soft-messages output from the $i$-th code decoder, whereas $\bm{o}_{i}=(\bm{o}_{i}^{(1)},\bm{o}_{i}^{(2)},\ldots,\bm{o}_{i}^{(m)})$ denotes the sequence of log-APP ratios provided by the detector. These $\bm{q}_{i}$ and $\bm{o}_{i}$ correspond to the $i$-th codeword $\bm{c}_{i}$ and are also expressed as using $m$ divided subblocks. Let us now look at the procedure for estimating $\bm{c}_{t}$. The $t$-th estimation can operate after the $(t-1)$-th estimation is completed and the sequences $\bm{y}_{t},\bm{y}_{t+1},\ldots,\bm{y}_{t+T_{\rm max}}$ are received. First, for all $i\in\{0,\ldots,T_{\rm max}\}$, we run the MAP detection for the sequence $\bm{y}_{t+i}$ given priori messages $\bm{q}_{t-T_{j}}^{(j)}$, $j\in\mathcal{\tilde{D}}_{i}$, and exploit a part of the log-APP ratios sequence $\bm{o}_{t}^{(j)}$, $j\in\mathcal{D}_{i}$. This is illustrated in Fig. 2, where $\bm{T}=(0,1,2,3)$ (i.e., $\mathcal{D}_{i}=\{i+1\}$ for $i\in\{0,\ldots,T_{\rm max}\}$, $\mathcal{\tilde{D}}_{0}=\{2,3,4\}$, $\mathcal{\tilde{D}}_{1}=\{3,4\}$, $\mathcal{\tilde{D}}_{2}=\{4\}$, and $\mathcal{\tilde{D}}_{3}=\phi$). As shown in the figure, the log-APP ratios $\bm{o}_{t}$ are collected from different $(T_{\rm max}+1)$ received sequences and then fed to the $t$-th code decoder, such as the BP decoder of an LDPC code. Finally, the decoder estimates $\bm{c}_{t}$, operating as it would on a memoryless channel, and sends the extrinsic messages $\bm{q}_{t}^{(j)}$, $j\in\mathcal{\tilde{D}}_{0}$ to subsequent estimations.

As shown in Fig. 2, at the $t$-th estimation round, the MAP detector can use reliable a priori information corresponding to the pre-estimated codewords $\bm{c}_{t-3}$, $\bm{c}_{t-2}$, and $\bm{c}_{t-1}$. Moreover, the known bits provide perfect a priori information to the detector. In other words, these reliable bits behave as pilot symbols. The chained estimation strategy benefits from this advantage, which prevents the DC scheme from using a joint iterative detection and decoding strategy.

Before leaving this section, we compare the computational complexity between the existing and DC schemes in terms of the MAP detection. It goes without saying that the non-iterative scheme typically used with concatenated codes has the lowest complexity because it applies the MAP detection only once. For the iterative scheme, the execution number of the MAP detection depends on the received sequences, channel parameters, code structures, and decoder configuration. For instance, if we use a standalone LDPC code with a BP-based decoding algorithm, the detection is performed at every iteration until all parity check equations are satisfied, or a predefined number of iterations is reached. Meanwhile, for the DC scheme, the MAP detection is performed just $(T_{\rm max}+1)$ times before channel code decoding. Note that these multiple detections are parallelizable because they are performed on received sequences that are independent of each other. Such a structure and non-iterative data flow strategy can improve the throughput and latency of the receiver and mitigate the effect of delay due to the DC scheme.

For memoryless symmetric channels, density evolution[4] is well known as a useful technique to predict the asymptotic performance of LDPC codes with BP-based decoding algorithms. This technique is also extended to channels with states or/and asymmetric nature[7, 13, 14], where LDPC coset codes are employed. Building on their results, we can establish the density evolution for the DC scheme with LDPC coset codes. When using LDPC codes, the chained estimation algorithm of the DC scheme involves $(T_{\rm max}+1)$ MAP detection and subsequent BP decoding for each codeword/time instant $t\in\{1,\ldots,L\}$, starting from $t=1$. Here, our interest is the convergence behavior of the BP decoding for the $t$-th codeword. We assume that the $t^{\prime}$-th ($t^{\prime}<t$) BP decoder produces a probability of error that converges to zero as the number of BP iterations tends to infinity, i.e., the prior decoding round is successful. Under this assumption, the transmission of the $t$-th codeword is reduced to the transmission over a DCSC. Therefore, by running density evolution for a DCSC, we can predict the asymptotic threshold (i.e., the BP threshold) of an ID probability $p^{\ast}_{\rm id}$ over the IDS channel with a given $p_{\rm s}$.

In this study, we primarily investigate the irregular LDPC code ensembles introduced in [4]. They are specified by degree distribution pairs $\lambda(x)=\sum^{d_{\rm v}}_{i=2}\lambda_{i}x^{i-1}$ and $\rho(x)=\sum^{d_{\rm c}}_{i=2}\rho_{i}x^{i-1}$, where $\lambda_{i}$ (resp. $\rho_{i}$) denotes the fraction of the edges connected to the degree $i\geq 2$ variable (resp. check) nodes and $d_{\rm v}$ (resp. $d_{\rm c}$) denotes the maximum degree of the variable (resp. check) nodes. The design rate of an LDPC code is given by $R=1-(\int_{0}^{1}\rho(x)dx/\int_{0}^{1}\lambda(x)dx)$.

Let us now compare the BP thresholds of some existing irregular LDPC codes of a rate $R=0.5$, whose degree distributions are shown in Table I. The ID and IDS codes are designed for the iterative scheme over the ID ($p_{\rm s}=0$) and IDS ($p_{\rm s}=0.04$) channels, respectively. In Table II, we show the BP thresholds of these codes with the DC scheme. For comparison, we also show the SIRs and BP threshold of the $C(J=3,K=6,L)$ SC-LDPC code [16] (variable node degree $J$, check node degree $K$, and coupling length $L$). We can see that, with the iterative scheme, the ID, IDS, and SC-LDPC codes exhibit outstanding performance, whereas the Bi-AWGN code cannot correct IDS errors. However, interestingly, for the Bi-AWGN code with the DC scheme, the BP thresholds approach the corresponding BCJR-once rates (see Fig. 4) given $T_{\rm max}$ and are close to the SIRs, without depending on $p_{\rm s}$. This is also observed for the DC scheme with the SC-LDPC code. These results indicate that the DC scheme provides its universal performance even in conjunction with practical linear codes and decoding schemes. For this to be realized, careful code selection is necessary. More precisely, it seems reasonable to use codes designed for random errors, instead of ID and IDS codes, which have many low-degree check nodes.

In this section, we present the simulation results of finite-length LDPC codes with the DC scheme. We compare the bit-error rate (BER) performance of the following schemes: (1) the DC scheme (we use $\bm{T}=(0,1,\ldots,T_{\rm max})$) with the Bi-AWGN code, (2) the iterative scheme with the $C(3,6,25)$ SC-LDPC and ID codes, and (3) the non-iterative scheme with concatenated rate-$0.5$ optimized LDPC and marker codes[6] (two-bit markers are inserted into an LDPC codeword every 10 bits).

Figure 6 shows the BER curves with length $n\approx 5\times 10^{4}$ LDPC codes as a function of $p_{\rm id}$ with a sufficient number of iterations, where $p_{\rm s}=0$. From the figure, the good performance can be obtained with the DC scheme for a wide range of $T_{\rm max}$, with a sharp waterfall drop in BER. The BER curves of the DC scheme are positioned between the non-iterative and iterative schemes, and approach the latter when $T_{\rm max}=15$ at ID probabilities around $p_{\rm id}=0.08$. Table III shows the average number of executions of MAP detection for the DC and iterative schemes. Although it is clear from Fig. 6 that the BERs of both schemes are vanishing (we did not observe any errors in our simulations), the DC scheme has smaller execution numbers compared with the iterative scheme. At $p_{\rm id}=0.080$, in terms of the complexity of detection, the DC scheme is 2 and 4.5 times as efficient as the iterative scheme with the ID and $C(3,6,25)$ SC-LDPC codes, respectively.