Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe next-to-minimal weights of binary projective Reed-Muller codes
142
0
0.0
(
0
)
Added by
Cicero Carvalho
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Projective Reed-Muller codes were introduced by Lachaud, in 1988 and their dimension and minimum distance were determined by Serre and S{o}rensen in 1991. In coding theory one is also interested in the higher Hamming weights, to study the code performance. Yet, not many values of the higher Hamming weights are known for these codes, not even the second lowest weight (also known as next-to-minimal weight) is completely determined. In this paper we determine all the values of the next-to-minimal weight for the binary projective Reed-Muller codes, which we show to be equal to the next-to-minimal weight of Reed-Muller codes in most, but not all, cases.
rate research
Read More
In this paper we present several values for the next-to-minimal weights of projective Reed-Muller codes. We work over $mathbb{F}_q$ with $q geq 3$ since in IEEE-IT 62(11) p. 6300-6303 (2016) we have determined the complete values for the next-to-minimal weights of binary projective Reed-Muller codes. As in loc. cit. here we also find examples of codewords with next-to-minimal weight whose set of zeros is not in a hyperplane arrangement.
The notion of a Private Information Retrieval (PIR) code was recently introduced by Fazeli, Vardy and Yaakobi who showed that this class of codes permit PIR at reduced levels of storage overhead in comparison with replicated-server PIR. In the present paper, the construction of an $(n,k)$ $tau$-server binary, linear PIR code having parameters $n = sumlimits_{i = 0}^{ell} {m choose i}$, $k = {m choose ell}$ and $tau = 2^{ell}$ is presented. These codes are obtained through homogeneous-polynomial evaluation and correspond to the binary, Projective Reed Muller (PRM) code. The construction can be extended to yield PIR codes for any $tau$ of the form $2^{ell}$, $2^{ell}-1$ and any value of $k$, through a combination of single-symbol puncturing and shortening of the PRM code. Each of these code constructions above, have smaller storage overhead in comparison with other PIR codes appearing in the literature. For the particular case of $tau=3,4$, we show that the codes constructed here are optimal, systematic PIR codes by providing an improved lower bound on the block length $n(k, tau)$ of a systematic PIR code. It follows from a result by Vardy and Yaakobi, that these codes also yield optimal, systematic primitive multi-set $(n, k, tau)_B$ batch codes for $tau=3,4$. The PIR code constructions presented here also yield upper bounds on the generalized Hamming weights of binary PRM codes.
Let $G$ be a connected graph and let $mathbb{X}$ be the set of projective points defined by the column vectors of the incidence matrix of $G$ over a field $K$ of any characteristic. We determine the generalized Hamming weights of the Reed--Muller-type code over the set $mathbb{X}$ in terms of graph theoretic invariants. As an application to coding theory we show that if $G$ is non-bipartite and $K$ is a finite field of ${rm char}(K) eq 2$, then the $r$-th generalized Hamming weight of the linear code generated by the rows of the incidence matrix of $G$ is the $r$-th weak edge biparticity of $G$. If ${rm char}(K)=2$ or $G$ is bipartite, we prove that the $r$-th generalized Hamming weight of that code is the $r$-th edge connectivity of $G$.
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.
A projective Reed-Muller (PRM) code, obtained by modifying a (classical) Reed-Muller code with respect to a projective space, is a doubly extended Reed-Solomon code when the dimension of the related projective space is equal to 1. The minimum distance and dual code of a PRM code are known, and some decoding examples have been represented for low-dimensional projective space. In this study, we construct a decoding algorithm for all PRM codes by dividing a projective space into a union of affine spaces. In addition, we determine the computational complexity and the number of errors correctable of our algorithm. Finally, we compare the codeword error rate of our algorithm with that of minimum distance decoding.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
