New Upper Bounds on the Error Probability under ML Decoding for Spinal Codes and the Joint Transmission-Decoding System Design

First proposed by Perry et al. in [1], Spinal codes are a new type of near-Shannon-capacity channel coding techniques that have been theoretically proved to achieve the Shannon capacity over both the additive white Gaussian noise (AWGN) channel and the binary symmetric channel (BSC) [2]. The core idea in this code is applying a sequential of hash functions combing with the random number generators (RNGs) to generate pseudo-random coded symbols: the hash functions provide the coded symbols with the pairwise independent feature, which thereby ensures good resilience to noise and errors; the RNGs inherit from the idea of Shannon random coding, which can generate pseudo-random coded symbols as much as possible to cope with the time-varying channel by nature. Spinal code draws its strength from the excellent code rate performance. It has been shown in [3] that rateless Spinal codes exhibit superiority in rate performance when compared to fixed-rate LDPC codes [4], rateless Raptor codes [5], and the layered rateless coding approach [6] of Strider codes [7], across various channel conditions and message sizes.

In addition to the capacity-approaching code rate performance, a more attractive feature for Spinal codes is that Spinal codes are also a family of rateless codes. Different from conventional fixed-rate codes that should dynamically pre-define the “bit rate”, i.e., a modulation mode, channel code, and code rate, Spinal codes transmit coded symbols in a rateless mode. By rateless transmission, Spinal codes do not need to frequently estimate the time-varying channel state to dynamically adjust the code rate and the modulation mode. Instead, they keep generating and transmitting pseudo-random coded symbols until the transmitted symbols are sufficient for the decoder to decode successfully and an acknowledgment (ACK) is fed back to the transmitter to interrupt the transmission. By this means, Spinal codes themselves are a type of advanced adaptive coding modulation technique, which enables adaptive parameter selection to ensure reliable and efficient end-to-end communication.

Attributed to the near-Shannon-capacity characteristic and the rateless feature, Spinal codes have aroused extensive research interest in both performance optimization and theoretical analysis. One of the most popular and open challenges in facilitating Spinal codes from theory to practice is to design a practical low-complexity decoding algorithm for Spinal codes. Formally, such a challenge exists due to the high-frequency use of hash functions and the multiple rounds of tentative decoding. To circumvent this problem, traditionally, the tree pruning strategies have been extensively explored to design the low-complexity decoding algorithms [1, 9, 10, 11]. In [3], the proposed bubble decoding algorithm is the initial practical decoding algorithm customized for Spinal codes. Then, inspired by the tree-structure feature of Spinal codes, Yang et al. introduce the forward stack decoding (FSD) algorithm, which was first proposed in [8], to implement the decoding process of Spinal codes [9]. By such an implementation, the FSD algorithm showcases much lower decoding time complexity compared to the bubble decoding algorithm without sacrificing rate performance. In [10], the proposed sliding window decoding (SFD) algorithm further reap benefits in much lower decoding time complexity compared to the FSD algorithm. A trade-off between decoding efficiency and decoding reliability is also investigated. In [11], Hu et al. introduces several dynamic parameters in the decoding process Spinal codes. The proposed algorithm, referred to as the block dynamic decoding (BBD) algorithm, also demonstrates superior performance in both the decoding complexity and the decoding error probability. Nevertheless, we notice that the above works mainly focus on designing the pruning strategy to eliminate the calculation required in a single decoding round. For rateless Spinal codes, the transmission and decoding process are both consecutive and not unique. In this regard, we would like to pay attention to investigating the dynamic changes of the decoding tree between adjacent decoding rounds of rateless Spinal codes.

