Appears in collection : ALCOCRYPT - ALgebraic and combinatorial methods for COding and CRYPTography
Projective Reed Muller Codes constitute an interesting class of linear codes, which was introduced by Gilles Lachaud in 1988. Questions about their minimum distance are intimately related to the question about the maximum possible number of F-rational points in the m-dimensional projective space on a hypersurface of degree d in m+1 variables with coefficients in a finite field F. Michael Tsfasman gave a conjectural formula for this maximum possible number of points on such hypersurfaces, and the conjecture was soon proved in the affirmative by Jean-Pierre Serre. In all these works, it is generally assumed that the degree d is at most q, where q is the number of elements in F. Anders Sørensen considered in 1991 more general projective Reed Muller codes where d can be larger than q. From a coding theoretical perspective, it is more natural to consider this larger class. Sørensen proposed a formula for the minimum distance in the general case, and also studied the duals of the projective Reed-Muller codes.
We shall revisit the work of Sorensen by pointing out some minor inaccuracies in his proof of the minimum distance. We then propose an alternative proof. Further, we address the question of obtaining a characterization of the minimum weight codewords of projective Reed Muller codes.
This is a joint work with Rati Ludhani.