Tight Upper Bounds on the Error Probability of Spinal Codes over Fading Channels

Xiaomeng Chen, Aimin Li and Shaohua Wu Aimin Li has contributed equally to this work. This work has been supported in part by the National Key Research and Development Program of China under Grant no. 2020YFB1806403, and in part by the National Natural Science Foundation of China under Grant nos. 61871147, 62071141, 61831008, 62027802, and in part by the Shenzhen Municipal Science and Technology Plan under Grant no. GXWD20201230155427003-20200730122528002, and in part by the Major Key Project of PCL under Grant PCL2021A03-1. (Corresponding author: Shaohua Wu.) Harbin Institute of Technology (Shenzhen)
518055 Shenzhen, China
[email protected], [email protected], [email protected]

Abstract

Spinal codes, a family of rateless codes introduced in 2011, have been proved to achieve Shannon capacity over both the additive white Gaussian noise (AWGN) channel and the binary symmetric channel (BSC). In this paper, we derive explicit tight upper bounds on the error probability of Spinal codes under maximum-likelihood (ML) decoding and perfect channel state information (CSI) over three typical fading channels, including the Rayleigh channel, the Nakagami-m channel and the Rician channel. Simulation results verify the tightness of the derived upper bounds.

Index Terms:

Spinal codes, decoding error probability, fading channels, ML decoding. upper bounds.

I Introduction

First proposed in 2011 [1], Spinal codes are a family of rateless codes that have been proved to achieve Shannon capacity over both the AWGN channel and the BSC [2]. Possessing the rateless capacity-achieving nature, Spinal codes demonstrate their superiority in bridging a reliable and high-efficiency information delivery pipeline between transceivers under highly dynamic channels. Specifically, the rateless nature allows Spinal codes to automatically adapt to time-varying channel conditions. Unlike fixed-rate codes, which require a specific code rate in advance, rateless codes work by a natural channel adaptation manner: the sender transmits a potentially limitless stream of encoded bits, and the receiver collects bits consecutively until the successful decoding process takes place. In [3], Spinal codes have shown advantages in terms of rate performance compared to other state-of-the-art rateless codes under different channel conditions and message sizes. Also, [3] notes the similarity between Spinal codes and Trellis Coded Modulation (TCM) [4, 5] is superficial because of their differences in nature and encoded popuse.

In coding theory, performance analysis is an intriguing topic. A closed-form expression for the error probability, in general, could not only enable more efficient performance evaluations but also shed light on coding optimization design. However, in most cases, it is intractable to obtain a closed-form expression for error probabilities. As an alternative, bounding techniques are usually used to approximate performance [6]. Along this avenue, there are already a lot of established bounds for some specific channel codes, such as the advanced tight bounds on Polar codes [7, 8], the upper and lower bounds on Raptor codes [9], and the performance bounds on the LT codes [10, 11]. And in [12], upper and lower bounds on the error probability of linear codes under ML decoding are surveyed. For Spinal codes, however, it is still early days to get tight explicit bounds over fading channels.

To date, there have been a few works that have preliminarily explored the performance analysis of Spinal codes. In [2], Balakrishnan et al. analyze the asymptotic rate performance of Spinal codes and theoretically prove that Spinal codes are capacity-achieving over both the AWGN channel and the BSC. In [13], two state-of-the-art results in the finite block length (FBL) regime, i.e., the Random Coding Union (RCU) bound [14] and a variant of Gallager result [15] are applied to analyze the error probability of Spinal codes over the AWGN channel and the BSC, respectively. In [16], the authors further tighten bounds by characterizing the error probability as the volume of a hypersphere divided by the volume of a hypercube, while the analysis is still performed over the AWGN channel. Until now, little has been done in the way of error probability analysis for Spinel codes over fading channels. An exception work is [17], which derived a probability-dependent convergent upper bound over Rayleigh fading channels by adopting the Chernoff bound [18]. However, $i$ ) the derived bound over the Rayleigh fading channel in [17] is not strictly explicit, since the convergence of the upper bound is probability-dependent; $ii$ ) Nakagami-m and Rician channels, both common in practical wireless communication scenarios, have not been considered in the available error probability analyses; $iii$ ) There is not yet an upper bound that achieves uniform tight approximations over a wide range of signal-to-noise ratio (SNR), either over the fading channel or over the AWGN channel.

Motivated by the above, this paper aims to derive tight upper bounds over three typical fading channels, Rayleigh, Nakagami-m and Rician fading channels. Strictly explicit upper bounds are provided, which cover uniform tight error probability approximations over a wide range of SNR.

The paper is organized as follows. In Section II, the encoding process of Spinal codes is given as a priori knowledge. Section III derives upper bounds over Rayleigh, Nakagami-m and

Refer to caption — Figure 1: The encoding process of Spinal codes.

Rician fading channels, respectively. Numerical results comparing the bounds with Monte Carlo simulations are illustrated in Section IV. Section V presents the conclusions of our work.

II Encoding Process of Spinal Codes

This section briefly introduces the primary building blocks of Spinal codes, where the combination of a hash function and random number generator (RNG) functions is a key. Fig. 1 shows the encoding process of Spinal codes, which comprises five steps:

1.

Segmentation: Divide an $n$ -bit message $\mathbf{M}$ into $k$ -bit segments $\mathbf{m}_{i}\in\left\{0,1\right\}^{k}$ , where $i=1,2,\cdots,n/k$ .
2.

Sequentially Hashing¹¹1A discussion concerning the properties of the hash function can be found in Appendix A.: The hash function sequentially generates $v$ -bit spine values $\mathbf{s}_{i}\in{\{0,1\}}^{v}$ , with

$\mathbf{s}_{i}=h(\mathbf{s}_{i-1},\mathbf{m}_{i}),~{}i=1,2,\cdots,n/k,~{}\mathbf{s}_{0}=\mathbf{0}^{v}\text{.}$ (1)
3.

RNG: Each spine value $\mathbf{s}_{i}$ is used to seed an RNG to generate a binary pseudo-random uniform-distributed sequence $\{\mathbf{x}_{i,j}\}_{j\in\mathbb{N}^{+}}$ :

$\mathrm{RNG:}~{}\mathbf{s}_{i}\to\{\mathbf{x}_{i,j}\},~{}j=1,2,3,\cdots\text{,}$ (2)

where $\mathbf{x}_{i,j}\in{\{0,1\}}^{c}$ .
4.

Constellation Mapping: The constellation mapper maps each $c$ -bit symbol $\mathbf{x}_{i,j}$ to a channel input set $\Psi$ :

$\operatorname{f}:\mathbf{x}_{i,j}\rightarrow\Psi\text{.}$ (3)

In this paper, $\operatorname{f}$ is a uniform constellation mapping function, i.e., it converts each $c$ -bit symbol $\mathbf{x}_{i,j}$ to a decimal symbol $\operatorname{f}(\mathbf{x}_{i,j})$ .
5.

Rateless Transmission: The encoder continues to generate and transmit symbols pass by pass until the receiver successfully decodes the message.

III UPPER BOUNDS ON THE ERROR PROBABILITY

Error probability analysis is of primary importance in coding theory. Closed-form expressions for error probabilities, however, are intractable in most cases. To address this issue, a commonly adopted alternative approach is to introduce bounding techniques for the error probability approximation. In line with this idea, this section aims to derive tight upper bounds on the error probability for Spinal codes over Rayleigh, Nakagami-m and Rician fading channels, respectively.

III-A Upper Bounds on the Rayleigh Fading Channel

Theorem 1.

Consider Spinal codes with message length $n$ , segmentation parameter $k$ , modulation parameter $c$ , and sufficiently large hash parameter $v$ transmitted over a flat slow Rayleigh fading channel with mean square $\Omega$ and AWGN variance $\sigma^{2}$ , the average error probability given perfect channel state information (CSI) under ML decoding for Spinal codes can be upper bounded by

\small P_{e}\leq 1-\prod_{a=1}^{n/k}\left(1-\epsilon_{a}\right)\text{,}

(4)

with

\epsilon_{a}=\mathrm{min}\left\{1,\left(2^{k}-1\right)2^{n-ak}\cdot\mathscr{F}_{\text{Rayleigh}}(L_{a},\sigma)\right\}\text{,}

(5)

\small\mathscr{F}_{\text{Rayleigh}}\left(L_{a}\text{,}\sigma\right)=\sum_{r=1}^{N}b_{r}\mathcal{F}_{\text{Rayleigh}}(\theta_{r}\text{;}\sigma\text{,}L_{a})\text{,}

(6)

\small\mathcal{F}_{\text{Rayleigh}}(\theta_{r}\text{;}\sigma\text{,}L_{a})={\left(\sum_{i\in\Psi}\sum_{j\in\Psi}2^{-2c}\frac{8{\sigma}^{2}{\sin}^{2}{\theta}_{r}}{{\Omega}(i-j)^{2}+8{\sigma}^{2}{\sin}^{2}{\theta}_{r}}\right)}^{L_{a}}\text{,}

(7)

where $b_{r}=\frac{\theta_{r}-\theta_{r-1}}{\pi}$ , $L_{a}=(n/k-a+1)L$ , $L$ is the number of transmitted passes, $\theta_{r}$ is arbitrarily chosen with $\theta_{0}=0$ , $\theta_{N}=\frac{\pi}{2}$ and $0<\theta_{1}<\theta_{2}<\cdots<\theta_{N-1}<\frac{\pi}{2}$ , and $N$ represents the number of $\theta$ values which enables the adjustment of accuracy.

Proof.

Suppose a message $\mathbf{M}=\left(\mathbf{m}_{1},\mathbf{m}_{2},\cdots,\mathbf{m}_{n/k}\right)\in{\{0,1\}}^{n}$ is encoded to $\operatorname{f}\left(\mathbf{x}_{i,j}(\mathbf{M})\right)$ to be transmitted over a flat slow Rayleigh fading channel with an AWGN. The received signal can be expressed as:

y_{i,j}=h_{i,j}\operatorname{f}\left(\mathbf{x}_{i,j}(\mathbf{M})\right)+n_{i,j}\text{,}

(8)

where $y_{i,j}$ is the corresponding received signal at the receiver, $h_{i,j}$ is the channel fading parameter following Rayleigh distribution with mean square $\Omega$ , and $n_{i,j}$ is the AWGN with variance $\sigma^{2}$ .

ML decoding selects the one with the lowest decoding cost from the candidate sequence space ${\{0,1\}}^{n}$ . Given received symbols $y_{i,j}$ and perfect CSI $\hat{h}_{i,j}=h_{i,j}$ , the ML rule for the Rayleigh fading channel with the AWGN is

\small\begin{split}\hat{\mathbf{M}}&\in\underset{\mathbf{\bar{M}}\in{\{0,1\}}^{n}}{\mathrm{arg\,min}}\sum_{i=1}^{n/k}\sum_{j=1}^{L}{(y_{i,j}-h_{i,j}\operatorname{f}(\mathbf{x}_{i,j}(\bar{\mathbf{M}})))}^{2}\text{,}\end{split}

(9)

where $\hat{\mathbf{M}}$ is the decoding result, $\bar{\mathbf{M}}$ is the candidate sequence.

From this perspective, we classify the set of candidate sequences ${\{0,1\}}^{n}$ into two subsets: $i$ ) the correct decoding sequence $\mathbf{M}=\left(\mathbf{m}_{1},\mathbf{m}_{2},\cdots,\mathbf{m}_{n/k}\right)$ ; $ii$ ) wrong decoding sequences $\mathbf{M}^{\prime}=\left(\mathbf{m}^{\prime}_{1},\mathbf{m}^{\prime}_{2},\cdots,\mathbf{m}^{\prime}_{n/k}\right)\in\mathcal{W}$ , with $\mathcal{W}\triangleq\left\{\left(\mathbf{m}^{\prime}_{1},\mathbf{m}^{\prime}_{2},\cdots,\mathbf{m}^{\prime}_{n/k}\right):\exists 1\leq i\leq n/k,\mathbf{m}^{\prime}_{i}\neq\mathbf{m}_{i}\right\}$ . Denoting the cost of $\mathbf{M}$ as $\mathscr{D}(\mathbf{M})$ , it turns out that

\displaystyle\small\begin{split}\mathscr{D}(\mathbf{M})&\triangleq\sum_{i=1}^{n/k}\sum_{j=1}^{L}{\left(y_{i,j}-h_{i,j}\operatorname{f}(\mathbf{x}_{i,j}(\mathbf{M}))\right)}^{2}=\sum_{i=1}^{n/k}\sum_{j=1}^{L}n_{i,j}^{2}\text{.}\end{split}

(10)

Similarly, denote the cost of $\mathbf{M}^{\prime}$ as $\mathscr{D}(\mathbf{M}^{\prime})$ , given by:

\displaystyle\mathscr{D}(\mathbf{M}^{\prime})\triangleq\sum_{i=1}^{n/k}\sum_{j=1}^{L}{\left(y_{i,j}-h_{i,j}\operatorname{f}(\mathbf{x}_{i,j}(\mathbf{M}^{\prime}))\right)}^{2}\text{.}

(11)

In the sequal, we attempt to explicitly express the error probability of Spinal codes. Let $\mathcal{E}_{a}$ be the event that there exists an error in the $a^{th}$ segment, which implies that:

1.

The $a^{th}$ segment is different, i.e., $\mathbf{m}_{a}\neq\mathbf{m}^{\prime}_{a}$ .
2.

The cost of the wrong decoding sequence is less than the correct one, i.e., $\mathscr{D}(\mathbf{M}^{\prime})\leq\mathscr{D}(\mathbf{M})$ . In this case, the ML decoder will incorrectly choose a certain wrong sequence $\mathbf{M}^{\prime}\in\mathcal{W}$ as the decoding output.

Denote $\overline{\mathcal{E}}_{a}$ as the complement of $\mathcal{E}_{a}$ . The error probability of Spinal codes can be expressed as:

\small\begin{split}P_{e}&=\mathrm{Pr}\left(\bigcup_{a=1}^{n/k}\mathcal{E}_{a}\right)=1-\mathrm{Pr}\left(\bigcap_{a=1}^{n/k}\overline{\mathcal{E}}_{a}\right)\\ &=1-\prod_{a=1}^{n/k}\left[1-\mathrm{Pr}\left(\mathcal{E}_{a}\bigg{|}\bigcap_{i=1}^{a-1}\overline{\mathcal{E}}_{i}\right)\right]\text{.}\end{split}

(12)

Thus, to obtain the error probability $P_{e}$ , the remaining issue is to calculate $\mathrm{Pr}\bigg{(}\mathcal{E}_{a}\bigg{|}\bigcap_{i=1}^{a-1}\overline{\mathcal{E}}_{i}\bigg{)}$ , which is interpreted as the probability that the $a^{th}$ segment is wrong while the previous $(a-1)$ segments are correct. With the defination that $\mathcal{W}_{a}\triangleq\{\left(\mathbf{m}^{\prime}_{1},\cdots,\mathbf{m}^{\prime}_{a}\right)\text{:}\mathbf{m}^{\prime}_{1}=\mathbf{m}_{1},\cdots,\mathbf{m}^{\prime}_{a-1}=\mathbf{m}_{a-1},\mathbf{m}^{\prime}_{a}\neq\mathbf{m}_{a}\}\subseteq\mathcal{W}$ , the conditional probability is transformed as:

\small\mathrm{Pr}\left(\mathcal{E}_{a}\bigg{|}\bigcap_{i=1}^{a-1}\overline{\mathcal{E}}_{i}\right)=\mathrm{Pr}\left(\exists\mathbf{M}^{\prime}\in\mathcal{W}_{a}:\mathscr{D}(\mathbf{M}^{\prime})\leq\mathscr{D}(\mathbf{M})\right)\text{.}

(13)

Applying the union bound of probability [19] yields that

\begin{split}&\mathrm{Pr}\left(\exists\mathbf{M}^{\prime}\in\mathcal{W}_{a}:\mathscr{D}(\mathbf{M}^{\prime})\leq\mathscr{D}(\mathbf{M})\right)\\ &\leq\sum_{\mathbf{M}^{\prime}\in\mathcal{W}_{a}}\mathrm{Pr}\left(\mathscr{D}(\mathbf{M}^{\prime})\leq\mathscr{D}(\mathbf{M})\right)\text{.}\end{split}

(14)

Given that $\mathscr{D}(\mathbf{M})$ and $\mathscr{D}(\mathbf{M}^{\prime})$ have been calculated in (10) and (11) respectively, the probability $\mathrm{Pr}\left(\mathscr{D}(\mathbf{M}^{\prime})\leq\mathscr{D}(\mathbf{M})\right)$ is calculated as follows:

		$\displaystyle\mathrm{Pr}\left(\mathscr{D}(\mathbf{M}^{\prime})\leq\mathscr{D}(\mathbf{M})\right)$
		$\displaystyle=\mathrm{Pr}\bigg{(}\sum_{i=1}^{n/k}\sum_{j=1}^{L}{\left(y_{i,j}-h_{i,j}\operatorname{f}(x_{i,j}(\mathbf{M^{\prime}}))\right)}^{2}\leq\sum_{i=1}^{n/k}\sum_{j=1}^{L}n_{i,j}^{2}\bigg{)}$
		$\displaystyle\overset{(a)}{=}\mathrm{Pr}\bigg{(}\sum_{i=a}^{n/k}\sum_{j=1}^{L}{\left(y_{i,j}-h_{i,j}\operatorname{f}(x_{i,j}(\mathbf{M^{\prime}}))\right)}^{2}\leq\sum_{i=a}^{n/k}\sum_{j=1}^{L}n_{i,j}^{2}\bigg{)}$
		$\displaystyle\overset{(b)}{=}\mathrm{Pr}\bigg{(}\sum_{i=a}^{n/k}\sum_{j=1}^{L}{\left[h_{i,j}(\operatorname{f}(x_{i,j}(\mathbf{M}))-f(x_{i,j}(\mathbf{M^{\prime}})))+n_{i,j}\right]}^{2}$
		$\displaystyle\qquad\qquad\qquad\qquad\leq\sum_{i=a}^{n/k}\sum_{j=1}^{L}n^{2}_{i,j}\bigg{)},$		(15)

where ( $a$ ) establishes since $\operatorname{f}(\mathbf{x}_{i,j}(\mathbf{M}))=\operatorname{f}(\mathbf{x}_{i,j}(\mathbf{M^{\prime}}))$ for $1\leq i<a$ , which is proved in Appendix A by leveraging the property of hash function. ( $b$ ) is obtained by applying (8).

Define $U_{i,j}\triangleq\operatorname{f}(\mathbf{x}_{i,j}(\mathbf{M}))-\operatorname{f}(\mathbf{x}_{i,j}(\mathbf{M^{\prime}}))$ and $V_{i,j}\triangleq h_{i,j}U_{i,j}$ , and then (III-A) can be expanded as

\small\begin{split}&\mathrm{Pr}\bigg{(}\sum_{i=a}^{n/k}\sum_{j=1}^{L}{\bigg{[}\underbrace{h_{i,j}(\operatorname{f}(x_{i,j}(\mathbf{M}))-\operatorname{f}(x_{i,j}(\mathbf{M^{\prime}})))}_{V_{i,j}}+n_{i,j}\bigg{]}}^{2}\\ &\qquad\qquad\quad\quad\leq\sum_{i=a}^{n/k}\sum_{j=1}^{L}n^{2}_{i,j}\bigg{)}\\ &=\mathrm{Pr}\left(\sum_{i=a}^{n/k}\sum_{j=1}^{L}V^{2}_{i,j}+2\sum_{i=a}^{n/k}\sum_{j=1}^{L}V_{i,j}n_{i,j}\leq 0\right)\text{.}\end{split}

