RS Codes and Optimized Distributed RS-Coded Relay Cooperative Communications: Code Constructions and Performance Analysis

Abstract

This chapter introduces the Reed-Solomon (RS) codes and the distributed RS-coded cooperative system over the Rayleigh fading channel, where the encoding and decoding procedures of the RS codes are elaborated. Besides, two optimized selection approaches, i.e., the exhaustive search approach and partial search approach, are employed in the relay to obtain a resultant code at the destination with better weight distribution. Moreover, the two joint decoding algorithms, namely naive and smart algorithms, are presented that further improve the overall average bit error rate (BER) performance of the cooperative scheme. Also, the performance analysis of the distributed RS-coded cooperative scheme is provided in detailed.

1. Introduction

Fifth-generation (5G) communication systems may accommodate the traffic generated by a variety of wireless network types such as Device-to-Device (D2D) and sensor networks. Hence, it is reasonable to consider the short-information-transmission scenario. Generally, one of the most important aspects of transmission is to combat the signal fading over a wireless channel. Spatial diversity has proven to be the most effective method for mitigating the impacts of fading [1]. However, many mobile communication devices are unable to leverage spatial diversity techniques owing to size, power, and hardware complexity. Therefore, coded cooperative diversity with the aid of the relay was proposed to provide uplink diversity via single antenna sharing. Factually, various distributed linear block codes have been employed in the coded cooperation such as the distributed turbo codes (DTC) [2], distributed low-density parity-check codes (D-LDPC) [3], and polar codes [4]. Nevertheless, for the non-binary codes with short information sizes in coded cooperation, the literature has not been thoroughly investigated. Note that Reed-Solomon (RS) codes are a well-known class of non-binary codes with low encoding and decoding complexity. Furthermore, as a member of maximum distance separatable (MDS) codes, short-to-medium-length RS codes perform well in correcting random burst errors. Hence, RS-coded relay cooperation is considered a promising exploration to support short information transmission [5]. In addition, the distinct information selection in the relay may result in a different resultant code at the destination, which will influence the performance of the overall transmission. Hence, the optimized selection approaches [6] at the relay are also introduced in this chapter.

The remaining contexts of this chapter are summarized as follows. Section 2 provides a brief introduction to the BCH codes and RS codes. The general distributed RS-coded cooperative system is presented in Section 3. Section 4 exhibits the two optimized selection approaches and the corresponding examples. The joint decoding algorithms and the performance analysis are elaborated in Section 5. Section 6 concludes this chapter.

2. BCH codes and RS codes

2.1 BCH codes

Bose-Chaudhuri-Hocquenghem (BCH) codes are a kind of cyclic codes that can effectively correct random errors [7], which can be classified into binary BCH codes and non-binary BCH codes according to the different fields from which symbols are taken. Given any finite field $\mathrm{GF}\left(\mathrm{q}\right)$ and its extension field $\mathrm{GF}\left(q^{\mathrm{m}}\right)$, where $q$ is a prime or a power of a prime and $m$ is a positive integer, let $\alpha$ be a non-zero and non-one element of $\mathrm{GF}\left(q^{\mathrm{m}}\right)$. If the generator polynomial $g\left(x\right)\in F\left[x\right]\left(F\in \mathit{GF}\left(q\right)\right)$ is the lowest-degree-polynomial with consecutive roots $\left\{\alpha ,{\alpha }^2,\cdots ,{\alpha }^{2t}\right\}$, then a cyclic code generated from this polynomial $g\left(x\right)$ is called a BCH code.

Assume that ${\phi }_i\left(x\right)$ denotes the minimum polynomial of ${\alpha }^i\left(1\le i\le 2t\right)$ and $e^i$ represents the order of ${\alpha }^i$. Therefore, the generator polynomial $g\left(x\right)$ and the code length $n$ of BCH code are provided as,

$$g\left(x\right)=\mathit{LCM}\left\{{\phi }_1\left(x\right),{\phi }_2\left(x\right),\dots ,{\phi }_i\left(x\right)\right\},n=\mathit{LCM}\left\{e_1,e_2,\dots ,e_{2}t\right\},$$E1

where $\mathit{LCM}$ denotes the least common multiple. In particular, when $q=2$, it is the binary BCH code. Also, if $\alpha$ is the primitive element in $\mathrm{GF}\left(q^{\mathrm{m}}\right)$, it is a primitive BCH code of code length $n=q^m-1$. Otherwise, the BCH code is non-primitive where n is the factor of $q^m-1$. Consider a BCH code of length $n$, its parity check matrix is provided as [8],

$$H=\left[\begin{array}{cccccc}1& \alpha & {\alpha }^2& {\alpha }^3& \cdots & {\alpha }^{n-1}\\ 1& {\alpha }^2& {\left({\alpha }^2\right)}^2& {\left({\alpha }^2\right)}^3& \cdots & {\left({\alpha }^2\right)}^{n-1}\\ 1& {\alpha }^3& {\left({\alpha }^3\right)}^2& {\left({\alpha }^3\right)}^3& \cdots & {\left({\alpha }^3\right)}^{n-1}\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮\\ 1& {\alpha }^{2t}& {\left({\alpha }^{2t}\right)}^2& {\left({\alpha }^{2t}\right)}^3& \cdots & {\left({\alpha }^{2t}\right)}^{n-1}\end{array}\right].$$E2

Then, the minimum distance of the $t$-error-correcting BCH codes is at least $2t+1$. The proof process can be referred to [9]. This lower bound on the minimum distance is called the BCH bound.

2.2 RS codes: encoding and decoding

The most important subclass of $q$-ary BCH codes is the RS codes, a particular subclass of $q$-ary BCH codes for which $m=1$. The efficient encoding and hard-decision decoding algorithms of RS codes as well as their improved capacity to rectify random burst errors have made them extensively applied for error control in both storage systems and digital communication [9]. The following describes the specific characteristic, encoding, and decoding processes of the RS codes.

2.2.1 Free distance of RS codes

Suppose that $\alpha$ is a primitive element in $\mathit{GF}\left(q\right)$. The generator polynomial g(x) of $t$-error-correcting $\left(n,k\right)$ RS code has $\left\{\alpha ,{\alpha }^2,\cdots ,{\alpha }^{2t}\right\}$ as all its roots, where all symbols of RS codes are chosen from $\mathit{GF}\left(q\right)$, $n$ and $k$ denote the code length and length of information sequence, respectively. Therefore, the minimum polynomial ${\phi }_i\left(x\right)$ corresponding to each ${\alpha }^i$ is $x-{\alpha }^i$. And $g\left(x\right)$ can be obtained from Eq. (1) given as,

$$\begin{array}{ll}g\left(x\right)& =\left(x-\alpha \right)\left(x-{\alpha }^2\right)\cdots \left(x-{\alpha }^{2t}\right)\\ & =g_0+g_{1}x+g_2{x}^2+\cdots +g_{2t-1}{x}^{2t-1}+x^{2t},\end{array}$$E3

where $g_i\in \mathit{GF}\left(q\right)$ for $0<i<2t$. Since the all roots of $x^{q-1}-1$ are $\alpha ,{\alpha }^2,\dots ,{\alpha }^{2t}$, $g\left(x\right)$ can divides $x^{q-1}-1$. Thus, $g\left(x\right)$ generates a $q$-ary RS code of length $n=q-1$ with exactly $2t$ parity-check symbols, which means $n-k=2t$.

