（基础数学专业论文）列表译码算法的改进及其在jpeg2000中的应用.pdf

东南大学学位论文 独创性声明及使用授权的说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果尽我所知，除了文中特别加以标明和致谢的地方外，论文中不包含 其他人已经发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机 构的学位或证书而使用过的材料与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示了谢意 二、关于学位论文使用授权的说明 签名衄晰丝止 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学 位论文的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文本 人电子文档的内容和纸质论文的内容相一致除在保密期内的保密论文外，允许 论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分内容论文的公布( 包 括刊登) 授权东南大学研究生院办理 摘要 在纠错码的理论研究中，r e e d - s o l o m o n 码( 以下简称r s 码) 扮演着重要的角 色r s 码具有很强的纠错能力，它不仅适合纠正随机错误，而且适合纠正突发 错误近年来，很多学者在r s 码的代数译码方法上做了很多的研究，并得到一 大批十分深刻的结果本文在前人的基础上主要对r s 码的代数译码方法中的 列表译码算法进行了研究，并对g u r u s w a m i - s u d a n 算法进行了改进全文主要分 为以下几个章节： 第一章主要介绍了r s 码代数译码方法的进展情况以及本研究拟解决的问 题和论文的总体安排 第二章首先介绍了g u r u s w a m i s u d a n 算法注意到在g u r u s w a m i - s u d a n 算法 的推导过程中，和计算复杂度密切相关的有关不等式有更紧的估计，所以本章 对r s 码的列表译码算法进行了重新推导，得到了更优的参数，并将算法的计 算复杂度降了下来，同时也达到了列表纠错界n ( x 一钔= 石) 此外，我们还对改 进算法的正确性给出了证明，分析了改进算法的计算复杂度，并给出了算法过 程中出现的一些参数的界最后对改进算法的过程作了总结，并讨论了将这一 算法加以推广的可行性 第三章首先介绍了j p e g 2 0 0 0 的组成结构和特征，接着介绍了j p e g 2 0 0 0 第 l l 部分( j p w l ) 的主要内容及其特点和应用本章的重点是研究j p w l 中r s 码 的列表译码方案经过对j p w l 中采用的r s 码的特性以及i t s 码译码算法的性 能分析，我们提出了将列表译码算法作为j p w l 中r s 码的译码方案最后我们 将改进算法用于j p e g 2 0 0 0 第十一部分的编译码方案，并进行了性能仿真和结 果分析，为后继算法优化和硬件实现提供了平台 关键词：纠错码，r e e d - s o l o m o n 码，代数译码，列表译码算法，j p e g 2 0 0 0 ，j p w l a b s t r a c t i nt h ef i e l do fe r r o r - c o r r e c t i n gc o d e s ，r e e d - s o l o m o nc o d e s ( r sc o d e s ) p l a ya ni m - p o r t a n tr o l e r sc o d e sh a v eas t r o n ge r r o rc o r r e c t i o nc a p a b i l i t y ：n o to n l yd ot h e ys u i tf o r c o r r e c t i n gr a x l d o me r r o r s ，b u ta l s of o rc o r r e c t i n gb u r s te r r o r s e x t e n s i v ee x p l o r a t i o no f a l g e b r a i cd e c o d i n go fr sc o d e sl e a d e dt oal a r g en u m b e ro fi m p o r t a n tr e s u l t s b a s e do n t h ep r e v i o u sw o r k s ，w ei n v e s t i g a t e dt h el i s td e c o d i n ga l g o r i t h mf o rr sc o d e sa n di m p r o v e d t h eg u r u s w a m i - s u d a na l g o r i t h m f u u - t e x ti sd i v i d e di n t ot h ef o l l o w i n gc h a p t e r s ： i nt h ef i r s tc h a p t e r ，w eb r i e f l yi n t r o d u c et h ep r o g r e s so ft h ea l g e b r a i cd e c o d i n gf o rr s c o d e s ，d e t a i lt h ep r o b l e m st h i sd i s s e r t a t i o nw i l ls o l v ea n dd i s c u s st h eo v e r a l lo r g a n i z a t i o n o ft h ev o l u m e i nt h es e c o n dc h a p t e r ，w ed e m o n s t r a t et h a to n ee s t i m a t i o no ft h eg u r u s w a m i - s u d a n a l g o r i t h m ，t h a ti sr e l a t e dt ot h ec o m p u t a t i o n a lc o m p l e x i t y , i sn o tt i g h te n o u g h t h e n w er e f o r m u l a t et h el i s td e c o d i n ga l g o r i t h mo fr e e d - s o l o m o nc o d e sa n dg e tt h es a m e l i s te r r o rc o r r e c t i o nb o u n dn ( 1 一钔：面) w i t ham u c hl o w e ra l g o r i t h m i cc o m p l e x i t y t h a nt h eg u r u s w a m i - s u d a na l g o r i t h m a n dw ea l s oa n a l y z et h ep e r f o r m a n c eo ft h e m o d i f i e da l g o r i t h ma n dc o m p a r ei tw i t hp r e v i o u sw o r k s t oc o n c l u d et h i sc h a p t e r ，w e s u m m a r i z et h ep r o c e s so fi m p r o v e da l g o r i t h ma n dd i s c u s st h ep o s s i b i l i t yo fp r o m o t i o no f t h i sa l g o r i t h mt oo t h e rf i e l d s i nt h et h i r dc h a p t e r w ei n v e s t i g a t et h ed e c o d i n gs c h e m e so fr sc o d e sf o rj p 兄 a f t e rh a v i n ga n a l y z e dt h ec h a r a c t e r so fr sc o d e si nj p w l w ec h o o s et h ei m p r o v e dl i s t d e c o d i n ga l g o r i t h mf o rt h ed e c o d i n gs c h e m e t h e nw ec o n d u c tap e r f o r m a n c es i m u l a t i o n a n da n a l y z ei t sr e s u l t s a l lo ft h e s ew i l lh e l pt h eo p t i m i z a t i o nf o rt h ef o l l o w - u pa l g o r i t h m s a n dp r o v i d eap l a t f o r mf o rh a r d w a r ei m p l e m e n t a t i o n k e y w o r d s ：e r r o r - c o r r e c t i n gc o d e s ，r e e d - s o l o m o nc o d e s ，a l g e b r a i cd e c o d i n g ，l i s td e e o d - i n ga l g o r i t h m ，j p e g 2 0 0 0 ，j p w l 摘要 a b s t r a c t 目录 第一章绪论 1 1 背景介绍 1 2r s 码译码算法的研究进展 1 3 本研究拟解决的问题及论文的总体安排 第二章改进的列表译码算法 2 1g u r u s w a m i - s u d a n 算法 2 2 改进的g u r u s w a m i - s u d a n 算法 2 2 1 改进的g u r u s w a m i - s u d a n 算法 2 2 2 改进算法的正确性 2 2 3 复杂度分析 2 3 小结 第三章列表译码算法在j p e g 2 0 0 0 中的应用 3 1 j p e g 2 0 0 0 及其发展状况 3 2j p w l 中r s 码译码算法研究与实现 3 2 1j p w l 与r s 码译码算法的研究与实现 3 2 2 译码方案选择 3 2 3 算法流程与仿真方案 3 2 4 性能仿真 3 3 小结 参考文献 | 致谢 ； n l 1 2 5 6 6 7 8 9 埒 坞 坞 殂 毖 船 丛 媚 必 缸 第一章绪论 1 1 背景介绍 r e e d - s o l o m o n 码( 以下简称r s 码) 是r e e d 和s o l o m o n1 9 6 0 年发现的一类多 元多项式码 2 2 】同年，r c b o s e 和d k r a y - c h a u d h u r i 独立于a h o c q u e n g h e m ( 1 9 5 9 年) 提出了纠正多个随机错误的循环码一b c h 码r s 码是一类特殊的 b c h 码，其符号域和根域是同一个域另外，一个给定的b c h 码总可以看成是 某个r s 码的子域子码 r s 码通常按如下方式定义：令g f ( q ) 是包含g 个元素的有限域，记有限域 g f ( q ) 上的多项式环为g f 口【捌r s 码是多项式环g f 口i x 】的一个子空间在点集 z 1 ，x 2 ，z n ) g f ( q ) 上赋值得到的码g f ( q ) 上长为n ，维数为k 的r s 码定义 为： ( ，( z 1 ) ，f ( x 2 ) ，f ( x n ) ) if ( x ) g f 口【捌，d e g f ( x ) 七) 其中，赋值点集x l ，x 2 ，z n ) g f ( q ) 常取为g f ( q ) 或g f ( q ) + ，其中g f ( q ) 是 g f ( q ) 中的所有非零元素 自诞生之日起，r s 码就得到了广泛的应用，下面是其一些主要的应用领 域【2 9 ，3 1 】：数字存储设备( 硬盘、c d 、d v d 等) ；无线通信系统( 移动电话、微 波中继等) ；数字电视、d v b 等；卫星通信( 包括深空通信系统) ；宽带调制解调 ( a d s l 、x d s l 等) 此外，r s 码还被推荐为其他不同行业中的标准码例如，由于深空通信可 以近乎精确的模型化为无记忆a w g n 信道，而且信道的频带资源丰富，这就允 许在系统中采用频带利用率低的码和b p s k 调制方式，又因功率受限，传输距 离远，信号衰减严重，所以采用了纠错能力强的r s 码作为深空通信行业中的 标准码；此外，r s 码以其超强的纠错能力( 特别是纠突发错误的能力) ，在c d 和c d r o m 中得到了广泛应用 在分组码的理论研究中，r s 码扮演着重要的角色r s 码是有限域上的极大 距离可分码，具有参数阶，k ，n 一七+ 1 】口，达到了s i n g l e t o n 限，从这个意义上讲，r s 码是最佳的r s 码的最大特点是纠错能力较强，它不仅能纠正随机的错误，而 且适合纠正突发的错误这一领域一直是一个很活跃的研究方向，近年来，很 东南大学硕士学位论文列表译码算法的改进及其在j p e g 2 0 0 0 中的应用 2 多学者在r s 码的代数译码方法上做了很多工作，得到一大批十分深刻的结果 1 2r s 码译码算法的研究进展 在早期的r s 码译码算法研究中，最具代表性的属b e r l e k a m p - m a s s e y 算法和 e u c l i d 算法【1 9 ，2 7 ，3 0 】以下先分别介绍这两算法及其相应的改进 1 2 1b e r l e k a m p - m a s s e y 算法及其改进 b e r l e k a m p 从代数学的角度出发，提出了r s 码的迭代译码算法，避免了 p e t e r s o n 算法中繁琐的矩阵运算，m a s s e y 的线性反馈移位寄存器综合算法也有 与之相同的结论算法的描述如下： 计算伴随式& ，岛，鼠； 进行b e r l e k a m l m m a s s e y 迭代过程求差错定位多项式口( z ) ； 用c h i e n 搜索求差错定位多项式的根( 根的倒数即为差错位置) ； 求差错值( f o r n e y 算法) b e r l e k a m p - m a s s e y 算法又分为时域算法和频域算法频域译码也称作变换 译码，由于在频域中可以利用有限域中的快速傅立叶变换，因而译码速度可大 大提高 b e r l e k a m p - m a s s e y 算法自出现起就不断被改进，从而提高了r s 码译码器的 性能t r u o n g 证明了对变换译码中的d f t 采用质因数分解的方法可提高译码速 度2 6 ；l i u 证明了f e r m a t 质数域上的r s 码采用高基值f f t 变换译码比通常以 2 为基的f f t 译码器快得多【17 】；c h o o m c h u a y 证明了改进的时域算法要比b l a h u t 提出的时域算法计算量减少6 0 2 】 1 2 2e u c l i d 算法及其改进 e u c s d 算法是另外一种主要的r s 码译码算法，其实质是通过求解两个 多项式的最大公因式，获得差错定位多项式及差错值多项式，以后的计算同 b e r l e k a m p - m a s s e y 算法算法的步骤如下。 计算伴随式岛，岛，； 东南大学硕士学位论文列表译码算法的改进及其在j p e g 2 0 0 0 中的应用 3 用e u c l i d 迭代过程求差错定位多项式盯( z ) 和差错值多项式u ( z ) ； 求差错值( f o r n e y 算法) e u c l i d 算法与b e r l e k a m p - m a s s e y 算法的主要差别在于迭代过程b e r l e k a m p - m a s s e y 迭代是基于自回归滤波器综合原理求最短反馈连接多项式的代数迭代过 程；e u c l i d 迭代是基于多项式分解原理求两多项式的最大公因式的过程 1 2 3 列表译码算法及其改进 列表译码算法的思想早在1 9 5 7 年就已提出 5 】在之后的几十年里，列表译 码的思想并没能成功的应用到译码算法中直到1 9 9 7 年，s u d a n 突破了传统的 r s 码的代数译码方法，他发现了超越传统纠错能力【警j 的列表译码算法【2 4 】， 将r s 译码问题转化成有限域上的曲线拟合问题，给出并证明了几个重要的定 理，奠定了r s 码列表译码的基础，该算法的的计算复杂度是多项式计算复杂 度的其算法在码率妾 情形下是有效的算法的步骤如下： 根据接受码字，插值出一个较高阶的二元多项式q ( x ，y ) ； 对所得多项式q ( x ，y ) 进行因式分解； 对因式分解得到的最高阶小于等于k - 1 的因式进行最大似然选择，得到其中 的一个作为码的生成多项式 在【9 】中，g u r u s w a m i 和s u d a n 对【2 4 】中方法进行了改进，使得在任意码率下， 改进算法( g u r u s w a m i - s u d a n 算法) 的纠错能力都超过传统纠错能力i 掣j 对于 接收码字，g u r u s w a m i - s u d a n 算法需要构造通过相应点若干次的多项式然后将 这一多项式进行因式分解，得到一由其因式组成的列表事实上，这一列表列 出了所有与接收码字的h a m m i n g 距离为n ( 1 一钔= 西) ( 其中d 为归一化最小距 离d 竺= d ) 的码字，所以在码率0 7 - l 情形下，g u r u s w a m i - s u d a n 算法的纠错能 力都超过传统纠错能力i 譬i j o h n s o n 界 1 3 】给出了小列表所能纠正错误个数的 一个下界，g u r u s w a m i - s u d a n 算法的纠错性能达到了【1 3 】中所给出的j o h n s o n 界 事实上，g u r u s w a m i - s u d a n 算法是多项式曲线拟合算法，它确定了所有通过 佗个点对中至少 几( n d ) 个点的多项式特别的，对于这n 个点对 ( 盈，玑) ) 銎l ， 东南大学硕士学位论文列表译码算法的改进及其在j p e g 2 0 0 0 中的应用 4 其中 z l ，x 2 ，z n ) 是赋值点集，( y 1 ，耽，) 为接收码字，g u r u s w a m i - s u d a n 算 法首先构造二元多项式q ( x ，秒) ，使得q ( x ，y ) 穿过每个点对一定次数，这样构造 的二元多项式q ( x ，秒) ，对于所希望找到的，( z ) ，满足y f ( x ) 是q ( x ，y ) 的一个因 子，所以接下来我们只要对二元多项式q ( x ，y ) 进行因式分解就得到我们所需的 输出列表【9 】对于上述算法的计算复杂度，k 5 t t e r 【1 4 】和r u t h - r u c k e n s t e i n 2 3 】等 人做了很多降低复杂度的工作，他们对g u r u s w a m i - s u d a n 算法中的关键步骤的 低复杂度的实现做了很多很好的工作特别的，他们证明了插值过程所需的计 算复杂度只要p ( 佗2 ) 就够了，而如果采用高斯消元法进行插值的话，则需要的 计算复杂度为p ( 护) 在 2 8 】中，w - u 设计了一个有理曲线拟合算法，并将其应用到r s 码和b c h 码的列表译码算法中这一算法达到了列表纠错能力佗( 1 一钔= 石) ，从而与 g u r u s w a m ia n ds u d a n 算法一样，都达到了j o h n s o n 界对于给定的列表纠错能 力，w _ u 所提的算法所需的乘法次数要比g u r u s w a m i - s u d a n 算法所需的乘法次数 低的多乘法次数选取的大小与计算复杂度是密切相关的，所以w u 所提的算 法的计算复杂度要比g u r u s w a m i - s u d a n 算法的计算复杂度低的多，这也是迄今 为止，所有文献中达到相同列表纠错性能，复杂度最低的算法 在【1 5 】中，k s t t e r 和v a r d y 通过一种很自然的方式将信道中的软信息转化成 一个与乘法系数相关的乘法矩阵，这一乘法矩阵改变了g u r u s w a m i - s u d a n 算法中 乘法次数的分配由于把信道中的软信息也考虑进来了，这使得k s t t e r - v a r d y 算 法的纠错能力有所提高，该算法与硬判决算法( h d ) 有着明显的增益，宣告了r s 码软判决译码时期的到来从此，g a u s s 算法【2 1 ，c h e r n o f f 算法【4 】，w a t e r f i l l i n g l i k e 算法【1 1 ，a b p 算法【1 2 】，分解译码【6 】以及各种级联型算法【4 】接踵而至虽然软 判决译码算法的性能越来越好，但复杂度也水涨船高，所以软判决算法在实际 工程中运用起来，仍有很多问题待解决2 0 0 5 年，r s 码的最大似然译码( m l d ) 问题被g u r u s w a m i 和v a r d y 证明是n p h a r d 问题【10 】寻找逼近最大似然译码性能 且低复杂度的r s 码译码算法成为了纠错码领域的一个炙手可热的问题在 3 】 中，d u g g a n 和b a r g 证明了在码率较低或中等的情况下，r s 码的列表译码算法 的代数软判决算法是优于硬判决算法的( g u r u s w a m i - s u d a n 算法) 在高码率情形 下，这两算法的优劣现在还没有确切结论，所以研究在任意码率下的硬判决算 东南大学硕士学位论文列表译码算法的改进及其在j p e g 2 0 0 0 中的应用 5 法仍具体现实意义 1 3 本研究拟解决的问题及论文的总体安排 当前，r s 码的列表译码方案得到了来自学术界和工程界的广泛关注，一些 学者陆续对列表译码的各模块的优化算法以及高速硬件实现架构进行了大量的 研究但是，我们也看到，目前的研究重点主要集中在新算法的提出或对算法 的性能进行分析上至于对g u r u s w a m i - s u d a n 算法的参数的改进，就我们目前掌 握的文献来看并没有涉及 注意到g u r u s w a m i - s u d a n 算法中，一个和计算复杂度密切相关的不等式有 更紧的估计所以本文想到对r s 码的列表译码算法进行重新推导，希望能得 到更好的参数，并将算法的计算复杂度降下来改进后的算法的纠错能力为 n ( 1 一而) ，这一结果与之前算法是一致的，但改进算法的计算复杂度要比 g u r u s w a m i - s u d a n 算法的计算复杂度低的多 综合国内外关于r s 码编译码方法及其相关技术的研究状况，本论文提出 了将我们的改进算法用于j p e g 2 0 0 0 中第1 1 部分的无线网络上传输的编译码方 案，以降低r s 码编译码器的硬件开销、提高它们的运算速度所以r s 码算法 的性能分析也是我们研究工作必须考虑的重要因素 本文的总体安排如下。第一章为绪论部分；第二章首先给出了g u r u s w a m i - s u d a n 算法，接着针对g u r u s w a m i - s u d a n 算法中一不等式的改进，提出了我们的 改进算法，然后我们对算法的正确性给出了证明，最后对算法的性能进行了分 析，并将所得结论与其他人在r s 码译码工作上所得的结论进行比较第三章首 先介绍了j p e g 2 0 0 0 的发展情况，并详细介绍了j p e g 2 0 0 0 第1 1 部分( j p w l ) 的 主要内容，注意到其前向纠错编码( f e c ) 的译码方案仍在发展中。接下来我们 讨论了j p w l 中r s 码译码方案的选取，最终采用了改进的列表译码算法用于这 一部分的编译码方案中最后我们对该译码方案进行了理论分析与实验模拟 第二章改进的列表译码算法 本章首先介绍了g u r u s w a m i - s u d a n 算法注意到g u r u s w a m i - s u d a n 算法的推 导过程中，有一个和计算复杂度密切相关的不等式有更紧的估计，所以对r s 码的列表译码算法进行重新推导，从而得到更好的参数，并将算法的计算复杂 度降下来本章的第二部分介绍了我们的改进算法，然后对其过程的正确性给 出了证明，分析了改进算法的复杂度，并给出了算法过程中出现的一些参数的 界最后我们对改进算法的过程作了总结，并讨论了将这一算法加以推广的可 行性 2 1g u r u s w a m i s u d a n 算法 考虑n 个互不相同的点对 ( z 1 ，y 1 ) ，( x 2 ，y 2 ) ，( z n ，) ) ，其中 z 1 ，x 2 ，z n ) 是赋值点集，( 秒1 ，抛，) 是接收向量我们所感兴趣的是寻找d e g f ( x ) t 6 僦 6 + 2 仃 陀 东南大学硕士学位论文列表译码算法的改进及其在j p e g 2 0 0 0 中的应用7 特别的，令 删a+(k-1)n+v(k-1)2n2+巫4(t2-(k-1)n)j l q 全m 一1 ( 2 1 3 ) ( 2 1 4 ) 2 找多项式q ( x ，y ) 使得d e g ( 1 扣1 ) q ( x ，y ) l q ，即找多项式的系数田。庇，其中 矗，如o ，j l + ( k 一1 炀三q ，使得以下几个条件成立： ( a ) 劬。j 。不全为0 ( b ) 对每个l 1 ，2 ，扎) ，如果q ( ) 是q 在( 鼢，y i ) 处的展开，则q ( ) 中所有 ( 1 ，1 ) 加权次数小于m 的系数全为0 即： 对v 1 ，2 ，仡) ，v j l ，j 2 0 ，s t 歹l + j f 2 l q( 2 2 8 ) 佗( m 1 ) 堕堡与必 ( 2 2 9 ) l q = at m 一1 ( 2 2 1 0 ) ( 2 2 1 1 ) 2 找多项式q ( z ，y ) 使得d e g ( t , 七一1 、q ( z ，y ) 三q ，且多项式q ( z ，y ) 穿过( x i ，y i ) 至少 m 次，其中i = 1 ，2 ，n 3 找出所有的次数至多为k 一1 的多项式，( z ) g f 。【捌，使得，( z ) 是q ( z ，y ) 的 一个根( 即可一，( z ) 是q ( z ，y ) 的一个因子) 对每个这样的多项式，( z ) ，验证 是否至少有 1 ，2 ，n ) 中的t 个点满足，( 甄) = y i 如果，满足以上条件，则 将，包括在输出列表中如果不存在满足以上条件的多项式，宣布译码失 败 2 2 2 改进算法的正确性 接下来我们证明改进算法的正确性引理1 和引理2 的证明方法和【9 】中相 应结论的证明过程很相似，我们只列出其结论，证明就不再重复了 引理1 设q ( z ，y ) 是( 1 ，k 一1 ) - 加权次数为l q 的二元多项式，且对于 ( z 1 ，y 1 ) ， ( x 2 ，沈) ，( x 。，鲰) ) 中的每个点，q ( z ，y ) 在该处的乘法次数都为m 次如果 l q l q 自然成立i gn = 譬，注意到l q = t m - 1 ， 则 ! ! 墨里! 二! 墨二! ! 墨型! ( 墨望1 2 2 一( 2 ( t i n 一1 ) + 2 一( k 一1 ) l 掣) ( 厶+ 1 ) ：= ：- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - 二- - - - - - 二- - - - - - 一 = ( t m a l v ) ( l 材+ 1 ) = - a l ；+ ( t m a ) l ! ，+ t m = 一。( l y t m - a 12 + t ( t i n + a ) 2 = 一。( 1 替j _ t m - a 1 2 + 一( t i n + a ) 2 一一a + ( t i n + a ) 2 为了满足限制( 2 2 1 2 ) ，只要证 这等价于 一五a + ( t i n f + a ) 2 n m 丁( m + 1 ) m 2 ( 亡2 2 h a ) + ( 2 t a 一2 a n ) m 0 注意到t 瓜，所以只要取m 为 m = i 一2 a n - 2 a t + 1 j = l 粼+ 1 j ， m = j1 f 二丽+ ll = l 了f = 刁f 丽十上l ， 这正是我们在改进算法中所取的参数 注意到改进算法的最佳列表纠错能力为： e 叫= n 一亡。彬= m x ( k - 1 ) n 一1 1 这一列表纠错能力与【9 】和 2 8 】中结论是一致的 我们将上述讨论总结为以下定理。 东南大学硕士学位论文列表译码算法的改进及其在j p e g 2 0 0 0 中的应用1 1 定理1 对任一给定的纠错能力e ，其中e e 唧，如果我们所选取的多项式q ( x ，y ) 的次数k 满足( 2 2 1 0 ) 式，乘法次数m 满足( 2 2 9 ) 式，且q ( x ，y ) 如引理1 所定义， 则所有穿过 p l ，y 1 ) ，( 钇，抛) ，( x n ，鲰) ) 中t 个点的多项式，( z ) ，满足一f ( x ) 是q ( x ，y ) 的一个因子 例1 对于参数为( 3 1 ，6 ) 的r s 码，此时n 一 丽可= 1 8 5 5 0 1 所以我们能纠正 e 倒= 1 8 个错误，而传统的纠错算法只能纠正【譬j = 1 3 个错误我们只要取乘 法次数m 为m = 【( k - 一1 ( 七) ( 一n 1 - ) n t ) - + 1 j = 7 相比之下，为了达到相同的列表纠错能力 e = 1 8 ，g u v u s w a m i s u d a n 算法所需的乘法次数为m = 1 2 ，在肌所提算法中所需 的乘法次数为m = 1 0 注：算法的复杂度和乘法次数m 的选取是紧密相关的，所以对于参数为 ( 3 1 ，6 ) 的咒s 码的译码算法，我们所改进的算法是最优的 接下来我们推导在r s 码译码算法所得列表中，半径为e e 卿的码字个数 注意到卿一、虱可可看成是o ( 1 ) 【2 s ，我们可得类似于【2 8 】中定理2 的结论 推论1 在接收列表中，与发送码字的汉明距离为e e 卿的码字个数有d ( e 啊) 个 1 正明? 田b 网疋义f u 刘，与反透哟子明仪明圯呙刀e 卿即俏子个双芏多自 厶个将( 2 2 9 ) 和( 2 2 1 0 ) 代入到( 2 2 6 ) ，我们有 驴。( 离) = 。( 各警等等) 却( 各面蒜罨器葡) = p ( 各坚等型) 结论得证 东南大学硕士学位论文 列表译码算法的改堂丞基垄生堕堡星塑一主堕壁旦 1 2 图2 2 对于参数为( 2 5 5 ，1 1 2 ) 的r s 码，不同列表纠错能力时所输出的列表的大小 注? 以上结论大大改进了【9 1 中所得的结论p ( 、忌n 3 ) 考虑参数为( n ，后) 的r s 码，对于给定的列表纠错能力e ( e e 哪) ，文献【9 】提出的算法中，所需的匕，g s 为： 玩一【- 坐竺雾一j 文献【2 8 】提出的算法中，所需的岛，g s 为： = 1 某南l 觜掣j j 而在我们的改进算法中，我们所需的岛，为： 岛= 【击l 锹+ 1 j j 对于参数为( 2 5 5 ，1 1 2 ) 的r s 码，图2 2 比较了这三个算法所得到的列表的大小 从表2 2 中可以看出，我们发现岛和厶玑w 包基本上是相近的，两者都比l 掣，小 的多 如果不考虑取整所带来的影响，考虑列表纠错能力为t = 佗一d ) 的情形 东南大学硕士学位论文列表译码算法的改进及其在j p e g 2 0 0 0 中的应用 1 3 下，此时比值箜可表示为 l 可，g sl n ( 礼一d ) 几 百l 而2 矿而习2 i 而葡 1 一们f 面 这表明，对于参数几，改进算法所得到的列表中码字个数要比g u r u s w a m i - s u d a n 算法所得到的列表中码字个数要少的多这与 2 8 】中所得的结论是一致的这 也从某种程度上说明我们之前的猜测是合理的 2 2 3 复杂度分析 目前，所有达到j o h n s o n 界的r s 码的列表译码算法中，【2 8 】中所提算法的 计算复杂度是最低的以下我们分析改进算法的计算复杂度，并将其与之前的 工作进行比较，特别是【9 】和【2 8 】中所提的算法 我们先分析域中元素之间操作的计算复杂度，假设n 和k 足够大，且域中 的元素个数q 2 n ( 域中的元素个数涉及到因式分解的复杂度【9 】) 首先，我们先 归一化极小距离d = d n ，然后令n ( 和d ) 趋向无穷以下我们主要考虑极大列 表纠错性能。叫当t = 亡唧时，( 2 2 9 ) 中所取的乘法次数可简化为 m = 。( 粼) = 。( 面爿号瓮) =p f，型2v(n-d)n) = d ( 几汀刁( 1 一厕) ) = p ( 、而( 何一、而) ) = p ( n ) 插值过程所要做的是t 寻找一个二元多项式q ( x ，y ) ，使其满足下面两个条 件；首先，对给定的乘法次数m ，o ( x ，y ) 以重数m 穿过该点；其次，q ( x ，y ) 的阶 数尽量小，这是出于降低复杂度的考虑 东南大学硕士学位论文列表译码算法的改进及其在j p e g 2 0 0 0 中的应用 1 4 关于插值过程，目前最有效的方法是k s t t e r 所提的算法，该算法是基于迭 代的插值算法该算法采用“分而治之”的策略：在构造一组初始解的情况下， 逐步更新这组初始解使其满足一个约束条件，直到所有的约束条件被满足为止 该算法两个条件都满足得较好若将这个过程理解成解一个由个线性方程组 成的线性方程组，其所需的计算复杂度为d ( 2 ) 【1 4 ，1 8 ，2 0 1 所以为了达到最大 列表纠错性能，所需的限制( 线性方程个数) 为o ( n m 2 ) = 0 ( 护) 所以关于插值 过程的计算复杂度，我们有以下的特征刻画： 引理4 在改进的g u r u s w a m i s u d a n 算法中，对于参数为( n ，k ) 的r s 码，为了达到 极大列表纠错性能e o p t = m 一1 一 礼 一d ) ，插值过程的计算复杂度为0 ( n 6 ) 因式分解过程的主要任务是对插值过程生成的插值多项式进行因式分解， 以期从分解出的因式中获得码的生成多项式接下来我们考虑因式分解过程的 计算复杂度由【9 】中性质1 1 可知，因式分解过程的计算复杂度为 o ( l 霉瑶+ 厶l f + ( k 一1 ) 2 鬈2 ) 注意到q ( z ，y ) 关于z 的次数厶至多为l q ，所以我们有 o ( l ) = o ( l q ) = o ( e o p t m ) = o ( ( 佗一 n ( n d ) ) n ) = o ( n 2 ( 1 一厕) ) = o ( n 2 ) 因此，我们可将整个因式分解过程的计算复杂度刻画为； 引理5 在改进的g u r u s w a m i s u d a n 算法中，对于参数为( n ，k ) 的r s 码，为了达 到最优纠错性能e o p t ，整个因式分解过程的计算复杂度为p ( 亿6 ) 注：在 2 3 】中，r o t h 和r u c k e n s t e i n 所提的算法是目前关于二元多项式因式分 解最有效的算法，所以在我们的改进算法中我们也可以采用 2 3 】中的算法来进 行因式分解该算法采用递归的思想，将因式分解问题转化成了树的深度搜索 问题，首先求得生成多项式的常数项的候选解，然后通过变量代换将生成多项 式的常数项消去，使得原一次项变成常数项这样，一次项系数的求解就与前 述常数项的求解步骤相同，如此往复，最终可以将输入的插值多项式分解成各 因式的积其具体分析过程与【2 8 】中引理6 的证明过程相似，注意到这个因式分 东南大学硕士学位论文 列表译码算法的改进及其在j p e g 2 0 0 0 中的应用 1 5 图2 3 对于参数为( 1 2 7 ，2 4 ) 的r s 码，不同列表纠错能力所需的乘法次数的大小 解的方法在我们所提算法中，其计算复杂度为p ( 舻) ，注意到插值过程的计算复 杂度为p ( n 6 ) ，所以这不影响整个改进算法的计算复杂度，在此我们不再重复 以下定理总结了所提算法的整个过程的计算复杂度 定理2 对于参数为m ，k ) 的r s 码，如果域中所有元素的个数至多为2 n ，为了达 到最优列表纠错能力e 卿= h 一1 一 n ( 七一1 ) ，我们所改进的列表译码算法关 于域中元素操作的计算复杂度为p ( 舻) 注：对于参数为( n ，k ) 的r s 码，为了达到相同的列表纠错能力，g u r u s w a m i - s u d a n 算法所需的乘法次数为p ( 七佗) ，且该算法的计算复杂度也是由插值过程 所决定的，其整个过程的计算复杂度为o ( n 6 k 4 ) 【2 8 】中所提的算法所需的乘 法次数为o ( ( v - a 一弧) 2 ) 且整个过程的计算复杂度为移 ( 西一以) 7 ) 注意到 o ( k n ) = o ( 佗2 ) ，o ( ( 4 - a 一以) 2 ) = p ( n ) 和p ( 何一v - z ) 7 ) = p ( n 6 ) ，所以我们所 提的改进算法的计算复杂度要比g u r u s w a m i s u d a n 算法低，且在渐进情形下与 w u 所提的算法是一致的 注意到乘法次数与计算复杂度是紧密相关的，对于参数为( n ，k ) 的r s 码， 比较不同算法在相同的列表纠错能力下所需的乘法次数是有意义的考虑 东南大学硕士学位论文列表译码算法的改进及其在j p e g 2 0 0 0 中的应用 1 6 图2 4 对于参数为( 1 2 7 ，5 6 ) 的r s 码，不同列表纠错能力所需的乘法次数的大小 旦 e n v n ( n - d ) ，【9 】中所需的乘法次数为， 嘲-l+(k-1)n+x(k-1)2n2+巫4(t2-(k-1)n)j 【2 8 】中所需的乘法次数为， 一【耳筹j 由( 2 2 9 ) 可知，我们所提算法所需的乘法次数为， m = 【- 一2 a n - 2 a t + 1 j = l 睾粼+ 1 j 对于参数为( 1 2 7 ，2 4 ) 和( 1 2 7 ，5 6 ) 的r s 码，图2 3 和2 4 比较了各个算法所需的乘 法次数 对于最优列表纠错能力e = n ( 1 一而) ，我们考虑比值警，有如下结论 r a g sln 一d ) ml 括俪而( n d ) ( n 一亡) n 一 佗( n 一回 1 1 一析f 面 l叠id兰，z互若卫殳_暑量 东南大学硕士学位论文列表译码算法的改进及其在j p e g 2 0 0 0