(16)

Denoting $\mathbf{V}^{L_{a}}$ as the random row vector composed of random variables $V_{i,j}$ with $a\leq i\leq n/k,1\leq j\leq L$ , and $\mathbf{N}^{L_{a}}$ as the random row vector composed of random variables $n_{i,j}$ with $a\leq i\leq n/k,1\leq j\leq l_{i}$ , (16) could be rewritten into a vector form, given as

\small\begin{split}&\mathrm{Pr}\left(\sum_{i=a}^{n/k}\sum_{j=1}^{L}V^{2}_{i,j}+2\sum_{i=a}^{n/k}\sum_{j=1}^{L}V_{i,j}n_{i,j}\leq 0\right)\\ &=\mathrm{Pr}\left(\mathbf{V}^{L_{a}}{\left(\mathbf{V}^{L_{a}}+2{\mathbf{N}}^{L_{a}}\right)}^{\mathrm{T}}\leq 0\right),\end{split}

(17)

which could be then expanded as

		$\displaystyle\int_{\mathbb{R}^{L_{a}}}\mathrm{Pr}\left(\mathbf{V}^{L_{a}}{\left(\mathbf{V}^{L_{a}}+2{\mathbf{N}}^{L_{a}}\right)}^{\mathrm{T}}\leq 0\big{\|}\mathbf{V}^{L_{a}}=\mathbf{v}^{L_{a}}\right)\cdot$		(18)
		$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\mathrm{Pr}\left(\mathbf{V}^{L_{a}}=\mathbf{v}^{L_{a}}\right){~{}\mathrm{d}\mathbf{v}^{L_{a}}}$
		$\displaystyle=\int_{\mathbb{R}^{L_{a}}}\mathrm{Pr}\left(\mathbf{v}^{L_{a}}{\left(\mathbf{v}^{L_{a}}+2{\mathbf{N}}^{L_{a}}\right)}^{\mathrm{T}}\leq 0\right)\cdot$
		$\displaystyle\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\mathrm{Pr}\left(\mathbf{V}^{L_{a}}=\mathbf{v}^{L_{a}}\right){~{}\mathrm{d}\mathbf{v}^{L_{a}}}.$

With (18) in hand, the next problem is to explicitly solve $\mathrm{Pr}\left(\mathbf{v}^{L_{a}}{\left(\mathbf{v}^{L_{a}}+2{\mathbf{N}}^{L_{a}}\right)}^{\mathrm{T}}\leq 0\right)$ and $\mathrm{Pr}\left(\mathbf{V}^{L_{a}}=\mathbf{v}^{L_{a}}\right)$ . First, we attempt to simplify $\mathrm{Pr}\left(\mathbf{v}^{L_{a}}{\left(\mathbf{v}^{L_{a}}+2{\mathbf{N}}^{L_{a}}\right)}^{\mathrm{T}}\leq 0\right)$ . By introducing two rotation matrices for $L_{a}$ -dimensions hyperspace, we obtain Lemma 1 as follows:

Lemma 1.

Given that $n_{i,j}$ is i.i.d AWGN with variance $\sigma^{2}$ , the probability in (18) can be simplified as

\small\mathrm{Pr}\left(\mathbf{v}^{L_{a}}{\left(\mathbf{v}^{L_{a}}+2{\mathbf{N}}^{L_{a}}\right)}^{\mathrm{T}}\leq 0\right)=Q\left(\frac{\left\|\mathbf{v}^{L_{a}}\right\|}{2\sigma}\right),

(19)

where $Q(\cdot)$ represents the $Q$ function, $\left\|\cdot\right\|$ represents the $\ell^{2}$ norm.

Proof.

Please refer to Appendix B. ∎

Note that [20] has shown a transformation of $Q(\cdot)$ , which is presented as an exponential form, given as

\small Q(x)=\frac{1}{\pi}\int_{0}^{\frac{\pi}{2}}\mathrm{exp}\left(\frac{-x^{2}}{2\mathrm{sin}^{2}\theta}\right)\mathrm{d}\theta\text{.}

(20)

Adopting (20) into (19) yields that

		$\displaystyle\mathrm{Pr}\left(\mathbf{v}^{L_{a}}{\left(\mathbf{v}^{L_{a}}+2{\mathbf{N}}^{L_{a}}\right)}^{\mathrm{T}}\leq 0\right)$
		$\displaystyle=Q\left(\frac{\left\\|\mathbf{v}^{L_{a}}\right\\|}{2\sigma}\right)=\frac{1}{\pi}\int_{0}^{\frac{\pi}{2}}\mathrm{exp}\left(\frac{-{\left\\|\mathbf{v}^{L_{a}}\right\\|}^{2}}{8\sigma^{2}\mathrm{sin}^{2}\theta}\right)\mathrm{d}\theta\text{.}$		(21)

Applying (III-A) in (18) and swapping the integrates, we have

\small\begin{split}&\mathrm{Pr}\left(\mathbf{V}^{L_{a}}{\left(\mathbf{V}^{L_{a}}+2{\mathbf{N}}^{L_{a}}\right)}^{\mathrm{T}}\leq 0\right)\\ &=\frac{1}{\pi}\int_{\mathbb{R}^{L_{a}}}\int_{0}^{\frac{\pi}{2}}\mathrm{exp}\left(\frac{-{\left\|\mathbf{v}^{L_{a}}\right\|}^{2}}{8\sigma^{2}\mathrm{sin}^{2}\theta}\right)\mathrm{d}\theta\cdot\mathrm{Pr}\left(\mathbf{V}^{L_{a}}=\mathbf{v}^{L_{a}}\right)\mathrm{d}\mathbf{v}^{L_{a}}\\ &=\frac{1}{\pi}\int_{0}^{\frac{\pi}{2}}\underbrace{\int_{\mathbb{R}^{L_{a}}}\mathrm{exp}\left(\frac{-{\left\|\mathbf{v}^{L_{a}}\right\|}^{2}}{8\sigma^{2}\mathrm{sin}^{2}\theta}\right)\cdot\mathrm{Pr}\left(\mathbf{V}^{L_{a}}=\mathbf{v}^{L_{a}}\right)~{}\mathrm{d}\mathbf{v}^{L_{a}}}_{\mathcal{F}_{\text{Rayleigh}(\theta;\sigma,L_{a})}}\mathrm{d}\theta\text{.}\end{split}

(22)

For the Rayleigh fading channel, we denote the multiple integrals with respect to $\mathbf{v}^{L_{a}}$ as $\mathcal{F}_{\text{Rayleigh}}\left(\theta;\sigma,L_{a}\right)$ . By adopting the i.i.d of $V_{i,j}$ , given as

\small\Pr\left(\mathbf{V}^{L_{a}}=\mathbf{v}^{L_{a}}\right)=\prod_{i=a}^{n/k}\prod_{j=1}^{L}f_{V_{i,j}}\left(v_{i,j}\right),

(23)

$\mathcal{F}_{\text{Rayleigh}}\left(\theta;\sigma,L_{a}\right)$ could be decomposed as

\small\begin{split}&\underbrace{\int_{\mathbb{R}}\cdots\int_{\mathbb{R}}}_{L_{a}}\mathrm{exp}\left(\frac{-{\left\|\mathbf{v}^{L_{a}}\right\|}^{2}}{8\sigma^{2}\mathrm{sin}^{2}\theta}\right)\prod_{i=a}^{n/k}\prod_{j=1}^{L}f_{V_{i,j}}(v_{i,j})\prod_{i=a}^{n/k}\prod_{j=1}^{L}\mathrm{d}v_{i,j}\\ &\overset{(a)}{=}\prod_{i=a}^{n/k}\prod_{j=1}^{L}\int_{\mathbb{R}}\mathrm{exp}\left(\frac{-v_{i,j}^{2}}{8\sigma^{2}\mathrm{sin}^{2}\theta}\right)f_{V_{i,j}}(v_{i,j})~{}\mathrm{d}v_{i,j}\\ &\overset{(b)}{=}{\left(\int_{\mathbb{R}}{\mathrm{exp}}{\left(-\frac{v_{a,1}^{2}}{{8}{\sigma^{2}}{\sin^{2}}\theta}\right)}f_{V_{a,1}}(v_{a,1})\mathrm{d}v_{a,1}\right)}^{L_{a}}\text{,}\end{split}

(24)

where (a) establishes by adopting

\small\begin{split}\exp\left(\frac{-\|\mathbf{v}^{L_{a}}\|^{2}}{8\sigma^{2}\sin^{2}\theta}\right)&=\exp\left(\frac{-\sum_{i=a}^{n/k}\sum_{j=1}^{L}v^{2}_{i,j}}{8\sigma^{2}\sin^{2}\theta}\right)\\ &=\prod_{i=a}^{n/k}\prod_{j=1}^{L}\exp\left(\frac{-v^{2}_{i,j}}{8\sigma^{2}\sin^{2}\theta}\right)\text{,}\end{split}

(25)

and (b) holds for the i.i.d of the random variable $V_{i,j}$ . Recall that $V_{i,j}=h_{i,j}U_{i,j}$ where $h_{i,j}$ and $U_{i,j}$ are independent with each other, the integral in (24) with respect to $v_{a,1}$ could be then transformed to

\small\begin{split}&\int_{\mathbb{R}}{\mathrm{exp}}{\left(-\frac{v_{a,1}^{2}}{{8}{\sigma^{2}}{\sin^{2}}\theta}\right)}f_{{V}_{a,1}}(v_{a,1})\mathrm{d}v_{a,1}\\ &\xlongequal{v_{a,1}=hu}\sum_{u}p_{{}_{U}}(u)\int_{\mathbb{R}}{\mathrm{exp}}{\left(-\frac{{h^{2}}{u^{2}}}{{8}{\sigma^{2}}{\sin^{2}}\theta}\right)}g_{{}_{1}}(h)\mathrm{d}h\text{,}\end{split}