From the BCH bound and the Eq. (3) where the code polynomial comprises $2t+1$ terms. Hence, there cannot be a zero for any of the coefficients in $g\left(x\right)$ can be zero. Otherwise, the resultant codeword would have a weight less than $2t+1$, which would be in conflict with the BCH bound on the minimum distance. As a result, the $g\left(x\right)$ corresponds to a codeword with a weight of precisely $2t+1$. It follows that the minimum distance of the $t$-error-correcting RS code generated by Eq. (3) is determined as exactly $2t+1$, i.e., $d_{\mathit{min}}=2t+1$. In addition, the minimum distance of the RS code is more than the number of its parity-check symbols. Therefore, RS codes are a prominent subgroup of the maximum distance separable (MDS) codes [10]. In this chapter, we simply consider $q=2$.

Example 1. Let $\alpha$ is a primitive element in $\mathit{GF}\left(2^4\right)$ constructed based on the primitive polynomial $1+x+x^4$ shown in Table 1. Consider the double-error-correcting RS codes with the symbols from $\mathit{GF}\left(2^4\right)$. The generator polynomial $g\left(x\right)$ of this code has $\alpha ,{\alpha }^2,{\alpha }^3,{\alpha }^4$ as all its roots. Hence, $g\left(x\right)$ is acquired as,

Field elements	Vector	Field elementst	Vector
0	$\left[0000\right]$	${\alpha }^7=1+\alpha +{\alpha }^3$	$\left[1101\right]$
	$\left[1000\right]$	${\alpha }^8=1+{\alpha }^2$	$\left[1010\right]$
$\alpha$	$\left[0100\right]$	${\alpha }^9=\alpha +{\alpha }^3$	$\left[0101\right]$
${\alpha }^2$	$\left[0010\right]$	${\alpha }^{10}=1+\alpha +{\alpha }^2$	$\left[1110\right]$
${\alpha }^3$	$\left[0001\right]$	${\alpha }^{11}=\alpha +{\alpha }^2+{\alpha }^3$	$\left[0111\right]$
${\alpha }^4=1+\alpha$	$\left[1100\right]$	${\alpha }^{12}=1+\alpha +{\alpha }^2+{\alpha }^3$	$\left[1111\right]$
${\alpha }^5=\alpha +{\alpha }^2$	$\left[0110\right]$	${\alpha }^{13}=1+{\alpha }^2+{\alpha }^3$	$\left[1011\right]$
${\alpha }^6={\alpha }^2+{\alpha }^3$	$\left[0011\right]$	${\alpha }^{14}=1+{\alpha }^3$	$\left[1001\right]$

Table 1.

Galois field $\mathit{GF}\left(2^4\right)$ with the primitive polynomial $1+\alpha +{\alpha }^4=0$.

$$\begin{array}{ll}g\left(x\right)& =\left(x-\alpha \right)\left(x-{\alpha }^2\right)\left(x-{\alpha }^3\right)\left(x-{\alpha }^4\right)\\ & ={\alpha }^{10}+{\alpha }^{3}x+{\alpha }^6{x}^2+{\alpha }^{13}{x}^3+x^4,\end{array}$$E4

The code is (15,11) RS code over the $\mathit{GF}\left(2^4\right)$ that can correct two errors. And, the minimum distance of this RS code is 5.

The end of Example 1.

2.2.2 Encoding of RS codes

Given the generator polynomial $g\left(x\right)$ illustrated in Eq. (3), the polynomial $c\left(x\right)$ of the codeword $\mathbf{c}$ of the RS code is generated as,

$$c\left(x\right)=g\left(x\right)u\left(x\right),$$E5

where $u\left(x\right)=u_0+u_{1}x+u_2{x}^2+\cdots +u_{k-1}{x}^{k-1}$ is the polynomial of the information sequence m, $u_i\in \mathrm{GF}\left(2^m\right)$ for $i=0,1,\dots ,k-1$. Moreover, the polynomial $c\left(x\right)$ of systematic codeword $\mathbf{c}$ is obtained as,

$$c\left(x\right)=x^{n-k}u\left(x\right)+p\left(x\right),$$E6

where $p\left(x\right)=p_0+p_{1}x+p_2{x}^2+\cdots +p_{n-k-1}{x}^{n-k-1}\left(p_i\in \mathrm{GF}\left(2^m\right),i=0,1,\dots ,n-k-1\right)$ denotes the parity-check polynomial which can be computed by the polynomial division as,

$$p\left(x\right)=x^{n-k}u\left(x\right)/g\left(x\right).$$E7

2.2.3 Decoding of RS codes

Consider a $\left(n,k\right)$ RS code with the symbols from $\mathrm{GF}\left(q\right)$. Suppose that a codeword $c\left(x\right)=c_0+c_{1}x+\cdots +c_{n-1}{x}^{n-1}$ is transmitted, and the transmission error result in the following received vector $r\left(x\right)=r_0+r_{1}x+\cdots +r_{n-1}{x}^{n-1}$. Let $e\left(x\right)=e_0+e_{1}x+\cdots +e_{n-1}{x}^{n-1}$ be the error pattern which have relationship with $c\left(x\right)$ and $r\left(x\right)$ as,

$$e\left(x\right)=r\left(x\right)-c\left(x\right).$$E8

Assume that error pattern $e\left(x\right)$ contains $\tau$ errors (nonzero components) at locations $x^{j_1},x^{j_2},\dots ,x^{j_{\tau }}$, where $0\le j_1<j_2<\cdots <j_{\tau }\le n-1$. Then,

$$e\left(x\right)=e_{j_1}{x}^{j_1}+e_{j_2}{x}^{j_2}+\cdots +e_{j_{\tau }}{x}^{j_{\tau }}$$E9

where $x^{j_i}$ denotes error-location and $e_{j_i}$ is error values, $1\le i\le \tau$. And the specific decoding steps are given as follows,

Step 1. Compute the syndrome. The syndrome is a $2t$-tuple vector as,

$$\begin{array}{ll}\mathbf{S}& =\left(S_1,S_2,\dots ,S_{2t}\right)=\mathbf{r}\cdot H^T\\ & =\left[r_0,r_1,\dots ,r_{n-1}\right]\cdot \left[\begin{array}{ccccc}1& 1& 1& \cdots & 1\\ \alpha & {\alpha }^2& {\alpha }^3& \cdots & {\alpha }^{2t}\\ {\alpha }^2& {\left({\alpha }^2\right)}^2& {\left({\alpha }^3\right)}^2& \cdots & {\left({\alpha }^{2t}\right)}^2\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ {\alpha }^{n-1}& {\left({\alpha }^2\right)}^{n-1}& {\left({\alpha }^3\right)}^{n-1}& \cdots & {\left({\alpha }^{2t}\right)}^{n-1}\end{array}\right].\end{array}$$E10

Evidently, $S_i=r\left({\alpha }^i\right)\left(1\le i\le 2t\right)$.

Step 2. Determined the error-location polynomial $\sigma \left(x\right)$ and the error value evaluator $Z_0\left(x\right)$ based on Euclidean algorithm.

(1) From Eq. (8) and (10), we obtain,

$$S_i=r\left({\alpha }^i\right)=e\left({\alpha }^i\right)+c\left({\alpha }^i\right)=e\left({\alpha }^i\right).$$E11

From Eq. (9), all $2t$ syndromes are obtained,