Puncturing on the coded symbols is a commonly adopted transmission design to improve the rate performance of channel coding techniques. In [12], coding schemes that can be punctured to adapt to time-varying channels are known as rate-compatible codes. As the redundant symbols are punctured, the code rate increases by nature. As such, the puncturing technique has drawn extensive interest in the literature, such as punctured LDPC codes [15, 13, 14], punctured Turbo codes [16], and punctured Polar codes [17, 18]. For rateless Spinal codes, uniform puncturing is one of the most commonly used puncturing schemes, where the coarse-grained transmission unit, pass, is refined into some finer-grained sub-passes, and the transmitter only transmits a single symbol in a sub-pass [3]. In [19], uniform puncturing is also adopted in the proposed S-Spinal codes to achieve finer granularity for compression purposes. However, the uniform puncturing implementation is only a general-purpose puncturing method that has been applied extensively in rateless coded systems[20]. In such a case, the puncturing scheme that customizes the unique properties of Spinal codes is expected to be designed.

Performance evaluation of channel codes is another important work in understanding the essence of a coding technique. In addition to Monte Carlo simulations, which require amounts of repeated calculations, the bounding technique is a more straightforward method to evaluate the performance of a coding technique¹¹1In most of the cases, to derive the exact closed-form expression to evaluate the performance of a near-Shannon-limit coding technique is intractable, and thus to derive the bound is an alternative.. The recent focus given to the performance bounds of codes is on some near-Shannon-limit performing codes, ranging from the performance bounds on LDPC codes [21, 22], to other advanced tight bounds on Turbo codes[23, 24, 25], and Polar codes[26, 27]. However, for Spinal codes, which are a new family of near-Shannon-capacity codes, the theoretical performance analysis is still in its infancy. One of the first works devoted to the performance of Spinal codes is that of Yu et al.[28], wherein the tree structure of Spinal codes is considered, and some general bounding techniques on pairwise independent random codes, i.e., the Random Coding Union (RCU) bound and a variant of Gallager’s result, are introduced as cores to obtain the closed-form upper bounds on the error probability of Spinal codes. Nevertheless, we notice that derived upper bounds are not customized for Spinal codes, but play as applications of the RCU bound and Gallager’s result. In this regard, the bounds on the error probability exhibit loose performance (see Section VI). In our previous work [29], we analyze the upper bound on the error probability of Spinal codes over the BSC. However, the derived upper bound in [29] remains several static parameters obtained through simulation implementations. Therefore, the bounds in [29] and are not completely explicit. To this end, we would like to derive explicit upper bounds on the error probability of Spinal codes. Instead of taking the general upper bounds of pairwise independent random codes as cores, we consider the coding, decoding and transmission process of Spinal codes in detail to derive the upper bounds on the error probability for Spinal codes in the FBL regime.

Motivated by the above, the main contributions of this work are summarized as follows. We begin with deriving the upper bounds on the error probability of ML-decoded Spinal codes over both the BSC and the AWGN channel under the finite block-length (FBL) regime. The derivation leads to the closed-form upper bounds shown in Section III, and demonstrate tighter performance at high SNRs as shown in Section VI. Then, based on the derived closed-form upper bounds, we formulate a rate maximization problem and correspondingly design a customized iterative algorithm to solve it. Notice that the optimal solution to this problem forms an incremental-tail-transmission pattern; heuristically, we propose the thresholded incremental tail transmission (TITT) scheme for Spinal codes. Furthermore, to address the high decoding complexity issue at the receiver, we investigate the dynamic changes of the decoding tree between adjacent decoding tentatives and show that only parts of the decoding tree change during the consecutive decoding process, and thus the tree reconstruction of the unchanged parts can be skipped. To this end, we find that most of the available decoding algorithms for Spinal codes in the literature can be improved by simply introducing an extra memory to restore the unchanged parts of the decoding tree. For the experimental purpose, we take the most commonly used bubble decoding algorithm as an example, and design a bubble-decoding-based dynamic decoding algorithm, referred to as the bubble decoding with memory (BD-M). By combing the proposed TITT scheme at the transmitter with the BD-M algorithm at the receiver, we further observe that the BD-M algorithm can match perfectly with the tail-incremental-transmission property of the TITT scheme, enjoying both higher rate performance and lower decoding complexity.

The rest of this paper is organized as follows. Section II introduces the preliminaries of Spinal codes. In Section III, the new upper bounds on the error probability of ML-decoded Spinal codes are derived. The details of the transmission scheme design are presented in Section IV. In Section V, the details of the BD-M algorithm and its complexity analysis are presented. In Section VI, simulation results are provided, followed by conclusions in Section VII.