(26)

where $p_{{}_{U}}(u)$ is the probability mass function (PMF) of $U_{a,1}$ and $g_{{}_{1}}(h)$ is the probability density function (PDF) of $h$ . At this point, the right-hand side (RHS) of (26) could be explicitly calculated by the following lemma.

Lemma 2.

For Rayleigh distribution whose PDF is $g_{{}_{1}}(h)$ , the RHS of (26) can be calculated by

\small\sum_{i\in\Psi}\sum_{j\in\Psi}2^{-2c}\frac{8{\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8{\sigma}^{2}{\sin}^{2}{\theta}}\text{,}

(27)

where $\Psi$ is the channel input set.

Proof.

Please refer to Appendix C for the detailed derivation. ∎

As such, substituting (27) back into (24) turns out that

\small\mathcal{F}_{\text{Rayleigh}}(\theta\text{;}\sigma\text{,}L_{a})={\left(\sum_{i\in\Psi}\sum_{j\in\Psi}2^{-2c}\frac{8{\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8{\sigma}^{2}{\sin}^{2}{\theta}}\right)}^{L_{a}}\text{.}

(28)

With (28) in hand, the RHS of (LABEL:eq12) is transformed as

\small\begin{split}&\sum_{\mathbf{M}^{\prime}\in\mathcal{W}_{a}}\mathrm{Pr}\left(\mathscr{D}\left(\mathbf{M}^{\prime}\right)\leq\mathscr{D}\left(\mathbf{M}\right)\right)\\ &=\frac{1}{\pi}\sum_{\mathbf{M}^{\prime}\in\mathcal{W}_{a}}\int_{0}^{\frac{\pi}{2}}\mathcal{F}_{\text{Rayleigh}}(\theta\text{;}\sigma\text{,}L_{a})\mathrm{d}\theta\text{.}\end{split}

(29)

Note that $\mathcal{F}_{\text{Rayleigh}}(\theta\text{;}\sigma\text{,}L_{a})$ is inreasing with $\theta$ for $0\leq\theta\leq\frac{\pi}{2}$ (see Appendix D for the detailed proof), so we can arbitrarily choose $N+1$ values of $\theta$ such that $\theta_{0}=0$ , $\theta_{N}=\frac{\pi}{2}$ and $0<\theta_{1}<\theta_{2}<\cdots<\theta_{N-1}<\frac{\pi}{2}$ to explicitly upper bound the error probability. Combining these values back into (29), we get the inequality as

\small\begin{split}&\sum_{\mathbf{M^{\prime}}\in\mathcal{W}_{a}}\mathrm{Pr}\left(\mathscr{D}\left(M^{\prime}\right)\leq\mathscr{D}\left(M\right)\right)\\ &=\frac{1}{\pi}\cdot\sum_{\mathbf{M}^{\prime}\in\mathcal{W}_{a}}\int_{0}^{\frac{\pi}{2}}\mathcal{F}_{\text{Rayleigh}}(\theta\text{;}\sigma\text{,}L_{a})\mathrm{d}\theta\\ &\leq\frac{\left|\mathcal{W}_{a}\right|}{\pi}\cdot\sum_{r=1}^{N}\int_{\theta_{r-1}}^{\theta_{r}}\mathcal{F}_{\text{Rayleigh}}(\theta_{r}\text{;}\sigma\text{,}L_{a})\mathrm{d}\theta\\ &=\left|\mathcal{W}_{a}\right|\cdot\sum_{r=1}^{N}b_{r}\mathcal{F}_{\text{Rayleigh}}(\theta_{r}\text{;}\sigma\text{,}L_{a})\text{,}\end{split}

(30)

where

\small b_{r}=\frac{\theta_{r}-\theta_{r-1}}{\pi}\text{,}\quad\left|\mathcal{W}_{a}\right|=(2^{k}-1)2^{n-ak}.

(31)

Denoting

\small\mathscr{F}_{\text{Rayleigh}}\left(L_{a}\text{,}\sigma\right)=\sum_{r=1}^{N}b_{r}\mathcal{F}_{\text{Rayleigh}}(\theta_{r}\text{;}\sigma\text{,}L_{a})\text{,}

(32)

and applying (32) to (LABEL:eq12) results in the explicit bound. ∎

III-B Bounds on the Nakagami-m Fading Channel

Theorem 2.

Consider Spinal codes with message length $n$ , segmentation parameter $k$ , modulation parameter $c$ and sufficiently large hash parameter $v$ transmitted over a flat slow Nakagami-m fading channel with mean square $\Omega$ , shape parameter $m$ and AWGN variance $\sigma^{2}$ . The average error probability given perfect CSI under ML decoding for Spinal codes can be upper bounded by

\displaystyle\small P_{e}\leq 1-\prod_{a=1}^{n/k}\left(1-\epsilon_{a}\right)\text{,}

(33)

with

\epsilon_{a}=\mathrm{min}\left\{1,\left(2^{k}-1\right)2^{n-ak}\cdot\mathscr{F}_{\text{Nakagami}}(L_{a},\sigma)\right\}\text{,}

(34)

\mathscr{F}_{\text{Nakagami}}\left(L_{a}\text{,}\sigma\right)=\sum_{r=1}^{N}b_{r}\mathcal{F}_{\text{Nakagami}}(\theta_{r}\text{;}\sigma\text{,}L_{a})\text{,}

(35)

\small\begin{split}&\mathcal{F}_{\text{Nakagami}}(\theta_{r}\text{;}\sigma\text{,}L_{a})\\ &={\left(\sum_{i\in\Psi}\sum_{j\in\Psi}2^{-2c}{\left(\frac{8m{\sigma}^{2}{\sin}^{2}{\theta}_{r}}{{\Omega}(i-j)^{2}+8m{\sigma}^{2}{\sin}^{2}{\theta}_{r}}\right)}^{m}\right)}^{L_{a}}\text{,}\end{split}

(36)

where $b_{r}=\frac{\theta_{r}-\theta_{r-1}}{\pi}$ , $L_{a}=(n/k-a+1)L$ , $L$ is the number of transmitted passes, $\theta_{r}$ is arbitrarily chosen with $\theta_{0}=0$ , $\theta_{N}=\frac{\pi}{2}$ and $0<\theta_{1}<\theta_{2}<\cdots<\theta_{N-1}<\frac{\pi}{2}$ , and N represents the number of $\theta$ values which enables the adjustment of accuracy.

Proof.

Please refer to Appendix E. ∎

III-C Bounds on the Rician Fading Channel

Theorem 3.

Consider Spinal codes with message length $n$ , segmentation parameter $k$ , modulation parameter $c$ and sufficiently large hash parameter $v$ transmitted over a flat slow Rician fading channel with mean square $\Omega$ ,shape parameter $K$ and AWGN variance $\sigma^{2}$ . The average error probability given perfect CSI under ML decoding for Spinal codes can be upper bounded by

\small P_{e}\leq 1-\prod_{a=1}^{n/k}\left(1-\epsilon_{a}\right)\text{,}

(37)

with

\epsilon_{a}=\mathrm{min}\left\{1,\left(2^{k}-1\right)2^{n-ak}\cdot\mathscr{F}_{\text{Rician}}(L_{a},\sigma)\right\}\text{,}

(38)

\mathscr{F}_{\text{Rician}}\left(L_{a}\text{,}\sigma\right)=\sum_{r=1}^{N}b_{r}\mathcal{F}_{\text{Rician}}(\theta_{r}\text{;}\sigma\text{,}L_{a})\text{,}

(39)

\small\begin{split}&\mathcal{F}_{\text{Rician}}(\theta_{r}\text{;}\sigma\text{,}L_{a})\\ &=\Bigg{(}\sum_{i\in\Psi}\sum_{j\in\Psi}2^{-2c}\frac{8(K+1){\sigma}^{2}{\sin}^{2}{\theta}_{r}}{{\Omega}(i-j)^{2}+8(K+1){\sigma}^{2}{\sin}^{2}{\theta}_{r}}\\ &\qquad\cdot{\mathrm{exp}\left(\frac{8K(K+1){\sigma}^{2}{\sin}^{2}{\theta}_{r}}{{\Omega}(i-j)^{2}+8(K+1){\sigma}^{2}{\sin}^{2}{\theta}_{r}}-K\right)\Bigg{)}}^{L_{a}}\text{,}\end{split}

(40)

where $b_{r}=\frac{\theta_{r}-\theta_{r-1}}{\pi}$ , $L_{a}=(n/k-a+1)L$ , $L$ is the number of transmitted passes, $\theta_{r}$ is arbitrarily chosen with $\theta_{0}=0$ , $\theta_{N}=\frac{\pi}{2}$ and $0<\theta_{1}<\theta_{2}<\cdots<\theta_{N-1}<\frac{\pi}{2}$ , and N represents the number of $\theta$ values which enables the adjustment of accuracy.

Proof.

Please refer to Appendix F. ∎

IV Simulation Result

In this section, we conduct Monte Carlo simulations to illustrate the accuracy of the upper bounds derived in Section III. Since the exponential nature of the ML-decoding complexity, the input message bits $n$ is selected as low as $n=8$ and the number of pass is set as $L=6$ here for the easy ML-decoding simulation setup. The parameter $v$ is set to $v=32$ for the implementation and experiments, demonstrated by the property 2 in Appendix A that the hash collision will occur only once per $2^{32}$ hash function invocations on average. Furthermore, to improve the accuracy of approximation for upper bounds, we set $N=20$ and the sample size of Monte Carlo simulations to be $10^{6}$ .

We nomalize the mean square values of all fading channels, i.e., $\Omega=1$ . Besides the setting of $\Omega$ , for the Nakagami-m fading channel, we also set the shape parameter as $m=2$ . And for Rician fading channels, the shape parameter $K$ , defined as the ratio of the power contributions by line-of-sight path to the remaining multipaths, is set as $K=0.5$ and $K=1$ , respectively.

Fig.2 shows examples of the error probability for Rayleigh, Nakagami-m and Rician fading channels, respectively. All approximations are close to simulated values. We could observe that the FER curve for $K=1$ is lower than the one for $K=0.5$ in Rician fading channels, which is due to $K$ is the ratio of the energy in the specular path to the energy in the scattered paths, i.e., the larger $K$ , the more deterministic the channel.

V Conclusion

This paper analyzes the error probability of Spinal codes and derives upper bounds on the error probability under ML decoding over several fading channels, including the Rayleigh fading channel, the Nakagami-m fading channel and the Rician fading channel. Additionally, we conduct simulations for different fading channels and parameters. Our experimental examples show that the upper bounds we derived have a good performence on the estimation of the average error probablity.

The work in this paper may also inspire innovation about further research and efforts in related topics. The derived upper bounds can provide theoretical support and guidance for designing other high-efficiency coding-associated techniques, such as unequal error protection and concatenation with outer codes.

References

[1] J. Perry, H. Balakrishnan, and D. Shah, “Rateless Spinal Codes,” Proceedings of the 10th ACM Workshop on Hot Topics in Networks, 2011.
[2] H. Balakrishnan, P. Iannucci, J. Perry, and D. Shah, “De-randomizing shannon: The design and analysis of a capacity-achieving rateless code,” arXiv preprint arXiv:1206.0418, 2012.
[3] J. Perry, P. A. Iannucci, K. E. Fleming, H. Balakrishnan, and D. Shah, “Spinal Codes,” Proceedings of the ACM SIGCOMM 2012 Conference, pp. 49––60, 2012.
[4] G. Ungerboeck, “Channel coding with multilevel/phase signals,” IEEE Transactions on Information Theory, vol. 28, no. 1, pp. 55–67, 1982.
[5] G. Ungerboeck and I. Csajka, “On Improving data-link performance by increasing the channel alphabet and introducing sequence coding,” IEEE International Symposium on Information Theory, 1976.
[6] S. Yousefi and A. Khandani, “A new upper bound on the ML decoding error probability of linear binary block codes in AWGN interference,” IEEE Transactions on Information Theory, vol. 50, no. 12, pp. 3026–3036, 2004.
[7] D. Goldin and D. Burshtein, “Performance Bounds of Concatenated Polar Coding Schemes,” IEEE Transactions on Information Theory, vol. 65, no. 11, pp. 7131–7148, 2019.
[8] B. Shuval and I. Tal, “A Lower Bound on the Probability of Error of Polar Codes over BMS Channels,” IEEE Transactions on Information Theory, vol. 65, no. 4, pp. 2021–2045, 2019.
[9] F. Lázaro, G. Liva, G. Bauch, and E. Paolini, “Bounds on the Error Probability of Raptor Codes Under Maximum Likelihood Decoding,” IEEE Transactions on Information Theory, vol. 67, no. 3, pp. 1537–1558, 2021.
[10] B. Schotsch, G. Garrammone, and P. Vary, “Analysis of LT Codes over Finite Fields under Optimal Erasure Decoding,” IEEE Communications Letters, vol. 17, no. 9, pp. 1826–1829, 2013.
[11] B. Schotsch, Rateless coding in the finite length regime. Hochschulbibliothek der Rheinisch-Westfälischen Technischen Hochschule Aachen, 2014.
[12] I. Sason and S. Shamai, “Performance Analysis of Linear Codes under Maximum-Likelihood Decoding: A Tutorial,” Foundations and Trends in Communications and Information Theory, vol. 3, no. 1–2, pp. 1–222, 2006.
[13] X. Yu, Y. Li, W. Yang, and Y. Sun, “Design and Analysis of Unequal Error Protection Rateless Spinal Codes,” IEEE Transactions on Communications, vol. 64, no. 11, pp. 4461–4473, 2016.
[14] Y. Polyanskiy, H. V. Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,” IEEE Transactions on Information Theory, vol. 56, no. 5, pp. 2307–2359, 2010.
[15] R. G. Gallager, Information theory and reliable communication. Wiley, 1968, vol. 588.
[16] A. Li, S. Wu, J. Jiao, N. Zhang, and Q. Zhang, “New Upper Bounds on the Error Probability under ML Decoding for Spinal Codes and the Joint Transmission-Decoding System Design,” arXiv preprint arXiv:2101.07953, 2021.
[17] A. Li, S. Wu, J. Jiao, N. Zhang, and Q. Zhang, “Spinal Codes Over Fading Channel: Error Probability Analysis and Encoding Structure Improvement,” IEEE Transactions on Wireless Communications, vol. 20, no. 12, pp. 8288–8300, 2021.
[18] H. Chernoff, “A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations,” The Annals of Mathematical Statistics, pp. 493–507, 1952.
[19] G. Boole, The mathematical analysis of logic. Philosophical Library, 1847.
[20] U. Erez, M. D. Trott, and G. W. Wornell, “Rateless Coding for Gaussian Channels,” IEEE Transactions on Information Theory, vol. 58, no. 2, pp. 530–547, 2012.
[21] M. Mitzenmacher and E. Upfal, Probability and computing: Randomized algorithms and probabilistic analysis. Cambridge University Press, 2005.
[22] W. Kaplan, Advanced calculus. Pearson Education India, 1952.

Appendix A The properties of hash and related inferences

The core idea of Spinal codes is to apply a hash function sequentially to generate a pseudo-random mapping from message bits to coded bits. The hash function is expressed as

h:\{0,1\}^{v}\times\{0,1\}^{k}\rightarrow\{0,1\}^{v},

(41)

where $v$ and $k$ are both integers. In Spinal codes, $h$ is chosen from a pairwise independent family of hash functions $\mathscr{H}$ [21] by uniformly using a random seed.

Property 1.

As Perry et al. indicate [3], the hash function employed by Spinal codes should have pairwise independent property:

\begin{split}&\mathrm{Pr}\{h(\mathbf{s},\mathbf{m})=\mathbf{x},h(\mathbf{s}^{\prime},\mathbf{m}^{\prime})=\mathbf{x}^{\prime}\}\\ &=\mathrm{Pr}\{h(\mathbf{s},\mathbf{m})=\mathbf{x}\}\cdot\mathrm{Pr}\{h(\mathbf{s}^{\prime},\mathbf{m}^{\prime})=\mathbf{x}^{\prime}\}\\ &=2^{-2v}\text{,}\end{split}

(42)

where $(\mathbf{s},\mathbf{m})$ and $(\mathbf{s}^{\prime},\mathbf{m}^{\prime})$ are arbitrarily chosen, $(\mathbf{s},\mathbf{m})\neq(\mathbf{s}^{\prime},\mathbf{m}^{\prime})$ .

Property 2.

A sufficiently large v will lead to a zero-approaching hash collision probability, with [3]

\begin{split}&\mathrm{Pr}\{h(\mathbf{s},\mathbf{m})=h(\mathbf{s}^{\prime},\mathbf{m}^{\prime})\}\\ &=\sum_{\mathbf{x}\in{\{0,1\}}^{v}}\underbrace{\mathrm{Pr}\{h(\mathbf{s},\mathbf{m})=\mathbf{x},h(\mathbf{s}^{\prime},\mathbf{m}^{\prime})=\mathbf{x}^{\prime}\}}_{\mathrm{Property}\ref{property1}}\\ &=2^{v}\cdot 2^{-2v}\\ &=2^{-v}\approx 0,\ \text{iff}\ v\gg 0\text{,}\end{split}

(43)

where $(\mathbf{s},\mathbf{m})$ and $(\mathbf{s}^{\prime},\mathbf{m}^{\prime})$ are arbitrarily chosen, $(\mathbf{s},\mathbf{m})\neq(\mathbf{s}^{\prime},\mathbf{m}^{\prime})$ .

Recall that $\mathbf{M}$ is the correct decoding sequence and $\mathbf{M}^{\prime}\in\mathcal{W}$ is a certain wrong decoding sequence. We denote the spine values of $\mathbf{M}$ as $s(\mathbf{M})=(\mathbf{s}_{1},\mathbf{s}_{2},\cdots,\mathbf{s}_{n/k})$ and the spine values of $\mathbf{M}^{\prime}$ as $s(\mathbf{M}^{\prime})=(\mathbf{s}^{\prime}_{1},\mathbf{s}^{\prime}_{2},\cdots,\mathbf{s}^{\prime}_{n/k})$ .

In (1), the process of generating $\mathbf{s}_{i}$ has given that $\mathbf{s}_{i}=h(\mathbf{s}_{i-1},\mathbf{m}_{i})$ , $\mathbf{s}_{0}=\mathbf{0}^{v}$ . So it is natural to get that

\mathrm{Pr}(\mathbf{s}_{i}=\mathbf{s}^{\prime}_{i}|\mathbf{m}_{i}=\mathbf{m}^{\prime}_{i},\mathbf{s}_{i-1}=\mathbf{s}^{\prime}_{i-1})=1\text{,}

(44)

for $1\leq i\leq n/k$ .

Conversely, if $\mathbf{m}_{i}\neq\mathbf{m}^{\prime}_{i}$ or $\mathbf{s}_{i-1}\neq\mathbf{s}^{\prime}_{i-1}$ with a sufficiently large $v$ , from Property 2 we can obtain that $\mathbf{s}_{i}\neq\mathbf{s}^{\prime}_{i}$ for $1\leq i\leq n/k$ .

When $\mathbf{M}^{\prime}\in\mathcal{W}_{a}$ , $i.e.$ , $\mathbf{m}_{i}=\mathbf{m}^{\prime}_{i}$ for $1\leq i<a$ and $\mathbf{m}_{a}\neq\mathbf{m}^{\prime}_{a}$ , we can iterate to obtain that $\mathbf{s}_{i}=\mathbf{s}^{\prime}_{i}$ for $1\leq i<a$ and $\mathbf{s}_{i}\neq\mathbf{s}^{\prime}_{i}$ for $a\leq i\leq n/k$ . Hence after RNGs and uniform constellation mapping, the coded symbols satisfy

\operatorname{f}(\mathbf{x}_{i,j}(\mathbf{M}))=\operatorname{f}(\mathbf{x}_{i,j}(\mathbf{M^{\prime}}))\text{,}

(45)

where $1\leq i<a$ .

Attributed to $\mathbf{s}_{i}\neq\mathbf{s}^{\prime}_{i}$ for $a\leq i\leq n/k$ , $\operatorname{f}(\mathbf{x}_{i,j}(\mathbf{M}))$ and $\operatorname{f}(\mathbf{x}_{i,j}(\mathbf{M^{\prime}}))$ follow the uniform distribution over $[0,2^{c}-1]$ , i.d.d (independent and identically distribution).

Appendix B Proof of lemma 1

To simplify the probability $\mathrm{Pr}\left(\mathbf{v}^{L_{a}}{\left(\mathbf{v}^{L_{a}}+2{\mathbf{N}}^{L_{a}}\right)}^{\mathrm{T}}\leq 0\right)$ in (18), we introduce a rotation matrix for the $L_{a}$ -dimensions hyperspace. The rotation matrix is denoted as

\mathbf{A}=\begin{bmatrix}\mathbf{A}_{1}\\ \vdots\\ \mathbf{A}_{L_{a}}\end{bmatrix}\in\mathbb{R}^{L_{a}\times L_{a}}\text{,}

(46)

which satisfies

\mathbf{A}{\left[\mathbf{v}^{L_{a}}\right]}^{\mathrm{T}}={\bigg{[}\left\|\mathbf{v}^{L_{a}}\right\|,\underbrace{0,\cdots,0}_{L_{a}-1}\bigg{]}}^{\mathrm{T}}\text{.}

(47)

As a rotation matrix, $\mathbf{A}$ owns the property that ${\mathbf{A}}^{\mathrm{T}}\mathbf{A}=\mathbf{I}_{L_{a}}$ , which can be used to rewrite the probability as

\begin{split}&\mathrm{Pr}\left(\mathbf{v}^{L_{a}}{\left(\mathbf{v}^{L_{a}}+2{\mathbf{N}}^{L_{a}}\right)}^{\mathrm{T}}\leq 0\right)\\ &=\mathrm{Pr}\left(\mathbf{v}^{L_{a}}\mathbf{I}_{L_{a}}{\left(\mathbf{v}^{L_{a}}+2{\mathbf{N}}^{L_{a}}\right)}^{\mathrm{T}}\leq 0\right)\\ &=\mathrm{Pr}\left(\mathbf{v}^{L_{a}}{\mathbf{A}}^{\mathrm{T}}\mathbf{A}{\left(\mathbf{v}^{L_{a}}+2{\mathbf{N}}^{L_{a}}\right)}^{\mathrm{T}}\leq 0\right)\\ &=\mathrm{Pr}\left({\left[\mathbf{A}{\left[\mathbf{v}^{L_{a}}\right]}^{\mathrm{T}}\right]}^{\mathrm{T}}\left(\mathbf{A}{\left[\mathbf{v}^{L_{a}}\right]}^{\mathrm{T}}+2\mathbf{A}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}\right)\leq 0\right)\text{.}\end{split}

(48)

Applying (46) and (47) in (48) results in

\begin{split}&\mathrm{Pr}\left({\left\|\mathbf{v}^{L_{a}}\right\|}^{2}+2\left\|\mathbf{v}^{L_{a}}\right\|\cdot\mathbf{A}_{1}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}\leq 0\right)\\ &=\mathrm{Pr}\left(\mathbf{A}_{1}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}\leq-\frac{\left\|\mathbf{v}^{L_{a}}\right\|}{2}\right)\text{,}\end{split}

