Efficient information reconciliation in quantum key distribution systems using informed design of non-binary LDPC codes

In this paper, we provide techniques to get high IR rates without a large increase in the key generation complexity by optimizing the MLC scheme of [6]. Our techniques involve NB-LDPC code design considering the properties of the ET-QKD channel resulting in higher IR rates compared to conventional LDPC codes. In particular, the contributions of this paper are listed as follows: Overall, as demonstrated in Fig. 1, the NB-MLC(a) protocol with a small value of a that utilizes the above proposed techniques results in a significant 40–60\(\%\) improvement in the IR rate compared to the MLC scheme without much increase in complexity.

In this paper, we focus on the entanglement-based ET-QKD protocol and show that it can result in high secret key rates. Along with the above ET-QKD protocol, various other QKD protocols have been proposed for this application that differ in the quantum step of raw key generation compared to the ET-QKD protocol considered in this paper. In [28, 29], twin-field (TF) QKD protocols were proposed for use in practical quantum communication networks. To reduce the experimental complexity and allow free-space realization while maintaining high secret key rates, asynchronous measurement-device independent QKD protocols were proposed in [30, 31]. To mitigate the effect of device imperfections, a phase-matching QKD protocol was proposed in [32]. Quantum digital signature techniques were proposed in [33] to achieve various cryptographic tasks such as integrity, authenticity, and non-repudiation. Along with the above works, various experimental works such as [34‐37] demonstrate the feasibility of using QKD and quantum cryptography protocols in real-world applications.

The rest of this paper is organized as follows. In Sect. 2, we provide the preliminaries and the ET-QKD system model. We describe the NB-MLC(a) protocol in Sect. 3. In Sect. 4, we provide the techniques to optimize the NB-MLC(a) protocol that include the JRDO algorithm and the IDC scheme. Finally, we provide simulation results in Sect. 5 to demonstrate the improvements provided by our techniques and conclude the paper in Sect. 6.

As discussed in Sect. 1, an ET-QKD system consists of the following steps:

As suggested in [24, 40] and also observed from our ET-QKD experiment testbed [9], the ET-QKD channel \(P_{Y|X}\) in the raw key generation step is a mixture of a local and a global channel modeling local and global errors, respectively. Local errors are caused by timing jitters and synchronization errors that result in the two entangled photons falling into different but close enough bins. Global errors are caused due to channel losses and accidental concurrent detection of two non-entangled photons in the same frame. Experimental results show that the local channel is well-fitted by a discretized Gaussian distribution, whereas the global channel is well-fitted by a mixture of a discretized Gaussian and a uniform distribution. Overall, the ET-QKD channel can be approximated using the transition probabilitywhere the parameters \(\alpha \) and \(\beta \), respectively, determine the strengths of the Gaussian component and the uniform component of the global channel in the overall channel transition probability and c is a normalization constant. We observe from our experimental data that \(\mu _1\) and \(\mu _2\) are both nonzero which makes the ET-QKD channel asymmetric. This asymmetry is due to the misalignment of the center of the bins with the real arrival time of photons [40]. The global component of the channel causes a low SNR in our system resulting in a high operating frame error rate (FER) (\(\sim 1-10 \%\)). Finally, note that the distribution \(P(X = x)\) is uniform in \({{\mathbb {G}}}{{\mathbb {F}}}(q)\).

Figure 3 provides a comparison of the model in Eq. (3) with that of the empirical transition probabilities obtained from our experimental data. We can see the model closely approximates the data for different choices of q and binwidth. Importantly, the ET-QKD channel is different from conventional channels such as AWGN, BSC, etc. As such, LDPC codes that have been optimized for these channels are not necessarily the best ones for the ET-QKD channel.

