A hybrid decoding of Reed–Muller codes

Abstract

In this article, a hybrid decoding algorithm for Reed–Muller codes is presented. Unlike the conventional algorithm, the presented algorithm ends recursive decomposition when $R(1,m)$ and $R(m-1,m)$ appeared. A simplified maximum-likelihood algorithm based on fast Hadamard transform is also exploited to decode the systematic code through its special structure. As a result, the presented hybrid decoding algorithm reduces the number of floating-point multiplications significantly as compared with the conventional algorithms. In addition, the new algorithm has better error performance than the conventional ones.

Introduction

Error correcting codes (ECC) introduce controlled redundancy to correct errors that might have happened in the channel during signal transmission. The error-correction capability is achieved by mapping words from the k-dimensional information space to the n-dimensional code space, where $k\le n$ in a general block coding scheme. This implies that a channel coder takes k-bit-long binary blocks as input and maps them to the corresponding n-bit-long binary blocks as output, which are then transmitted over the channel. In general, all $2^k$ possible information words are assumed to be equiprobable, and each of those words is uniquely mapped to one of $2^n$ available vectors in the code space. Thus, different codewords are separated from each other in some distance away.

A binary code C is linear if the sum of any two codewords in C is also a legal codeword in C , that is, it is closed under modulo-2 addition in $F_2^n$ . Thus, a linear code C is a linear subspace of $F_2^n$ . Let G be a matrix whose rows form a basis of C . This matrix is called the generator matrix of the code C . If G has k rows and n columns, then it defines a linear code of dimension k and length n. The encoding of an information word x into a codeword c is performed by

$$c=\mathit{xG}$$ (1)

Thus, the matrix G can be considered as a compact representation of a linear code.

Binary Reed–Muller (RM) codes $R(r,m)$ , $0\le r\le m$ , are a linear block code of length n, dimension k, and the minimum Hamming distance d. The code can be defined as the set of all mappings $\{f_r^m:F_2^m\to F_2\}$ , where $f_r^m$ represents m-variate Boolean polynomial of degree being less than or equal to r.^1,2 Decoding of the RM codes is commonly carried out by a recursive algorithm called the Plotkin algorithm.^3–5 In this algorithm, the recursion ends when either $R(0,m)$ or $R(m,m)$ appeared. That is, the algorithm decomposes a received word to the final stage.

In this article, a hybrid decoding algorithm for RM codes is presented and analyzed. According to the stages of decomposition processes, the proposed hybrid algorithm exploits Green machine and Wagner decoding, as well as the traditional Plotkin recursive algorithm. Unlike the conventional algorithms, the recursive decomposition in the presented algorithm is ended when $R(1,m)$ and $R(m-1,m)$ appeared. That is, the presented scheme ends recursion one step earlier than the conventional ones so that computational complexity for decoding of RM codes can be reduced. In addition, a simplified maximum-likelihood (ML) decision based on fast Hadamard transform (FHT) is also exploited to decode the systematic code. Hence, the presented hybrid decoding algorithm possibly reduces computational complexity significantly. And computer simulation shows that the new decoding algorithm has improved error performance as compared with the conventional ones, as well.

The remainder of this article is organized as follows. In section “RM codes,” the RM codes are introduced shortly, and the conventional recursive decoding algorithm for the RM codes is also presented. In section “A hybrid recursive decoding for RM codes,” a hybrid recursive decoding algorithm is presented in detail. In section “Performance analysis,” numerical analysis on the decoding complexity of the proposed algorithm is provided. And error performance of the proposed algorithm compared with the conventional ones is also discussed. Finally, some concluding remarks are drawn in section “Conclusion.”

RM codes

Binary RM codes $R(r,m)$ , $0\le r\le m$ , are a kind of linear block codes of length n, dimension k, and the minimum distance d such that^4,5

$$n=2^m,k(r,m)=\sum _{i=0}^r\left(\begin{array}{c}m\hfill \\ \multicolumn{1}{c}{i}\end{array}\right),d_{\min }=2^{m-r}$$ (2)

