Sparse Multi-Decoder Recursive Projection Aggregation for Reed-Muller Codes

Reed-Muller (RM) codes are one of the oldest families of codes. Recently, a recursive projection aggregation (RPA) decoder has been proposed, which achieves a performance that is close to the maximum likelihood decoder for short-length RM codes. One of its main drawbacks, however, is the large amount of computations needed. In this paper, we devise a new algorithm to lower the computational budget while keeping a performance close to that of the RPA decoder. The proposed approach consists of multiple sparse RPAs that are generated by performing only a selection of projections in each sparsified decoder. In the end, a cyclic redundancy check (CRC) is used to decide between output codewords. Simulation results show that our proposed approach reduces the RPA decoder's computations up to $80\%$ with negligible performance loss.


I. INTRODUCTION
Reed-Muller (RM) codes were introduced by Muller [1] in 1954. Shortly after, Reed proposed a majority logic decoding algorithm [2] correcting errors up to half of its minimum distance. Since then, many approaches for decoding RM codes have been investigated. An overcomplete minimum weight parity check matrix is used in [3] to exploit the redundant code constraints; recursive list decoding in [4]- [6] achieves a performance close to maximum likelihood (ML) decoding with list size at-most 1024 for short block lengths; and the Sidel'nikov-Pershakov algorithm [7] decodes secondorder RM codes of length ≤ 1024 by exploiting derivatives of the received codeword and majority voting. Additionally, Sakkour's [8] variant of [7] simplifies the majority voting leading to achieving a smaller decoding error probability.
Recently, RM codes have received a great deal of attention. One reason for this surge of interest is their close connection to polar codes, a family of error-correcting codes that provably achieves capacity for any binary-input memoryless symmetric channel [9]. This connection was already mentioned in the seminal paper [9], and it was exploited to design a family of interpolating codes with improved performance at practical block lengths in [10]. Furthermore, it has been shown that, under ML decoding, RM codes achieve capacity on erasure channels [11]. Achieving similar results for a more general class of channels is a long-standing conjecture.
In general, ML decoding is not computationally efficient. This has spurred research on finding an efficient algorithm. D Many approaches taking advantage of different aspects of RM codes have been exploited recently. In [12], minimum-weight parity checks are employed taking advantage of the large automorphism group of RM codes. Berlekamp-Welch type algorithms on random errors and erasures are considered and analyzed in [13], [14]. Successive cancellation (SC) decoding [9] and SC list (SCL) decoding [15], initially proposed for polar codes, are also applicable to RM codes as they share a similar construction. An algorithm based on successive factor graph permutations is presented in [16]. For a thorough review on RM codes, we refer the reader to [17].
Most recently, a recursive projection aggregation (RPA) [18] decoder has been proposed. The RPA decoder uses projections of the codeword on its index space cosets in order to obtain valid RM codewords of smaller length. Then, the smaller codewords are recursively decoded and aggregated. RPA decoding performs close to ML decoding up-to length 1024 for second-order RM codes and also benefits from a parallel implementation. A recursive puncturing aggregation (RXA) decoder is presented in [19], and it is a modification of RPA decoding using puncturing instead of projections, built for high-rate codes.
In this paper, we focus on the RPA decoding algorithm. The near ML decoding performance benefits of the RPA decoder comes with the need for a large computational budget. We propose an optimized version of RPA decoding, namely a sparse RPA with multiple decoders (SRPA). The new method chooses a subset of recursions for each decoder at random. When combined, these smaller decoders can perform close to RPA decoding while requiring a significantly smaller computational budget.
We compare the proposed SRPA method with RPA decoding on code lengths ≤ 512. The results show that by using only two sparse decoders, one can achieve almost the same performance at 20% of the computational budget of RPA decoding. Also, the performance of SRPA is compared with SCL decoding while fixing the computational budget. The results indicate that for second-order RM codes, the performance of the proposed SRPA is more stable, staying relatively close to the performance of ML decoding as the block length increases.
The rest of the paper is organized as follows. In Section II, we give the basic definition of RM codes and the description of the RPA decoder. In Section III, we discuss the problem formulation and the proposed method. In Section IV, we present the simulation results. Finally, in Section V, we draw the main conclusions of the paper.

A. Reed-Muller Codes
There are many approaches to describing RM codes. Here we define them by using low-degree polynomials following the notations of [18].
as the polynomial ring of m variables. Since Z 2 = Z in F 2 , then the following set of monomials with size 2 m forms a basis for where [m] := {1, 2, . . . , m} and i∈∅ Z i := 1.

B. Recursive Projection Aggregation Decoder
For a binary-input memoryless channel W : {0, 1} → W the log-likelihood ratio (LLR) of the channel output is defined as Given L as a vector corresponding to the LLR values of the channel output, the RPA decoder obtains codewords of a shorter length by projecting L onto the cosets of the index subspaces. The shorter codewords are decoded recursively. Later, the results are aggregated via a voting procedure to estimate the original codeword.
Let E := F m 2 and let each codeword correspond to an mvariate polynomial of degree at-most r. Then, the coordinates of the codeword c ∈ RM(m, r) are indexed by the binary vectors z ∈ E, i.e., c = (c(z), z ∈ E). Definition 2 (Projection): Let B be an s-dimensional (s ≤ r) subspace of E and E/B be the set of all cosets of B in E; in other words, ∀T ∈ E/B , T = z + B for some z ∈ E. The projection of the codeword y on the cosets of B for the binary symmetric channel (BSC) is defined as where For general binary-input channels having vector L as LLR values of the noisy codeword, the definition above is modified into Note that, from Lemma 1 in [18], we have that if y ∈ RM(m, r), then y /B ∈ RM(m − s, r − s).
The RPA algorithm is obtained by setting s = 1. In this case, at level i in the recursion, each codeword will make 2 n−i − 1 branches. After obtaining the estimated codewords for each branch, the results are aggregated using the voting algorithm below.
Definition 3 (Aggregation/Voting Algorithm): Let L be the output LLRs,ŷ Bi be the decoded codeword corresponding to the cosets of the one dimensional subspaces B i = {0, z i }, z i ∈ F m 2 , andL be the final estimation. For each bit index z ∈ {0, 1} m , the estimation is computed aŝ where [z + B i ] is defined as the coset containing z. One way to look at (8) is that for a one dimensional is more likely to be 1, then their sign of LLR values should be different. On the other hand, if the sum is more likely to be 0, then their LLR values should also have the same sign. Fig. 1 shows an example of this procedure on RM(3, 2) and cosets of B 1 .
The algorithm starts from RM(m, r) and recursively decodes RM(m − 1, r − 1) until reaching RM(m − r + 1, 1). For first-order RM codes, the ML decoder has complexity O(n log n) and can be implemented using the Fast Hadamard Transform (FHT) [20]. According to Algorithm 3 in [18], the RPA decoding algorithm is iterative, in the sense that it repeats the procedure above at most m 2 times until it reaches a fixed point where |L(z) −L(z)| ≤ , ∀z ∈ F m 2 , for some small assigned constant .

III. SPARSE RECURSIVE PROJECTION AGGREGATION
Although the RPA decoding algorithm performs well on RM codes with respect to the block error rate (BLER), it requires significant computing power. Given an r-th order RM code of block length n, the algorithm runs in O(n r log n) time for a sequential implementation and in O(n 2 ) time for a parallel implementation using O(n r ) processors. That is because at the i-th level of recursion, the RPA decoder uses n2 −i − 1 recursive calls to vote for each sub-code. As we will see in Section III-A, having this amount of recursive calls is redundant for obtaining a reliable vote. Our goal is to achieve the same error probability to that of the RPA decoder using lower computational power. We will achieve this goal by reducing the number of recursive calls.

A. Random Selection of Recursions
In order to reduce the amount of computation required, several recursions are chosen at random to be kept and the rest are removed to generate a sparse decoder as defined below.
Definition 4: A sparse decoder D S (SRPA) that has at most t iterations and q recursions/subspaces per iteration, performs only a subset S = {s 1,1 , . . . , s t,q } of possible projections, where s i,j is the j-th chosen subspace in the i-th iteration that the codeword is projected on.
Definition 4 suggests that the aggregation formula in (8) for each z ∈ {0, 1} m is modified tô where S i = {s i,1 , s i,2 , . . . , s i,q } is the subset of S corresponding to the i-th iteration of SRPA decoding. The simulation results for RM(7, 2) in Fig. 2 show that removing up to half of the recursions causes a negligible loss in performance, which confirms the high redundancy of the RPA decoding algorithm. However, if only 1/4 of the projections are kept, the error probability starts to degrade. The reason for this degradation is that each projection estimates certain codewords more reliably and by removing a large fraction of recursions, it is more likely to miss the suitable projections.

B. Choice of Multiple Decoders
The loss of performance that is caused by the pruning method in SRPA can be compensated by using multiple SRPA decoders. The idea is that the low-complexity decoders work well for a subset of errors. Choosing multiple low-complexity decoders at random will improve the error probability of SRPA while having lower complexity than RPA decoding.
Let us select k sparse decoders D S1 , D S2 , . . . , D S k at random. We call this set of k SRPA decoders the k-SRPA decoder. The input LLR L is individually decoded by each of the k SRPA decoders resulting in estimationsL 1 ,L 2 , . . . ,L k . The final estimation is then chosen via one of the following methods: 1) Most likely codeword: The most likely codeword is chosen by computing argmax i L i , L , where ·, · denotes the scalar product.
2) CRC verification: The final codeword is chosen by first checking the CRC condition and then choosing the most likely codeword among the codewords satisfying the CRC condition.
Note that lower levels of recursions can only use the first approach in this setting, as projections do not allow the concatenation of CRC at these levels.

IV. SIMULATION RESULTS
The proposed SRPA is tested on RM codes of up to third order, with block lengths 128, 256, and 512. The performance of the proposed method is compared with the original RPA decoding algorithm. In the implementation of SRPA, the 3-bit CRC (CRC-3-GSM: x 3 + x + 1) is used to select the final codeword.
Note that each projection and aggregation has complexity Θ(n), and the decoding of first-order RM codes has complexity Θ(n log n) since it is equivalent to performing an FHT. These operations are exactly the same in both RPA decoding and SRPA decoding. The difference lies in the number of operations performed, and we elaborate on this difference for RM codes of second and third order below.
In order to decode RM(m, r), we denote by q i , t i and d i the number of projections, iterations, and decoders used by SRPA for the sub-code RM(m − i, r − i). Then, in order to decode RM(m, 2), the total number of projections, aggregations, and FHTs is d 0 t 0 q 0 . Furthermore, in order to decode RM(m, 3), we need d 0 t 0 q 0 + d 0 t 0 q 0 d 1 t 1 q 1 projections, d 0 t 0 q 0 + d 0 t 0 q 0 d 1 t 1 q 1 aggregations, and d 0 t 0 q 0 d 1 t 1 q 1 FHTs. Recall that the complexity of the FHT has an extra log n factor with respect to projections and aggregation. Note also thatin our experimental setting -d 0 t 0 q 0 is much smaller than d 0 t 0 q 0 d 1 t 1 q 1 . Thus, in order to compare the computational budget of RPA and SRPA, it suffices to count the number of FHTs executed by the two algorithms.
In the implementations in this paper, we use two randomlyselected decoders. For second-order RM codes, each of the decoders keep 1 8 of the recursions chosen uniformly at random. For second-order RM codes, having at most 8 SRPAs, we can achieve a performance better than RPA decoding or even approach the ML bound.
Thus, SRPA roughly leads to a 4× speed-up with respect to the original RPA decoding. For third order RM codes, 1 8 of the first level recursions are chosen. When the recursions reach RM(m−1, 2), four decoders are used instead of two to avoid an increase in the error rate. This leads to a factor of 1 8 × 1 2 reduction in the number of FHTs. Thus, SRPA roughly leads to an 8× speed-up. Fig. 3 shows the BLER of different decoders as a function of the SNR (E b /N 0 ). It is visible that the 2-SRPA decoder has close performance to that of RPA decoder. In addition, by adding more decoders to the 2-SRPA decoder for second-order RM codes, one can gain considerable improvement in the error probability and approach the performance of ML decoding. Table I provides a detailed comparison of the number of FHTs used by 2-SRPA and RPA. We report (i) the average number of FHTs used for RPA decoding at different E b /N 0 levels where the early stopping condition is the same as [18], (ii) the number of FHTs used by RPA when there is no early stopping (see the column Full Rounds), and (iii) the number of FHTs required for SRPA decoding. As SRPA decoding does not necessarily converge to a fixed point, it runs for a fixed number of iterations and does not require a comparison at different E b /N 0 levels. The last column of Table I provides the savings in the number of FHTs guaranteed by 2-SRPA when compared to the RPA decoder with no early stopping (Full Rounds). It can be seen that the proposed SRPA decoder can save up to 87% of the FHT operations with respect to RPA decoding. When comparing with the average number of FHT operations in RPA decoding at different E b /N 0 levels, the 2-SRPA decoder leads to a saving between 50% and 79% of RPA's computational budget, while having little to no performance loss. Fig. 4 compares the performance of 2-SRPA decoding with SCL decoding. Recall that, given an RM code of order r, decoding each of its first-order RM sub-codes takes 2 −(r−1) n log(2 −(r−1) n) operations. Furthermore, SCL decoding has complexity Ln log n, where L is the list size. Thus, in our comparison, we assume that the decoding complexity of SCL with list size L is roughly the same as SRPA using 2 r−1 L FHTs. For second-order RM codes, the list size for each code is chosen such that either the computational budget of SCL is roughly the same as that of SRPA, or SCL reaches the ML decoding bound with less computation. It is visible that the performance of SCL decoding deteriorates quickly as  (8,2) and RM(9, 2), SRPA yields a performance improvement while requiring the same computational budget; for third-order RM codes, SCL performs better than RPA methods. the block length increases: for N = 128 and N = 256, SCL slightly improves upon SPRA using the same computational budget; However, for N = 512, SRPA provides a significant improvement. This fact does not hold for third-order RM codes. As seen in plots for RM (7,3) and RM (8,3), the SCL decoder with list size 32 and 1024, respectively, outperforms RPA methods, while requiring a much smaller computational budget.

V. CONCLUSIONS
RPA decoding incorporates the algebraic structure of RM codes by using projections. By sparsifying the decoder on each iteration, this paper suggests that there exist more efficient ways to utilize these projections to lower the computational power required. Future work includes determining whether there exists a strategy for choosing the recursions that minimizes the error probability.