Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userReed-Muller Codes: Theory and Algorithms
115
0
0.0
(
0
)
Added by
Emmanuel Abbe
Publication date
2020
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Reed-Muller (RM) codes are among the oldest, simplest and perhaps most ubiquitous family of codes. They are used in many areas of coding theory in both electrical engineering and computer science. Yet, many of their important properties are still under investigation. This paper covers some of the recent developments regarding the weight enumerator and the capacity-achieving properties of RM codes, as well as some of the algorithmic developments. In particular, the paper discusses the recent connections established between RM codes, thresholds of Boolean functions, polarization theory, hypercontractivity, and the techniques of approximating low weight codewords using lower degree polynomials. It then overviews some of the algorithms with performance guarantees, as well as some of the algorithms with state-of-the-art performances in practical regimes. Finally, the paper concludes with a few open problems.
rate research
Read More
In this article we count the number of generalized Reed-Solomon (GRS) codes of dimension k and length n, including the codes coming from a non-degenerate conic plus nucleus. We compare our results with known formulae for the number of 3-dimensional MDS codes of length n=6,7,8,9.
The well known Plotkin construction is, in the current paper, generalized and used to yield new families of Z2Z4-additive codes, whose length, dimension as well as minimum distance are studied. These new constructions enable us to obtain families of Z2Z4-additive codes such that, under the Gray map, the corresponding binary codes have the same parameters and properties as the usual binary linear Reed-Muller codes. Moreover, the first family is the usual binary linear Reed-Muller family.
The famous Barnes-Wall lattices can be obtained by applying Construction D to a chain of Reed-Muller codes. By applying Construction ${{D}}^{{(cyc)}}$ to a chain of extended cyclic codes sandwiched between Reed-Muller codes, Hu and Nebe (J. London Math. Soc. (2) 101 (2020) 1068-1089) constructed new series of universally strongly perfect lattices sandwiched between Barnes-Wall lattices. In this paper, we explicitly determine the minimum weight codewords of those codes for some special cases.
Reed-Muller codes are some of the oldest and most widely studied error-correcting codes, of interest for both their algebraic structure as well as their many algorithmic properties. A recent beautiful result of Saptharishi, Shpilka and Volk showed that for binary Reed-Muller codes of length $n$ and distance $d = O(1)$, one can correct $operatorname{polylog}(n)$ random errors in $operatorname{poly}(n)$ time (which is well beyond the worst-case error tolerance of $O(1)$). In this paper, we consider the problem of `syndrome decoding Reed-Muller codes from random errors. More specifically, given the $operatorname{polylog}(n)$-bit long syndrome vector of a codeword corrupted in $operatorname{polylog}(n)$ random coordinates, we would like to compute the locations of the codeword corruptions. This problem turns out to be equivalent to a basic question about computing tensor decomposition of random low-rank tensors over finite fields. Our main result is that syndrome decoding of Reed-Muller codes (and the equivalent tensor decomposition problem) can be solved efficiently, i.e., in $operatorname{polylog}(n)$ time. We give two algorithms for this problem: 1. The first algorithm is a finite field variant of a classical algorithm for tensor decomposition over real numbers due to Jennrich. This also gives an alternate proof for the main result of Saptharishi et al. 2. The second algorithm is obtained by implementing the steps of the Berlekamp-Welch-style decoding algorithm of Saptharishi et al. in sublinear-time. The main new ingredient is an algorithm for solving certain kinds of systems of polynomial equations.
New quaternary Plotkin constructions are given and are used to obtain new families of quaternary codes. The parameters of the obtained codes, such as the length, the dimension and the minimum distance are studied. Using these constructions new families of quaternary Reed-Muller codes are built with the peculiarity that after using the Gray map the obtained Z4-linear codes have the same parameters and fundamental properties as the codes in the usual binary linear Reed-Muller family. To make more evident the duality relationships in the constructed families the concept of Kronecker inner product is introduced.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