(49)

the RHS of which is given by the following equivalent form:

\begin{split}&\mathrm{Pr}\left(\mathbf{A}_{1}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}\leq-\frac{\left\|\mathbf{v}^{L_{a}}\right\|}{2}\right)\\ &=\overbrace{\int\cdots\int}^{L_{a}}_{{}_{\mathbf{A}_{1}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}\leq-\frac{\left\|\mathbf{v}^{L_{a}}\right\|}{2}}}\frac{1}{{\left(\sqrt{2\pi}\sigma\right)}^{L_{a}}}\mathrm{e}^{-\frac{{\left\|\mathbf{N}^{L_{a}}\right\|}^{2}}{2\sigma^{2}}}\prod_{i=a}^{n/k}\prod_{j=1}^{L}\mathrm{d}n_{i,j}\text{.}\end{split}

(50)

In order to further simplify the $L_{a}$ -fold integral above, we introduce another rotation matrix $\mathbf{B}$ , which is denoted as

\mathbf{B}=\begin{bmatrix}\mathbf{B}_{1}\\ \vdots\\ \mathbf{B}_{L_{a}}\end{bmatrix}\in\mathbb{R}^{L_{a}\times L_{a}}\text{,}

(51)

such that

\mathbf{B}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}={\bigg{[}\mathbf{A}_{1}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}},\underbrace{0,\cdots,0}_{L_{a}-1}\bigg{]}}^{\mathrm{T}}\text{,}