A NB-LDPC code over \({{\mathbb {G}}}{{\mathbb {F}}}(2^g)\), where \(g\) is a positive integer, is defined by a sparse parity check matrix \({\textbf{H}}\in {{\mathbb {G}}}{{\mathbb {F}}}(2^g)^{M \times N}\). The matrix \({\textbf{H}}\) has a Tanner graph representation comprising of M check nodes (CNs) and N variable nodes (VNs) corresponding to rows and columns of \({\textbf{H}}\). A CN is connected to a VN by an edge if the corresponding entry in \({\textbf{H}}\) is nonzero where the edge is additionally labeled by the nonzero entry. The interconnection between VNs and CNs of a code is represented by node-perspective degree distributions \(L(x) = \sum _d L_dx^{d}\) and \(P(x) = \sum _dP_dx^{d}\), where \(L_d\) and \(P_d\) represent the fraction of VNs and CNs of degree d, respectively. The coding rate R of the code is given by \(R = 1 - \frac{L'(1)}{P'(1)}\). The FER performance of the code depends on the degree distributions \(L(x)\) and \(P(x)\). Degree distribution optimization techniques for LDPC codes based on code thresholds (e.g., [27]) optimize the degree distribution for a fixed code rate R and are not directly applicable to the current ET-QKD problem which needs a joint code rate and FER optimization as we demonstrate in Sect. 2.4. Additionally, the optimized degree distributions are designed for non-QKD channels (e.g., BIAWGN in [27]) and they do not result in large IR rates as we demonstrate in Sect. 5.