As shown in Fig. 1, the encoding process of Spinal codes can be accomplished in four steps:

1. 1.

   An $n$-bit message $M$ is divided into $k$-bit segments, denoted by $m_{i}$, where $i=1,2,\ldots,n/k$.

2. 2.

   An iterative process is invoked to generate the series of $v$-bit spine values ${s_{i}}$:

   $${s_{i}}={\rm{}}h({s_{i-1}},{\rm{}}{m_{i}}),i=1,\ldots,n/k,s_{0}=0^{v}.$$

   (1)

3. 3.

   The $v$-bit spine value ${s_{i}}$ serves as a seed of an RNG to generate a pseudo-random uniform-distributed sequence $\left\{{x_{i,j}}\right\}$:

   $${\rm{RNG:}}{s_{i}}\mathop{\to}\left\{{x_{i,j}}\right\},j=1,2,3,\cdots,$$

   (2)

   where ${x_{i,j}}\in{\left\{{0{\rm{,}}1}\right\}^{c}}$, ${s_{i}}\in{\left\{{0{\rm{,}}1}\right\}^{v}}$.

4. 4.

   The constellation mapper maps each c-bit symbol to a channel input set $\Omega$:

   $${\operatorname{f}:{x_{i,j}}\mathop{\to}\Omega,}$$

   (3)

   where $\operatorname{f}$ is a constellation mapping function and ${\Omega}$ denotes the channel input set. In this paper, we consider the uniform constellation mapper, where $\operatorname{f}$ converts each $c$-bit symbol $x_{i,j}$ to a decimal symbol $\operatorname{f}\left(x_{i,j}\right)$.

The original transmission scheme for Spinal codes is a pass-by-pass transmission scheme. Denote ${\textbf{X}_{j}}=[\operatorname{f}\left(x_{1,j}\right),\operatorname{f}\left(x_{2,j}\right),\ldots,\operatorname{f}\left(x_{n/k,j}\right)]$ as the $j^{\rm th}$ pass of coded symbols. The conventional pass-by-pass transmission scheme will form a transmission process of ${\textbf{X}_{j}}\to{\textbf{X}_{j+1}}\to{\textbf{X}_{j+2}}\to\cdots$. This transmission process ends only when the number of received symbols is enough for successful decoding and an ACK is sent to interrupt the transmission. Note that correct decoding may be completed in any round of transmission, the cumulative transmitted symbols before correct decoding must be a multiple of $n/k$, belonging to the set $\left\{in/k|i\in\mathbb{Z}^{+}\right\}$.

In [3], the authors propose a uniform-puncturing-based transmission scheme for Spinal codes. Instead of transmitting Spinal codes pass by pass, the uniform-puncturing-based transmission scheme transmits Spinal codes in a symbol by symbol pattern. By this means, the cumulative transmitted symbols before correct decoding belongs to a finer set $\left\{i|i\in\mathbb{Z}^{+}\right\}$. Take a typical $(n,k)$ Spinal codes as an example. Let ${\bf g}=[g_{1},g_{2},\ldots,g_{n/k}]$ denote the transmission order of the symbols. The uniform-puncturing-based transmission scheme forms a transmission process of $\operatorname{f}\left(x_{g_{1},j}\right)\to\operatorname{f}\left(x_{g_{2},j}\right)\to\cdots\to\operatorname{f}\left(x_{g_{n/k},j}\right)\to\operatorname{f}\left(x_{g_{1},j+1}\right)\to\operatorname{f}\left(x_{g_{2},j+1}\right)\to\cdots$. The transmitter will continue the transmission process until an ACK is received.