(52)

and that

{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}=\mathbf{B}^{\mathrm{T}}{\left[\mathbf{n}^{L_{a}}\right]}^{\mathrm{T}}\text{,}

(53)

where $\mathbf{n}^{L_{a}}$ is the transformed vector composed of $n^{\prime}_{i,j}$ with $a\leq i\leq n/k,1\leq j\leq L$ .

From (52) we can get that

\mathbf{B}_{1}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}=\mathbf{A}_{1}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}\text{.}

(54)

Substitute (53) into (54), we have that

		$\displaystyle\mathbf{A}_{1}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}=\mathbf{B}_{1}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}$
		$\displaystyle=\mathbf{B}_{1}\mathbf{B}^{\mathrm{T}}{\left[\mathbf{n}^{L_{a}}\right]}^{\mathrm{T}}$
		$\displaystyle=\begin{bmatrix}\mathbf{B}_{1}\mathbf{B}_{1}^{\mathrm{T}}&\mathbf{B}_{1}\mathbf{B}_{2}^{\mathrm{T}}&\cdots&\mathbf{B}_{1}\mathbf{B}_{L_{a}}^{\mathrm{T}}\end{bmatrix}{\left[\mathbf{n}^{L_{a}}\right]}^{\mathrm{T}}$
		$\displaystyle\overset{(c)}{=}\left[1,\underbrace{0,\cdots,0}_{L_{a}-1}\right]{\left[\mathbf{n}^{L_{a}}\right]}^{\mathrm{T}}=n^{\prime}_{a,1}\text{,}$		(55)

where (c) is obtained from the property that rotation matrix fulfills $\mathbf{B}{\mathbf{B}}^{\mathrm{T}}=\mathbf{I}_{L_{a}}$ .

From (53) we can also derive that

\begin{split}{\left\|\mathbf{N}^{L_{a}}\right\|}^{2}&={\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}\mathbf{N}^{L_{a}}\\ &=\mathbf{n}^{L_{a}}\mathbf{B}\mathbf{B}^{\mathrm{T}}{\left[\mathbf{n}^{L_{a}}\right]}^{\mathrm{T}}\overset{(c)}{=}{\left\|\mathbf{n}^{L_{a}}\right\|}^{2}\text{,}\end{split}

(56)

where (c) establishes by adopting $\mathbf{B}{\mathbf{B}}^{\mathrm{T}}=\mathbf{I}_{L_{a}}$ .

Together with (B) and (56), (50) can be rewritten as [22]

\small\begin{split}&\overbrace{\int\cdots\int}^{L_{a}}_{\mathbf{A}_{1}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}\leq-\frac{\left\|\mathbf{v}^{L_{a}}\right\|}{2}}\frac{1}{{\left(\sqrt{2\pi}\sigma\right)}^{L_{a}}}\mathrm{e}^{-\frac{{\left\|\mathbf{N}^{L_{a}}\right\|}^{2}}{2\sigma^{2}}}\prod_{i=a}^{n/k}\prod_{j=1}^{L}\mathrm{d}n_{i,j}\\ &=\overbrace{\int\cdots\int}^{L_{a}}_{n^{\prime}_{a,1}\leq-\frac{\left\|\mathbf{v}^{L_{a}}\right\|}{2}}\frac{1}{{\left(\sqrt{2\pi}\sigma\right)}^{L_{a}}}\mathrm{e}^{-\frac{{\left\|\mathbf{n}^{L_{a}}\right\|}^{2}}{2\sigma^{2}}}\left|\mathbf{J}\left(\mathbf{n}^{L_{a}}\right)\right|\prod_{i=a}^{n/k}\prod_{j=1}^{L}\mathrm{d}n^{\prime}_{i,j}\text{,}\end{split}

(57)

in which $\mathbf{J}\left(\mathbf{n}^{L_{a}}\right)$ is the Jacobi matrix, behaving as

\mathbf{J}\left(\mathbf{n}^{L_{a}}\right)=\begin{bmatrix}\frac{\partial n^{\prime}_{a,1}}{n_{a,1}}&\cdots&\frac{\partial n^{\prime}_{a,1}}{n_{n/k,L}}\\ \vdots&\ddots&\vdots\\ \frac{\partial n^{\prime}_{n/k,L}}{n_{a,1}}&\cdots&\frac{\partial n^{\prime}_{n/k,L}}{n_{n/k,L}}\end{bmatrix}\text{.}