where $\left(\begin{array}{c}m\hfill \\ \multicolumn{1}{c}{r}\end{array}\right)=m!/(m-r)!r!$ . Let $m=5$ , $r=2$ , then $n=32$ , $k(2,5)=16$ , $d_{\min }=8$ . Let a Boolean polynomial $\{f_r^m|F_2^m\to F_2\}$ of degree at most r map vectors $(x_1,\dots ,x_m)\in F_2^m$ into $f_r^m(x_1,\dots ,x_m)$ . Then, the code $R(r,m)$ can be defined as the set of all such mappings $\{f_r^m\}$ . It implies each m-variate Boolean polynomial $f_r^m$ of degree being less than or equal r defines a codeword as the vector of its values on $F_2^m$ . ⁶ As an example, the first-order code $R(1,2)$ of length 4 has eight codewords defined by polynomials of the form $a_0+a_1{x}_1+a_2{x}_2$ , where $a_0,a_1,a_2\in F_2$ and $x_1,x_2\in F_2$ . The truth tables on $F_2^m$ of the following $2^m$ monomials

$$1,x_1,x_2,\dots ,x_m,x_1{x}_2,\dots ,x_{m-1}{x}_m,\dots ,x_1{x}_2\dots x_m$$ (3)

form the basis for the $R(m,m)$ code. It means that any codeword of $R(m,m)$ can be represented as their linear combinations with binary coefficients. This, in turn, implies that their subsets upto degree r

$$\begin{array}{c}1,x_1,x_2,\dots ,x_m,x_1{x}_2,\dots ,x_{m-1}{x}_m,\dots ,\hfill \\ \multicolumn{1}{c}{x_1{x}_2\dots x_r,\dots ,x_{m-r+1}\dots x_m}\end{array}$$ (4)

also form the basis of the $R(m,m)$ code.

Since $x=x^2$ when $x\in F_2$ , the $R(m,m)$ code contains only m-variate Boolean multilinear polynomials. Such a polynomial can be expressed as a sum of the functions in equation (2) with binary coefficients, and there exist $2^{2^m}$ such sums. Given a vector of length $n=2^m$ , we make an m-variate Boolean polynomial represented as a truth table. Then, there exist $2^{2^m}$ different binary strings of length $2^m$ . It implies that all the sums of monomials in equation (2) are distinct, as every row in the $2^m$ truth tables is a linearly independent vector in $F_2^n$ .

To explain the recursive decoding of the Plotkin algorithm, ³ let ${\mathit{C}}_u$ and ${\mathit{C}}_v$ be $[n_u,k_u,d_u]$ and $[n_v,k_v,d_v]$ linear block codes, respectively. Define a new longer code C as^6,7

$$\mathit{C}=\{(\mathit{u},\mathit{u}+\mathit{v})|\mathit{u}\in {\mathit{C}}_u,\mathit{v}\in {\mathit{C}}_v\}$$ (5)

Then, the code C is also a $[n_u+n_v,k_u+k_v,\min (2d_u,d_v)]$ linear code. ⁸ Indeed, the length and dimension follow from the generator matrix

$${\mathit{G}}_C=\left[\begin{array}{cc}{\mathit{G}}_{C_u}\hfill & {\mathit{G}}_{C_u}\hfill \\ \multicolumn{1}{c}{0}& {\mathit{G}}_{C_v}\hfill \end{array}\right]$$ (6)

where ${\mathit{G}}_{C_u}$ and ${\mathit{G}}_{C_v}$ are the generator matrices of ${\mathit{C}}_u$ and ${\mathit{C}}_v$ , respectively. An example of the conventional generator matrix of $R(2,4)$ , which has a repetitive structure given in equation (6), is illustrated in Figure 1, where ∘ represents a binary 0 and • represents a binary 1.

Figure 1.

The conventional generator matrix of $R(2,4)$ .

For the codes u and v , if

$$\{\begin{array}{cc}w(\mathit{u},\mathit{u}+\mathit{v})\ge w(\mathit{v})\ge d_v\hfill & v\ne 0\hfill \\ \multicolumn{1}{c}{w(\mathit{u},\mathit{u}+\mathit{v})=2w(\mathit{u})\ge 2d_u}& v=0\hfill \end{array}$$ (7)

is satisfied, the minimum distance equals $\min (2d_u,d_v)$ . Here, $w(\mathit{x})$ denotes the weight of a code x .

RM codes can be recursively defined using the Plotkin $(\mathit{u},\mathit{u}+\mathit{v})$ structure. Let f be an m-variate polynomial of degree at most r. As f belongs to $R(r,m)$ , it can be decomposed as

$$\begin{array}{c}f(x_1,\dots ,x_m)=f_u(x_1,\dots ,x_{m-1})+\hfill \\ \multicolumn{1}{c}{x_m{f}_v(x_1,\dots ,x_{m-1})}\end{array}$$ (8)

where the degree of $f_u$ and that of $f_v$ are $\mathrm{deg}(f_u)<r$ and $\mathrm{deg}(f_v)<r-1$ , respectively. $f_u$ and $f_v$ do not depend on the coordinate $x_m$ any more. This implies that $f_u$ is a codeword of $R(r,m-1)$ and $f_v$ belongs to $R(r-1,m-1)$ . Note that $f(x_1,\dots ,x_m)=f_u(x_1,\dots ,x_{m-1})$ on a subcube $\{(x_1,\dots ,x_m):x_m=0\}$ and $f(x_1,\dots ,x_m)=f_u(x_1,\dots ,x_{m-1})+f_v(x_1,\dots ,x_{m-1})$ on the second subcube, that is, when $x_m=1$ . ⁵ Thus, we can partition the initial hypercube $F_2^m$ into two subcubes that differ only the value of the coordinate $x_m$ . Since the function $f_u$ does not depend on $x_m$ , it generates identical vectors on both of these subcubes, which correspond to the u components in the Plotkin construction algorithm.

Codewords $f_u$ and $f_v$ can be decomposed further to obtain successively all codes $R(\tau ,\mu )$ for $\tau \le r$ and $\mu \le m$ . For example, after r steps of such decomposition, the repetition code $R(0,m-r)$ is obtained, and the full code $R(r,r)$ can be found after $m-r$ steps. By continuing this process on codes $R(m-1,r)$ and $R(m-1,r-1)$ , we obtain RM codes of length $2^{m-2}$ , and so on. Finally, we arrive at the end nodes, which consist of repetition codes $R(g,0)$ for any $g=1,\dots ,m-r$ and full space $R(h,h)$ for $h=1,\dots ,r$ . Such a decomposition process for RM codes of length 8 is schematically shown in Figure 2. ⁵

Figure 2.

Decomposition of RM codes of length 8. ⁵

Let $a_r^m=\{a_j,j=1,2,\dots ,k\}$ be a block of k information bits $a_j$ that encodes a vector $(\mathit{u},\mathit{u}+\mathit{v})$ . By decomposing this vector into u and v , $a_r^m$ can be splitted into two information subblocks $a_r^{m-1}$ and $a_{r-1}^{m-1}$ that encode vectors u and v , respectively. The information subblocks are splitted further until the end nodes $R(g,0)$ or $R(h,h)$ . The information decomposition processes are shown in Figure 3 (the left of the decomposition path is referred to v path and the right is called u path in the following). It can be observed that only one information bit is assigned to the left-end (repetition) code $R(g,0)$ , while $2^n$ bits are assigned to the right-end code $R(h,h)$ . The $2^h$ bits will be encoded by the unit generator matrix. It is, therefore, considered that any codeword can be encoded from the information strings assigned to the end nodes $R(g,0)$ or $R(h,h)$ by combining codewords u and v in the $(\mathit{u},\mathit{u}+\mathit{v})$ construction repetitively.

Figure 3.

A general decomposition of information path.

A hybrid recursive decoding for RM codes

Since the Plotkin algorithm had been proposed, ³ a lot of researches have been carried out to develop or improve the recursive decoding algorithm.^4–7,9 We propose a new recursive decoding algorithm for the RM code. Here, the recursive decomposition processes are ended one step earlier than the conventional one. Moreover, for a single parity-check code, we use its systematic form introduced in Fossorier et al. ⁹ According to the stages of decomposition processes, the proposed hybrid algorithm exploits different decoding schemes including the Green machine, the Wagner decoding, and the traditional Plotkin recursive algorithm. An FHT is exploited to simplify the ML decoding algorithm of a dual-orthogonal code. We also present a simplified ML decoder for the systematic single parity-check code through its special structure.

In the conventional algorithm, the recursion is ended when the decomposition processes reach at either $R(0,m)$ or $R(m,m)$ . However, the new algorithm ends its recursion at the step $R(1,m)$ and $R(m-1,m)$ , that is, the decomposition processes are ended one step earlier than the conventional one. For example, recursion of $R(2,4)$ will be ended when $R(1,2)$ first appeared as shown in Figure 4. Thus, the new generator matrix for $R(2,4)$ has the structure shown in Figure 5. As it can be observed, the new decomposition has less steps and far sparser generator matrix than the conventional one shown in Figure 1. The new method can provide a good compromise between the decoding complexity and performance.

Figure 4.

An example of the new recursive decomposition path of $R(2,4)$ .

Figure 5.

The improved generator matrix of $R(2,4)$ .

Let $c={\varphi }_{r,m}(a)$ be the encoding algorithm of $R(r,m)$ , where a and c are the input and the output of the encoder, respectively. The algorithm is executed as

Encoder: $c={\varphi }_{r,m}(a)$

$$\begin{array}{c}\begin{array}{c}\mathrm{if}r=1\hfill \\ \multicolumn{1}{c}{c_1=a_1}\end{array}\}\mathrm{Initialization}\hfill \\ (c_{2^{i-1}+1},\dots ,c_{2^i})=(c_1,\dots ,c_{2^{i-1}})\oplus (a_{i+1},\dots ,a_{i+1})\hfill \\ \mathrm{else}\mathrm{if}r=m-1\hfill \\ c=(a,a_1\oplus a_2\oplus \cdots \oplus a_m)\hfill \end{array}$$

