Reed-Muller Codes: Spherically-Punctured Codes and Decoding Algorithms

Reed-Muller (RM) codes are classical codes that have enjoyed unabated interest since their introduction in 1954 due to their simple recursive structure and low-complexity decoding. The main goal of the thesis is to develop new coding techniques that can improve the performance of RM codes. In this work, we wish to keep the recursive low-complexity structure of RM codes while extending the sets of possible parameters and decoding algorithms. We address this task using two different methods. First, we consider new code constructions that extend code parameters using puncturing. Second, we design new decoding algorithms that repeatedly use the gradient properties of the classic recursive structure to improve code performance of RM codes.;In the first part of the thesis, we propose a new class of codes that enjoy the recursive structure of RM codes, but reduce the exponential length of RM codes to a polynomial in m. These codes are obtained by puncturing classical RM codes, i.e. by restricting binary RM codes to small subsets of their positions. We study new recursive properties of these codes and analyze their parameters.;In the second part of the thesis we develop new decoding algorithms for binary RM codes of second order that achieve near optimal performance for short and moderate code lengths. RM codes enjoy some simple decoding procedures; however, these algorithms fall short of optimal performance on moderate block lengths. We propose a suboptimal algorithm that reduces the complexity of maximum-likelihood decoding from super-polynomial order O(n (m+1)/2) to polynomial order O(mn2) . At the same time, our numerical simulations show that the new algorithm performs very closely to its maximum-likelihood counterpart for blocks of up to several thousand bits.