(58)

Since ${\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}=\mathbf{B}^{\mathrm{T}}{\left[\mathbf{n}^{L_{a}}\right]}^{\mathrm{T}}$ , we get ${\left[\mathbf{n}^{L_{a}}\right]}^{\mathrm{T}}=\mathbf{B}{\left[\mathbf{N}^{L_{a}}\right]}^{\mathrm{T}}$ , therefore the Jacobi matrix behaves as

\mathbf{J}\left(\mathbf{n}^{L_{a}}\right)=\mathbf{B}\text{.}

(59)

Recalling that $\mathbf{B}{\mathbf{B}}^{\mathrm{T}}=\mathbf{I}_{L_{a}}$ , we have

\begin{split}\left|\mathbf{J}\left(\mathbf{n}^{L_{a}}\right)\right|&=\sqrt{{\left|\mathbf{J}\left(\mathbf{n}^{L_{a}}\right)\right|}^{2}}\\ &=\sqrt{{\left|\mathbf{B}\right|}^{2}}=\sqrt{\left|\mathbf{B}{\mathbf{B}}^{\mathrm{T}}\right|}=1\text{.}\end{split}

(60)

Then, by substituting (60) into (57), we could verify that

\small\begin{split}&\overbrace{\int\cdots\int}^{L_{a}}_{n^{\prime}_{a,1}\leq-\frac{\left\|\mathbf{v}^{L_{a}}\right\|}{2}}\frac{1}{{\left(\sqrt{2\pi}\sigma\right)}^{L_{a}}}\mathrm{e}^{-\frac{{\left\|\mathbf{n}^{L_{a}}\right\|}^{2}}{2\sigma^{2}}}\left|\mathbf{J}\left(\mathbf{n}^{L_{a}}\right)\right|\prod_{i=a}^{n/k}\prod_{j=1}^{L}\mathrm{d}n^{\prime}_{i,j}\\ &=\overbrace{\int\cdots\int}^{L_{a}}_{n^{\prime}_{a,1}\leq-\frac{\left\|\mathbf{v}^{L_{a}}\right\|}{2}}\frac{1}{{\left(\sqrt{2\pi}\sigma\right)}^{L_{a}}}\mathrm{e}^{-\frac{{\left\|\mathbf{n}^{L_{a}}\right\|}^{2}}{2\sigma^{2}}}\prod_{i=a}^{n/k}\prod_{j=1}^{L}\mathrm{d}n^{\prime}_{i,j}\\ &=\int_{-\infty}^{-\frac{\left\|\mathbf{v}^{L_{a}}\right\|}{2}}\frac{1}{{\sqrt{2\pi}\sigma}}\mathrm{e}^{-\frac{{\left(n^{\prime}_{a,1}\right)}^{2}}{2\sigma^{2}}}\mathrm{d}n^{\prime}_{a,1}=Q\left(\frac{\left\|\mathbf{v}^{L_{a}}\right\|}{2\sigma}\right)\text{.}\end{split}

(61)

Appendix C Proof of Lemma 2

The central problem is to solve out the integral of $h$ in the RHS of (26). Recall that $h$ follows Rayleigh distribution, whose PDF is given as

g_{{}_{1}}\left(h\right)=\frac{2h}{\Omega}\mathrm{exp}\left(\frac{-h^{2}}{\Omega}\right)\text{.}

(62)

Insert (62) into the RHS of (26), the integral is transformed as

\begin{split}&\int_{h}{\mathrm{exp}}{\left(-\frac{{h^{2}}{u^{2}}}{{8}{\sigma^{2}}{\sin^{2}}\theta}\right)}g_{{}_{1}}(h)\mathrm{d}h\\ &=\int_{0}^{+\infty}{\mathrm{exp}}{\left(-\frac{{h^{2}}{u^{2}}}{{8}{\sigma^{2}}{\sin^{2}}\theta}\right)}\cdot\frac{2h}{\Omega}\mathrm{exp}\left(\frac{-h^{2}}{\Omega}\right)\mathrm{d}h\\ &\xlongequal{z=\frac{u^{2}}{8{{\sigma}^{2}}{{\sin}^{2}}\theta}}\frac{1}{\Omega}\int_{0}^{+\infty}\mathrm{exp}\left[-\left(z+\frac{1}{\Omega}\right){h^{2}}\right]\mathrm{d}{h^{2}}\\ &=\frac{1}{z\Omega+1}=\frac{8{\sigma^{2}}{\sin^{2}}\theta}{{\Omega}u^{2}+8{\sigma^{2}}{\sin^{2}}\theta}\text{,}\end{split}

(63)

with which the RHS of (26) becomes

\begin{split}&\sum_{u}p_{{}_{U}}(u)\int_{h}{\mathrm{exp}}{\left(-\frac{{h^{2}}{u^{2}}}{{8}{\sigma^{2}}{\sin^{2}}\theta}\right)}g_{1}(h)\mathrm{d}h\\ &=\sum_{u}p_{{}_{U}}(u)\cdot\frac{8{\sigma^{2}}{\sin^{2}}\theta}{{\Omega}u^{2}+8{\sigma^{2}}{\sin^{2}}\theta}\text{.}\end{split}

(64)

Recall that $U=U_{a,1}=\operatorname{f}(\mathbf{x}_{a,1}(\mathbf{M}))-\operatorname{f}(\mathbf{x}_{a,1}(\mathbf{M^{\prime}}))$ . Appendix A draws the conclusion that both $\operatorname{f}(\mathbf{x}_{a,1}(\mathbf{M}))$ and $\operatorname{f}(\mathbf{x}_{a,1}(\mathbf{M^{\prime}}))$ follow the uniform distribution over $[0,2^{c}-1]$ , i.d.d. As a result, (64) extends to

