RS码的表单解码与多元插值分解算法

《RS码的表单解码与多元插值分解算法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中山大学硕士毕业论文RS码的表单解码与多元插值．分解算法【中文摘要】本文在McEliece等人工作的基础上，将RS码表单解码的GS算法推广到多元情形，多元GS算法由多元插值定理与多元分解定理构成．【关键词】表单解码，RS码，多元插值算法，多元分解算法Rs码表单解码与多冗插值．分解算法ListDecodingofReed—SolomonCodesandMultivariateInterpolation—FactorizationAlgorithmsABSTRl虻TInthisarticle，theGurus

2、wami—SudanalgorithmforlistdecodingofReed-Solomoncodesisextendedtomultivariatecase，whichconsistsofmultivariateinterpolationalgorithmandmul。tivariatefactorizationalgorithm．KEYWORDSlistdecoding，Reed—SolomonCodes，multivariateinterpolationalgorithm，multivariat

3、efactorizationalgorithm．中山大学硕士毕业论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。学位论文作者签名：日期：年月日学位论文使用授权声明本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留学位论文并向国家主管部门或其指定机构送交

4、论文的电子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。学位论文作者签名：——导师签名：——日期：年月日第一章预备知识弟一早以亩划识纠错码【11】：一个F上的h，k，明码就是Fn的一个七维线性子空间，其中瓣为距离，扎称为码长。给定一个In，k，d】码够。若7．满足27-+1≤d那么够是一个r--幺q错码，即对够中的任一码字，距离该码字的距离为7．的码字至多存在一个，满足2丁

5、+1≤d的最大的7-被称为码够的纠错界，。冗·S码[1l】：RS码是一种特殊的BCH码。众所周知，RS码也是最大距离分离码(MDS码)，即n一南=d—l，其中d为兄s码的距离。若够是如上的一个h，k，明Rs码，u是F中的某个本原元，那么够={◇(u)，p(u2)，⋯，p(wJF卜1))：P∈日Ix]，degp≤d)．符号说明：·N-非负整数集·⋯：集合x的势·F：域，一般指有限域·Fixl：域F上的多项式环·degf(x)：，(z)的次数·R㈨：Fix]上次数不超过u的多项式集合·Fix，引：F上的二元多

6、项式环·Mix，Y】={∥Y‘：i≥0，歹≥o’：系数为1的二元单项式集合·如乳，"Q(x，y)：Q(z，秒)的U，v))JH权次数degu，t，Q(z，可)全(m州ax{{仳i+力))，其中，是指标集。·Fix，Y，z】：域F上的三元多项式环·Mix，Y，zl={∥CZ七：i≥o，J≥0，k≥o}：系数为l的三元单项式集合·deg,,舢埘Q(x，Y，z)：Q(x，Y，z)的(钆，u，伽)加权次数de乳鸬加Q(z，可，z)全({囊m七a)x∈，，'【{饿+巧+叫七))，其中，’是指标集。·degzQ(x，

7、Y，z)，deguQ(x，∥，z)，deg。Q(z，Y，z)：多项式Q(x，Y，z)的z，可，z的次数degxQ(x，Y，z)全de91，o，oQ(x，Y，z)=．ma．x，{{)【lJ，k)el如如Q(z，Y，z)垒dego，1，oQ(x，Y，z)=max，{歹)‘lJ，七J61degxQ(x，Y，名)全dego，o’1Q(z，Y，z)=，max，{七)IlJ，膏)61·ELk，引：Fix，y】中y的次数不超过L的多项式组成的集合·ELIX，Y，z】：F[z，Y，z]中z的次数不超过己的多项式组成的集合

8、第二章表单解码已有的重要理论与算法§2．1Sudan算法经典的解码方法“最大似然解码”：给定一个向量s∈Fn，找一个码字c∈够，使c到8的汉明距离不超过7-，如果够是7．纠错码，这样的码字存在的话，肯定是唯一的。这种解码方法固然非常有效，但也有缺点，那就是在有些情况下不能解码，如最小距离为2时，而且解码受纠错界限制，对于超出纠错界的情形无法纠错。在1997年，MadhuSudan在前人工作的基础上发现了一种能够解决超过经典纠错