$$\begin{array}{c}\mathrm{else}1<r<m-1\hfill \\ \multicolumn{1}{c}{\mathrm{Split\; original\; information}a:}\\ \multicolumn{1}{c}{a=(a^u,a^v)}\\ \multicolumn{1}{c}{u\mathrm{and}v\mathrm{encoding},\mathrm{respectively}}\\ \multicolumn{1}{c}{u={\psi }_{r,m-1}\left(a^u\right)}\\ \multicolumn{1}{c}{v={\psi }_{r-1,m-1}\left(a^v\right)}\end{array}\}\mathrm{Plotkin\; algorithm}$$

$$\begin{array}{c}\mathrm{Merge}u\mathrm{and}v:\hfill \\ c=(u,u\oplus v)\hfill \end{array}$$

In this encoding processes, ⊕ represents modulo-2 addition.

Assume that the coded bit sequence is modulated by binary phase-shift keying (BPSK) in the transmitter and is transmitted in an additive white Gaussian noise (AWGN) environment. We also assume that the transmitted signals are $\mathit{x}(=x_1,x_2,\dots ,x_n)$ . After demodulation, the decoder calculates a posteriori probability of the received signals $y_i$ , $i=1,2,\dots ,n$

$$\mathrm{Pr}[y_i|x_i]=\mathrm{Pr}[c_i=0|x_i]-\mathrm{Pr}[c_i=1|x_i]$$ (9)