$$\begin{array}{lllll}{S}_1& =e_{j_1}{\left({\alpha }^{j_1}\right)}^1+e_{j_2}{\left({\alpha }^{j_2}\right)}^1+\cdots +e_{j_{\tau }}{\left({\alpha }^{j_{\tau }}\right)}^1,& & & \\ S_2& =e_{j_1}{\left({\alpha }^{j_1}\right)}^2+e_{j_2}{\left({\alpha }^{j_2}\right)}^2+\cdots +e_{j_{\tau }}{\left({\alpha }^{j_{\tau }}\right)}^2,& & & \\ & ⋮& & & \\ S_{2t}& =e_{j_1}{\left({\alpha }^{j_1}\right)}^{2t}+e_{j_2}{\left({\alpha }^{j_2}\right)}^{2t}+\cdots +e_{j_{\tau }}{\left({\alpha }^{j_{\tau }}\right)}^{2t},& & & \end{array}$$E12

where ${\alpha }^{j_i}$ is called the error location number and $e_{j_i}$ is the error value $\left(1\le i\le 2t\right)$. Let ${\beta }_i\triangleq {\alpha }^{j_1},{\delta }_i\triangleq e_{j_i}$, Eq. (12) can be simplified as,

$$\begin{array}{lllll}{S}_1& ={\delta }_1{\beta }_1+{\delta }_2{\beta }_2+\cdots +{\delta }_{\tau }{\beta }_{\tau },& & & \\ S_2& ={\delta }_1{\beta }_1^2+{\delta }_2{\beta }_2^2+\cdots +{\delta }_{\tau }{\beta }_{\tau }^2,& & & \\ & ⋮& & & \\ S_{2t}& ={\delta }_1{\beta }_1^{2t}+{\delta }_2{\beta }_2^{2t}+\cdots +{\delta }_{\tau }{\beta }_{\tau }^{2t}.& & & \end{array}$$E13

(2) To solve these $2t$ equations, the error-location polynomial is firstly defined as:

$$\begin{array}{ll}\sigma \left(x\right)& =\left(1-{\beta }_{1}x\right)\left(1-{\beta }_{2}x\right)\cdots \left(1-{\beta }_{\tau }x\right)\\ & ={\sigma }_0+{\sigma }_{1}x+{\sigma }_2{x}^2+\cdots +{\sigma }_{\tau }{x}^{\tau }.\end{array}$$E14

The roots of $\sigma \left(x\right)$ are ${\beta }_1^{-1},{\beta }_2^{-1},\dots ,{\beta }_{\tau }^{-1}$, which are the inverses of the error-location numbers [11].

(3) Define error-value evaluator $Z_0\left(x\right)$. Firstly, the syndrome polynomial $S\left(x\right)$ is defined as,

$$S\left(x\right)\triangleq S_1+S_{2}x+S_3{x}^2+\cdots +S_{2t}{x}^{2t-1}+S_{2t+1}{x}^{2t}+\cdots =\sum _{j=1}^{\infty }{S}_j{x}^{j-1}.$$E15

Then, $S\left(x\right)$ can be further simplified as,

$$S\left(x\right)=\sum _{j=1}^{\infty }{x}^{j-1}\sum _{l=1}^{\tau }{\delta }_l{\beta }_l^j=\sum _{l=1}^{\tau }{\delta }_l{\beta }_l\sum _{j=1}^{\infty }{\left(x{\delta }_l\right)}^{j-1}.$$E16

Since $\frac{1}{1-{\beta }_{l}x}={\sum }_{j=1}^{\infty }{\left(x{\beta }_l\right)}^{j-1}$, Thus Eq. (16) comes to,

$$S\left(x\right)=\sum _{l=1}^{\tau }\frac{{\delta }_l{\beta }_l}{1-{\beta }_{l}x}.$$E17

Then, we have,

$$\begin{array}{ll}& \sigma \left(x\right)S\left(x\right)=\left(1+{\sigma }_{1}x+\cdots +{\sigma }_{\tau }{x}^{\tau }\right)\left(S_1+S_{2}x+S_3{x}^2+\cdots \right)=S_1+\left(S_2+{\sigma }_1{S}_1\right)\\ & +\left(S_3+{\sigma }_1{S}_2+{\sigma }_2{S}_1\right)x^2+\cdots +\left(S_{2t}+{\sigma }_1{S}_{2t-1}+{\sigma }_2{S}_{2t-2}+\cdots +{\sigma }_{\tau }{S}_{2t-\tau }\right)x^{2t-1}\\ & +\left(S_{2}t+{\sigma }_1{S}_{2t-1}+{\sigma }_2{S}_{2t-2}+\cdots +{\sigma }_{\tau }{S}_{2t-\tau }\right)x^{2}t+\cdots .\end{array}$$E18

Therefore,

$$\begin{array}{ll}{Z}_0\left(x\right)& \triangleq \left\{\prod _{i=1}^{\tau }\left(1-{\beta }_{i}x\right)\right\}\cdot \left\{\sum _{l=1}^{\tau }\frac{{\delta }_l{\beta }_l}{1-{\beta }_{l}x}\right\}\\ & =\sum _{l=1}^{\tau }\frac{{\delta }_l{\beta }_l}{1-{\beta }_{l}x}\cdot \prod _{i=1}^{\tau }\left(1-{\beta }_{i}x\right)\\ & =\sum _{l=1}^{\tau }{\delta }_l{\beta }_l\cdot \prod _{i=1,i\ne l}^{\tau }\left(1-{\beta }_{i}x\right).\end{array}$$E19

Step 3. Solve the key equation based on the Euclidean algorithm. In the expansion of $\sigma \left(x\right)S\left(x\right)$, only the coefficient of the first $2t$ terms (from $x^0$ to $x^{2t}$) are known. Let $Z_0\left(x\right)={\left[\sigma \left(x\right)S\left(x\right)\right]}_{2t}$ denote the first $2t$ terms of $\sigma \left(x\right)S\left(x\right)$. Then, $\sigma \left(x\right)S\left(x\right)-{\left[\sigma \left(x\right)S\left(x\right)\right]}_{2t}$ is divisible by $x^{2t}$. This simply says that if $\sigma \left(x\right)S\left(x\right)$ is divided by $x^{2t}$, the remainder is $Z_0\left(x\right)$.

Therefore, we obtain,

$$\sigma \left(x\right)S\left(x\right)=Z_0\left(x\right)mod{x}^{2t},$$E20

which is called the key equation in decoding BCH code. Thus, the key equation can be expressed in the following forms:

$$\sigma \left(x\right)S\left(x\right)=Q\left(x\right)x^{2t}+Z_0\left(x\right)\Rightarrow Z_0\left(x\right)=-Q\left(x\right)x^{2t}+\sigma \left(x\right)S\left(x\right).$$E21

Setting,

$$a\left(x\right)=x^{2t},b\left(x\right)=S\left(x\right).$$E22

Then the key equation is exactly in the form given as follows,

$$Z_0\left(x\right)=-Q\left(x\right)a\left(x\right)+\sigma \left(x\right)b\left(x\right).$$E23

Therefore, $\sigma \left(x\right)$ and $Z_0\left(x\right)$ can be found by the Euclidean iterative division algorithm. Let

$$Z_0^{\left(i\right)}\left(x\right)=r_i\left(x\right),{\sigma }^{\left(i\right)}\left(x\right)=g_i\left(x\right),{\gamma }^{\left(i\right)}\left(x\right)=-Q^{\left(i\right)}\left(x\right)=f_i\left(x\right).$$E24