\begin{split}&\sum_{u}p_{{}_{U}}(u)\cdot\frac{8{\sigma^{2}}{\sin^{2}}\theta}{{\Omega}u^{2}+8{\sigma^{2}}{\sin^{2}}\theta}\\ &\xlongequal[Y=\operatorname{f}(\mathbf{x}_{a,1}(\mathbf{M^{\prime}}))]{X=\operatorname{f}(\mathbf{x}_{a,1}(\mathbf{M}))}\sum_{i\in\Psi}\sum_{j\in\Psi}p_{{}_{X}}(i)p_{{}_{Y}}(j)\frac{8{\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8{\sigma}^{2}{\sin}^{2}{\theta}}\\ &=\sum_{i\in\Psi}\sum_{j\in\Psi}2^{-2c}\frac{8{\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8{\sigma}^{2}{\sin}^{2}{\theta}}\text{.}\end{split}

(65)

Appendix D Proof Of Monotony

\small\mathcal{F}_{\text{Rayleigh}}(\theta\text{;}\sigma\text{,}L_{a})={\left(\sum_{i\in\Psi}\sum_{j\in\Psi}2^{-2c}\frac{8{\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8{\sigma}^{2}{\sin}^{2}{\theta}}\right)}^{L_{a}}\text{.}

(66)

The monotony of $\mathcal{F}_{\text{Rayleigh}}(\theta\text{;}\sigma\text{,}L_{a})$ equals to the monotony of

F_{\text{Rayleigh}}(\theta)\triangleq\frac{8{\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8{\sigma}^{2}{\sin}^{2}{\theta}}\text{,}

(67)

where $\theta\in[0,\frac{\pi}{2}]$ .

Denoting $8{\sigma}^{2}=b$ and ${\Omega}(i-j)^{2}=k$ , the derivative of $F(\theta)$ is given by

\frac{\mathrm{d}F_{\text{Rayleigh}}(\theta)}{\mathrm{d}\theta}=2kb\frac{\mathrm{sin}\theta\mathrm{cos}\theta}{{(k+\mathrm{sin}^{2}\theta)}^{2}}\geq 0\text{,}

(68)

which indicates the monotonically increasing property of function $F_{\text{Rayleigh}}(\theta)$ .

As a consequence, $\mathcal{F}_{\text{Rayleigh}}(\theta\text{;}\sigma\text{,}L_{a})$ is a monotonically increasing function.

\begin{split}&\mathcal{F}_{\text{Nakagami}}(\theta\text{;}\sigma\text{,}L_{a})\\ &={\left(\sum_{i\in\Psi}\sum_{j\in\Psi}2^{-2c}{\left(\frac{8m{\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8m{\sigma}^{2}{\sin}^{2}{\theta}}\right)}^{m}\right)}^{L_{a}}\text{.}\end{split}

(69)

Because $m\geq 0.5$ , the monotony of $\mathcal{F}_{\text{Nakagami}}(\theta\text{;}\sigma\text{,}L_{a})$ equals to the monotony of

F_{\text{Nakagami}}(\theta)\triangleq\frac{8m{\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8m{\sigma}^{2}{\sin}^{2}{\theta}}\textbf{,}

(70)

where $\theta\in[0,\frac{\pi}{2}]$ .

Similar to the proof for $\mathcal{F}_{\text{Rayleigh}}(\theta\text{;}\sigma\text{,}L_{a})$ , we denote that $8m{\sigma}^{2}=b$ and ${\Omega}(i-j)^{2}=k$ . Since the result is the same as (68), $\mathcal{F}_{\text{Nakagami}}(\theta\text{;}\sigma\text{,}L_{a})$ is also a monotonically increasing function.

\small\begin{split}&\mathcal{F}_{\text{Rician}}(\theta\text{;}\sigma\text{,}L_{a})\\ &=\Bigg{(}\sum_{i\in\Psi}\sum_{j\in\Psi}2^{-2c}\frac{8(K+1){\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8(K+1){\sigma}^{2}{\sin}^{2}{\theta}}\\ &\qquad\cdot{\mathrm{exp}\left(\frac{8K(K+1){\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8(K+1){\sigma}^{2}{\sin}^{2}{\theta}}-K\right)\Bigg{)}}^{L_{a}}\text{,}\end{split}

(71)

Because exponential function is monotonically increasing, the monotony of $\mathcal{F}_{\text{Rician}}(\theta\text{;}\sigma\text{,}L_{a})$ equals to the monotony of

F_{\text{Rician}}(\theta)\triangleq\frac{8(K+1){\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8(K+1){\sigma}^{2}{\sin}^{2}{\theta}}\text{.}

(72)

where $\theta\in[0,\frac{\pi}{2}]$ .

Similar to the proof for $\mathcal{F}_{\text{Rayleigh}}(\theta\text{;}\sigma\text{,}L_{a})$ , we denote $8(K+1){\sigma}^{2}=b$ and ${\Omega}(i-j)^{2}=k$ . As the result is the same as $(\ref{derivation}),\mathcal{F}_{\text{Rician}}(\theta\text{;}\sigma\text{,}L_{a})$ is also a monotonically increasing function.

Appendix E Proof of Theorem 2

For Spinal codes over the Nakagami-m fading channel, the only difference is to replace Rayleigh distribution with Nakagami-m distribution. The PDF Nakagami-m distribution is given by

g_{{}_{2}}(h)=\frac{2m^{m}}{\Gamma(m)\Omega^{m}}h^{2m-1}\text{exp}\left(\frac{-mh^{2}}{\Omega}\right)\text{,}

(73)

where $h$ is the channel fading parameter, $m\geq 0.5$ and the Gamma function is defined as

\Gamma(m)={\int_{0}^{+\infty}}\mathrm{e}^{-t}t^{m-1}\mathrm{d}t\text{.}

(74)

Substitute (73) into the integral of (26) and denote $z=\frac{u^{2}}{8{{\sigma}^{2}}{{\sin}^{2}}\theta}$ , after which the integral of $h$ is transformed as

\begin{split}&\int_{h}{\mathrm{exp}}{\left(-\frac{{h^{2}}{u^{2}}}{{8}{\sigma^{2}}{\sin^{2}}\theta}\right)}g_{{}_{2}}(h)\mathrm{d}h\\ &=\int_{0}^{+\infty}\mathrm{e}^{-{z}{h^{2}}}\cdot\frac{2m^{m}}{\Gamma(m)\Omega^{m}}h^{2m-1}\mathrm{e}^{-\frac{mh^{2}}{\Omega}}\mathrm{d}h\\ &\xlongequal[h=\sqrt{\frac{t}{z+\frac{m}{\Omega}}}]{t=\left(z+\frac{m}{\Omega}\right)h^{2}}\frac{m^{m}}{\Gamma(m){(z\Omega+m)}^{m}}{\int_{0}^{+\infty}}\mathrm{e}^{-t}t^{m-1}\mathrm{d}t\\ &=\frac{m^{m}}{{(z\Omega+m)}^{m}}\text{.}\end{split}

(75)

As mentioned above, $z=\frac{u^{2}}{8{{\sigma}^{2}}{{\sin}^{2}}\theta}$ , substitute $z$ into (LABEL:eq48):

\begin{split}\frac{m^{m}}{{(z\Omega+m)}^{m}}={\left(\frac{8m{\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}u^{2}+8m{\sigma}^{2}{\sin}^{2}{\theta}}\right)}^{m}\text{.}\end{split}

(76)

Then the process is similar to Theorem 1, by denoting that

\begin{split}&\mathcal{F}_{\text{Nakagami}}(\theta\text{;}\sigma\text{,}L_{a})\\ &={\left(\sum_{i\in\Psi}\sum_{j\in\Psi}2^{-2c}{\left(\frac{8m{\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8m{\sigma}^{2}{\sin}^{2}{\theta}}\right)}^{m}\right)}^{L_{a}}\text{,}\end{split}

(77)

which is monotonically increasing proved in Appendix D, and that

\mathscr{F}_{\text{Nakagami}}\left(L_{a}\text{,}\sigma\right)=\sum_{r=1}^{N}b_{r}\mathcal{F}_{\text{Nakagami}}(\theta_{r}\text{;}\sigma\text{,}L_{a})\text{,}

(78)

we can get the explicit bound.

Appendix F Proof of Theorem 3

For Spinal codes over the Rician fading channel, the only difference is to replace Rayleigh distribution with Rician distribution. The PDF of Rician distribution is given by

\small g_{{}_{3}}(h)=\frac{2(K+1)h}{{\Omega}\,{\mathrm{exp}\left(K+\frac{(K+1){h^{2}}}{\Omega}\right)}}I_{0}\left(2\sqrt{\frac{K(K+1)}{\Omega}}h\right)\text{,}

(79)

where $h$ is the channel fading parameter, and $I_{0}(\cdot)$ is the modified Bessel function of the first kind with order zero, given by

I_{0}(x)=\sum_{k=0}^{+\infty}\frac{{(x^{2}/4)}^{k}}{k!\Gamma(k+1)}\text{.}

(80)

Substitute (79) into (26) and denote $z=\frac{u^{2}}{8{{\sigma}^{2}}{{\sin}^{2}}\theta}$ , then the integral of $h$ is transformed as

\small\begin{split}&\int_{h}{\mathrm{exp}}{\left(-\frac{{h^{2}}{u^{2}}}{{8}{\sigma^{2}}{\sin^{2}}\theta}\right)}g_{{}_{3}}(h)\mathrm{d}h=\int_{0}^{+\infty}\mathrm{e}^{-{z}{h^{2}}}g_{{}_{3}}(h)\mathrm{d}h\\ &=\frac{2(K+1)}{{\Omega}\mathrm{e}^{K}}{\int_{0}^{+\infty}}{h\mathrm{e}^{-\left(\frac{K+1}{\Omega}+z\right)h^{2}}I_{0}\left(2\sqrt{\frac{K(K+1)}{\Omega}}h\right)\mathrm{d}h}\\ &=\frac{2}{\mathrm{e}^{K}}\sum_{m=0}^{+\infty}\frac{K^{m}{(K+1)}^{m+1}}{m!\Gamma(m+1)\Omega^{m+1}}{\int_{0}^{+\infty}}h^{2m+1}\mathrm{e}^{-\left(\frac{K+1}{\Omega}+z\right)h^{2}}\mathrm{d}h\text{.}\end{split}

(81)

Let $t=\left(z+\frac{K+1}{\Omega}\right)h^{2}$ , $h=\sqrt{\frac{t}{z+\frac{K+1}{\Omega}}}$ , we have

\begin{split}&{\int_{0}^{+\infty}}h^{2m+1}\mathrm{e}^{-\left(\frac{K+1}{\Omega}+z\right)h^{2}}\mathrm{d}h\\ &=\int_{0}^{+\infty}\mathrm{e}^{-t}\cdot\frac{t^{m}}{2{\left(z+\frac{K+1}{\Omega}\right)}^{m+1}}\mathrm{d}t\\ &=\frac{\Gamma(m+1)}{2{\left(z+\frac{K+1}{\Omega}\right)}^{m+1}}\text{.}\end{split}

(82)

With (LABEL:eq59) in hand, (LABEL:eq58) can be rewritten as

\begin{split}&\int_{h}{\mathrm{exp}}{\left(-\frac{{h^{2}}{u^{2}}}{{8}{\sigma^{2}}{\sin^{2}}\theta}\right)}g_{{}_{3}}(h)\mathrm{d}h\\ &=\frac{1}{K\mathrm{e}^{K}}\cdot\frac{K(K+1)}{{\Omega}z+K+1}\cdot\sum_{m=0}^{+\infty}\frac{1}{m!}{\left(\frac{K(K+1)}{{\Omega}z+K+1}\right)}^{m}\\ &=\frac{1}{K\mathrm{e}^{K}}\cdot\frac{K(K+1)}{{\Omega}z+K+1}\cdot\mathrm{exp}\left(\frac{K(K+1)}{{\Omega}z+K+1}\right)\text{.}\end{split}

(83)

Now that $z=\frac{u^{2}}{8{{\sigma}^{2}}{{\sin}^{2}}\theta}$ , (83) comes into

\small\begin{split}&\frac{1}{K\mathrm{e}^{K}}\cdot\frac{K(K+1)}{{\Omega}z+K+1}\cdot\mathrm{exp}\left(\frac{K(K+1)}{{\Omega}z+K+1}\right)\\ &=\frac{8\mathrm{e}^{-K}(K+1){\sigma^{2}}{\sin^{2}}\theta}{{\Omega}u^{2}+8(K+1){\sigma^{2}}{\sin^{2}}\theta}\mathrm{exp}\left(\frac{8K(K+1){\sigma^{2}}{\sin^{2}}\theta}{{\Omega}u^{2}+8(K+1){\sigma^{2}}{\sin^{2}}\theta}\right)\text{.}\end{split}

(84)

Then the process is similar to Theorem 1. By denoting that

\small\begin{split}&\mathcal{F}_{\text{Rician}}(\theta\text{;}\sigma\text{,}L_{a})\\ &=\Bigg{(}\sum_{i\in\Psi}\sum_{j\in\Psi}2^{-2c}\frac{8(K+1){\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8(K+1){\sigma}^{2}{\sin}^{2}{\theta}}\\ &\qquad\cdot{\mathrm{exp}\left(\frac{8K(K+1){\sigma}^{2}{\sin}^{2}{\theta}}{{\Omega}(i-j)^{2}+8(K+1){\sigma}^{2}{\sin}^{2}{\theta}}-K\right)\Bigg{)}}^{L_{a}}\text{,}\end{split}

(85)

which is monotonically increasing proved in Appendix D, and that

\mathscr{F}_{\text{Rician}}\left(L_{a}\text{,}\sigma\right)=\sum_{r=1}^{N}b_{r}\mathcal{F}_{\text{Rician}}(\theta_{r}\text{;}\sigma\text{,}L_{a})\text{,}

(86)

we can get the explicit bound.