Those a posteriori probabilities compose a vector $\mathit{y}=(y_i,\dots ,y_n)$ as the input of the decoding algorithm. We use $[\hat{a},\hat{c}]={\varphi }_{r,m}(\mathit{y})$ as $R(r,m)$ decoding algorithm, where $\hat{a}$ is an information block and $\hat{c}$ is a decoded codeword.

For $1<r\le m-1$ , decoder use $[\hat{a},\hat{c}]={\varphi }_{r-1,m-1}({\mathit{y}}^v)$ for v path decoding and use $[\hat{a},\hat{c}]={\varphi }_{r,m-1}({\mathit{y}}^u)$ for u path decoding, respectively. Then, merge the result of the two decoding paths. At the end of path, for $R(1,m)$ , Green machine is employed for decoding.^2,10 The Green machine produces the ML estimate. We need to transform y to get a log-likelihood ratio (LLR) l as the input of the Green machine

$$l_i=\log \left(\frac{1+y_i}{1-y_i}\right)$$ (10)

• Step 1: Apply the FHT to get the ML estimate instead of the LLR to reduce the computational complexity. ⁴

• Step 2: At the end of u path, for $R(m-1,m)$ , apply the Wagner decoding algorithm ¹⁰ to y .

• Step 3: Compute the decoded output components: $\hat{a}=({\hat{a}}^u,{\hat{a}}^v)$ , $\hat{c}=(\hat{u},\hat{u}\oplus \hat{v})$ .

The algorithm can be implemented as

Decoder: $[\hat{a},\hat{c}]={\varphi }_{r,m}(y)$

