MDS conjecture

所需积分/C币:15 2019-02-23 01:08:14 157KB PDF
收藏 收藏

The latest introduction of MDS conjecture, from a french sicentist
la: Introduction-The Singleton Bound Singleton Bound. k< n-d+1, for any [n, k, d] code Proof Any 2 codewords disagree in the first n-d+l coordinates somewhere, so there are gn-d+i in total L Linear codes achieving equality are called Maximum Distance Sepa rable(MDs)codes. a general question given d and k, what is the greatest length n of an MDs code? 1b: MDS codes and generic subsets of Fk List k rows generating mds code c as a k x n matrix A Claim. The columns of a give rise to a set s of n vectors, such that any k=n-d+l of them are Ll. We call such an s generic Proof. any k-dependence in columns →∑cA6=0(K|=k) 6∈K →)x6=0 V rows x of a(→x∈C) 6∈K So not all gn-d+i choices for the n-d+1 such(xs sek appear in C. Contradiction! Conversely, any generic s gives rise to an MDs code of length S Ic:(Supposedly) best example We have a correspondence Length of MDS code +Si ize of generic SCFg Try RM codes! We know they meet the Singleton Bound Enc: fb(f(a1),., f(an))as an rS encoder needs to use distinct i,so we can obtain a length of up to n usIn g all possible elements of Under this correspondence, the generic s obtained is the normal ra tiona| curve“{(1,t,t t E Fqg-any k such form a VDM matrix, hence are LI! We can add (0, .. 0, 1) to this S, reaching n=q+1 MDS Conjecture: Hfk≤q, then a generic|S≤q+1. We prove case k≤p(=q) 2a: Segre's Tangent Function Say S C fk is generic. Then, if Z C s has Z=k-2, consider the codimension-1 hyperplanes 2) z with normal vectors vy. We define a variable polynomia 7z(X):=Ⅱ<,X> ∑∩S=Z Then, if x,y, zJUY is a basis, we have TYux (y)Truly (z) Trufz(x (-1)17y YUx(zT (x)Ty{z}() where t=p+k-1-s 2b: Interpolating T For E=a1,., at+2 and Y=k-2 disjoint in 0=∑7(a)I ∈E b∈E\a But all we needed was that{b,a}∪ Y was a basis va≠b∈E.We never sp olit up Idea: exchange elements of E and r. More generally, if r T、(a)I ∈E 0;+1(y) ∈EUy(0rU{ar} t (ar, z, 0r) Here B;=(al, .. ai-1, yi,..., yk-2), as a set and a tuple 2c: Using Segre's lemma to simplify the interpolation equation Any order of a1,..., ar give the same term in the sum So, we have 0(a 0=r! T、(a)II det(ar, z, 8r) <ar∈E|=1 FOrFar Set r=t +2( use all of E). then the above is a product of many nonzero elements of Fp, together with(t+2)!, so(t+2)!=0 Hence p≤t+2=p+k+1-|s|,so|S|≤k+1≤p+1■ 3a: Caveats If r=t+2>k-l, we use 0. which only has k-2 entries. But t=q+k-1-|5 If s<t+k, we have no room for disjoint E= t+2 and r k-2 in S. Here, we can use the dual"generic set S'CFK'-Ea corresponding to the dual code, with S=n=S. Then, if also S<t'+k', have t+k′+t+k 2 3b: Potential to generalise The same argument gives, for q>p, that S< q+k+1-min k, p But we cannot hope to replace p by g in this proof because of the final step: p!=0 in Fo Nevertheless, in a follow-up paper, Ball relaxed the condition from k< p to k 2p-2, for mds to hold Iso when p Als 2 and k=3 or g-l, the conjecture isn t quite true-insteadS<q+2 is known. For k=3 we may add(o, 1,0)to the aforementioned normal rational curve, making g +2 vectors in total-a hyperoval". Similarly, when k= q- 1, we may add ek-1

试读 11P MDS conjecture
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
MDS conjecture 15积分/C币 立即下载
MDS conjecture第1页
MDS conjecture第2页
MDS conjecture第3页

试读结束, 可继续读1页

15积分/C币 立即下载