To find $\sigma \left(x\right)$ and $Z_0\left(x\right)$, we carry out the iteration process as follows:

(1) Firstly, the initial conditions are given as,

$$\begin{array}{ll}& Z_0^{\left(-1\right)}\left(x\right)=x^{2t}\left(a\left(x\right)=x^{2t}\right),\\ & Z_0^{\left(0\right)}\left(x\right)=S\left(X\right)\left(b\left(x\right)=S\left(x\right)\right),\\ & {\gamma }^{\left(-1\right)}\left(x\right)={\sigma }^{\left(0\right)}\left(x\right)=1,\\ & {\gamma }^{\left(0\right)}\left(x\right)={\sigma }^{\left(-1\right)}\left(x\right)=0..\end{array}$$E25

(2) Step $i$: at the $i$-th step,

$$\begin{array}{ll}& Z_0^{\left(i-2\right)}\left(x\right)=q_1\left(x\right)Z_0^{\left(i-1\right)}\left(x\right)+Z_0^{\left(i\right)}\left(x\right),\\ \Rightarrow & Z_0^{\left(i\right)}\left(x\right)={\gamma }^{\left(i\right)}\left(x\right)x^{2t}+{\sigma }^{\left(i\right)}\left(x\right)S\left(x\right),\end{array}$$E26

where

$${\sigma }^{\left(i\right)}\left(x\right)={\sigma }^{\left(i-2\right)}\left(x\right)-q_i\left(x\right){\sigma }^{\left(i-1\right)}\left(x\right),{\gamma }^{\left(i\right)}\left(x\right)={\gamma }^{\left(i-2\right)}\left(x\right)-q_i\left(x\right){\gamma }^{\left(i-1\right)}\left(x\right).$$E27

(3) Finally, iteration stops when the iteration reaches a step $\rho$ for which

$$deg{Z}_0^{\left(\rho \right)}\left(x\right)<deg{\sigma }^{\left(\rho \right)}\left(x\right)\le t.$$E28

Therefore, $Z_0\left(x\right)=Z_0^{\left(\rho \right)},\sigma \left(x\right)={\sigma }^{\left(\rho \right)}$ are obtained.

Step 4. Evaluate error location numbers and error values.

(1) Determine error-location numbers ${\alpha }^{j_i}$ from $\sigma \left(x\right)$. The error-location numbers are the inverse of the roots of $\sigma \left(x\right)$.

(2) Determine the error values ${\delta }_l,1\le l\le \tau$ from $Z_0\left(x\right)$ and $\sigma \left(x\right)$. Subsitituting ${\beta }_l^{-1}$ in $Z_0\left(x\right)$, then,

$$\begin{array}{ll}{Z}_0\left({\beta }_l^{-1}\right)& =\sum _{l=1}^{\tau }{\delta }_l{\beta }_l\prod _{i=1,i\ne l}^{\tau }\left(1-{\beta }_i{\beta }_l^{-1}\right)\\ & ={\delta }_l{\beta }_l\prod _{i=1,i\ne l}^{\tau }\left(1-{\beta }_i{\beta }_l^{-1}\right)\end{array}$$E29

(3) Compute the derivative of $\sigma \left(x\right)$ as,

$${\sigma }^{\prime }\left(x\right)=\frac{\mathrm{d}}{\mathrm{d}x}\prod _{i=1}\tau \left(1-{\beta }_{i}x\right)=-\sum _{l=1}^{\tau }{\beta }_l\prod _{i=1,i\ne l}^{\tau }\left(1-{\beta }_{i}x\right).$$E30

Moreover, substitute ${\beta }_l^{-1}$ in Eq. (30) and obtain,