For the uniform-puncturing-based transmission scheme, the punctured redundant symbols are from the last pass of transmission. For example, assuming that only $in/k+1$ symbols need to be sent for successful decoding of uniform-puncturing-based transmission scheme, then under the same condition, the traditional pass-by-pass transmission scheme needs to send additional $n/k-1$ symbols in the ${i+1}$ pass to decode correctly since its transmission unit is pass. Compared with the traditional pass-by-pass transmission scheme, the uniform-puncturing-based transmission scheme punctured out $n/k-1$ symbols, thus improving the rate performance of Spinal codes. To conclude, the uniform-puncturing-based transmission scheme reduces the transmission of redundant symbols in the last pass and improves the code rate of Spinal codes by refining the unit of each transmission from the coarse-grained pass to the finer-grained symbol.

Although the uniform-puncturing-based transmission scheme indeed improves the rate performance of Spinal codes, there are still some shortcomings that can be improved. First, the uniform-puncturing-based transmission scheme needs to completely transmit a whole pass of symbols before continuing to transmit the subsequent pass, which limits its puncturing coverage to the last transmitted pass only. A more flexible transmission scheme without this limitation has yet to be proposed. Second, the symbol-by-symbol transmission pattern increases the decoding attempts at the receiver and thus reduces the decoding throughput of Spinal codes. To resolve this issue, we design a dynamic decoding framework for Spinal codes. The proposed decoder can dynamically store the decoding information in each decoding process and utilize it to assist subsequent decoding.

For Spinal codes over the AWGN channel, the optimal decoding algorithm is maximum likelihood (ML) decoding. In ML decoding, the decoder adopts the shared knowledge of the same hash function, the same initial spine value $s_{0}$ and the same RNG to replay the coding process over the set of received symbols. By adopting the shared knowledge, the decoder aims to find the best matching sequence $\hat{M}\in{\left\{{0,1}\right\}^{n}}$ whose coded vector $\textbf{x}(\hat{M})$ is closest to the received vector y in Euclidean distance.

For conventional pass-by-pass transmission scheme, let $L$ denote the number of transmitted passes for Spinal codes, the ML decoding rule can be expressed as:

where $\hat{M}$ is the decoding result, $M^{\prime}$ represents the candidate sequence.

For puncturing symbol-by-symbol transmission scheme, let $\ell_{i}$ denote the number of transmitted symbols generated from the $i^{\rm th}$ spine value $s_{i}$, the ML decoding rule should be slightly

For the BSC, the only difference is that the Euclidean distance should be replaced with Hamming distance.

However, traversing all candidate sequences $M^{\prime}$ results in an exponential increase in complexity. The serial coding structure of Spinal codes determines that Spinal codes are a type of tree code. As a result, the bubble decoding algorithm proposed in [3] can be applied to decrease the decoding complexity. Instead of searching the entire decoding tree, a bubble decoder calculates the cost $C_{\lambda}$ for the nodes at each layer and sorts them to retain only the $B$ best candidate nodes with the lowest cost at each layer. The reserved nodes are then expanded to $B2^{k}$ child nodes. This repeats until the bubble decoder ends up with a list of $B$ messages at the last layer, from which the best one is selected as the decoding output. The cost at each layer can be calculated as:

where $\lambda$ denotes the currently expanded number of layers.

Here we simply review the upper bounds obtained in [28], where the authors have derived the upper bounds on the error probability of ML decoding for Spinal codes over the AWGN channel and the BSC, respectively.

Different from the analysis in [28], which investigates the performance of Spinal codes by introducing general bounding techniques on random codes, we pay attention to Spinal code itself to obtain the new characterized upper bounds. Specifically, we systematically consider the coding structure, the decoding rule and the pairwise independent property of Spinal codes to conduct performance analysis for Spinal codes.

Note that the right-hand side (RHS) of (10a) can be immediately calculated by solving the integrals ${\int\limits_{0}^{\mathcal{D}}{{r^{2{L_{a}}-1}}}{e^{-\frac{{{r^{2}}}}{{2{\sigma^{2}}}}}}dr}$ and ${\int\limits_{\mathcal{D}}^{\infty}{{r^{{L_{a}}-1}}}{e^{-\frac{{{r^{2}}}}{{2{\sigma^{2}}}}}}dr}$:

The proof of Theorem 3 is given as follows: