{'fraction_non_alphanumeric': 0.05332780917995916, 'fraction_numerical': 0.013287561776804475, 'mean_word_length': 3.9295404814004375, 'pattern_counts': {'":': 1, '<': 2, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 24, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Recursive projection-aggregation decoding of Reed-Muller codes

We propose a new class of efficient decoding algorithms for Reed-Muller (RM) codes over binary-input memoryless channels. The algorithms are based on projecting the code on its cosets, recursively decoding the projected codes (which are lower-order RM codes), and aggregating the reconstructions (e.g., using majority votes). We further provide extensions of the algorithms based on list-decoding algorithms and code concatenation.We run our main algorithm for AWGN channels and Binary Symmetric Channels at the short code length (≤ 1024) and low code rate (≤ 0.5) regime. Simulation results show that the new algorithm not only outperforms the previous decoding algorithms for RM codes, it also outperforms the optimal decoder for polar codes (SCL+CRC) with the same parameters by a wide margin. The performance of the new algorithm for RM codes in those regimes is in fact close to that of the maximal likelihood decoder. Finally, the new decoder naturally allows for parallel implementations.

I. INTRODUCTION Reed-Muller (RM) codes are among the oldest families of error-correcting codes [1]. The recent breakthrough of polar codes [2] has brought the attention back to RM codes, due to the closeness of the two codes. RM codes have in particular the advantage of having a simple and universal code construction, and promising performances were demonstrated in several works [3], [4], with a scaling law conjectured to be comparable of that of random codes.
RM codes do not possess yet the generic analytical framework of polar codes (i.e., polarization theory). It was recently shown that RM codes achieve capacity on the Binary Erasure Channel (BEC) at constant rate [5], as well as for extremal rates for BEC and Binary Symmetric Channels (BSC) [6], but obtaining such results for a broader class of communication channels and rates remains open. Recent progress was made on these questions with a polarization approach to RM codes shown in [7].
An important missing component for RM codes is an efficient decoding algorithm that competes with that of polar codes. Various decoding algorithms have been proposed for RM codes, starting with Reed algorithm [1], [8], and three important more recent line of works based on recursive list-decoding [9]- [11], a new Berlekamp-Welch type of algorithm [12], [13], and a new algorithm utilizing minimumweight parity checks [14]. In particular, [9]- [13] give fairly powerful theoretical guarantees for efficient decoding of RM codes in specific regimes. However, there appears to be no known algorithm for RM codes competing with the performance of polar codes in the low rate/blocklength regime [15].
In this paper, we propose a new class of decoding algorithms for Reed-Muller codes over any binaryinput memoryless channels. The new algorithms are based on recursive projections and aggregations of cosets decoding, exploiting the self-similarity of RM codes, and are extended with list-decoding procedures and with outer-code concatenations. The main algorithm significantly improves on the existing algorithms for RM codes [1], [9]- [13] and on the best known decoding algorithm for polar codes [15] for the regimes of interest, i.e., short code length (≤ 1024) and low code rate (≤ 0.5) regime. This is the type of regime where polar codes are planned to enter the 5G standards [16] as well as relevant regimes for applications in the Internet of Things (IoT).
More specifically, we compare our new algorithm for RM codes with the Successive Cancellation List (SCL) decoder for CRC-aided polar codes [15], where we set the list and CRC size to take optimal values 1 . This gives essentially the optimal decoding error probability for polar codes. For AWGN channels, our new algorithm has about 0.75dB gain (more in some cases) over polar codes in the short code length (≤ 1024) and low code rate (≤ 0.5) regime, and similar improvements are also obtained for BSC channels.
In the above regimes, the decoding error probability of our new algorithm is in fact shown to be close to that of the Maximal Likelihood decoder on RM codes. Some extensions and variants to potentially further improve the performance are also discussed, as well as possible extensions of the projection-aggregation and list-decoding procedures to other families of codes.
In Section II, we give a high level description of the new type of algorithms. In Section III, we present decoding algorithm for BSC channels. In Section IV we generalize the algorithms to decode RM codes over any binary-input channel. Finally, in Section V we present simulation results. In addition to the previously mentioned improvements over polar codes, we also empirically validate the improved scaling-law of RM codes over polar codes on BSC channels [17].

II. A HIGH-LEVEL DESCRIPTION OF THE NEW ALGORITHMS
We begin with some notation and background on RM codes. In this paper, we use ⊕ to denote sums over F 2 . Let us consider the polynomial ring F 2 [Z 1 , Z 2 , . . . , Z m ] of m variables. Since Z 2 = Z in F 2 , the following set of 2 m monomials forms a basis of F 2 [Z 1 , Z 2 , . . . , Z m ]: Next we associate every subset A ⊆ [m] with a row vector v m (A) of length 2 m , whose components are indexed by a binary vector z = (z 1 , where In other words, each vector v m (A) consists of all the evaluations of the monomial i∈A Z i at all the points in the vector space E := F m 2 , and each codeword c ∈ RM(m, r) corresponds to an m-variate polynomial with degree at most r. The coordinates of the codeword c are also indexed by the binary vectors z ∈ E, and we write c = (c(z), z ∈ E). Let B be an s-dimensional subspace of E, where s ≤ r. The quotient space E/B consists of all the cosets of B in E, where every coset T has form T = z + B for some z ∈ E. For a binary vector y = (y(z), z ∈ E), we define its projection on the cosets of B as  y ←ŷ 10: end for 11:ĉ ←ŷ 12: returnĉ is the binary vector obtained by summing up all the coordinates of y in each coset T ∈ E/B. Here the sum is over F 2 and the dimension of y /B is n/|B|.
In the next section, we will show that if c is a codeword of RM(m, r), then c /B is a codeword of RM(m − s, r − s), where s is the dimension of B. Our new decoding algorithm makes use of the case s = 1, namely, the one-dimensional subspaces. More precisely, let y = (y(z), z ∈ E) be the output vector of transmitting a codeword of RM(m, r) over some BSC channel. Our decoding algorithm is defined in a recursive way: For every one-dimensional subspace B, we first obtain the projection y /B , and then we use the decoding algorithm for RM(m − 1, r − 1) to decode y /B , where the decoding result is denoted asŷ /B . Since every one-dimensional subspace of E consists of 0 and a non-zero element, there are n − 1 such subspaces in total. After the projection and recursive decoding steps, we obtain n − 1 decoding resultsŷ /B1 ,ŷ /B2 , . . . ,ŷ /Bn−1 . Next we use a majority voting scheme to aggregate these decoding results together with y to obtain a new estimateŷ of the original codeword. Finally we update y asŷ, and iterate the whole procedure for up to N max rounds. Notice that if y =ŷ (see line 6), then y is a fixed (stable) point of this algorithm and will remain unchanged for the next iterations. In this case we should exit the for loop on line 1 (see line [6][7][8]. In practice we set the maximal number of iterations N max = m/2 to prevent the program from running into an infinite loop, and typically m/2 iterations are enough for the algorithm to converge to a stable y. This high-level description is summarized in Fig. 1 and Algorithm 1. While this description focuses on the decoding algorithm over BSC, a natural extension of this algorithm bases on log-likelihood ratios (LLRs) allows us to decode RM codes over any binary-input memoryless channels, including the AWGN channel; see Section IV for details.

A. List decoding procedure and code concatenation
Here we describe a simple and generic list decoding procedure and a code concatenation method that can be composed with any unique decoding method for any code family in order to decrease the decoding error probability. Suppose that we have a unique decoding algorithm decodeC for some code C over some binary-input memoryless channel W : {0, 1} → W. Without loss of generality, assume that decodeC is based on the LLR vector of the channel output, where the LLR of an output symbol x ∈ W is defined as Clearly, if | LLR(x)| is small, then x is a noisy symbol, and if | LLR(x)| is large, then x is relatively noiseless.
Our list decoding procedure works as follows. Suppose that y = (y 1 , y 2 , . . . , y n ) is the output vector when we send a codeword of C over the channel W . We first sort | LLR(y i )|, i ∈ [n] from small to large. Without loss of generality, let us assume that | LLR(y 1 )|, | LLR(y 2 )|, | LLR(y 3 )| are the three smallest components in the LLR vector, meaning that y 1 , y 2 and y 3 are the three most noisy symbols in the channel outputs (we take three arbitrarily). Next we enumerate all the possible cases of the first three bits of the codeword c = (c 1 , c 2 , . . . , c n ): The first three bits (c 1 , c 2 , c 3 ) can be any vector in F 3 2 , so there are 8 cases in total, and for each case we change the value of LLR(y 1 ), LLR(y 2 ), LLR(y 3 ) according to the values of c 1 , c 2 , c 3 . More precisely, we set LLR(y i ) = (−1) ci L max for i = 1, 2, 3, where L max is some large real number. In practice, we can choose L max := max(| LLR(y i )|, i ∈ [n]) or L max := 2 max(| LLR(y i )|, i ∈ [n]). For each of these 8 cases, we use decodeC to obtain a decoded codeword, and we denote them asĉ (1) ,ĉ (2) , . . . ,ĉ (8) . Finally, we calculate the posterior probability of W n (y|ĉ (i) ), 1 ≤ i ≤ 8, and choose the largest one as the final decoding result, namely, we perform a maximal likelihood decoding among the 8 candidates in the list.
When we apply this list decoding procedure together with Algorithm 1 to decode RM codes, the decoding error probability is typically close to that of the Maximal Likelihood decoder.
The list decoding procedure can be further composed with the code concatenation method. More precisely, we first use a (high rate) outer code C out to encode the information bits, and then we encode the codeword of C out by C. In the list decoding procedure above, after obtainingĉ (1) ,ĉ (2) , . . . ,ĉ (8) , we need to check whetherĉ (i) is a codeword of C out or not and only keep it in the list if it belongs to C out . In this way, we can further shrink the list and decrease the decoding error probability. At the same time, this method will also decrease the code rate. In practice, the number of parities (i.e., the difference between code length and dimension) in C out is set to be 1 or 2 in order to obtain best performance, and we can use random codes as C out , i.e., we generate the parity check matrix as i.i.d. Bernoulli-1/2 random variables.

III. DECODING ALGORITHM FOR BSC
We begin with the definition of the quotient code. Then we show that the quotient code of an RM code is also an RM code. The proof of this Lemma is straightforward and can be found in Appendix A. Note that Reed's algorithm [1] relies on the special case of s = r in Lemma 1, and our new decoding algorithm makes use of the case s = 1 in Lemma 1 (in addition to using all subspaces and adding an iterative process). The RPA_RM decoding function is already presented in the previous section. Here we fill in the only missing component, namely the Aggregation function; see Algorithm 2 below. Both are indexed by the cosets T ∈ E/B, and we use [z + B] to denote the coset containing z (see line 3).

Algorithm 2 The Aggregation function for BSC
Here addition is over F 2 5:ŷ ← y 6: returnŷ From line 3, we can see that the maximal possible value of changevote(z) for each z ∈ E is n − 1. Therefore the condition changevote(z) > n−1 2 on line 4 can indeed be viewed as a majority vote. As discussed in Section III-A, this algorithm can be viewed as one step of the power iteration method to find the eigenvector of a matrix built from the quotient code decoding.
In Algorithms 1-2, we write the pseudo codes in a mathematical fashion for the ease of understanding. In Appendix C, we present another version of the RPA_RM function in a program language fashion. Proposition 1. The complexity of Algorithm 1 is O(n r log n) in sequential implementation and O(n 2 ) in parallel implementation with O(n r ) processors.
In Section V-A, we further discuss options to reduce the computation time by using fewer subspaces in the projection step.
Proof. We prove by the induction on the order of the RM code. To establish the base case, observe that the complexity of decoding first-order RM codes using Fast Hadamard Transform (FHT) [8] is O(n log n). Now we assume the proposition holds for decoding (r − 1)-th order RM codes and prove the inductive step. Clearly, the complexity of Algorithm 1 is determined by the complexity of the recursive decoding step on line 3. By induction hypothesis, the complexity of decoding each y /Bi is O(n r−1 log n). Since there are n − 1 one-dimensional subspaces B 1 , B 2 , . . . , B n−1 , the complexity of Algorithm 1 is indeed O(n r log n).
In the next proposition, we show that whether Algorithm 1 outputs the correct codeword or not is independent of the transmitted codeword and only depends on the error pattern imposed by the BSC channel.
Proposition 2. Let c ∈ RM(m, r) be a codeword of the RM code. Let e = (e(z), z ∈ E) be the error vector imposed on c by the BSC channel, and the output vector of the BSC channel is y = c+e. Denote the decoding result asĉ = RPA_RM(y, m, r, N max ). Then the indicator function of decoding error 1[ĉ = c] is independent of the choice of c and only depends on the error vector e.
Notice that we use maximal likelihood decoder for first-order RM code, and the proposition can be proved by induction on the order of the RM code 3 . This proposition is useful for simulations because we can simply transmit the all-zero codeword over the BSC channel to measure the decoding error probability.

A. Spectral interpretations of Algorithm 4
Algorithm 4 can be viewed as a one-step power iteration of a spectral algorithm. More precisely, observe is the transmitted codeword. Suppose for the moment that we want to find aŷ = (ŷ(z), z ∈ E) ∈ {0, 1} n to agree with as many estimates of these sums as possible. This is in fact a reconstruction problem on the following graph model: Consider the complete graph whose vertices are all the points in E. Each vertex z ∈ E is assigned a valueŷ(z). On each edge, we have an estimate of the sum of the values on its two endpoints, so we can build the adjacency matrix A whose dimension is n × n. The rows and columns of A are indexed by z ∈ E, and the entry A z,z is the estimate of c(z) ⊕ c(z ). Now we map all the {0, 1} in this problem to {1, −1}. Ignoring what was the received word y, one would like to find a reconstruction that agrees with the maximal number of constraints, i.e., argmaxŷ ∈{1,−1} nŷ T Aŷ.
If no errors perturb the codeword, then we can satisfy all the constraints by taking any spanning tree of the graph (such as connecting one vertex to all others) and we obtain two solutions: the codeword and its complement. Without a perfect solution, it corresponds to a min-cut problem (on a censored block model [18]) with the following classical spectral relaxation: The solution to this problem is the eigenvector corresponding to the largest eigenvalue. One way to find this eigenvector is to use the power iteration method: pick some vector v (e.g., at random), then A t v converges to this eigenvector when t is large enough. 4 Then one can look at the sign of each coordinate of A t v to determine our final outputŷ (picking the global sign flip so that we are closer to the received word y). In our case, we also want to find a reconstruction that is close to the received word (MAP looks for the closest codeword), so a possibility is to start the power-iteration at y itself. Then, one-step of this iteration gives precisely the voting algorithm described previously. We tried to use the power-iteration method in the Aggregation function for more than one step. However, the performance does not improve over the current version of Aggregation function based on majority vote. This is because in the spectral method above we tried our best to agree withŷ /B1 ,ŷ /B2 ,. . . , y /Bn−1 , ignoring the original channel output y, and many of these are very noisy measurements.
Another possibility would be to use an SDP relaxation, or modify the graph operator as done for community detection algorithms [18].

IV. DECODING ALGORITHM FOR GENERAL BINARY-INPUT MEMORYLESS CHANNELS
The decoding algorithm in the previous section only works for the BSC. In this section, we will present a natural extension of Algorithm 1 that works for any binary-input memoryless channels, and this new algorithm is based on LLRs (see (3)). Similarly to Algorithm 1, this new algorithm is also defined recursively, i.e., we first assume that we know how to decode (r − 1)-th order Reed-Muller code, and then we use it to decode the r-th order Reed-Muller code. To begin with, we need to show how to decode the first order RM code efficiently. We will show that based on LLR, we can also use the Fast Hadamard Transform to implement the Maximum Likelihood (ML) decoder for general binary-input channels, and the complexity is O(n log n), as opposed to the naive implementation of the ML decoder, whose complexity is O(n 2 ).
We still use c = (c(z), z ∈ E) to denote the transmitted (true) codeword and y = (y(z), z ∈ E) to denote the corresponding channel output. Given the output vector y, the ML decoder for first order RM codes aims to find c ∈ RM(m, 1) to maximize z∈E W (y(z)|c(z)). This is equivalent to maximizing the following quantity: which is further equivalent to maximizing Notice that the codeword c is a binary vector. Therefore, .
From now on we will use the shorthand notation L(z) := LLR(y(z)), and the formula in (4) can be written as so we want to find c ∈ RM(m, 1) to maximize this quantity. By definition, every c ∈ RM(m, 1) corresponds to a polynomial in . . , z m are the coordinates of the vector z. Now our task is to find For a binary vector u = (u 1 , u 2 , . . . , u m ) ∈ E, we definê Clearly, to find the maximizer of (6), we only need to calculateL(u) for all u ∈ E, but the vector (L(u), u ∈ E) is exactly the Hadamard Transform of the vector (L(z), z ∈ E), so it can be calculated using the Fast Hadamard Transform with complexity O(n log n). Once we know the values of (L(u), u ∈ E), we can find u * = (u * 1 , u * 2 , . . . , u * m ) ∈ E that maximizes |L(u)|. IfL(u * ) > 0, then the decoder outputs the codeword corresponding to u * 0 = 0, u * 1 , u * 2 , . . . , u * m . Otherwise, the decoder outputs the codeword corresponding to u * 0 = 1, u * 1 , u * 2 , . . . , u * m . This completes the description of how to decode the first order RM codes for general channels.
The next problem is how to extend (2) in the general setting. The purpose of (2) is mapping two output symbols (y(z), z ∈ T ) whose indices are in the same coset T ∈ E/B to one symbol. In this way, we reduce the r-th order RM code to an (r − 1)-th order RM code. For BSC, this mapping is simply the addition in F 2 . The sum y /B (T ) can be interpreted as an estimate of c /B (T ), where c is the transmitted (true) codeword. In other words, where Y is the channel output random vector.
For general channels, we also want to estimate c /B (T ) based on the LLRs (L(z), z ∈ T ). More precisely, given (y(z), z ∈ T ), or equivalently given (L(z), z ∈ T ), we would like to calculate the following LLR: We use the following simplified model to calculate this LLR: Suppose that S 1 and S 2 are i.i.d. Bernoulli-1/2 random variables, and we transmit them over two independent copies of the channel W : {0, 1} → W.
Now replacing x 1 , x 2 with (y(z), z ∈ T ), we obtain that In fact, this model approximates RM codes fairly well because the marginal distribution of each coordinate of the codeword is indeed Bernoulli-1/2 if we pick the codeword uniformly, and intuitively, the correlation between two coordinates is small when the code length is large. Now we are ready to present the decoding algorithm for general binary-input channels. In Algorithms 3-4 below, we still denote the decoding result of the (r − 1)-th order RM code asŷ /B (see line 7 of Algorithm 3), whereŷ /B = (ŷ /B (T ), T ∈ E/B) are indexed by the cosets T ∈ E/B, and we use [z + B] to denote the coset containing z (see line 3 of Algorithm 4).
Algorithm 3 is very similar to Algorithm 1: From line 8 to line 10, we compareL(z) with the original L(z). If the relative difference between these two is below the threshold θ for every z ∈ E, then the values of L(z), z ∈ E change very little in this iteration, and the algorithm reaches a "stable" state, so we can exit the for loop on line 2. In practice, we find that θ = 0.05 works fairly well, and we still set the maximal number of iterations N max = m/2, which is the same as in Algorithm 1. On line 13, the algorithm simply produces the decoding result according to the LLR at each coordinate.
A few explanations of Algorithm 4: On line 3, we set cumuLLR(z) = z =z α(z, z )L(z ), where the coefficients α(z, z ) can only be 1 or −1. More precisely, α(z, z ) is 1 if the decoding result of the corresponding (r − 1)th order RM code at the coset {z, z } is 0, and α(z, z ) is −1 if the decoding result at the coset {z, z } is 1. The reason behind this assignment is simple: The decoding result at the coset {z, z } is an estimate of c(z) ⊕ c(z ). If c(z) ⊕ c(z ) is more likely to be 0, then the sign of L(z) and L(z ) should be the same. Here cumuLLR(z) serves as an estimate of L(z) based on all the other L(z ), z = z, so we assign the coefficient α(z, z ) to be 1. Otherwise, if c(z) ⊕ c(z ) is more likely to be 1, then the sign of L(z) and L(z ) should be different, so we assign the coefficient α(z, z ) to be −1. In Section V-A, we further discuss options to reduce the computation time by using fewer subspaces in the projection step.
Similarly to Proposition 2, we can also show that the decoding error probability of Algorithm 3 is independent of the transmitted codeword for binary-input memoryless symmetric (BMS) channels.
The proof is given in Appendix B. Similarly to Proposition 2, this proposition is also very useful for simulations because we can simply transmit the all-zero codeword over the BMS channel W to measure the decoding error probability.
In the last part of this section, we present the list decoding and code concatenation version of the RPA_RM function. The main idea is already explained in Section II-A. Here we only write down the pseudo code of the list decoding version. Note that the purpose of line 8 is to make sure thatĉ (u) is a codeword of RM code, which is not always true for the decoding result of the RPA_RM function. The list decoding+code concatenation version is rather similar, and we put the pseudo code in Appendix E. (L(z 1 ), L(z 2 ), . . . , L(z t )) ← u 7:ĉ (u) ← RPA_RM(L, m, r, N max , θ) 8 Reedsdecoder is the classical decoding algorithm in [1] 9: end for 10: u * ← argmax u z∈{0,1} m (−1)ĉ (u) (z)L (z) 11: This follows from (5). Maximization is over u ∈ {L max , −L max } t 12:ĉ ←ĉ (u * ) 13: returnĉ V. SIMULATION RESULTS We run our decoding algorithm for second and third order Reed-Muller codes with code length 256, 512 and 1024 over AWGN channels and BSCs, and we compare its performance with the recent algorithms for polar codes with the same length and dimension. We compare to two versions of polar codes: Polar codes with optimal CRC size and polar codes without CRC, and we use the Successive Cancellation List (SCL) decoder introduced by Tal and Vardy [15] as the decoder, where we set list size to be 32. In [15], it was shown that SCL decoder with list size 32 has essentially the same performance as the Maximum Likelihood (ML) decoder for polar codes, so we compared with the optimal decoder for polar codes.
The simulation results for AWGN channels are plotted in Figure 2, where the number of Monte Carlo trials is 10 5 . We can see that our decoding algorithm for RM codes has about 0.75dB gain (sometimes more) over CRC-aided polar codes with SCL decoder, which has the best known performance among various versions of polar codes. Moreover, for certain cases the list decoding version of RPA decoding algorithm has almost the same performance as the Maximal Likelihood (ML) decoder for RM codes 6 . The performance improvement is thus in agreement with the advantages of RM codes over polar codes under ML decoding [4]. We also make comparisons with Dumer's recursive decoding algorithm [9]- [11]. To the best of our knowledge, this is the decoder for RM codes affording best numerical performance over AWGN channels. Due to complexity constraints, Dumer's decoding algorithm can only be applied to the cases in (a),(c),(f) of Fig. 2, and its performance is very close to that of polar codes with optimal CRC size. Note also that the algorithm in [14] only applies to codes with very short code length (no larger than 128) due to complexity constraints.
For the BSC channel, the simulation results are plotted in Figure 3. The number of Monte Carlo trials is 10 5 . We also tested in this case all the previous decoding algorithms known for RM codes, including Reed's algorithm [1], Dumer's recursive decoding algorithm [9]- [11] as well as the algorithm from Saptharishi-Shpilka-Volk [12]. For all these algorithms, the decoding error probability exceeds 0.1 for the tested parameters, so we did not include them in Figure 3 as they would not fit. From Figure 3, we can clearly see that the new decoding algorithm for RM codes significantly outperforms the SCL decoder for polar codes: On average the decoding error probability of our decoder is typically between 100 or 1000 times smaller than that of SCL decoder for polar codes.
We also compare the running time of our decoder and the SCL decoder for polar codes. Note that we use here the most naive implementation of our algorithm, without boosting (i.e., using a subset of the subspaces B 1 , B 2 , . . . , B n−1 in the RPA algorithms) and parallelization. The results are listed in Table I. We can see that for second order RM codes, our decoder is always faster than the SCL decoder for polar codes with the same parameters. However, for third order RM codes, our decoder is slower than the SCL decoder. This is because when we increase the order of RM code by 1, the decoding complexity roughly grows by a factor of n (see Proposition 1) while the decoding complexity of polar codes does not change too much if we only increase the dimension of the code and keep the code length the same. Reducing the number of subspaces would potentially help here. More importantly, the algorithm should be run in parallel fashion as discussed next.   ). We use the same decoders as in Figure 3.

A. Parallelization and acceleration
Another important advantage of the new decoding algorithm for RM codes over the SCL decoder for polar codes is that our algorithm naturally allows parallel implementation while the SCL decoder is not parallelizable. The key step in our algorithm for decoding a codeword of RM(r, m) is to decode the quotient space codes which are in RM(r − 1, m − 1) codes, and each of these can be decoded in parallel. Such a parallel structure is crucial to achieving high throughput and low latency.
Another way to accelerate the algorithm is to use only certain "voting sets": In the projection step, we can take a subset of one-dimensional subspaces instead of all the one-dimensional subspaces. Then we still use recursive decoding followed by the aggregation step. In this way, we decode fewer RM(r − 1, m − 1) codes, and if the voting sets were chosen properly, we would obtain a similar decoding error probability with shorter running time.

B. Optimal scaling and sharp threshold of Reed-Muller codes over BSC channels
Recently, Hassani et al. gave theoretical results backing the conjecture that RM codes have an almost optimal scaling-law over BSC channels under ML decoding [17], where optimal scaling-law means that for a fixed linear code, the decoding error probability of ML decoder transitions from 0 to 1 as a function of the crossover probability of the BSC channel in the sharpest manner (i.e., comparable to random codes). In particular, this implies that RM codes have sharper transition than polar codes under ML decoding (if capacity achieving). In this section we give simulation results that show that for BSC channels, Reed-Muller codes under the RPA decoder also have sharper transition than polar codes under SCL+list decoder.
In Figure 4, we plot the decoding error probability of RM codes and polar codes over BSC channels as a function of the channel crossover probability, where for RM codes we use the RPA decoder in Algorithm 1, and for polar codes we use SCL decoder with list size 32. We can see that in all 4 cases, the transition in the curve of RM codes is sharper than the transition in the curve of polar codes. To further quantify the transition width, we introduce the following common notation: Let us denote the   [11] and Saptharishi-Shpilka-Volk's algorithm [12], the decoding error probability exceeds 0.1 for all the parameters we tested in the figures above. channel crossover probability as . For a given code and a corresponding decoding algorithm, we write its decoding error probability over BSC( ) as P e ( ). For 0 < δ < 1/2, we define the transition width 7 . Clearly, w(δ) is a decreasing function. For a fixed value of δ, smaller w(δ) means sharper transition and better scaling of the code and the corresponding decoder.
In Figure 5, we compare w(0.1) and w(0.01) between RM codes and polar codes with the same parameters, where we use the same decoders as above. We can see that RM codes always have smaller transition width than polar codes. Moreover, within the same code family, the transition width w(0.1) and w(0.01) both decrease with the code length, meaning that the transition becomes sharper as the code length increases. This phenomena has already been proved for ML decoders in [19] and [17].
VI. EXTENSIONS Here we mention a few possible extensions of the decoding algorithms. 1. The "voting sets" idea to further accelerate the RPA decoding, as discussed in Section V-A. 2. Our new algorithms make use of one-dimensional subspace reduction. In practice, we can change the B 1 , . . . , B n−1 in the RPA decoding algorithms to any of the s-dimensional subspaces, with different combinations possible.
3. The RPA decoding algorithms can also be used to decode other codes that are supported on a vector space, or any code that has a well-defined notion of "code projection" that can be iteratively applied to produce eventually a trivial code (that can be decoded efficiently). In the case of RM codes, the quotient space projection has the specificity of producing again RM codes, and the trivial code is the Hadamard code that can be decoded using the FHT.
4. As discussed in Section III-A, we can use spectral decompositions or other relaxations in the Aggregation step instead of the majority voting, and depending on the regimes, one may take multiple iteration of the power-iteration method. Notice that B = {z : (z 1 , z 2 , . . . , z s ) ∈ F s 2 , z s+1 = z s+2 = · · · = z m = 0}. Therefore for every coset T ∈ E/B, the last m − s coordinates under the basis (b 1 , b 2 , . . . , b m ) are the same for all the points in T . As a result, we can use binary vectors of length m − s to label the cosets, i.e.,

APPENDIX B PROOF OF PROPOSITION 4
We need the following technical lemma to prove Proposition 4.
Proof. We prove by induction on r. For the base case r = 1, we use the ML decoder as described at the beginning of this section. More precisely, according to (5),ĉ 2 = RPA_RM(L (2) , m, 1, N max , θ) is the codeword in RM(m, 1) that maximizes i.e., ∀c ∈ RM(m, 1).
Therefore,ĉ 2 ⊕ c 0 is the codeword in RM(m, 1) that maximizes Thus we conclude thatĉ 1 =ĉ 2 ⊕ c 0 . This establishes the base case. For the inductive step, let us assume that the lemma holds for r − 1 and prove it for r. Notice that in Algorithm 3,ĉ(z) is simply determined by the sign of L(z). It is easy to see that if in Algorithm 4, the updated LLR vectorsL (1) andL (2) always satisfy (8), thenĉ 1 =ĉ 2 ⊕ c 0 . Therefore, we only need to prove (8) for the updated LLR vectorsL (1) andL (2) .
Proof of Proposition 4: Since W is a BMS channel, there is a permutation π of the output alphabet W satisfying the two conditions in Definition 3. Since both c 1 and c 2 are codewords of RM(m, r), c 0 := c 1 + c 2 is also a codeword of RM(m, r). Clearly, both channel output vectors Y 1 and Y 2 belong to W n . Now we define a permutation π c0 on W n : For any y = (y(z), z ∈ E) ∈ W n , π c0 (y) := (π c0(z) (y(z)), z ∈ E).
As a result, RPA_RM(L y , m, r, N max , θ) = c 2 . For a vector y ∈ W n and a codeword c ∈ RM(m, r), we use W n (y|c) to denote the probability of outputting y when the transmitted codeword is c. Again by the property of π, it is easy to see that W n (y|c 1 ) = W n (π c0 (y)|c 2 ) ∀y ∈ W n .
Recall that in Proposition 4, we use L (1) and L (2) to denote the random LLR vectors corresponding to the random channel outputs when transmitting c 1 and c 2 , respectively. Therefore, If r = 2, then we use the Fast Hadamard Transform to decode the first-order RM code 9: for each z ∈ E do