1. Green machine for the step 1.

   $$\begin{array}{c}\mathrm{if}r=1\hfill \\ f=(f_1,f_2,\dots ,f_n)=\mathrm{FHT}(y)\hfill \\ i\prime =\arg \underset{1\le i\le 2^m}{\max }|f_i|\hfill \\ ({\hat{a}}_2,{\hat{a}}_3,\dots ,{\hat{a}}_k)\mathrm{is}\mathrm{binary}\mathrm{form}\mathrm{of}i\prime \hfill \\ {\hat{a}}_1=\{\begin{array}{cc}1,\hfill & f_{i\prime }<0\hfill \\ \multicolumn{1}{c}{0,}& f_{i\prime }\ge 0\hfill \end{array}\hfill \end{array}$$

2. Wagner decoder for the step 2.

   $$\begin{array}{c}\mathrm{if}r=m-1\hfill \\ \mathrm{Hard}\mathrm{decision}:{\hat{c}}_{\mathrm{i}}=\{\begin{array}{cc}0,\hfill & y_{\mathrm{i}}>0\hfill \\ \multicolumn{1}{c}{1,}& y_{\mathrm{i}}\le 0\hfill \end{array}\hfill \\ \mathrm{if}{\hat{c}}_1\oplus {\hat{c}}_2\oplus \cdots \oplus {\hat{c}}_{2\mathrm{m}-1}\ne 0\hfill \\ i‴=\arg \underset{1\le \mathrm{i}\le 2^{\mathrm{m}}}{\min }|y_{\mathrm{i}}|\hfill \\ {\hat{a}}_{\mathrm{i}″}=1\oplus {\hat{\mathrm{c}}}_{\mathrm{i}″}\hfill \\ \hat{a}=({\hat{c}}_1,{\hat{c}}_2,\dots ,{\hat{c}}_{\mathrm{k}},)\hfill \end{array}$$

3. Decoding u and v paths for the step 3.

   $$\begin{array}{c}\mathrm{if}1<r<m-1\hfill \\ \mathrm{For}i=1,2,\dots ,2^{m-1}\hfill \\ y_i^v=y_i{y}_{i+2^{m-1}}[{\hat{a}}^v,\hat{v}]={\varphi }_{r-1,m-1}(y^v)\hfill \\ \mathrm{For}i=1,2,\dots ,2^{m-1}\hfill \\ y_i^u=\frac{y_i+{y\prime }_i}{1+y_i{y\prime }_i},\mathrm{and}\hfill \\ {y\prime }_i=\{\begin{array}{cc}{y}_{i+2^{m-1}},\hfill & v_i=0\hfill \\ \multicolumn{1}{c}{-y_{i+2^{m-1}},}& v_i=1\hfill \end{array}\hfill \\ [{\hat{a}}^u,\hat{u}]={\varphi }_{r,m-1}(y):\mathrm{merge}\mathrm{the}\mathrm{results}\hfill \end{array}$$

Performance analysis

Computational complexity

In general, if the recursive algorithm stops decomposition at the end nodes $R(0,m)$ and $R(m,m)$ , the complexity tends to be minimum. Unlike the conventional algorithm, the proposed algorithm exploits a simplified ML decoder to decode a systematic single parity-check code through its special structure. For the analysis on the computational complexity, the number of floating-point operations needed in both algorithms is used as the main measure.

For $1<r<m-1$ , the number of floating-point operations required for step 3 of the hybrid decoding method is computed as

$$\begin{array}{c}|{\varphi }_{r,m}{|}^{*}=|{\varphi }_{r,m-1}{|}^{*}+|{\varphi }_{r-1,m-1}{|}^{*}+\frac{3}{2}\times 2^m\hfill \\ |{\varphi }_{r,m}{|}^{+}=|{\varphi }_{r,m-1}{|}^{+}+|{\varphi }_{r-1,m-1}{|}^{+}+2^m\hfill \end{array}$$ (11)

where, $|\varphi {|}^{*}$ and $|\varphi {|}^{+}$ represent the number of floating-point multiplications and that of additions, respectively.

Since the FHT is exploited, the decoder does not execute additions at the end of v path. $m\times 2^m$ floating-point additions are needed in the FHT and $2^{m-1}$ floating-point additions to find the maximum absolute value of f are required. Thus, the number of floating-point operations needed in the process to find ${\varphi }_{1,m}$ can be expressed as

$$\begin{array}{c}|{\varphi }_{1,m}{|}^{*}=0\hfill \\ |{\varphi }_{1,m}{|}^{+}=m\times 2^m+2^m-1\hfill \end{array}$$ (12)

At the end of u path, $R(m-1,m)$ , decoder makes hard decision and modulo-2 addition. If the result of modulo-2 addition is 0, floating-point operations are not carried out. Otherwise, $2^{m-1}$ floating-point additions must be executed to find the absolute minimum of y . Thus, the number of floating-point operations required are

$$\begin{array}{c}|{\varphi }_{m-1,m}{|}^{*}=0\hfill \\ |{\varphi }_{m-1,m}{|}^{+}=\{\begin{array}{cc}{2}^m-1,\hfill & \mathrm{sum}=1\hfill \\ \multicolumn{1}{c}{0,}& \mathrm{sum}=0\hfill \end{array}\hfill \end{array}$$ (13)

From equations (11)–(13), the number of floating-point operations for decoding $R(r,m)$ is given by

$$\begin{array}{c}|{\varphi }_{r,m}{|}^{*}=\frac{3}{2}\sum _{i=0}^{r-2}\sum _{j=0}^{m-r-2}{C}_{i+j}^j{2}^{m-i-j}\hfill \\ |{\varphi }_{r,m}{|}^{+}=\sum _{i=0}^{r-2}\sum _{j=0}^{m-r-2}{C}_{i+j}^j{2}^{m-i-j}+\hfill \\ \sum _{i=0}^{r-2}{C}_{i+m-r-2}^i(2^{r+1-i}-1)+\hfill \\ \sum _{i=0}^{m-r-2}{C}_{i+r-2}^i[(m-r+2-i)·2^{m-r+1-i}-1]\hfill \end{array}$$ (14)

Equation (14) is satisfied when all checksums in equation (13) equal to 1. The number of floating-point multiplication and that of additions of $R(r,m)$ with respect to the variation of r and m are presented in Tables 1 and 2, respectively.

Table 1.

The number of floating-point multiplications of ${\varphi }_{r,m}$ .

r	m
	2	3	4	5	6	7	8	9	10
1	0	0	0	0	0	0	0	0	0
2		0	24	72	168	360	744	1512	3048
3			0	72	240	600	1344	2856	5904
4				0	168	600	1584	3696	8088
5					0	360	1344	3606	8928
6						0	744	2856	8088
7							0	1512	5904
8								0	3048
9									0

Table 2.

The number of floating-point additions of ${\varphi }_{r,m}$ .

r	m
	2	3	4	5	6	7	8	9	10
1	3	31	79	191	447	1023	2303	5119	11,263
2		7	54	165	420	995	2274	5089	11,232
3			15	101	330	878	2129	4915	11,028
4				31	196	654	1788	4429	10,368
5					63	387	1297	3597	9050
6						127	770	2579	7200
7							255	1537	5140
8								511	3072
9									1023

It is difficult to make out a common relationship between the complexity and codeword length. Hence, the maximum operations of $|{\varphi }_{r,m}{|}^{*}$ and $|{\varphi }_{r,m}{|}^{+}$ have roughly been bounded as

$$\begin{array}{c}|{\varphi }_{r,m}{|}^{*}=3n·\min (r-1,m-r-1)\hfill \\ |{\varphi }_{r,m}{|}^{+}=2n·\min (r-1,m-r-1)+n(m-r+2)\hfill \end{array}$$ (15)

For the v path of ${\varphi }_{r,m}^v$ , the recursion ends at $R(0,m)$ . The computational complexity can be expressed as

$$|{\varphi }_{1,m}^v{|}^{*}=0\mathrm{and}|{\varphi }_{0,m}^v{|}^{+}=2^m$$ (16)

Since the complexity to arrive at the end of u path is the same as that of ${\varphi }_{r,m}$ , the number of floating-point operations for decoding of ${\varphi }_{r,m}^v$ for $0<r<m-1$ is given as

$$\begin{array}{c}|{\varphi }_{r,m}^v{|}^{*}=\frac{3}{2}\sum _{i=0}^{r-1}\sum _{j=0}^{m-r-2}{C}_{i+j}^j{2}^{m-i-j}\hfill \\ |{\varphi }_{r,m}^v{|}^{+}=\sum _{i=0}^{r-1}\sum _{j=0}^{m-r-2}{C}_{i+j}^j{2}^{m-i-j}+\hfill \\ \sum _{i=0}^{m-r}{C}_{i+r-1}^i{2}^{m-r+i}+\sum _{i=0}^{r-2}{C}_{i+m-r-2}^{m-r-2}(2^{(r+1-i)}-1)\hfill \end{array}$$ (17)

Hence, the number of operations needed is bounded by

$$\begin{array}{c}|{\varphi }_{r,m}^v{|}^{*}<3n·\min (r,m-r-1)\hfill \\ |{\varphi }_{r,m}^v{|}^{+}<2n·\min (r,m-r-1)+n\hfill \end{array}$$ (18)

For u path of ${\varphi }_{r,m}^u$ , the recursion ends when $R(m,m)$ appeared. Since the decoder only makes hard decision, neither floating-point multiplications nor floating-point additions is executed. Thus, the complexity is

$$|{\varphi }_{m,m}^u{|}^{*}=0\mathrm{and}|{\varphi }_{m,m}^v{|}^{+}=0$$ (19)

For the case of $1<r<m$ , the number of floating-point operations for ${\varphi }_{r,m}^u$ is

$$\begin{array}{c}|{\varphi }_{r,m}^u{|}^{*}=\frac{3}{2}\sum _{i=0}^{r-2}\sum _{j=0}^{m-r-1}{C}_{i+j}^j\times 2^{m-i-j}\hfill \\ |{\varphi }_{r,m}^u{|}^{+}=\sum _{i=0}^{r-2}\sum _{j=0}^{m-r-1}{C}_{i+j}^j\times 2^{m-i-j}+\hfill \\ \sum _{i=0}^{m-r-2}{C}_{i+r-2}^i[(m-r+2-i)\times 2^{m-r+1-i}-1]\hfill \end{array}$$ (20)

The maximum number of floating-point multiplications and that of additions for decoding of $R(r,10)$ is shown in Figures 6 and 7, respectively, where NAV and NMV represent the number of additions and that of multiplications for v path decoding process, respectively. NAU and NMU are the number of additions and that of multiplications for u path decoding process, respectively. NA and NM are the number of additions and that of multiplications executed in the new decoding process, respectively.

Figure 6.

The maximum number of floating-point multiplications for $R(r,10)$ with respect to the values of r.

Figure 7.

The maximum number of floating-point additions for $R(r,10)$ with respect to the values of r.

It is shown that NAV requires the smallest computational complexity in addition. In the case of multiplication operations, however, the proposed method (NA) has the least complexity. As the multiplication generally affects the computational complexity much more than the addition, the proposed algorithm reduces computational burden significantly. And the maximum number of operations for decoding processes of u path is also bounded by

$$\begin{array}{c}|{\varphi }_{r,m}^u{|}^{*}<3n·\min (r-1,m-r)\hfill \\ |{\varphi }_{r,m}^u{|}^{+}<2n·\min (r-1,m-r)+n(m-r+2)\hfill \end{array}$$ (21)

Error performance

When the ML decoding algorithm is exploited, it is known that step-by-step decompositions of end nodes do not have good performance. Unlike the conventional algorithm, the proposed algorithm stops recursive decompositions one step earlier than the conventional one. In addition, a systematic form is exploited. The systematic codes are known to have better error performance than nonsystematic codes. ⁹ For $R(m-1,m)$ , if the decomposition is continued, the systematic form can be lost.

The u path decoding depends on the results of v path decoding. If there are errors in v path decoding, u path decoding is not likely to obtain correct results. So, v path decoding is much more important than u path decoding in general. One-step earlier end of the recursive decompositions in v path tends to result in better performance than the one in the u path. To evaluate error performance of the proposed decoding algorithm, computer simulation has been carried out. The codedbits are modulated by the BPSK. The transmission environment is AWGN channel with zero-mean and power spectral density of $N_0/2$ . The results of computer simulation for three decoding algorithms applying to decode $R(5,10)$ and $R(7,10)$ are compared in Figure 8, where ${\varphi }_{r,m}$ is the proposed decoding algorithm. ${\varphi }_{r,m}^v$ and ${\varphi }_{r,m}^u$ represent v path and u path decoding algorithm, respectively.

Figure 8.

Bit-error rate of three algorithms.

It can be observed that the proposed decoding algorithm has the best error performance. As it can be expected, the v path decoding method has lower bit-error rate (BER) than the u path decoding method. For the $R(5,10)$ code, to achieve $\mathrm{BER}={10}^{-6}$ , the proposed algorithm requires about 0.2 and 0.8 dB less signal-to-noise ratio (SNR) than the v path and u path algorithm, respectively. In the case of $R(7,10)$ which is a kind of high-rate RM codes, performance differences among three algorithms are enlarged as compared with the ones in a low-rate code $R(5,10)$ .

Conclusion

In this article, an improved recursive decoding algorithm for RM codes is proposed and analyzed. Unlike the conventional algorithms, the recursion processes are ended when $R(1,m)$ and $R(m-1,m)$ appeared. And a systematic decoding is also exploited for the processes of $R(m-1,m)$ . Due to the one-step earlier end of decomposition processes, the proposed algorithm can reduce floating-point multiplication operations significantly. The numerical analysis verifies that the proposed algorithm has much reduced number of floating-point multiplications as compared with two existing algorithms. In addition, the proposed algorithm can provide improved BER as compared with the conventional v path and u path decoding algorithms, respectively.