（通信与信息系统专业论文）reedsolomon码代数软译码算法研究.pdf

摘要 r e e d s o l o m o n ( r s ) 码以其优美的代数结构和简便的工程实现被视为最优秀的纠 错编码之一，它对随机错误、突发错误和删除都有很好的纠错性能。从六十年代至 今，r s 码已被广泛应用于移动通信、深空通信、电磁存储等诸多领域但一直以 来，r s 码缺少实用而有效的软译码算法，这严重影响了r s 码在当今以及未来通信系统 中的应用，也刺激着世界范围内的研究者在寻找新的更有竞争力的码字的同时对r s 码 的有效的软译码算法仍抱有极大热情因此研究r s 码的软判决算法有着重要的理论意 义和应用价值。近年来出现的一些主流的软判决译码算法有k s t t e r 和v a r d y 提出的代数 软判决( a l g e b r a i cs o f t - d e c i s i o nd e c o d i n g ，a s d ) 译码算法，j i n gj i a n g 和n a r a y a n a n 提出 的自适应置信传播( a d a p t i v eb e l i e fp r o p a g a t i o n ，a b p ) 算法以及m o s t a f a 和m c e l i e c e 提 出的级联型译码算法。 本文主要致力于r s 码代数软判决译码算法( a s d ，k s t t e r v 盯d y 算法) 的研究在 系统的介绍了r s 码相关理论和硬译码算法( b m ) 之后，我们系统完整地介绍了r s 码代数 列表译码算法和k v 算法，包括其出发点，前端重数分配算法，后端代数算法( 包括多项 式插值算法以及因式分解算法) ，并给出了性能仿真结果我们还讨论了k v 算法的改进 方案，印最有代表性的重编码算法我们看到，这种算法可以有效地降低原k v 算法的 复杂度 在以上算法讨论的基础上，本文还分析了算法的时间复杂度，探讨了算法硬件实 现，并介绍了算法的模块化分解和v l s i 结构设计 关键词：r e e d - s o l o m o n 码代数软判决译码多项式插值因式分解重编码硬件复杂度 a b s t r a c t r e e d s o l o m o nc o d eh a sb e e ns e e na so n eo ft h em o s tc e l e b r a t e de r r o r - c o r r e c t i n g c o d e sf o ri t sa l g e b r a i ca r c h i t e c t u r ea n de a s ya p p r o a c hf o re n g i n e e r i n ga p p l i c a t i o n i t h a ss t r o n ge r r o r c o r r e c t i n gc a p a c i t ya g a i n s tr a n d o me r r o r s ，b u r s te r r o r sa n de r a s u r e s s i n c e1 9 6 0 s 。r sc o d eh a sb e e nu s e di naw i d ev a r i e t yo fa p p l i c a t i o n ss u c ha sm o b i l e c o m m u n i c a t i o n ，d e e p - s p a c ec o m m u n i c a t i o n ，e l e c t r o m a g n e t i cs t o r a g e sa n ds oo i l h o w e v e r ， t h el a c ko fa ne f f e c t i v es o f t - d e c i s i o nd e c o d i n ga l g o r i t h mw i l lc e r t a i n l yb a f f l ei t sa p p l i c a t i o n s i nt o d a y sa n df u t u r ec o m m u n i c a t i o ns y s t e m s ，r e s e a r c h e so nw h i c ht h e r e f o r ed oh a v eg r e a t v a l u en o to n l yi nt h e o r y , b u ta l s oi ne n g i n e e r i n g a n d ，r e s e a r c h e r si nt h ew o r l d w i d e h a v es h o w ng r e a ti n t e r e s t si nr ss o f t d e c i s i o nd e c o d i n gw h i l eb e i n gd e v o t e di ns e e k i n g n e wc o m p e t e n te r r o r - c o r r e c t i n gc o d e s l a t et h e s e sy e a r sk i n d so fs o f t - d e c i s i o nd e c o d i n g a l g o r i t h m sh a v eb e e np r o p o s e ds u c ha st h e “a l g e b r a i cs o f t d e c i s i o nd e c o d i n g ( a s d ， k v ) a l g o r i t h mb yk s t t e ra n dv a r d y , t h e “a d a p t i v eb e l i e fp r o p a g a t i o n ”( a b p ) a l g o r i t h m b yj i n gj i a n ga n dn a r a y a n a na n dt h ec o n c a t e n a t e da l g o r i t h mb ym o s t a f aa n dm c e l i e c e t h i sp a p e r i sm a i n l y ，d e v o t e do nt h e ，“a l g e b r a i cs o f 卜d e s i c i o nd e c o d i n g ”a l g o r i t h m o ft h er sc o d e f i r s tw es y s t e m i c a l l yi n t r o d u c et h er e l e v a n tc o n c e p t so fr sc o d ea n di t s t r a d i t i o n a lh a r d - d e s i c i o nd e c o d i n ga l g o r i t h m b ma l g o r i t h m t h e nw ed e s c r i b ei nd e t a i l t h ea l g e b r a i cl i s td e c o d i n ga l g o r i t h ma n dk va l g o r i t h m i n c l u d i n gt h e i rf r o n t e n dm u l - t i p l i c i t ya s s i g n m e n ta l g o r i t h ma n db a c k - e n da l g o r i t h m s ( t h a ti s ，p o l y n o m i a li n t e r p o l a t i o n a n df a c t o r i z a t i o na l g o r i t h m s ) f o l l o w e dw i t hs i m u l a t i o nr e s u l t s a n dw ef u r t h e rd i s c u s s t h e “r e e n c o d i n g t r i c k 。w h i c hc a nd r a m a t i c a l l yl o w e rt h ec o m p u t i n gc o m p l e x i t yo ft h e o r i 【g i n a lk va l g o r i t h m b a s e do nt h ed i s c u s s i o n sa b o v e ，w eh a v ea n a l y z e dt h ec o m p u t i n gc o m p l e x i t yo ft h e k v ( r e e n c o d i n 9 1a l g o r i t h m ，t o g e t h e rw i t ht h em o d u l a r i z a t i o na n dt h ev l s ia r c h i t e c t u r e s d e s i g no ft h ea l g o r i t h m k e y w o r d s cr e e d - s o l o m o nc o d e sa l g e b r a i cs o f t d e c i s i o nd e c o d i n gp o l y n o m i a li n t e r p o l a - t i o nf a c t o r i z a t i o nr e e n c o d ec o m p u t i n gc o m p l e x i t y v g f ( q ) 俨 f 陋，暑d f b l m 陋，们 本论文专用术语的注释表 q 阶有限域，在不致混淆时简记为f n 维向量空间，向量中的元素取自域f 上，即f 1 = f f f j ， n 个相乘 系数取自有限域f 中的二元多项式环，其中一个典型的多项式为：q ( z ，”) = j 啦j 矿 系数取自有限域f 中的关于z 的多项式环 单项式集合，定义为：m b ，胡= z i 矿l i ，歹o ) d e g ，w f f i ，一，x 单项式矿的( 魄，) 一加权阶数 如9 蜥) q ( z ，暑，)多项式q ( z ，彰) 的( 屹，吻) 一加权阶数，定义为d 嗷娩鳓) q ( 毛) = m a x ( i d ) w x i + 吻j ) ( ，6 )在( 屹，吻) 一加权反词典序下，( ，哟) 一加权阶数不大于6 的单项式个数 【只q 】d 己或? c s - - o r - - 1 , y _ e - e s l a l 泛函d 对应的双线性变换，定义为( p q 】d = d ( q ) p d ( p ) q r s 码的支撑集。定义为： z o ，z l ，x n - - 1 ) = 【q 0q ，矿- 1 ) 发送码字，对应的多项式表示分别为c ) ，c ( z ) r s 码发送码字，对应的多项式表示为( z ) 伴随式译码中的伴随式 译码端接收到的矢量 r s 码译码端接收到的矢量 信道噪声造成的错误图样 错误图样亩的估计 译码器输出的发送码字a 的估计 集合a 中元素的个数 东南大学硕士学位论文 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而 使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示了谢意。 研究生签名： 东南大学学位论文使用授权声明 日期： 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文 的复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档 的内容和纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借 阅，可以公布( 包括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权东 南大学研究生院办理。 一 冷a 研究生签名：边f 蒌衄绉导师签名- 主里勉期： t 1 1数字通信系统的构造 第一章绪论 1 9 4 8 年，香农( c l a u d e - s h a n n o n ) 发表了他的经典文章“通信的数学理论”( “am a t h e m a t i c a l t h e o r yo fc o m m u n i c a t i o n 【1 1 ) 。标志着信息论的诞生2 0 世纪以来，通信系统经历了模拟通信到数 字通信的发展过程。一个典型的数字通信系统主要由以下及部分构成( 图1 1 ) ： 图1 1 数字通信系统框图 信源编码器主要包括模数转换、波形变换等步骤，其作用是通过压缩冗余将输入的信息有效地 变成二进制数字序列，信源编码器输出的信息序列被送到信道编码器。信道编码会引入一些冗余以 克服信道传输中遭受的噪声的干扰。多数移动数字通信系统都会有交织器，交织器是通过一定的方 式将数据流重新排列，从而将突发错误( b u r s te r o r ) 在时间上打散，变为随机错误( r a n d o me r r o r ) 。 所以，交织器本身并不具有纠错性能，它必须与纠错编码技术相结合才能对抗移动衰落信道的不利 影响数字调制器是通信信道的接口，它将信息序列映射成适合信道传输的信号波形，而后通过射 频发射器发射出去 通信信道是用来将发送机的信号传送给接收机的物理媒质。它的基本特点是发送信号随机地受 到各种可能的恶化。 在接收端数字解调器对从射频天线接收到的波形进行处理，并还原成一组数字序列。该序列 经过解交织厉被送到信道解码器中，根据加入的冗余进一步重构初始的信息序列。这其中包含了数 字接收机的诸多基带处理技术最后，信源解码器将信息序列还原成原始的输入信息并输出。 1 2 纠错码的发展 发送信息在经过通信信道时不可避免地会受到不同程度的干扰和失真，这些干扰和失真会造 成数字通信系统的误码现象。误码现象主要分为错误和删除两种。错误从其分布上讲可分为随机错 误、突发错误和混合型错误错误并不明确其位置，而相比之下，删除的位置是明确的。比如在磁 介质传输时，某磁介质上的信息丢失，但该位置可以被磁头明确识别，即产牛了删除现象。正是由 1 东南大学硕士学位论文 于信息序列经过信道时会受到污染，我们需要针对不同系统设计相应的纠错编码机制，如纠随机错 误码、纠突发错误码和纠混合错误码。他们均可以在不同的译码方法下作为检错码、纠错码或纠删 码。 编码的使用解决了如何有效且可靠地传输信息的问题。s h a n n o n 开创的信息理论从通信系统的 整体最佳化来研究信息的传输和处理，并从理论上证明：随着码长的增加，平均译码错误概率p e 趋 于零、信道信息传输速率r 无限接近于信道容量c 的抗干扰信道编码是存在的通常我们又将信道 编码称之为纠错码。同时也必须看到：随着码长的增加，译码设备的复杂性呈指数型增加。所以， 我们研究纠错码的意义在于：在保持一定的信息传输效率的条件下，通过编译码来降低误码率以实 现可靠通信，并且要求译码设备尽可能简单嘲。在误码率一信噪比关系曲线上。某个误码率下编码 后的系统比编码前节省出的功率数( d b ) 称为编码增益。 仅仅根据上述理论和香农限是无法具体构造出这种码字来的，因为在理论证明过程中并没有给 出具体构造某个码字的方法但人们在理论的指导下赋予码以各种代数结构，提出了一系列设计好 码及其译码算法大体上可分为线性分组码、卷积码两类 线性分组码是发展最早的一类纠错码。这种码其一组码字的校验位只与该码字的信息位部分 有关，而前后两组码字间没有任何联系。比如格雷码、汉明码、循环码和b c h 码等都属于线性分 组码。在实际应用中，主要使用短码，因为这些码字纠错译码算法的复杂度随着码长的增加呈指数 级增长，长码的实现十分困难。1 9 5 9 年m h o c q u e n g h e m ，1 9 6 0 年由b o s e 和m 旷c h a u d h u r i 分别提 出了一种可以纠正多个随机错误的循环码一b c h 码的构造方法。它的纠错能力很强，并且构造方 便，在短码和中等码长下其性能十分接近于理论值。而且，它严格的代数结构在编码理论中起着 重要的作用。同时在1 9 6 0 年，r e e d 和s o l o m o n 3 l 用多项式方法构造出了一类有很强纠错能力的多进 制b c h 码，被称为r e e d - s o l o m o n 码，在其厉的几十年中这种码在诸多领域大行其道 ：卷积码是另一种重要的纠错编码，其一组码字的校验位不仅取决予该码字的信息位，丙且也取 决于前仇组码字的信息位，其中m 是记忆长度。卷积码在编码过程中充分利用了码元间的相关性， 且每组码元的信息位长度和码长通常都要比分组码的小因此在相同的码率和设备复杂性条件下可 以获得比线性分组码更高的编码增益，但是这种相关性同时也增加了分析和设计卷积码的复杂性 1 3r e e d s o l o m o n 码简介 1 9 6 0 年，m i tl i n c o l n 实验室的i s r e e d 和g s o l o m o n 发表了论文“p o l y n o m i a lc o d e so v e r c e r t a i nf i n i t ef i e l d s ”h 。在这篇文章中，他们用多项式的方法构造出一种具有很强纠错能力的 纠错码。在随后的几十年里，这种被称为“r e e d - s o l o m o n ”码的纠错编码方法在深空通信、电磁存 储、广播电视等诸多领域中被广泛采用 我们简要回顾一下r s 码的发展史：1 9 5 9 年r e e d 和s o l o m o n s j 用有限域中的多项式第 一次构造出了r s 码；1 9 6 1 年g o r e n s t e i n 和z i e r l e r 4 1 发现r s 码是多元域本原b c h 码的一种子 码，并给出了r s 码的时域编码及b c h 码和r s 码的译码算法。紧接着c h i e n 剐和r ) m e y 6 】改 进了算法。但这些译码算法在可纠错误个数较多时仍不够有效；1 9 6 7 年b e r l e k a m p l 构 造出另一种译码算法，使得r s 码能够有效地纠正大量错误；一年后，m a s s e y l s l i 正明 t b e r l e k a m p 算法等价于一种基于构造线性反馈移位寄存器的算法，从而进一步提高了译码 效率：1 9 7 5 年s u g i y & m a ，k a s a h a r a ，h i r a s a w a 和n a m e k a w a t 9 l 证明e u c l i d 算法能有效地对b c h 码 和r s 码译码；1 9 9 1 年n a s a 发射的用于研究木星的g a l i l e o 号飞船由于种种原因出现故障，其 高增益天线不能打开，导致往地球发回数据的时间间隔大大增加，幸而r s 准软判决算法等 2 第一章绪论 计算机技术的发展对此作出了弥补，这也客观上刺激了为各类通信系统设计的r s 码准软算 法的研究【o j ；1 9 9 7 年s u d a n l ；4 提出了种能够超越r s 码硬译码半径的代数列表译码，继 而g u r u s w a m i 和s u d a n z 3 1 对此作出了改进使之适用于更大的码率范围。并且让人们看到了进 行r s 码软译码的可能性。紧接着k 6 t t e r ，r o t h 和r u c k e n s t e i n 等人给出了其子算法的简单实现； 进入本世纪，2 0 0 4 年k 6 t t e r 和v 缸d y l l 在g s 算法的基础上提出了一种多项式复杂度的代数软判决 译码算法紧接着。g r o s s 埔1 及k s t t e r 采l v a r d y i l 6 1 分别对前端和j 舌端算法作出了简化改进。该算 法较硬判决算法( h d ) 有着明显的增益，从而宣告了r s 码软判决译码时代的到来；从此，g a u s s 算 法【1 - i 。c h e r n o 蹲法f l s 】，w a t e r - f i l l i n gl i k e 算法1 1 9 】a b p 算法f 2 0 ；，分解算法 2 1 1 2 2 1 以及各种级联型 算法【2 3 l 接踵而至。然而软判决译码算法性能的改善同时伴随着复杂度的提高；2 0 0 5 年，r s 码最大 似然译码( m l d ) i ；1 题被g u r u s w a m i 口v a r d y 证明是n p h a r d 问题。寻找逼近m l d 性能且低复杂 度的r s 码译码算法成为了纠错码领域的一个炙手可热的问题。 关于r s 代数软判决算法( a s d ) i 拘研究，上个世纪末以来，s u d a n 1 2 1 ，g u r u s w a m i 1 3 1 ，n i e l s e n 2 s l k s t t e r ，v a r d y f l 4 1 ，r o t h 和r u c k e n s t e i n 2 0 1 ，m c e l i e c e 2 r l 以及g r o s s 1 5 1 等人分别作出了卓有成效的 工作。 本文介绍了嗍的几种译码算法并给出了性能仿真结果，讨论了k v 算法的重编码改进方 案，在此基础上，我们的工作重点是。面向算法的硬件实现，着重分析了算法的运算复杂度。并 与b m 算法做了比较，此外还分析了算法的模块化分解和v l s i 结构设计 1 4论文安排 本文的主要内容包括r s 码代数软译码算法的理论分析、性能仿真、算法简化方案及复杂度分 析。文章共分六章。本章为绪论部分。第二章中我们将介绍代数中有限域的基本知识及代数软译码 算法用到的组合数学的相关概念。第三章中我们着重讨论r s 码的编码等相关概念和r ，s 码的硬判决 译码( b m 算法1 。重点是第四、五两章。第四章中我们将详述r ，s 码代数译码算法，包括代数列表译 码算法( g s 算法1 ，以及代数软译码算法的原理、各厉端子算法的实现、前端算法性能界的分析以及 算法性能仿真结果并加以比较：紧接着我们分析了代数软译码的改进算法，主要是对后端算法的简 化，这对算法的实现和性能改善都有重要意义。第五章中，我们分析并统计了算法的实际运算复杂 度，并从列表译码的角度着重仿真统计了算法的平均列表大小，然后对算法模块化分解及硬件结构 设计傲了讨论，这将有助于将来算法的硬件实现与应用。文章的最后是对自己工作的总结。 3 第二章代数初步 本章介绍后面将要用到的代数基本知识，内容基本是描述性的，并不追求严格的数学推导。 2 1代数基本概念一群和域 定义2 1 一个定义了二元运算术的集合g 如果满足以下条件，则称其为群。 i 二元运算木满足结合律； 玩g 中包含一个元素e ，使得对g 中任意元素a ，有 元素e 称为g 中的单位元 谢对g 中任意元素a ，在g 中存在另外个元素a ，满足 口宰o ，= a ，丰a = e 元素a 7 称为a 的逆元，a 同样是口的逆元 如果g 上的二元运算+ 同时满足下面的条件，则称g 是交换群或a b e l 群：对g 中任意的n 和b ，有 定理2 1 群g 的单位元是惟一的。 定理2 2 群中每个元素的逆元是惟一的 a 木b = b 书a 定义2 2 称定义了+ ，和q ”两种二元运算的集合冗为环，如果： t 在吓r 是一个交换群。 玩也。运算满足封闭性 i i i q ”对斗”运算满足分配率，即对r 中任意三个元素a 、6 和c ，有 c t ( b + c ) = n b + n c 下面我们用群的概念引出域的概念。 5 东南大学硕士学位论文 定义2 3 设f 为一组元素的集合，在其上定义了加法+ ，和乘法俩种二元运算。如果满足下列 条件。则集合f 与这两种运算，和t l 一起称为域： i 在加法斗吓f 是一个交换群。关于加法运算的单位元称为f 的零元或加法单位元，记为o i i f 中的非零元素在乘法吓构成一个交换群关于乘法运算的单位元称为f 的幺元或乘法单 位元。记为1 。 饿。乘法对加法满足分配率，即对f 中任意三个元素口、6 和c ，有 口( b + c ) = n b + d c 域中元素的个数称为域的阶一个含有限个元素的域称为有限域。t 域具有以下一些基本性质： 性质2 1 0 1 对域中任一元素a ，有口0 = 0 a = 0 性质2 1 0 2 对域中任意两个非零元素a 和b ，有a b 0 性质2 1 0 3 口b = o r a 0 ，则6 = 0 性质2 1 0 4 对域中任意两个元素a 和b ，有 - ( a b ) = ( 一n ) b = d ( - b ) 性质2 1 0 5a 0 r a b = n c ，则b = c 如，峋验证，集合 o ，1 ) 在模二加法和模二乘法下是一个含两个元素的域。通常称其为二元域， 记作g f ( 2 ) 。又如，同样可验证p 7 为素数时集合 o ，1 ，2 ，p ，一1 ) 在模加法和槲乘法下是一 个p 7 阶域通常称之为素域，4 a 作c f ( p ) 。通常我们将q 阶有限域表示为g f ( 口) ( 在不致混淆时也简 记为f ) 。为了纪念近世代数的奠基人g a l o i 8 ，有限域也称为g a l o i s 域- 定义2 4 有限域g f ( 口) 中。使得幺元1 的和：。1 = o 的最小正整数入称为该域的特征” 定义2 5 对于有限域g f ( q ) 中的非零元素a ，使得口“= 1 的最小正整数称为域元素n 的阶。 定义2 6 如果q 的阶为口一1 ，称q 是g f ( 口) 域的本原元素。 2 2g a l o i s 域扩域的构造 通常我们可以在任意g a l o i s 域g f ( g ) 构造纠错编码，口既可以是质数也可以是质数的幂。但在 纠错码理论中应用最广泛的是二元域g f ( 2 ) 以及它的扩域g f ( 2 “) 。因此，在这一节中，我们将主 要介绍扩域g f ( 2 ”) 的构造。但大部分结论都能够推广至任意质数域的扩域 我们先定义系数在二元域中的一元多项式，( z ) ： f ( x ) = f o + z + 厶z 2 + + 厶z ” 6 ( 2 1 ) 第二章代数初步 其中 g f ( 2 ) 。多项式的次数是非零系数对应的最高幂次g f ( 2 ) 上的多项式可以进行普 通的加减乘除运算。设9 ) 为另一个一元多项式 9 ( z ) = g o + 9 1 z + 9 2 x 24 - + g l x ，( z ) 与9 0 ) 的加( 减) 法等于两者相同次幂的系数相加( 减) ( 假定2 n ) ， ( 2 2 ) ，( z ) + 9 ( z ) = ( ，0 + g o ) + ( + 9 1 ) x + + ( ，l - t - 9 1 ) z + ，n z “( 2 3 ) 其中 + 9 沩模2 加( 减) 运算。，0 ) 与9 ( z ) 的乘法等于多项式展开： ，( z ) - 9 ( z ) = c o + c l z + c 2 铲+ + 岛+ i z “ ( 2 4 ) 其中 q = 至强，嚣* 搦i n 亿5 ， 可以证明g f ( 2 ) 的多项式满足交换律，结合律和分配律事实上，这些多项式的集合构成了一个 环，通常称为多项式环 我们假定9 扛) 为非零次多项式，用，( z ) 除以9 ( z ) ，我们得到了唯一确定的商式口( z ) 和余式r ( z ) ： ，( z ) = q ( x ) g ( x ) + r ( z ) ，d e g r ( z ) d e g g ( z ) 上面的表达式通常被称为e u c l i d 除法。 ( 2 6 ) 定义2 7 设，( z ) 是非零次多项式，若，( z ) 不能被次数低予自身且不为零的任何多项式除尽，那么 我们称它为既约阳咒如c 砧叫多项式。 定理2 3g f ( 2 ) 中次数为f 的既约多项式整除一一1 + 1 定义2 8 设， ) 是既约多项式，若能被， ) 整除的护+ l 的最小i f _ 整数n = 2 m 一1 ，那么我们称它 为本原佃n m i 托t ，0 多项式。 接下来，我们将定义一个新符号o t ，以及一种乘运算“”： o 。0 = 0 0 - i = 0 1 1 = 1 0 a = a 0 = 0 1 q = q i = q 口25 口口 一= o z - a 口ut i m e s ) 7 ( 2 7 ) 东南大学硕士学位论文 根据以上定义可以推出： 0 = 一0 = 0 1 一= 一1 = 一 乜一= 一q = q t q 这样。我们就得到了一个乘法运算“”的非空集合 f = o ，1 ，q ，o t 2 ，一，) ( 2 8 ) ( 2 9 ) 其中元素，1 通常用扩表示。 我们接下来对q 加上一些条件，限制f 的元素个数为2 m 。假定q 是本原多项式的根， 令p ( z ) 为g f ( 2 ) 上的一个m 次本原多项式，即p ( a ) = 0 。因为p 扛) 能整除z 2 ”一，所以 将q 代入上式，得到 又因为p ( a ) = 0 故 两边同时加1 ，得 z 2 ”一1 + 1 = q c x ) p ( x ) 口2 ”一1 + 1 = q c - ) p ( a ) o 2 ”一1 + 1 = 口( 口) o q 2 “一1 = 1 因此，在p ( q ) = o 的条件下，集合f 变成有限集合，包含以下元素 f + = o ，1 ，q ，q 2 ，q 2 ”一1 ( 2 1 0 ) ( 2 1 1 ) ( 2 1 2 ) ( 2 1 3 ) ( 2 1 4 ) 不难得出，乘法运算“，关于f 闭合，满足交换律和结合律，且1 ，口，口2 ，乜2 “一1 为不同的元素。 因此，非零元素构成了一个阶数为2 ”一1 的交换群。 我们再为集合p 定义加法运算十，并使得f + 构成加法+ 上的交换群。我们用p ( z ) 除，0 i 2 m 一1 ，得： = 吼( z ) p ( z ) + 口i ( z ) ( 2 1 5 ) 其中，m ( z ) 为商式，a i 扛) 为余式。t l 专式a t ( z ) 的次数不大于m 一1 ，可以写成以下形式： a i ( z ) = a ，o + a i , l x + a i , 2 x 2 + + n t 仇一i t , 仇一1 ( 2 1 6 ) 又因为和p ) 是互质的( 除常数以外没有任何公因子) ，不能被p ) 除尽。因此，对于任意t 0 。 n i ( z ) o( 2 1 7 ) 若o i ，j 2 m 一1 ，且i j ，则能用反证法证明 m ( z ) d j ( z )( 2 1 8 ) 8 第二章代数初步 因此。对于不同的i = 0 ，1 ，2 ，2 ”一2 我们得到次数不大于m 一1 的2 ”一1 个不同非零多项 式n i 0 ) ，再将q 代入式2 1 5 ，并利用条件q t ( c t ) 0 = 0 ，我们得到口的多项式表示： q = 口t ( 口) = 口t 。o + a i ，l q + n ，2 0 r 2 + + a i , m - 1 0 t ”一1( 2 1 9 ) 此外，p 中的0 元素用零多项式表示。最终，我们用次数不大于m 一1 的2 m 个不同的多项式表示 了p 中2 ”个不同元素。现在我们可以定义，上的加法运算为： 0 + 0 = 0 0 + q = q + 0 = q 口+ 一 =( o t 。0 + 毗。i 口+ a i , m - l o b ”一1 ) + ( ，o + a j ，1 a + 矿一1 ) ( 2 2 0 ) = ( 龟o + o ) + ( 8 ，l + a 1 。x ) c z + + ( 口i ，m l + m i ) a ”一1 其中o i ，j 2 m l ，口t 七+ q 七是g f ( 2 ) 上的模2 加运算，0sk 仇。从式2 2 0 可得， q + 矿= 0 ( 2 2 1 ) 而且，+ 一定是次数低于2 m 一1 的多项式，因此集合f 对于加法运算+ 封闭。因为模2 加满足 交换律和结合律，所以加法运算+ 也同样满足交换律和结合律而且式2 2 l 说明集合f 中所有元素 的逆为它自身。事实上，加法和乘法在集合f 上同样满足结合律。因此： 定理2 4 式2 0 彳中定义了+ 和两种运算的集合f + 是元素个数为2 “的有限域 通过以上步骤，可以构造g f ( 2 ) 的有限扩域o f ( 2 m ) ，该域的特征为2 ，并给出了扩域元素的 两种表达形式：幂形式和多项式形式。用幂形式进行乘法运算非常方便，用多项式形式进行加法运算 十分方便因此，在实现有限域运算时，我们通常利用幂形式进行乘法运算，利用多项式形式进行 加法运算，然后再利用查表完成幂形式与多项式形式间的相互转换。 例：设m = 4 ，多项式p ( z ) = 1 + z + z 4 是g f ( 2 ) p 的一个本原多项式。设p c a ) = 1 + q + a 4 = o 。据此我们可以构造g f ( 2 4 ) 。表2 1 给出t g f ( 2 4 ) 中所有元素的三种表示方式。我们可以反复利 用等式= l + n 来计算其他元素的多项式形式。妇： a 5=q a 4 = q ( 1 + q ) = q - t - a 2 a 6 = a a 5 = q ( q + a 2 ) = q 2 + q 3 q 7= q a 6 = q ( q 2 + a 3 ) = a 3 + a 4 = l + q + q 3 表2 1 中还给出了域元素的另种表示法：m 维向量表示，即如果域元素届的多项式表示为：p = 口o + 0 1 q + + a m - l o l ”，则口的向量表示为( ，口l ，a m - 1 ) 9 东南大学硕士学位论文 表2 1p 0 ) = 1 + z + z 4 t t 成的a f ( 2 4 ) 的元素的三种表示 幂表不多i 贝式表不 向量表示 00 ( 0 0 0 0 ) 11 ( 1 0 0 0 ) 口o t ( 0 1 0 0 ) q 2口2 ( 0 0 1 0 ) q 3q 3 ( 0 0 0 1 ) q 4l + a ( 1 1 0 0 ) a 5 a + q 2 ( 0 1 1 0 ) n 6q 2 + q 3 ( 0 0 1 1 ) q 7l + q + a 3 ( 1 1 0 1 ) q 8 1 十o t 2 ( 1 0 1 0 ) q 9a + q 3 ( 0 1 0 1 ) n , l o 1 + a + q 2 ( 1 1 1 0 ) q l lo t + a 2 + q 3 ( 0 1 1 1 ) q 1 2 1 + q + q 2 + q 3 ( 1 1 1 1 ) q 1 3 1 + o t 2 + o t 3 ( 1 0 1 1 ) o t l 41 + 0 3 ( 1 0 0 1 ) 定义2 9 设p 是g f ( 2 ”) 中的一个元素，毋( z ) 是g f ( 2 ) 上使咖( p ) = o 的最低次多项式，称( z ) 为卢的 最小多项式 最后，我们以定理的形式不加证明的给出有限域的一些性质，详细推导请参阅文献【：8 | 定理2 5 ，( z ) 是g f ( 2 ) 上的多项式，芦是g f ( 2 ) 扩域的元素。如果p 是，( z ) 的根，那么，：， o 也是，( z ) 的根 定理2 6g f ( 2 ”) 上的2 ”一1 个非零元素构成了z 2 ”+ 1 的所有的根。 定理2 7 域中元素p 的最小多项式( z ) 是既约多项式。 定理2 8 元素夕为g f ( 2 ”) 中的元素，e 为满足2 。= p 最小的非负整数。则 c l m ) = ( 卅p 2 ) ( 2 2 2 ) i = 0 为g f ( 2 ) 上的既约多项式，也是p 的最小多项式，且次数为e ，e 7 n 。 定理2 9 元素p 为a f ( 2 “) 中的本原元，则矿，夕r ，也是本原元。 定理2 1 0 元素p 为g f ( 2 “) 中的n 阶元素，则p 2 ，p 2 2 ，的阶也为n 。 2 3 有限域上的二元多项式 本节介绍的有限域上的二元多项式的基础知识是理解r s 码列表算法和代数软判决译码算法的 基础。我们从二元多项式的定义说起，然后引入单项式和多项式排序的概念，最后会介绍多重零点 及h a s s e - , 导数的概念【盯ip 9 1 1 0 第二章代数初步 定义2 1 0 我们将系数取自有限域f 中的二元多项式环记，b f x ，y 】， 如下： 0 0 q ( z ，) = 矿 i = 0j = o 多项式q ，可) f k ，们的定义 ( 2 2 3 ) 其中只有有限个系数8 t j 为非零 表达式2 2 3 是二维的形式，但后边我们希望将其表示为一维的形式。为此我们需要为单项式集合 m 扛，们= 矿h j o ) 定义一种排序。可以采用下面的加权阶数单项式排序：设数对( u 。，) ，其中，u i 均为非负整数， 且不同时为o 。则单项式矿的( ，) 加权阶数定义为 d e g ( w w ) x 矿= t + j 依此( ，) 一加权阶数我们可以对集合m 陋，胡中的任意两单项式九( z ，) ，咖6 ( z ，! ，) 进行如下排 序： 果d e g ( 。；，“ ) 。( z ，可) d e g ( 。) 咖b ( z ，可) 则西。( z ，! ，) b ( z ，) 但这还不是一个全排序， 对于具有相同( u 。，) 一加权阶数的单项式，我们采用如下反词典序( r e v e r l e x i c o g r a p h i co r - d e r ，r e v l e x ) 定义2 1 1 ( “k ，“) 一加权反词典序定义为：z 1 矿1 z 缸矿，当“k i l + “歹l i 2 例如：不论采用何种排序，我们都有z 2 可 t 3 y ；如果我们定义( 地，岣) = ( 1 ，3 ) 且采用加权反词典 序，则z 6 z 3 y 可2 。 设 为( “k ，“) 一加权反词典序，则我们可以对集合m 中的所有单项式进行排序： l = o ( z ，l ) 咖1 ( z ，秒) 妒2 ( z ，y ) 依据这种排序我们可以将式2 2 3 改写为一维形式： j q ( x ，耖) = n j 咖( 删) j f f i o ( 2 2 4 ) ( 2 2 5 ) 其中口f f ，n j 0 。整数j 称为二元多项式q ( z ，! ，) 的阶数( r a n k ) 。单项式，称为q ( z ，可) 的首单 项式我们将此记为r a n k ( q ) = 3 以及l m ( q ) = 咖j ( z ，y ) 。另外我门引a - - 元多项式的相等关 系p 三q ，它表示l m ( p ) = l m ( q ) 。我们还可以将前面定义的排序“ ”拓展到二元多项式 环f k 们上，我们定义p q ，如果l m ( p ) l m ( q ) 。这样“ 南协3 3 ， 1 2 第二章代数初步 在后面我们可以看到，根据上面的两个引理能导出代数软判决译码算法性能的一松一紧的两个重要 的性能界。 代数曲线的理论在r s 码编译码理论尤其是我们要讨论的代数列表算法和代数软译码算法中有 重要应用事实上r s 最初就是通过代数曲线( 即多项式) 的方法构造出来的。下面我们讨论二元多 项式的零点，尤其是多重零点的概念和性质。 如果多项式q ( z ，耖) f k 引，且q ( q ，p ) = 0 ，( q ，p ) f 2 ，其中f 2 = fxf 为二维向量空间 我们就称q 在( 口，p ) 处有一个零点，或者称曲线q ( z ，爹) = o 通过点( q ，p ) 。然而，我们更感兴趣的是 多项式的多重零点 定义2 1 3 如果q 缸，3 ) 不含有( 1 ，1 ) 珈权阶数小于m 的单项式，l i p a j = 0 ，如果t + j m ，我们 称多项式q 伽，v ) = ，ja i j x f z ，引在点( o ，o ) 处有m 重( 或m 阶) 零点，并且记作 o r d ( q ：0 ，0 ) = m 类似的如果q 仁+ 口，矽+ 厣) 在( o ，o ) 处有m 重零点，我们称多项式q ( 2 ，芗) 在点( q ，p ) 处有m 重零 点，并且记作 o r d ( q ：a ，卢) = m 如果已知q ( z