Weighted Reed–Muller codes revisited

We consider weighted Reed–Muller codes over point ensemble S ₁ × · · · × S _m where S _i needs not be of the same size as S _j . For m = 2 we determine optimal weights and analyze in detail what is the impact of the ratio |S ₁|/|S ₂| on the minimum distance. In conclusion the weighted Reed–Muller code construction is much better than its reputation. For a class of affine variety codes that contains the weighted Reed–Muller codes we then present two list decoding algorithms. With a small modification one of these algorithms is able to correct up to 31 errors of the [49,11,28] Joyner code.     

Minimal codewords in Reed–Muller codes

Minimal codewords were introduced by Massey (Proceedings of the 6th Joint Swedish-Russian International Workshop on Information Theory, pp 276–279, 1993) for cryptographical purposes. They are used in particular secret sharing schemes, to model the access structures. We study minimal codewords of weight smaller than 3 · 2 ^m−r in binary Reed–Muller codes RM(r, m) and translate our problem into a geometrical one, using a classification result of Kasami and Tokura (IEEE Trans Inf Theory 16:752–759, 1970) and Kasami et al. (Inf Control 30(4):380–395, 1976) on Boolean functions. In this geometrical setting, we calculate numbers of non-minimal codewords. So we obtain the number of minimal codewords in the cases where we have information about the weight distribution of the code RM(r, m). The presented results improve previous results obtained theoretically by Borissov et al. (Discrete Appl Math 128(1), 65–74, 2003), and computer aided results of Borissov and Manev (Serdica Math J 30(2-3), 303–324, 2004). This paper is in fact an extended abstract. Full proofs can be found on the arXiv.     

On low weight codewords of generalized affine and projective Reed–Muller codes

We propose new results on low weight codewords of affine and projective generalized Reed–Muller (GRM) codes. In the affine case we prove that if the cardinality of the ground field is large compared to the degree of the code, the low weight codewords are products of affine functions. Then, without this assumption on the cardinality of the field, we study codewords associated to an irreducible but not absolutely irreducible polynomial, and prove that they cannot be second, third or fourth weight depending on the hypothesis. In the projective case the second distance of GRM codes is estimated, namely a lower bound and an upper bound on this weight are given.     

Projective Reed–Muller type codes on rational normal scrolls

In this paper we study an instance of projective Reed–Muller type codes, i.e., codes obtained by the evaluation of homogeneous polynomials of a fixed degree in the points of a projective variety. In our case the variety is an important example of a determinantal variety, namely the projective surface known as rational normal scroll, defined over a finite field, which is the basic underlining algebraic structure of this work. We determine the dimension and a lower bound for the minimum distance of the codes, and in many cases we also find the exact value of the minimum distance. To obtain the results we use some methods from Gröbner bases theory.     

On Maximal Distance Separable Codes

ＯｎＭａｘｉｍａｌＤｉｓｔａｎｃｅＳｅｐａｒａｂｌｅＣｏｄｅｓ￥（万哲先，谢邦杰）ＷａｎＺｈｅｉｘａｎ（ＩｎｓｔｉｔｕｔｅｏｆＳｙｓｔｅｍｓＳｃｉｅｎｃｅ，ＣｈｉｎｅｓｅＡｃａｄｅｍｙｏｆＳｃｉｅｎｃｅ，Ｂｅｉｊｉｎｇ，１０００８０，Ｃｈｉｎａ）ａｎ...     

Simple algorithms for decoding systematic Reed–Solomon codes

A simple algorithm for decoding nonsystematic Reed–Solomon codewords was proposed by A. Shiozaki and independently by S. Gao. We first exhibit the companion algorithm for decoding systematic Reed–Solomon codes. Next, we improve this algorithm into one that is identical to traditional Reed–Solomon decoding. The algorithm will then be adjusted to work with nonstandard Reed–Solomon codes. Finally, we modify the algorithm into one that decodes Reed–Solomon codes with erasures that is slightly more efficient than existing techniques.     

Reverse–Complement Similarity Codes

We discuss a general notion of similarity function between two sequences which is based on their common subsequences. This notion arises in some applications of molecular biology [A.G. D'yachkov, P.L. Erdos, A.J. Macula, V.V. Rykov, D.C. Torney, C.-S. Tung, P.A. Vilenkin, and P.S. White, Exordium for DNA codes, Journal of Combinatorial Optimization 7 (4) (2003)]. We introduce the concept of similarity codes and study the logarithmic asymptotics for the size of optimal codes. Our mathematical results announced in [A.G. D'yachkov, D.C. Torney, P.A. Vilenkin, and P.S.White, On a class of codes for the insertion-deletion metric, Proc. of ISIT–2002, Lausanne, Switzerland, July 2002] correspond to the longest common subsequence (LCS) similarity function [V.I. Levenshtein, Binary codes capable of correcting deletions, insertions, and reversals, J. Soviet Phys.—Doklady, 10, 707–710, 1966] which leads to a special subclass of these codes called reverse-complement (RC) similarity codes. RC codes for additive similarity functions have been studied in previous papers [A.G. D'yachkov and D.C. Torney, On similarity codes, IEEE Trans. Inform. Theory 46 (4) (2000) 1558–1564], [A.G. D'yachkov, D.C. Torney, P.A. Vilenkin, and P.S. White, Reverse– complement similarity codes for DNA sequences, Proc. of ISIT–2000, Sorrento, Italy, July 2000], [P.A. Vilenkin, Some asymptotic problems of combinatorial coding theory and information theory (in Russian), Ph.D. dissertation, Moscow State University, 2000], [V.V. Rykov, A.J. Macula, C.M.Korzelius, D.C. Engelhart, D.C. Torney, and P.S. White, DNA sequences constructed on the basis of quaternary cyclic codes, Proc. of 4-th World Multiconference on Systemics, Cybernetics and Informatics, Orlando, Florida, USA, July 2000].     

On Algebraic Structures Related to Beltrami–Klein Model of Hyperbolic Geometry

A new approach to the algebraic structures related to hyperbolic geometry comes from Einstein’s special theory of relativity in 1988 (cf. Ungar, in Found Phys Lett 1:57–89, 1988). Ungar employed the binary operation of Einsteins velocity addition to introduce into hyperbolic geometry the concepts of vectors, angles and trigonometry in full analogy with Euclidean geometry (cf. Ungar, in Math Appl 49:187–221, 2005). Another approach is from Karzel for algebraization of absolute planes in the sense of Karzel et al. (Einführung in die Geometrie, 1973). In this paper we are going to develop a formulary for the Beltrami–Klein model of hyperbolic plane inside the unit circle ${\mathbb D}$ of the complex numbers ${\mathbb C}$ with geometric approach of Karzel.     

On the Classification of Self-Dual Codes over 𝔽5

 In this paper, we give the classification of self-dual 𝔽₅-codes of lengths 14 and 16. Up to equivalence, there are 53 and 535 such codes, respectively. It is also shown that there is no self-dual [18, 9, 8] code over 𝔽₅. Received: June 18, 2001 Final version received: April 9, 2002 RID="*" ID="*" Supported in part by the Academy of Finland under grants 44517 and 100500