In the IR step, we perform NB-LDPC decoding using side information which is known as the Slepian-Wolf (SW) problem [41]. In the SW problem, we try to decode a sequence of symbols \({\textbf{X}}^{sw}\) from syndrome \({\textbf{S}}^{sw} = {\textbf{H}}{\textbf{X}}^{sw}\) and side information \({\textbf{Y}}^{sw}\), where \({\textbf{H}}\) is the parity check matrix of an NB-LDPC code. The decoder is very similar to the sum-product decoder used in conventional decoding of NB-LDPC codes [10, 42] with minor modifications in the way the channel log-likelihood (LLR) messages are initialized and the CN to VN messages. We describe these quantities briefly here and refer the reader to see [41] and references therein for details about SW-LDPC decoding. The channel LLR message for VN n, denoted by \({\textbf{m}}^{\textrm{ch}}_n\), in a SW-LDPC decoder isLet \(\ominus \) and \(\oslash \) be the usual operators for subtraction and division, respectively, in \({{\mathbb {G}}}{{\mathbb {F}}}(2^g)\). At iteration \(\ell \) of the sum-product decoder, the message \({\textbf{m}}^{(\ell )}_{m,n}\) from CN m to VN n is given by [41]where, \({\bar{s}}_m = \ominus {\textbf{S}}^{sw}[m]\oslash {\textbf{H}}[n,m]\), \({\bar{g}}[n',m] = \ominus {\textbf{H}}[n',m]\oslash {\textbf{H}}[n,m]\), \({\mathcal {N}}(m)\) is the set of variable nodes in row m of \({\textbf{H}}\), and \({\mathcal {F}}\) and \({\mathcal {F}}^{-1}\) represent an Fourier-like transform and its inverse as defined in [41]. Additionally, \({\mathcal {A}}_{{\bar{s}}[m]}\) and \(W_{{\bar{g}}[n',m]}\) are matrices whose definitions can be found in [41]. Note that the CN to VN message in the channel coding version of the sum-product LDPC decoder is given by [41]The only difference between the CN to VN message in the SW-LDPC decoder in Eqn (5) and the channel coding version shown above is the matrix \({\mathcal {A}}_{{\bar{s}} [m]}\) (in the channel coding version, the matrix \({\mathcal {A}}_{{\bar{s}} [m]}\) is the identity matrix). As such, the decoding complexity of the SW-LDPC decoder is the same as the channel coding version of the sum-product decoder and is given by \(O(g\log g)\) [42].

Throughout this paper, for all non-binary parity check matrices \({\textbf{H}}\in {{\mathbb {G}}}{{\mathbb {F}}}(2^g)^{M \times N}\), each nonzero entry in \({\textbf{H}}\) is chosen uniformly at random from the set of nonzero element of \({{\mathbb {G}}}{{\mathbb {F}}}(2^g)\). For a given coding rate R and VN node degree distribution \(L(x)\), the CN node degree distribution \(P(x)\) is chosen to be a two-element distribution [10] such that it results in rate R. These types of CN degree distributions are called concentrated [10] and we show in Sect. 5 that they result in high IR rates. Finally, in the SW-LDPC sum-product decoding used in this paper, the maximum number of decoding iterations is set to \(\Gamma \).

In this subsection, we explain the FNB protocol for IR as a demonstrative example. Recall that \({\textbf{X}}\in {{\mathbb {G}}}{{\mathbb {F}}}(2^q)^{N}\) and \({\textbf{Y}}\in {{\mathbb {G}}}{{\mathbb {F}}}(2^q)^{N}\) are the raw keys recorded by Alice and Bob, respectively. In the FNB protocol, the raw keys are directly encoded/decoded using NB-LDPC codes in \({{\mathbb {G}}}{{\mathbb {F}}}(2^q)\). The protocol is as follows. Alice sends Bob \({\textbf{S}}= {\textbf{H}}{\textbf{X}}\) over the public channel where \({\textbf{H}}\in {{\mathbb {G}}}{{\mathbb {F}}}(2^q)^{M\times N}\) is the parity check matrix of a NB-LDPC code. Bob decodes \({\textbf{X}}\) using the received \({\textbf{S}}\) and side information \({\textbf{Y}}\) following SW-LDPC decoding as explained in Sect. 2.3 to get the decoding output \({\widehat{{\textbf{X}}}}\). After decoding, Alice and Bob proceed with the verification procedure verify-key \(({\textbf{X}}, {\widehat{{\textbf{X}}}})\). If the verification is successful, Alice and Bob use \({\textbf{K}}= {\textbf{X}}\) and \({\textbf{K}}' = {\widehat{{\textbf{X}}}}\) as the reconciled keys.

The goal of the NB-LDPC code is to make the decoding output \({\widehat{{\textbf{X}}}}\) equal to \({\textbf{X}}\) with high probability. Following Eqn (1), the IR rate \({\mathcal {R}}_{IR}^{FNB}\) for the FNB protocol can be calculated as follows. Let \(E\) be the frame error rate during decoding. Then, we have \({\mathbb {E}}[L_{IR}] = q(1 - E)N\). Similarly, we have \({\mathbb {E}}[\textrm{leak}_{IR}] = q(1 - E)M + l_{\textrm{ht}}(1-E)\) (recall that \(l_{\textrm{ht}}\) is the length of the hash function used during verification). Thus,

Note that in the above equation, \(\frac{N - M}{M}\) is the code rate of \({\textbf{H}}\). A unique property of the ET-QKD problem is that the IR rate of the system, as seen in Eq. (6), is closely dependent on both the code rate and the FER. Figure 4 shows the FER and IR rates obtained by a VN degree regular LDPC code constructed using the PEG algorithm [43] for different values of code rate. From this graph, we see that increasing the code rate can improve the IR rate even at the cost of higher FER. Additionally, as mentioned in Sect. 2.2, the global component of the ET-QKD channel leads to a low SNR in the system. Due to this property, we observe a high FER in the system that results in the maximum IR rate to occur at a relatively large value of FER (\(\sim 1-10\)%). While the conventional code design approach is to minimize the FER to a very small value for a given code rate, in this paper, we jointly optimize both the code rate and the FER to maximize the IR rate in Section 4.1. In the next section, we explain the NB-MLC(a) protocol for IR.

In the NB-MLC(a) protocol described above, the decoding output \({\widehat{{\textbf{X}}}}_i\) of layer i is used in the decoding of the subsequent layers. This process results in error propagation where a decoding error in \({\widehat{{\textbf{X}}}}_i\) results in decoding errors in the subsequent layers, increasing the FERs \(E_{i+1}, \ldots , E_{T}\) and decreasing the overall IR rate \({\mathcal {R}}_{IR}^{\text {\texttt {NB-MLC}}(a)}\). However, the effect of error propagation can be eliminated by using interactive communication (IC) between Alice and Bob [6]. In the interactive communication protocol, after decoding layer i, if the verification procedure verify-key \(({\textbf{X}}_i \;, {\widehat{{\textbf{X}}}}_i)\) fails, then Alice directly sends \({\textbf{X}}_i\) to Bob which Bob uses to decode the subsequent layers instead of \({\widehat{{\textbf{X}}}}_i\). Since now Bob uses the true \({\textbf{X}}_i\) instead of \({\widehat{{\textbf{X}}}}_i\) for decoding the subsequent layers, it gets a more accurate channel LLR initialization in Eq. (4), resulting in improved FERs \(E_{i+1}, \ldots , E_{T}\) and overall IR rate \({\mathcal {R}}_{IR}^{\text {\texttt {NB-MLC}}(a)}\). Note that when decoding fails for layer i, since the corresponding \({\textbf{X}}_i\) and \({\widehat{{\textbf{X}}}}_i\) are not added to the reconciled keys \({\textbf{K}}\) and \({\textbf{K}}'\), revealing \({\textbf{X}}_i\) does not add anything to \(\textrm{leak}_{IR}\). Hence, the IR rate for the NB-MLC(a) protocol with interactive communication is still given by Eq. (8) (where the FERs \(E_i\), \(1 \le i \le T\), are calculated considering the interactive communication protocol described above). The average communication cost due to interactive communication \(\text {\texttt {CommCost-IC}}(a)\) is given by \( \text {\texttt {CommCost-IC}}(a) = \sum _{i = 1}^{T - 1}\alpha _iE_iN\). Note that the FERs \(E_i\) encountered at the point of maximum IR rate are typically less than \(10\%\) and hence the additional communication cost due to interactive communication is small compared to the communication cost involved in sending the syndromes \({\textbf{S}}\). Figure 6 demonstrates the improvement in IR rates for different values of q when the NB-MLC(a) protocol utilizes interactive communication to prevent error propagation.

We call the decoding and the interactive communication protocol mentioned in this section as sequential decoding and communication (SDC) due to its sequential nature. Next, we discuss the design choices present in the NB-MLC(a) protocol which can be optimized to result in high IR rate \({\mathcal {R}}_{IR}^{\text {\texttt {NB-MLC}}(a)}\).

For a given a, the IR rate \({\mathcal {R}}_{IR}^{\text {\texttt {NB-MLC}}(a)}\) provided in Eq. (8) depends on three key design choices (marked in green in Fig. 5):

In this section, we describe the algorithm to design parity check matrices \({\textbf{H}}_i\) and coding rate \(R_i\), \(1 \le i \le T\) for use in the ith layer of the NB-MLC(a) protocol that has a channel transition probability \(\gamma ^{i}_{\textrm{seq}}\) provided in Eq. (7). The mapping that determines the channel transition probability \(\gamma ^{i}_{\textrm{seq}}\) is u(). Note that the construction method is the same for all layers; hence, we drop index i. As mentioned in Sect. 2.3, the FER performance of the code (and hence the IR rate \({\mathcal {R}}_{IR}^{\text {\texttt {NB-MLC}}(a)}\)) depends on the VN node degree distribution \(L(x)\) and coding rate R of \({\textbf{H}}\). In this section, we construct \({\textbf{H}}\) using the PEG algorithm [43] with VN node degree distribution \(L(x)\), code length N, and coding rate R that are optimized by the JRDO framework. We call such parity check matrices \({\textbf{H}}^{\texttt {PEG}}(L(x),R)\).

The JRDO algorithm utilizes differential evolution (DE) [25, 26] to find \(L(x)\) and R. DE is a popular and effective population-based evolutionary algorithm that can be used for the maximization (or minimization) of any function f(). The algorithm iteratively improves a candidate solution (that maximizes f()) using an evolutionary process and can explore large design spaces with low complexity. Note that other optimization algorithms such as genetic algorithms [44], evolution strategies [45, 46], and simulated annealing [47] have also been used in many applications for the minimization of the function f(). However, DE offers parallelizability to cope with computation-intensive functions f(), is easy to use with few hyperparameters, and has good convergence properties [25]. Hence, DE has been extensively used in coding theory literature to design good irregular LDPC codes for the erasure channel [48], AWGN channel [27], Rayleigh fading channel [49], etc. In these works, the goal is to design degree distributions that have low FER. This goal is achieved by using DE where the function f() is generally set to a low complexity predictor of the FER performance of the code such as the threshold obtained by density evolution [27]. However, the goal for us in this paper is to maximize the IR rate \({\mathcal {R}}_{IR}^{\text {\texttt {NB-MLC}}(a)}\) and not merely to minimize the FER. Additionally, the techniques for optimizing the degree distributions using code thresholds work for a fixed code rate and we have not found any work, relevant for this setting, that jointly optimizes the code rate along with maximizing the threshold. This observation is primarily because, in prior work, the performance of the system was not a direct function of the threshold and the code rate. However, in our case, the performance of the system in terms of the IR rate \({\mathcal {R}}_{IR}^{{\texttt {NB-MLC}}(a)}\) depends directly on the code rate R and degree distribution and hence must be optimized jointly. In the JRDO algorithm, we perform this joint optimization of the code rate and the degree distribution by maximizing the function \(f_{\textrm{JRDO}}(L(x), R)\) described aswhere \(E\) is the FER obtained by the parity check matrix \({\textbf{H}}^{\texttt {PEG}}(L(x),R)\) on a channel with transition probability \(\gamma _{\textrm{seq}}\). The function \(f_{\textrm{JRDO}}(L(x), R)\) is proportional to the IR rate (without the verification cost penalty²) of the corresponding layer of the NB-MLC(a) protocol whose parity check matrix is getting designed. Note that to be able to optimize \(f_{\textrm{JRDO}}(L(x), R)\) feasibly using DE, the cost of computing \(f_{\textrm{JRDO}}(L(x), R)\) must be low (since the DE algorithm evaluates \(f_{\textrm{JRDO}}(L(x), R)\) a certain fixed number of times in every iteration). However, since the FER \(E\) of the code at the point of maximum in IR rate is high (\(\sim 1--10\%\)), \(f_{\textrm{JRDO}}(L(x), R)\) can again be easily estimated using MC simulations with a small number of MC experiments (e.g., 200–300). The overall JRDO algorithm is provided in Algorithm 1.

The algorithm starts with initializing a population \(\Pi \) of degree distribution and rate pairs of size \(N_p\). The first entry \(L_1(x)\) in the population is initialized to a regular distribution with VN degree \(d_v\) (line 3) and the rate \(R_1\) is such that it results in the maximum value of \(f_{\textrm{JRDO}}(L_1, R_1)\) (line 4), where \({\mathcal {R}}_{search}= \{R_{\max }, R_{max}- R_{step}, R_{max}- 2R_{step}, \ldots , R_{\min }\}\). The remaining entries of the population are initialized randomly as shown in lines 5–7. Note that the rates are initialized from a small interval around \(R_1\) (e.g., \(\Delta _1 = 0.1\)) to ensure that the algorithm starts with good enough rates. Now, at every iteration of the JRDO algorithm, each population entry undergoes mutation and cross over (lines 9–12) to result in pairs \((L^{c}_j,R^{c}_j)\), \(1 \le j \le N_p\), where the procedures DiffMutation() and CrossOver() have conventional meanings as per [25]. Each population entry \((L_j, R_j)\) is then replaced with the corresponding \((L^{c}_j,R^{c}_j)\) if the function evaluation \(f_{\textrm{JRDO}}(L^{c}_j,R^{c}_j) > f_{\textrm{JRDO}}(L_j,R_j)\). After the completion of the maximum number of iterations of differential evolution, we perform a final rate search (lines 16–18) around the population entry \((L^f, R^f)\) to allow for further improvements in the function value. Finally, the algorithm outputs \((L^f, R^o)\). We demonstrate the improvements in the IR rate \({\mathcal {R}}_{IR}^{\text {\texttt {NB-MLC}}(a)}\) due to the JRDO algorithm in Sect. 5. In the next subsection, we provide the interleaved decoding and communication (IDC) protocol to further improve the IR rate under interactive communication.

In the NB-MLC(a) protocol described in Sect. 3 using interactive communication, the order of operations followed by Alice and Bob is the following: Starting from the first layer, (i) Bob decodes layer i to get \({\widehat{{\textbf{X}}}}_i\); (ii) Alice and Bob perform the verification procedure verify-key \(({\textbf{X}}_i \;, {\widehat{{\textbf{X}}}}_i)\) (iii) Alice sends \({\textbf{X}}_i\) to Bob if the verification procedure fails; (iv) Bob decodes layer \(i+1\). The process is then continued for all layers. We call the above sequential decoding and communication (SDC) since the order of operations is sequential where Bob completes the decoding of layer i and performs interactive communication to get the correct \({\textbf{X}}_i\) before starting to decode the next layer. In this case, sending the correct \({\textbf{X}}_i\) to Bob via interactive communication in the event of a decoding failure of layer i helps Bob get more reliable channel LLR initialization (Eq. 4) for decoding layers \(i+1, \ldots , T\) using the channels \(\gamma ^{i+1}_{\textrm{seq}}, \ldots , \gamma ^{T}_{\textrm{seq}}\) mentioned in Eq. (7). More reliable channel LLR initialization improves the FERs \(E_{i+1}, \ldots , E_{T}\) of layers \(i+1, \ldots , T\), thus, improving the overall IR rate \({\mathcal {R}}_{IR}^{\text {\texttt {NB-MLC}}(a)}\).

Now, consider the following transition probability:where, \(A'_1(x_1, x_2, \ldots , x_{T}) = \{x \in {{\mathbb {G}}}{{\mathbb {F}}}(2^q) \;\vert \; u_j(x) = x_j, 1\le j\le T\}\) and \(A_2(x_i) = \{x \in {{\mathbb {G}}}{{\mathbb {F}}}(2^q) \;\vert \; u_i(x) = x_i\}\). The above transition probability can provide a more accurate channel LLR for \({\textbf{X}}_i\) compared to the transition probability \( \gamma ^{i}_{\textrm{seq}}\) mentioned in Eq. (7), provided Bob has reliable values of \(\{{\textbf{X}}_1, \ldots , {\textbf{X}}_{i-1}, {\textbf{X}}_{i+1}, \ldots , {\textbf{X}}_{T}\}\). Thus, similar to the SDC protocol, the IR rate can also be improved if Bob can utilize the correct \({\textbf{X}}_{i+1}, {\textbf{X}}_{i+2}, \ldots ,{\textbf{X}}_{T}\) sent by Alice after interactive communication of layers \(i+1, i+2, \ldots , T\) for decoding the previous layers \(i, i-1, \ldots , 1\). We now describe the IDC protocol that achieves the above goal. The protocol provides an alternative way for Bob and Alice to get the reconciled keys \({\textbf{K}}\) and \({\textbf{K}}'\) using \({\textbf{X}}\), \({\textbf{Y}}\), \({\textbf{H}}_i\), \(1 \le i \le T\), and syndromes \({\textbf{S}}= \{{\textbf{S}}_1, \ldots , {\textbf{S}}_{T}\}\) compared to the SDC procedure mentioned in Sect. 3. The overall IDC protocol is provided in Algorithm 2 below. Recall that the maximum number of LDPC decoder iterations for each layer is \(\Gamma \).

In the above IDC protocol, Bob first decodes layers \(1, 2, \ldots , T\) sequentially (lines 2–4), but performs maximum \(\Gamma _1\) decoding iterations out of the \(\Gamma \) iterations allowed for each layer. The decoded output of the different layers at the end of \(\Gamma _1\) iterations is denoted by \({\overline{{\textbf{X}}}}_1, \ldots , {\overline{{\textbf{X}}}}_{T}\) (line 4). Here, the outputs \({\overline{{\textbf{X}}}}_1, \ldots , {\overline{{\textbf{X}}}}_{i-1}\) are used in the channel LLR initialization³ of layer i using transition probability \(\gamma ^{i}_{\textrm{seq}}\) (line 3). After performing \(\Gamma _1\) decoding iterations for every layer, Bob continues the decoding of the different layers in reverse order (lines 6–12) for \(\Gamma - \Gamma _1\) more decoding iterations using the updated channel LLRs \({\textbf{m}}^{\textrm{ch,i}}_{\textrm{int}}\). For each layer i, it finds the updated⁴ channel LLR \({\textbf{m}}^{\textrm{ch,i}}_{\textrm{int}}\) using the transition probability \(\gamma ^i_{\textrm{int}}\). To find the updated channel LLR, it uses the decoded outputs \({\overline{{\textbf{X}}}}_1, \ldots , {\overline{{\textbf{X}}}}_{i-1}\) of the layers \(1, \ldots , i-1\) (obtained after \(\Gamma _1\) iterations). It also uses \({\widehat{{\textbf{X}}}}_{i+1}, \ldots , {\widehat{{\textbf{X}}}}_{T}\) which are the decoded outputs of layers \(i+1, \ldots , T\) after continuing the decoding of each layer for \(\Gamma - \Gamma _1\) more decoding iterations with the updated channel LLR messages (line 8). Additionally, after obtaining \({\widehat{{\textbf{X}}}}_i\) for each layer, Alice and Bob perform the verification procedure verify-key \(({\textbf{X}}_i , {\widehat{{\textbf{X}}}}_i)\) (line 10). If the verification is unsuccessful, Alice sends the correct \({\textbf{X}}_i\) to Bob and Bob updates \({\widehat{{\textbf{X}}}}_i\) with \({\textbf{X}}_i\) (line 11). Thus, the \({\widehat{{\textbf{X}}}}_{i+1}, \ldots , {\widehat{{\textbf{X}}}}_{T}\) that Bob uses in line 7 to get the updated channel LLRs \(\gamma ^i_{\textrm{int}}\) are always accurate due to the interactive communication step in line 11.

In the IDC protocol, since Bob uses the transition probability \(\gamma ^{i}_{\textrm{int}}\) with the correct

\({\textbf{X}}_{i+1}, {\textbf{X}}_{i+2}, \ldots ,{\textbf{X}}_{T}\) (due to interactive communication) to get the updated channel LLRs (in line 7), it can improve the FER of layer i for the same rate or allow a higher rate for the same FER allowing to improve the IR rate. Note that since in the initial decoding phase (lines 2–4), the unverified decoded outputs \({\overline{{\textbf{X}}}}_1, \ldots , {\overline{{\textbf{X}}}}_{i-1}\) are used in the decoding of the next layers as well as in calculating the updated channel LLRs \(\gamma ^{i}_{\textrm{int}}\), there is an effect of error propagation in the system. However, with appropriately chosen code rates \(R_i\), \(1 \le i \le T\), and the value of \(\Gamma _1\) (which is the number of decoding iterations in the first phase), the effect of error propagation can be made small and the IDC protocol can improve⁵ the IR rate \({\mathcal {R}}_{IR}^{\text {\texttt {NB-MLC}}(a)}\). Note that the IR rate \({\mathcal {R}}_{IR}^{\text {\texttt {NB-MLC}}(a)}\) using the IDC protocol is also provided by Eq. (8).

We now describe how to choose appropriate rates \(R^{\textrm{IDC}}_i\), \(1 \le i \le T\), for use in the different layers of the NB-MLC(a) protocol with IDC. Let \(R^{o}_i\), \(1 \le i \le T\), be the rates provided by the JRDO algorithm. Note that the rates \(R^{o}_i\), \(1 \le i \le T\), in the JRDO algorithm are designed for the SDC case described in Sect. 3. For the case of the IDC protocol, the rates used have to be modified compared to \(R^{o}_i\), \(1 \le i \le T\), to result in the largest IR rate⁶. To find the rates, we perform a heuristic search in a small interval around \(R^{o}_i\), \(1 \le i \le T\), as provided in Algorithm 3 using the functionwhere \(E_i\) is the FER encountered in layer i of the NB-MLC(a) protocol with IDC. We demonstrate the improvements in IR rate provided by the IDC protocol in Sect. 5. In the next subsection, we discuss the choice of the mapping function u().

In this section, we discuss the choice of the mapping function u() that results in high IR rates. The mapping function \(u: {{\mathbb {G}}}{{\mathbb {F}}}(2^q) \rightarrow {{\mathbb {G}}}{{\mathbb {F}}}(2^{\alpha _1}) \times \ldots \times {{\mathbb {G}}}{{\mathbb {F}}}(2^{\alpha _{T}})\) can be equivalently represented as a mapping \(u_b: {{\mathbb {G}}}{{\mathbb {F}}}(2^q) \rightarrow {{\mathbb {G}}}{{\mathbb {F}}}(2)^q\) that converts a symbol \(x \in {{\mathbb {G}}}{{\mathbb {F}}}(2^q)\) into a binary string \(x^b\) of length \(q = \sum _{i = 1}^{T}\alpha _i\). Let \(x^b_1 || x^b_2 || \ldots || x^b_{T}\) be the partition of the binary string \(x^b\), such that \(l(x^b_i) = \alpha _i, 1 \le i \le T\). Then, \(x^b_i\) is the binary (base 2) representation of \(u_i(x)\). Thus, in the rest of the paper, we directly discuss the choices for the mapping function \(u_b(x)\) that leads to a reasonably good IR rate.

Binary mapping is the simplest mapping to consider. It is the function \(u_b: {{\mathbb {G}}}{{\mathbb {F}}}(2^q) \rightarrow {{\mathbb {G}}}{{\mathbb {F}}}(2)^q\) such that for \(x \in {{\mathbb {G}}}{{\mathbb {F}}}(2^q)\), \(x = \sum _{i = 1}^{q}u_b(x)[i]2^{i-1}\), where \(u_b(x)[i]\) is the ith bit in the bit string \(u_b(x)\). Another commonly used mapping is the gray mapping [50] where two successive symbols in \({{\mathbb {G}}}{{\mathbb {F}}}(2^q)\) differ only in 1 bit in their mapped bit strings. Binary and gray mappings are easy to construct. However, it is not clear if they are good choices of mapping to get high IR rates \({\mathcal {R}}_{IR}^{\text {\texttt {NB-MLC}}(a)}\) for our particular channels. Due to the large search space of mappings, it is computationally expensive to find the optimal mappings using a brute-force search. Here, we use a heuristic approach using the simulated annealing (SA) algorithm [47] to see whether we can improve the IR rates compared to binary or gray mapping.

In the SA algorithm, we start with the binary mapping as the initial choice of \(u_b\) and then modify \(u_b\) if the modification leads to a better mapping. Specifically, we swap the output of \(u_b\) for two distinct input values \(x,y \in {{\mathbb {G}}}{{\mathbb {F}}}(2^q)\) if the operation leads to a higher value of the function \(f_{\textrm{SA}}(u_b)\) defined aswhere, \({\mathcal {R}}_{search}= \{R_{\max }, R_{max}- R_{step}, R_{max}- 2R_{step}, \ldots , R_{\min }\}\), \(\alpha _i\) and \(T\) are constants in the NB-MLC(a) protocol, and \(E_i\) is the FER obtained on layer i of the NB-MLC(a) protocol with SDC by a VN degree regular NB-LDPC code constructed using the PEG algorithm [43] with constant VN degree \(d_v\), code length N, and coding rate \(R_i\). The function \(f_{\textrm{SA}} (u_b)\) follows similarly as Eq. (9) and approximates the maximum IR rate \({\mathcal {R}}_{IR}^{\text {\texttt {NB-MLC}}(a)}\) (see Eqn (8)) achieved by a VN degree regular PEG NB-LDPC code, where the rate \(R_i\) is found using a grid search in the set \({\mathcal {R}}_{search}\). The detailed SA algorithm is provided in Algorithm 4.

In the SA algorithm, we start with the binary mapping as the current mapping. Then in each iteration, we modify the current mapping \(u_b\) to obtain a new mapping⁷\(u'_b\) in line 5. Now, if the difference \(D_{\textrm{f}}\) in the \(f_{SA}()\) values of \(u'_b\) and \(u_b\) is greater than threshold \(f_{\textrm{th}}\) (line 7), we update the current mapping to \(u'_b\). If the difference \(D_{\textrm{f}}\) is less than \(f_{\textrm{th}}\), we update the current mapping to \(u'_b\) only a fraction of the times based on the condition in line 12 to allow the algorithm to break out of a local maximum.

A comparison of the IR rates obtained by mappings output by the SA search algorithm with that of binary and gray mapping is provided in Fig. 7. From the figure, we first see that in all cases, the binary and gray mappings have very close IR rates. Additionally, we see that the IR rates produced by the SA search algorithm are very close compared to binary and gray mappings. Thus, binary and gray mappings are good choices for mappings for use in the NB-MLC(a) protocol.