اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGeneralized Hamming weights of projective Reed--Muller-type codes over graphs
208
0
0.0
(
0
)
نشر من قبل
Rafael Villarreal H
تاريخ النشر
2018
مجال البحث
الهندسة المعلوماتية
والبحث باللغة
English
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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$.
قيم البحث
اقرأ أيضاً
We give a polynomial time algorithm to decode multivariate polynomial codes of degree $d$ up to half their minimum distance, when the evaluation points are an arbitrary product set $S^m$, for every $d < |S|$. Previously known algorithms can achieve t
his only if the set $S$ has some very special algebraic structure, or if the degree $d$ is significantly smaller than $|S|$. We also give a near-linear time randomized algorithm, which is based on tools from list-decoding, to decode these codes from nearly half their minimum distance, provided $d < (1-epsilon)|S|$ for constant $epsilon > 0$. Our result gives an $m$-dimensional generalization of the well known decoding algorithms for Reed-Solomon codes, and can be viewed as giving an algorithmic version of the Schwartz-Zippel lemma.
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 perfor
mance. 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.
We study affine cartesian codes, which are a Reed-Muller type of evaluation codes, where polynomials are evaluated at the cartesian product of n subsets of a finite field F_q. These codes appeared recently in a work by H. Lopez, C. Renteria-Marquez a
nd R. Villareal and, in a generalized form, in a work by O. Geil and C. Thomsen. Using methods from Grobner basis theory we determine the second Hamming weight (also called next-to-minimal weight) for particular cases of affine cartesian codes and also some higher Hamming weights of this type of code.
Projective Reed-Muller codes correspond to subcodes of the Reed-Muller code in which the polynomials being evaluated to yield codewords, are restricted to be homogeneous. The Generalized Hamming Weights (GHW) of a code ${cal C}$, identify for each di
mension $ u$, the smallest size of the support of a subcode of ${cal C}$ of dimension $ u$. The GHW of a code are of interest in assessing the vulnerability of a code in a wiretap channel setting. It is also of use in bounding the state complexity of the trellis representation of the code. In prior work by the same authors, a code-shortening algorithm was employed to derive upper bounds on the GHW of binary projective, Reed-Muller (PRM) codes. In the present paper, we derive a matching lower bound by adapting the proof techniques used originally for Reed-Muller (RM) codes by Wei. This results in a characterization of the GHW hierarchy of binary PRM codes.
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-mini
mal 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.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