$${\sigma }^{\text{'}}\left({\beta }_l^{-1}\right)=-{\beta }_l\prod _{i=1,i\ne l}^{\tau }\left(1-{\beta }_i{\beta }_l^{-1}\right).$$E31

Hence, the error values ${\delta }_l$ at location ${\mathit{\text{beta}}}_l$ is evaluated as,

$${\delta }_l=-\frac{Z_0\left({\beta }_l^{-1}\right)}{{\sigma }^{\text{'}}\left({\beta }_l^{-1}\right)}.$$E32

The Euclidean decoding algorithm is terminated [12].

Example 2. Consider the triple-error-correcting RS code of length $n=15$ over $\mathrm{GF}\left(2^4\right)$, $\alpha$ be a primitive element of $\mathrm{GF}\left(2^4\right)$ such that ${\alpha }^4+\alpha +1=0$. The generator polynomial has $\alpha ,{\alpha }^2,{\alpha }^3,{\alpha }^4,{\alpha }^5,{\alpha }^6$ as roots; that is,

$$\begin{array}{ll}g\left(x\right)& =\left(x+\alpha \right)\left(x+{\alpha }^2\right)\left(x+{\alpha }^3\right)\left(x+{\alpha }^4\right)\left(x+{\alpha }^5\right)\left(x+{\alpha }^6\right)\\ & ={\alpha }^6+{\alpha }^{9}x+{\alpha }^9{x}^2+{\alpha }^4{x}^3+{\alpha }^{14}{x}^4+{\alpha }^{10}{x}^5+x^6.\end{array}$$E33

Suppose that the codeword of all zero is transmitted, and the received polynomial is $r\left(x\right)={\alpha }^7{x}^3+{\alpha }^{11}{x}^{10}$. The decoding procedures are shown as follows,

Step 1. Compute the syndromes $\left(S_1,S_2,\dots ,S_6\right)$. The syndrome components are exhibited as,

$$\begin{array}{ll}& S_1=r\left(\alpha \right)={\alpha }^7\cdot {\alpha }^3+{\alpha }^{11}\cdot {\alpha }^{10}={\alpha }^7,\\ & S_2=r\left({\alpha }^2\right)={\alpha }^7\cdot {\left({\alpha }^2\right)}^3+{\alpha }^{11}\cdot {\left({\alpha }^2\right)}^{10}={\alpha }^{12},\\ & S_3=r\left({\alpha }^3\right)={\alpha }^7\cdot {\left({\alpha }^3\right)}^3+{\alpha }^{11}\cdot {\left({\alpha }^3\right)}^{10}={\alpha }^6,\\ & S_4=r\left({\alpha }^4\right)={\alpha }^7\cdot {\left({\alpha }^4\right)}^3+{\alpha }^{11}\cdot {\left({\alpha }^4\right)}^{10}={\alpha }^{12},\\ & S_5=r\left({\alpha }^5\right)={\alpha }^7\cdot {\left({\alpha }^5\right)}^3+{\alpha }^{11}\cdot {\left({\alpha }^5\right)}^{10}={\alpha }^{14},\\ & S_6=r\left({\alpha }^6\right)={\alpha }^7\cdot {\left({\alpha }^6\right)}^3+{\alpha }^{11}\cdot {\left({\alpha }^6\right)}^{10}={\alpha }^{14}.\end{array}$$E34

The syndrome polynomial is $S\left(x\right)={\alpha }^7+{\alpha }^{12}x+{\alpha }^6{x}^2+{\alpha }^{12}{x}^3+{\alpha }^{14}{x}^4+{\alpha }^{14}{x}^5$.

Step 2. Determine the error-location polynomial $\sigma \left(x\right)$ and the error-value evaluator $Z_0\left(x\right)$ based on the Euclidean algorithm.

(1) Firstly, the initial conditions are acquired as,

$$\begin{array}{ll}& Z_0^{\left(-1\right)}\left(x\right)=x^6,\\ & Z_0^{\left(0\right)}\left(x\right)=S\left(X\right)={\alpha }^7+{\alpha }^{12}x+{\alpha }^6{x}^2+{\alpha }^{12}{x}^3+{\alpha }^{14}{x}^4+{\alpha }^{14}{x}^5,\\ & {\gamma }^{\left(-1\right)}\left(x\right)={\sigma }^{\left(0\right)}\left(x\right)=1,\\ & {\gamma }^{\left(0\right)}\left(x\right)={\sigma }^{\left(-1\right)}\left(x\right)=0..\end{array}$$E35

(2) When l = 1, then,

$$\begin{array}{ll}& Z_0^{\left(-1\right)}\left(x\right)=q_1\left(x\right)Z_0^{\left(0\right)}\left(x\right)+Z_0^{\left(1\right)}\left(x\right),\\ \Rightarrow & x^6=q_1\left(x\right)\left({\alpha }^7+{\alpha }^{12}x+{\alpha }^6{x}^2+{\alpha }^{12}{x}^3+{\alpha }^{14}{x}^4+{\alpha }^{14}{x}^5\right)+Z_0^{\left(0\right)}\left(x\right),\\ \Rightarrow & q_1\left(x\right)=\mathit{\alpha x}+\alpha ,Z_0^{\left(1\right)}\left(x\right)={\alpha }^6{x}^4+{\alpha }^5{x}^3+{\alpha }^5{x}^2+{\alpha }^{3}x+{\alpha }^8,\end{array}$$E36

where,

$${\sigma }^{\left(1\right)}\left(x\right)={\sigma }^{\left(-1\right)}\left(x\right)-q_1\left(x\right){\sigma }^{\left(0\right)}\left(x\right)\Rightarrow {\sigma }^{\left(1\right)}\left(x\right)=\mathit{\alpha x}+\alpha$$E37

(3) When l = 2,

$$\begin{array}{ll}& Z_0^{\left(0\right)}\left(x\right)=q_2\left(x\right)Z_0^{\left(1\right)}\left(x\right)+Z_0^{\left(2\right)}\left(x\right),\\ \Rightarrow & {\alpha }^7+{\alpha }^{12}x+{\alpha }^6{x}^2+{\alpha }^{12}{x}^3+{\alpha }^{14}{x}^4+{\alpha }^{14}{x}^5\\ =& q_2\left(x\right)\left({\alpha }^6{x}^4+{\alpha }^5{x}^3+{\alpha }^5{x}^2+{\alpha }^{3}x+{\alpha }^8\right)+Z_0^{\left(2\right)}\left(x\right),\\ \Rightarrow & q_2\left(x\right)={\alpha }^{8}x+{\alpha }^{11},Z_0^{\left(2\right)}\left(x\right)={\alpha }^{2}x+{\alpha }^3,\end{array}$$E38

where,

$${\sigma }^{\left(2\right)}\left(x\right)={\sigma }^{\left(0\right)}\left(x\right)-q_2\left(x\right){\sigma }^{\left(1\right)}\left(x\right)\Rightarrow {\sigma }^{\left(2\right)}\left(x\right)={\alpha }^9{x}^2+{\alpha }^{8}x+{\alpha }^{11}$$E39

Observe that $deg{Z}_0^{\left(2\right)}\left(x\right)<deg{\sigma }^{\left(2\right)}\left(x\right)\le 3=t$. Hence, The iteration is terminated, and we can acquire,

$$Z_0\left(x\right)=Z_0^{\left(2\right)}\left(x\right)={\alpha }^{2}x+{\alpha }^3,\sigma \left(x\right)={\sigma }^{\left(2\right)}\left(x\right)={\alpha }^9{x}^2+{\alpha }^{8}x+{\alpha }^{11}$$E40

Step 3. Evaluate error-location numbers and error values. The all roots of $\sigma \left(x\right)$ are ${\alpha }^5$ and ${\alpha }^{12}$. Then, the error location numbers are ${\left({\alpha }^5\right)}^{-1}={\alpha }^{10},{\left({\alpha }^{12}\right)}^{-1}={\alpha }^3$. The error values at these locations are

$$\begin{array}{ll}& e_3=\frac{-Z_0\left({\alpha }^{-3}\right)}{{\sigma }^{\text{'}}\left({\alpha }^{-3}\right)}=\frac{{\alpha }^3+{\alpha }^2{\alpha }^{-3}}{{\alpha }^{11}{\alpha }^3\left(1+{\alpha }^{10}{\alpha }^{-3}\right)}=\frac{1}{{\alpha }^8}={\alpha }^7,\\ & e_{10}=\frac{-Z_0\left({\alpha }^{-10}\right)}{{\sigma }^{\text{'}}\left({\alpha }^{-10}\right)}=\frac{{\alpha }^3+{\alpha }^2{\alpha }^{-10}}{{\alpha }^{11}{\alpha }^{10}\left(1+{\alpha }^3{\alpha }^{-10}\right)}=\frac{{\alpha }^4}{{\alpha }^8}={\alpha }^{11}.\end{array}$$E41

Step 4. Perform error correction.

Therefore, the error polynomial is $e\left(x\right)={\alpha }^7{x}^3+{\alpha }^{11}{x}^{10}$. the decoded coded polynomial is $c^{\text{'}}\left(x\right)=r\left(x\right)-e\left(x\right)=\left({\alpha }^7{x}^3+{\alpha }^{11}{x}^{10}\right)-\left({\alpha }^7{x}^3+{\alpha }^{11}{x}^{10}\right)=\mathbf{0}$, which is all-zero codeword.

The end of Example 2.

3. General distributed RS coded-cooperative systems

Coded cooperative diversity is an efficient technique combining channel coding and cooperative diversity to combat the influence of channel fading and improve the performance of the systems [13]. Generally, the coded cooperation is composed of three terminals, i.e., source, relay, and destination. Hence, the channel codes employed in each terminal are named distributed channel codes. Many distributed channel codes are applied in the coded-cooperative systems. For short-to-medium-length transmission information blocks, the RS channel coding may be a promising candidate which illustrates a superior performance [13, 14, 15, 16].

Figure 1 demonstrates the general distributed RS coded-cooperative scheme. Evidently, all three terminals transmit and receive signals through one antenna and the entire transmission requires two-time slots. During time slot-1, the binary information sequence ${\mathbf{b}}_1$ is first converted to the $M$-ary symbol vector ${\mathbf{u}}_1$ of length $K_1$ over the $\mathrm{GF}\left(2^M\right)$. Then, ${\mathbf{u}}_1$ is encoded by the ${\mathit{RS}}_1\left(N,K_1,d_1\right)$ encoder to obtain the systematic codeword ${\mathbf{c}}_1$ of length $N$, where $d_1=N-K_1+1$ and the generator polynomial $g_1\left(x\right)$ of ${\mathit{RS}}_1$ is given as,

Figure 1.

The system model of the general distributed RS-coded cooperation.

$$g_1\left(x\right)=\left(x-\gamma \right)\left(x-{\gamma }^2\right)\cdots \left(x-{\gamma }^{N-K_1}\right),$$E42

where ${\gamma }^k\in \mathrm{GF}\left(2^M\right),k=0,1,\dots ,N-K_1$. Then, ${\mathbf{c}}_1$ is further modulated to the signal ${\mathbf{v}}_1$ by the $M$-ary quadrature amplitude modulation ($M$-QAM). Subsequently, ${\mathbf{v}}_1=\left[v_0,v_1,\dots ,v_{(}N-1\right)]$ generated at the source is transmitted to the both relay and destination through the respective fading channels where the signals ${\mathbf{r}}_1=\left[r_0^1,r_1^1,\dots ,r_{N-1}^1\right]$ and ${\mathbf{r}}_2=\left[r_0^2,r_1^2,\dots ,r_{N-1}^2\right]$ are obtained at the relay and destination, respectively. Moreover, each signal symbol $r_i^j\left(i=0,1,\dots ,N-1,j=1,2\right)$ is modeled as,

$$r_i^j=h_i^j{v}_i+n_i^j,$$E43

where $h_i^j$ is the complex Gaussian variable satisfying zero mean and $1/2$ variance per dimension, and $n_i^j$ represents the complex Gaussian variable with zero mean and $N_0/2$-variance per dimension. Note that $N_0$ denotes the power spectral density (PSD) of the noise.

During time slot 2, ${\mathbf{r}}_2$ is demodulated and decoded subsequently to obtain the estimated information sequence ${\tilde{\mathbf{u}}}_1$. If the source-to-relay channel is ideal, then, ${\tilde{\mathbf{u}}}_1={\mathbf{u}}_1$. For the system, the information symbols at the relay are only from the source. Therefore, the $K_2$ symbols are simply chosen from ${\tilde{\mathbf{u}}}_1$ of length $N$ through the ‘Symbol Selection’ block. Note that different selection patterns contribute to a different minimum distance of the resultant code at the destination and further affect the overall performance of the RS coded-cooperative scheme, which will be elaborated on in the next section. After that, the selected message vector ${\mathbf{u}}_2$ is also encoded by the ${\mathit{RS}}_2\left(N,K_2,d_2\right)$ to acquire the $c_2$, where $d_2=N-K_2$ and the generator polynomial $g_2\left(x\right)$ of ${\mathit{RS}}_2$ is provided as,

$$g_1\left(x\right)=\left(x-\gamma \right)\left(x-{\gamma }^2\right)\cdots \left(x-{\gamma }^{N-K_2}\right),$$E44

Similarly, the codeword ${\mathbf{c}}_2$ is modulated by an $M$-QAM modulator and further transmitted to the destination. The received signal ${\mathbf{r}}_3$ is also modeled similarly to Eq. (43).

At the destination, the obtained signals ${\mathbf{r}}_1$ and ${\mathbf{r}}_3$ are concatenated is series as,

$$\mathbf{r}=\left({\mathbf{r}}_1|{\mathbf{r}}_3\right),$$E45

where ‘$\mid$’ denotes that the two signals are conjunct in series during two-time slots. Following that, r passes to the ‘$M$-QAM Demodulator’ block to get the joint demodulated message sequence (${\tilde{\mathbf{c}}}_1\mid {\tilde{\mathbf{c}}}_2$) and then decoded by the joint RS decoding algorithm that will be introduced in detailed later. Finally, the estimated information sequence ${\widehat{\mathbf{u}}}_1$ is transformed to the extensive bit sequence ${\widehat{\mathbf{b}}}_1$.

4. The optimized codes resulted at destination by proper selection at relay

The different relay selection patterns determine the different minimum distance of the final joint code at the destination, which influences the performance of the system. Therefore, we need to consider the proper selection approach at the relay to capture the resulting code with a minimum distance as large as possible. The following will introduce two proper selection approaches, detailed content can refer to [13].

Obviously, we should consider the worst-case scenario and aim to avoid as many of them as possible. Since the minimum weight of the code at source is already determined as $d_1$, only the minimum weight of the codeword selected by the relay needs to be considered. Firstly, some nomenclatures are described below before providing design steps:

1. The first scenario is expressed as the minimum weights of code is $\mathit{wt}\left({\mathbf{c}}_1\right)=d_1$, $\mathit{wt}\left({\mathbf{c}}_2\right)=0$ for the source and relay, respectively, resulting in the final code at the destination has the minimum free distance $d_3^{\left(1\right)}=d_1$, which is the worst case.

2. The second scenario is described as $\mathit{wt}\left(c_1\right)=d_1$ and $\mathit{wt}\left(c_2\right)=d_2$. Hence the minimum weight of the final codeword is $d_3^{\left(2\right)}=d_1+d_2$ that is the second-worst case.

3. The third scenario is the weight of the resultant code $d_3^{\left(3\right)}$ is greater than $d_3^{\left(2\right)}$ at the destination.

4. Define $w_1$, $w_2$ and $w_3$ as the number of times three scenarios occur, respectively.

4.1 Exhaustive search approach

The exhaustive search approach is performed for all information sequences with the weight $0<\mathit{wt}\left({\mathbf{u}}_1\right)\le d_1$ that may be encoded to the codeword with the weight $d_1$. The preceding are the particular steps of this approach.

1. Define the set $\psi =\left\{{\mathbf{u}}_1|\mathit{wt}\left(c_1\right)=d_1\right\}$ to store the information sequence ${\mathbf{u}}_1$ that generate the exactly the codeword with weight $d_1$.

2. Determine the set $\varphi =\left\{{\xi }_g\right\}$ which stores all selection patterns ${\xi }_g=\left[{\xi }_1,{\xi }_2,\dots ,{\xi }_{K_2}\right]$, where ${\xi }_i\in 1,2,\dots ,K_2,g=1,2,\xi ,L$ and L is given as,

   $$L=K_1\begin{array}{c}\\ K_2\end{array}=\frac{K_1!}{K_2!\left(K_1-K_2\right)!}.$$E46

3. For each selection pattern ${\xi }_g$, determine the value of $w_1$. If $\mid \mathrm{\Gamma }\mid =1$, Moreover, save the selection patterns corresponding to the $min\left(w_1\right)$ to the set $\mathrm{\Gamma }$. If then skip step 6 otherwise come to the next step, where $\mid \cdot \mid$ denotes the cardinality of the set.

4. From the set $\mathrm{\Gamma }$, determine the selection patterns ${\xi }_g$ that correspond to the $min\left(w_2\right)$ and are stored to the set $\mathrm{\Omega }$. Similarly, if $\mid \mathrm{\Omega }\mid =1$, proceed to step 6, else move to the next step.

5. Determine the selection patterns ${\xi }_g$ corresponding to $min\left(w_3\right)$ from the set $\mathrm{\Omega }$ and are further saved in the set $\mathrm{\Psi }$. If $\mid \mathrm{\Psi }\mid =1$, then, come to step 6, otherwise add the $\mathit{wt}\left({\mathbf{c}}_2\right)$ by 1 and move on to step 5 until $\mid \mathrm{\Psi }\mid =1$.

6. The optimized selection pattern ${\xi }^{\left(\mathit{ES}\right)}={\xi }_g$ is captured. The selection is terminated.

Example 3. In the distributed RS-coded cooperative system, consider the ${\mathit{RS}}_1\left(\mathrm{15,11,5}\right)$ and ${\mathit{RS}}_2\left(\mathrm{15,7,9}\right)$ are employed in the source and relay, respectively. The symbol elements of the ${\mathit{RS}}_1$ and ${\mathit{RS}}_2$ are chosen from $\mathrm{GF}\left(2^4\right)$ shown in Table 1. The exhaustive search for selecting the information symbol of $K_2=7$ from $K_1=11$ is demonstrated below.

1. Find all information sequences ${\mathbf{u}}_1$ that generate the codewords ${\mathbf{c}}_1$ with weight $d_1=5$. And store them to the set $\psi$. By numerical simulation, $\mid \psi \mid =45045$.

2. Store all selection patterns ${\xi }_g=\left[{\xi }_1,{\xi }_2,\dots ,{\xi }_7\right]$ in the set $\varphi$. And calculate $\mid \varphi \mid =L=330$.

3. Through simulation, $min\left(w_1\right)$ and its corresponding selection patterns are obtained and saved in the set $\mathrm{\Gamma }$ as exhibited in Table 2. Since $\mid \mathrm{\Gamma }\mid =4\ne 1$, then come to the next step.

4. For the four selection patterns, determine the $min\left(w_2\right)=16635$ that corresponding to a selection pattern ${\xi }_g=\left[\mathrm{5,6,7,8,9,10,11}\right]$. Thus, $\mid \mathrm{\Omega }\mid =1$ and the optimized ${\xi }^{\left(\mathit{ES}\right)}=\left[\mathrm{5,6,7,8,9,10,11}\right]$ is determined.

No.	Selection pattern	$w_1$	$w_2$
1	$\left[456891011\right]$	840	17,010
2	$\left[457891011\right]$	840	17,280
3	$\left[467891011\right]$	840	17,535
4	$\left[567891011\right]$	840	16,635

Table 2.

The procedure of exhaustive search approach to obtain an optimized selection pattern.

The end of Example 3.

4.2 Partial search approach

The exhaustive search approach can choose the optimal selection pattern with the final codeword at the destination having a better weight distribution. However, the complexity of determining the information sequence set $\psi$ and the selection pattern set $\varphi$ increases rapidly when the information length and code length become large. Therefore, we need to consider a low-complexity search approach, i.e., a partial search approach [16]. This approach reduces the search range of the information sequences and the scope of the selection patterns.

First, divide the information positions into two parts illustrated in Figure 2. Case (a): the first part is greater than the other part one symbol. Case (b): the last part is greater than the first part symbol. In two cases, make sure the symmetric structure of the $K_1$ information symbols. Hence, it is reasonable to position the information symbols appropriately. Note that the message sequence generating the codeword with the weight $d_1$ has at least $\theta =K_1-min\left(K_1,d_1\right)$ zero symbols. Thus, we focus on selecting the distribution positions of the $\theta$ zero symbols and $K_2$ selection pattern.

1. Determine the distribution positions of the $\theta$ zero symbols. For case (a), take $\epsilon (⌈\theta /2⌉\le \mathit{\epsilon \theta }min\left(⌈K_1/2⌉,\theta \right)$ zero symbols set in the first part randomly, and the other $\theta -\epsilon$ distribute in the last part uniquely. For case (b), $\epsilon$ zero symbols are uniquely assigned in the first part and the remaining $\theta -\epsilon$ zero symbols are randomly set in the last part, where $⌈\cdot ⌉$ represent ceil operation. Consider two cases, the set $\overline{\psi }$ that stores partial information sequences generating the codeword with $d_1$ is determined.

2. Determine the selection positions of $K_2$ information symbols from the $K_1$ positions. For case (a), randomly choose $\zeta \left(⌈K_2/2⌉\le \zeta \le min\left(⌈K_1/2⌉,K_2\right)\right)$ positions out of the first part and the left $K_2-\zeta$ positions are fixed at the last part. For case (b), select $\zeta$ positions randomly from the last part and the other $K_2-\zeta$ positions are uniquely chosen from the first parts. Hence, the reduced selection patterns ${\xi }_g$ are stored in the set $\overline{\varphi }$.

   Based on the reduced sets $\overline{\psi }$ and $\overline{\varphi }$, the subsequent steps are same as the Step 3–6 of the exhaustive search approach.

Figure 2.

The symmetric division structure of the positions of $K_1$ information symbols, case (a) one more symbol in the first part, case (b) one more symbol in the last part.

Example 4. This example uses the same codes as Example 4.1. Evidently, the information sequence that can be encoded to the codeword with weight 5 includes at least 6 zero-symbols. The division structure of the partial search approach is shown in Figure 3.

1. Determine the distribution positions of the 6 zero symbols. For case (a), take $\epsilon \left(\epsilon =\mathrm{3,4,5,6}\right)$ zero symbols set in the first 6 positions randomly, and the other $6-\epsilon$ distribute in the last 5 positions uniquely. For case (b), $\epsilon$ zero symbols are uniquely assigned in the first part and the remaining $6-\epsilon$ zero symbols are randomly set in the last part. Consider two cases, the set $\overline{\psi }$ is determined and $\mid \psi \mid =24075$.

2. Determine the selection positions of 7 information symbols from the 11 positions. For case (a), randomly choose $\zeta \left(\zeta =\mathrm{4,5,6}\right)$ positions out of the first 6 positions, and the left $7-\zeta$ positions are fixed at the last 5 positions. For case (b), select $\zeta$ positions randomly from the last 6 positions, and the other $7-\zeta$ positions are uniquely chosen from the first 5 positions. Hence, the set $\overline{\varphi }$ of the partial selection pattern is determined, and $\mid \overline{\varphi }\mid =44$.

3. Through simulation, $min{w}_1=360$ and its corresponding selection patterns are stored in the set $\mathrm{\Gamma }$ as demonstrated in Table 3. Since $\mid \mathrm{\Gamma }\mid =3\ne 1$, then come to the next step.

4. For the three selection patterns, determine $min\left(w_2\right)$ that corresponds to two selection patterns. Thus, $\mid \mathrm{\Omega }\mid =2\ne 1$, go to the next step.

5. Obtain the $min\left(w_3\right)=6540$ and corresponding selection pattern from the set $\mathrm{\Omega }$ and are further saved in the set $\mathrm{\Psi }$. Since $\mid \mathrm{\Psi }\mid =1$, then, the optimized selection pattern ${\xi }^{\left(\mathit{PS}\right)}=\left[123691011\right]$ is acquired. The partial search stops.

Figure 3.

The symmetric division structure of the positions of 11 information symbols, case (a) 6 symbols in the first part, case (b) 6 symbols in the last part.

No.	Selection pattern	$w_1$	$w_2$	$w_3$
1	$\left[123491011\right]$	360	10,035	6615
2	$\left[123691011\right]$	360	10,035	6540
3	$\left[123891011\right]$	360	10,035	$----$

Table 3.

The procedure of partial search approach to obtain an optimized selection pattern.

The end of Example 4.

Based on Examples 3 and 4, the BER performance of the distributed RS-coded cooperative scheme over the Rayleigh fast-fading channel employing the exhaustive search and partial search is exhibited in Figure 4 where the 16-QAM modulation is employed and the source-to-relay channel is ideal. The result reveals that the scheme with two different approaches illustrates almost identical performance, which further shows the feasibility of the reduced-complexity approach. More simulation results can refer to [13].

Figure 4.

The BER performance comparison of the distributed RS-coded cooperative scheme with two selection approaches at the relay over the fast-fading channel.

4.3 Complexity comparisons

First, the complexity comparisons of the two search approaches are listed in Table 4, where $\left({\lambda }_1^{+},{\lambda }_1^{\times }\right)$ and $\left({\lambda }_2^{+},{\lambda }_2^{\times }\right)$ represent the number of the operations of the addition and the multiplication required to encode the information sequence from the set $\psi$ and $\overline{\psi }$ at the source and relay, respectively, and ${\lambda }_{\mathit{\text{total}}}$ denotes the total operations.

Approaches	Operations	$\left({\lambda }_1^{+},{\lambda }_1^{\times }\right)$	$\left({\lambda }_2^{+},{\lambda }_2^{\times }\right)$	${\lambda }_{\mathit{\text{total}}}$
Exhaustive Search		$(K_1\left(N-K_1\right)\mid \psi \mid$,	$(K_2\mid \psi \Vert \varphi \mid \left(N-K_2\right)$,	$2\mid \psi \mid [{\mathit{NK}}_1+{\mathit{NK}}_2\mid \varphi \mid$
		$K_1\left(N-K_1\right)\mid \psi \mid )$	$K_2\mid \psi \Vert \varphi \mid \left(N-K_2\right))$	$-{\left(K_1\right)}^2-{\left(K_2\right)}^2\mid \varphi \mid ]$
Partial Search		$(K_1\left(N-K_1\right)\mid \overline{\psi }\mid$,	$K_1\left(N-K_1\right)\mid \overline{\psi }\mid )$	$(K_2\mid \overline{\psi }\Vert \overline{\varphi }\mid \left(N-K_2\right)$,
		$K_2\mid \overline{\psi }\Vert \overline{\varphi }\mid \left(N-K_2\right))$	$2\mid \overline{\psi }\mid [{\mathit{NK}}_1+{\mathit{NK}}_2\mid \overline{\varphi }\mid$	$-{\left(K_1\right)}^2-{\left(K_2\right)}^2\mid \overline{\varphi }\mid ]$

Table 4.

Complexity comparisons of two approaches.

5. Joint decoding algorithms and error performance analysis

The section introduces the two joint decoding algorithms, namely, the naive algorithm and the smart algorithm. The two decoding algorithms may enhance the overall performance by making full advantage of the two signals from the source and relay, respectively.

5.1 Nave decoding algorithmm

The detailed steps for the naive algorithm are listed as follows:

1. For the received demodulated signal $\left({\tilde{\mathbf{c}}}_1|{\tilde{\mathbf{c}}}_2\right)$, ${\tilde{\mathbf{c}}}_1$ and ${\tilde{\mathbf{c}}}_2$ are decoded by ${\mathit{RS}}_1$ and ${\mathit{RS}}_2$ decoders, respectively, to acquire the estimated information sequences ${\mathbf{u}}_1^{\prime }$ and ${\mathbf{u}}_2^{\prime }$.

2. Determine the SNR cross-point of the ${\mathit{RS}}_1$ and ${\mathit{RS}}_2$ point-to-point coding scheme over the fast-fading channel, denoted $\eta$.

3. If SNR $\le \eta$, ${\widehat{\mathbf{u}}}_1={\mathbf{u}}_1^{\prime }$ due to the better performance of ${\mathit{RS}}_1$ code than that of ${\mathit{RS}}_2$ code at the low SNRs. Otherwise, ${\mathbf{u}}_2^{\prime }$ replaces ${\mathbf{u}}_1^{\prime }$ at the corresponding selected positions to obtain a re-combined ${\ddot{\mathbf{u}}}_1$, then, ${\widehat{\mathbf{u}}}_1={\ddot{\mathbf{u}}}_1$. This is because the ${\mathit{RS}}_2$ code with more parity-check symbols outperforms the ${\mathit{RS}}_1$ code at high SNRs. Finally, the estimated sequence ${\widehat{\mathbf{u}}}_1$ is obtained.

5.2 Smart decoding algorithm

The specific steps for the smart algorithm are described below:

1. For the received demodulated signal $\left({\tilde{\mathbf{c}}}_1|{\tilde{\mathbf{c}}}_2\right)$, only decode the last part ${\tilde{\mathbf{c}}}_2$ to get the systematic non-binary message sequence ${\mathbf{u}}_2^{\prime }$.

2. For the first part ${\tilde{\mathbf{c}}}_1$ comprising of the check-parity sequence ${\tilde{\mathbf{p}}}_1$ and information sequence ${\tilde{\mathbf{u}}}_1$, replace the non-binary symbols of ${\tilde{\mathbf{u}}}_1$ with ${\mathbf{u}}_2^{\prime }$ in the corresponding $K_2$ positions to obtain the re-combined sequence ${\overline{\mathbf{c}}}_1$ due to the reliability of ${\mathbf{u}}_2^{\prime }$ than original message symbols.

3. Decode ${\overline{\mathbf{c}}}_1$ by the ${\mathit{RS}}_1$ decoder to acquire the final estimated information sequence ${\overline{\mathbf{u}}}_1$.

Figure 5 illustrates the BER performance of the distributed RS-coded cooperative scheme under two different decoding algorithms over a fast fading channel, where 16-QAM is applied in the scheme and the partial search approach is employed in the relay. From the simulated result, the scheme under the smart decoding algorithm is superior to that of the naive by a gain of over 1.5 dB at $\mathit{BER}\approx 4\times {10}^{-5}$.

Figure 5.

The performance comparison of the distributed RS-coded cooperative scheme under two different joint decoding algorithms over the fast-fading channel.

5.3 Error performance of distributed RS coded-cooperative systems

This section presents the average error probability (AEP) bound for the distributed RS coded-cooperative scheme over the Rayleigh fast-fading channel. First, the unconditional error probability is provided as follows [5, 17, 18],

$$P_b\left(E\right)=\frac{1}{\pi }{\int }_0^{\pi /2}{\left(1+\frac{{\mathrm{\Lambda }}_1}{{sin}^2\phi }\right)}^{d_1}{\left(1+\frac{{\mathrm{\Lambda }}_2}{{sin}^2\phi }\right)}^{d_2}\mathit{d\phi },$$E47

where ${\mathrm{\Lambda }}_1$ and ${\mathrm{\Lambda }}_2$ denote the average signal-to-noise ratio (SNR) per information bit from the source-to-destination and relay-to-destination links. The integral in Eq. (47) is calculated by the available computer package. Then, the upper bound may be acquired by assuming ${sin}^2\phi =1$, shown as,

$$P_b\left(E\right)\le \frac{1}{2}{\left(\frac{1}{1+{\mathrm{\Lambda }}_1}\right)}^{d_1}{\left(\frac{1}{1+{\mathrm{\Lambda }}_2}\right)}^{d_2},$$E48

Therefore, based on Eq. (48), the upper bound of the bit error probability $P_b$ is further given as [6],

$$P_b\le \sum _{\varpi =d_1+d_2}^N\frac{J_{\varpi }}{K_1}{P}_b\left(E\right),$$E49

where $J_{\varpi }$ represents a weight enumerating factor for each codeword with weight w which is obtained by exhaustive computer search.

6. Conclusions

The chapter first introduces the encoding and decoding procedure of the BCH codes and RS codes. Then, the system model of the distributed RS-coded cooperation is presented which improves the anti-interference transmission performance of the short-to-medium-length information block. In the scheme, the exhaustive and partial search approaches are introduced and employed in the relay to choose an optimized selection pattern that results in a final code with a better weight distribution at the destination. In addition, two joint decoding algorithms are provided to further enhance the performance and the performance analysis validates the system.

Acknowledgments

The financial assistance provided by the National Natural Science Foundation of China under contract No. 61771241 is acknowledged.

Conflict of interest

The authors declare no conflict of interest.