（应用数学专业论文）域fq上的q1k循环码的研究.pdf

中山大学硕士学位论文 域舀上的k 一1 ，七】循环码的研究 专业： 姓名： 指导老师： 应用数学 朱书威 胡国权 摘要 研究码的纠错能力，也就是分析码长n 、信息位t 、码的最小距离d 之间的 关系，是编码理论中一个重要的课题。奉文主要研究的是域c 上的循环码当码 长nt q 一1 ，信息位t 确定时，最小距离d 与t , 七之间的关系。 由于线i 生空i b j “与域上的多项式剩余类坏c 【z 】，- 1 是同构的( 仅考虑 加法) ，所以一般用多项式来研究循环码。循环码是多项式剩余类环c 工”- 1 的一个主理想，因此可以由它的生成多项式g ( x ) 生成。循环码的最小距离与它 的生成多项式的根的形式有直接的联系，我们已经知道设计距离为6 的b c h 码 的最小距离d 6 。 因为循环码是一个特殊的线性子空间，我们希望从空间的基来研究循环码的 最小距离。由于，l 维线性空间的维子空问的基不是唯一的，所以我们希望构 造出能体现循环码性质的基。 本文通过m a t t s o n s o l o m o n ( m s ) 多项式构造域c 上的【t l , 七】循坏予空间的一 组基，其中n ；口一1 。在定理7 中，我们证明了：若l n ，那么可以构造出伽，k ，j n 循环子空间，并且任意的m ，七】循环子空问的最小距离dz 芸。特别地，若g 是奇 k 数，则2 i ( g 一1 ) ，那么存在【q 一1 芝 ，2 】循环子空间c 。令g m ，则循环子空 问c 的码率为r 一去，但最小距离仍然是2 。 在第3 章中，我们综述了由v g u r u s w a m i 和m s u d a n 于1 9 9 9 年提出来的 对r s 码的列表译码算法。 关键词：码率，最小距离，循环码，m s 多项式，列表译码。 中山大学硕士学位论文 t h er e s e a r c ho n q - l , k 】c y c l i cc o d e so v e re q m a j o r ：a p p l i e da a t h e m a t i c s n a m e ：z h us h u ，c i s u p e r w i s o r ：h ug u o q u a n a b s t r a c t t h er e s e a r c ho ne r r o r c o r r e c t i n ga b i l i t yo fac o d ei st oa n a l y s i st h er e l a t i o n s h i p b e t w e e nc o d el e n g t hn ，i n f o r m a t i o nb i tk a n dm i n i m u md i s t a n c ed t h i sw o r ki s t os t u d yt h er e l a t i o n s h i pb e t w e e nda n dn ，kw h e r en ，ki sf i xo fc y c l i cc o d e s o v e r f ：i si s o m o r p h i ct ot h e r e s i d u ec l a s sr i n g f x l x n 一1 ( c o n s i d e r e do n l ya sa n a d d i t i v eg r o u p ) ，u s u a l l yw es t u d yc y c l i cc o d e sb ym e a n so fp o l y n o m i a l c y c l i cc o d e i sap r i n c i p a li d e ao ff x l x 4 1 ，s 0t h e r ee x i s ta ng e n e r a t o rp o l y n o m i a lg ( x ) w h i c hg e n e r a t e st h ec y c l i cc o d e i ti sk n o w nt h a tt h em i n i m u md i s t a n c eo fac y c l i c c o d eh a sc l o s er e l a t i o n s h i pw i t ht h er o o t so fi t sg e n e r a t o rp o l y n o m i a l f o rc y c l i cc o d e sa r es p e c i a ls u b s p a c e so fal i n e a rs p a c e w eh o p et oc o n s t r u c ta b a s i sf o rac y c l i cs u b s p a c e b ym e a n so ft h em a t t s o n - s o l o m o np o l y n o m i a l ，w e c o n s t r u c tab a s i sf o rai n , k 】c y c l i cs u b s p a c eo v e r 只w h e r en 。q 一1 i nt h e o r e m 7 ，w es h o wt h a tt h e r ee x i s t s 砷，女，_ n 】c y c l i cs u b s p a c e s ，i fkin a n dt h em i n i m u m 庀 d i s t a n c ef o ra n yi n ，七】c y c l i cs u b s p a c ei sn ol e s st h a n _ n e s p e c i a l l y , i fqi so d d ， 托 t h e r ee x i s t s 【口一1 ，! 王 ，2 】 c y c l i cs u b s p a c ec l e tq ，。t h e nt h er a t e 。fc i s 三，b u t t n e 瓶t a n c e 。r c 趣。n ，2 t h i si sas u l p r i s i n s r e s u m c h a p t e r3i sas u m m a r yo ft h el i s t d e c o d i n gs c h e m ef o rr e e d - s o l o m o nc o d e i t w a sc o n s t r u c t e db yvg u r u s w a m ia n dm s u d a ni n1 9 9 9 k e yw o r d s ：r a t e ，m i n i m u md i s t a n c e ，c y c l i cc o d e ，m a t t s o n s o l o m o np o l y n o m i a l ， l i s t d e c o d i n g 中山大学硕士学位论文 第1 章背景介绍 1 1 通信系统的模型 在使用纠错码技术前的通信模型如图( 1 - 1 ) 所示： 信源，信源编码器 洞制器 噪声源 信宿信源浒码器 ， 信道 解调器 幽( 1 1 ) 图( 1 1 ) 中，信源编码器把信源发出的信息如图象、文字等转换成二进制 ( 或多进制) 的信息序列m 。在调制器中，把输入的信息序列m 变换为适合于 在实际信道中传输( 或存储) 的信号波形。调解器的任务就是将信号波形还原为 信息序列优，信源译码器再将信息序列m 7 转换成原始信息( 如图形或文字) ，这 就是一个完整的通信过程。出于信道会受到种种干扰( 如对于无线电信号来说， 自然界存在地、电磁源以及其他无线电系统发射的信号等) ，信号波形在信道中 传输时，不可避免地会发生变形出错。如果发生错误，解调器还原的信息序列m 7 就不是信源编码器所产生的信息序列m ，信源译码器所还原的信息也跟着出错， 那么信宿收到的信息与信源发送的信息是不同的。所以这样的通信模型是不能确 保快速、可靠的通信目的。那么怎样才能在有噪音的信道中进行快速、可靠的通 信呢? 我们修改以上的通信模型，在信源编码器与调制器之恻增加一个信道编码 器，相应地在解调器与信源译码器之间增加信道译码器，如图( 1 2 ) 所示： 巾山大学硕十学位论文 信源叫信源编码器1叫信道编码耦 j ? 噪声源 信宿信源译码器信道洋码器 一调制器 ， 信道 解调器 图( 1 2 ) ( 现实中任何一个具体的数字通信系统如通信、遥控遥测、计算机内的数据存储 都可以用图( 1 2 ) 束表示) 我们希望增加信道编码器来抗击传输过程巾的各种干扰。信道编码器将信源 编码器所产生的信息序列m 按一定的规则增加一些多余度( 多余度出m 确定) 变成序列c 。再通过调制器把序列c 变换为信号波形在信道中传输。信道译码器 对解调器输出的序列c7 进行检验，看它是不是满足信源编码器中所用的规则，如 果满足我们则认为序列c 7 就是序列c ，并且把c 7 还原成信息序列m ：如果c 7 不能 满足信源编码器中所用的舰则，则根据约定的法则将序列c 7 还原成序列c 后再将 c 还原成信息序列m 。这样就可以达到可靠通信的目的。 在信道编码器中，怎样将信息序列m 变换成信息序列c ，并且使c 具有所需 的纠锚能力呢? 而在信道译码器中，又是如何将与c 不同的信息序列c 7 还原成c 呢? 以上两个问题就是纠错码所要研究的核心内容一一编码与译码。 具体来讲，我们采用差错控制编码，其基本实现方法是在信道编码器中将要 传输的信息附上一些监督码元，这些多余的码元与信息码元之间以某种确定的规 则相互关联( 约束) 。信道译码器中按照既定的规则校验信息码元与监督码元之 间的关系，一旦传输发生差错，则信息码元与监督码元的关系就受到破坏，从而 信道译码器就可以通过某些信息发现错误乃至纠f 错误。差错控制随着差错控制 编码理论的完善和数字电路技术的飞速发展，信道编码已经成功地应用于各种通 中山大学硕士学位论文 信系统中，并且在计算机、磁记录与各种存储器中也得到日益广泛的应用。 为了进一步说明，我们先介绍纠错码的几个基本概念，我们假设信息用有q 个不同字母的字母表q 进行编码，下边我们要讨论的是字母表q 为域e ，其中 目= p7 ，p 是个素数。 分组码：对每段长为k 的信息序列m ，以一定规则增加，= n k 个校验元， 变成长为n 的序列c = ( c 。，c ：，气) ，称序列c 为一个码字，n 称为码长：存域一 _ = ， 共有矿个不同的信息序列，相应的也有矿个码字，称这矿个码字集为阮k 】分组 码c 。 线性分组码：域c 上码长为n 的线性分组码c 就是域c 上的_ ，l 维线性空阳j 的 一个子空间：如果c 的维数为k ，那么称c 为一个i n ，k 】线性码，k 称为【n , k 】码 的信息位长。 码率：码率r ；k n ，k 为信息位的长度，n 为码长。它反映了传输信息的 效率；码率越高，传输信息的效率就越高。 距离( h a m m i n g 距离) ：假设码字x c ，y c ，那么码字x 与y 的h a m m i n g 距离定义为：d ( x ，) ，) _ i f i t y i , x i ，y ，c l 。 码c 的最小距离：码c 的最小距离d - m i n d ( x ，y ) i 比，y c ，x y 。如果 i n ，詹】线性码c 的最小距离为d ，则记c 为【，l ，k ，d 】线性码。最小距离反映了分组 码纠错能力的大小，最小距离越大，码的纠错能力就越强。 ( i l q 率r 和码的最小距离d 是【，l ，k 】码最重要的两个参数。编码的主要任务就 是码率r 一定，构造最小距离d 尽可能大的码：或最小距离d 一定，构造码率r 尽可能高的码。 3 中山大学硕士学位沦文 0 1 jd ( d 1 ) ，2 幽( 1 3 ) 从图( 1 - - 3 ) 看到码c 的最小距离d 与其纠错能力的关系：对于一个【n ，k ，d 1 码，由于以码字c ；( c 1 ，c ：，巳) 为球心，以f 。d - ! 为半径的h a r e m i n g 球是互不 相交的。所以当码字c ；( c l ，c 2 ，) 在信道中发生，s 之 位错误时，阮七，d j 码 是能够将这t 个错误唯一地纠正过来的。 那么码c 的最小距离跟什么有关呢? 推论1 ：( s i n g l e t o n 限) 域c 上的，后，d j 码的最小距离ds n t + l 。 证明见【1 】，此处从略。 1 2 编码 1 2 1 编码的主要思想 编码的任务就是找一个域上的编码函数e ：一“，将域上长为k 的信息肌= ，m ：，) 映射到域上长为以的e ( m ) 一( c 。，c ：，c n ) ，其中m ， c i c ，= l ，2 ，k ，i l ，2 ，n 。显然我们要求编码函数是单射函数，而且 要求编码函数e 不同的象( 码字) 之间的h a m m i n g 距离不要太小，这样构造出 来的码才具有一定的纠错能力。 由于域e 上m ，k 】线性码c 是 维线性空阃的一个女维子空问，所以它的编 码问题就是在域e 上的n 维线性空间k 中，如何找出码的最小距离满足一定条件 4 中山大学硕士学位论文 的，有矿个向量的i 维线性子空间k 。而，l 维线性空间k 中的七维线性子空间 k 。是齐次线性方程组： 也即： 口1 l c i + 口1 2 c 2 + + n h c n 篁0 口2 l + a 2 2 x 2 + + 口2 上 = 0 a n _ k , l c l + 谊n i 七2 c 2 + + 口 一月c n 暑0 口l la 1 2 n l h a 2 1a 2 2 口2 “ a h j1a 一 ，2a 一t c 1 c 2 ： c 1 0( 1 2 ) 的解空问。其中日，；1 2 ，l - k ，i = 1 ，2 ，l ；在公式( 1 2 ) 中n x ( n t ) 的矩阵记为h ，h 的秩为h k 。称矩阵h 为i n ，k 】线性码c 的一致校验矩阵。 i n ，七】线性码c 有q 个码字，因此可以在这矿个码字中选出k 个线性无关的 码字，那么这个k 维线性子空间就可以由这k 个码字作为一组基生成。设这k 个 码字为： c lt ( g i 】，9 1 2 ，g l j l ) c l = ( 9 2 1 ，9 2 2 ，9 2 。) c l 一( g g ，g h ) 若把这k 个向量作为矩阵的行，则有： g _ 占l l 9 1 2 9 2 19 2 2 g l 9 2 。 gk 1g k 2 g h 那么f 1 1 , 七】线性码c 的任意码字都可以表示成为： c m g 。( ，l ，m ：，m ) i 肠 g a 2 9 1 9 2 29 2 。 g k 19 1 2 g h ( 1 3 ) 其中，m 一 。，m ：，) 是七个信息元组成的信息组，m i ，i - l 2 ，k 。那么 中山大学硕士学位论文 通过公式( 1 - 3 ) 就可以对任意信息m = 仰。，m ：，m 。) 进行编码了，这也就完成 了一个编码过程。称矩阵g 为【n , k 】线性码c 的生成矩阵。 由于域ce 的n 维线性空间k 的维子空问k ，。不止- - 9 ，那么对于固定的 ，l ，k ，怎样找到k 维子空间v 。也就是k 七】线性码c 使得码c 的最小距离d 达到 最大，满足这样性质的码称为最优码【2 】。这就是编码要考虑的核心问题。 那么对于一个i n ，】码c ，它的最小距离是由什么决定的呢? 它与哪些因素 有关? 我们将讨论在域c 上i n ， 】循环码的最小距离与它的基之j 1 _ 】j 的关系，其中 h ；q 一1 。这也是本文的主要目的。 1 2 2b c h 码与代数几何码 1 9 5 0 年h a m m i n g 构造了纠讵单个随机错误的h a m m i n g 码以后，经过了近 l o 年，才于1 9 5 9 年由h o c q u e n g h e m ，1 9 6 0 年出b o s e 和r a y - c h a u d h u r i 分别提 出了纠正多个随机错误的循环码一- - b c h 码的构造方法。b c h 码是迄今为止所 发现的一类最好的线性纠错码：它的纠错能力强，特别是在短和中等码长下，其 性能接近于理论值，并且构造方便，编码简单，特别是它具有严格的代数结构， 因此它在编码理论中起着重要的作用。 1 9 6 0 年，p e t e r s o n 从理论上构造了二进制b c h 码的译码算法，奠定了b c h 码译码的理论基础，稍后，g o r e n s t e n 和z i c r l e r 把它推广到多进制。1 9 6 6 年， b e r l c k a m p 提出迭代译码算法，从而大大加快了译码速度，从实际上解决了b c h 码得译码问题【1 】。 代数几何码是前苏联数学家v d g o p p a 在1 9 8 0 年前后发现的，丌始并没有 引起人们太多的注意。直到1 9 8 2 年，t s f a s m a n 等人证明了一个惊人的结果：存 在渐进好的代数几何码，超过g l b e r t - v a r s h a m o v 界。在此之前人们只知道存在渐 进好码达到g l b e r t v a r s h a m o v 界，而且还从未能具体地构造出这样一列渐进好 码。由于t s f a s m a n 等人关于代数几何码的工作，代数几何码成为编码理论中的 一个热点【1 1 】。 6 中山大学硕士学位硷文 1 3 译码 1 3 1 译码准则 怎样将被破坏了的信息码元与监督码元之间的关系有效快速地发现甚至纠 正过来，这就是译码所要解决的问题。设收到的字为r ，发送端发送的码字为c ， 错误模式为e ，贝t j c 一，一e ，这样只要把e 找出来了，c 就可以从，巾恢复过来。 在译码之前先确定译码准则，以下是主要的译码准则： ( 1 ) 最大似然译码( m a x i m u ml i k e l i h o o dd e c o d i n g ) ：假设收到字，希望找 到码字c 使得，一c 即错误模式e 发生的概率最大。 ( 2 ) 最近距离译码( n e a r e s tc o d e w o r dp r o b l e m l ：假没收到字r ，希望找到码 7 - c 使得d 。( r ，c ) 一m i n d z ( r ，口) i v a e c 。 ( 在一个“一个比较多的错误发生的概率比一个比较少的错误发生的概率要 小”的信道上译码时，m l d 译码等价于n c p 泽码。) ( 3 ) 列表译码( l i s t d e c o d i n g ) ：对给定的一个错误界z ，希望找到满足 d 。( r ，c ) sf 的所有码字c 。( 当r ，d ( d 为码的最小距离) h e ，满足条件的码字c 可 能不止一个) ( 4 ) 有界距离译码( b o u n d e dd i s t a n c ed e c o d i n g ) ：对给定的错误界e ，希望 找到唯一的码字c ，使得c 满足如( ，c ) s e ：若不存在则不输出。 ( 5 ) 唯一译码( u n i q u e d e c o d i n g ) 错误界p 。之 的有界距离译码，其中d 二 为码c 的最小距离。 1 3 2 唯一译码 假设码c 的最小距离为d ( d 为偶数) ，码字c l ，c 2 e c 且d p ，c ：) = d ，如果 收到的字r 有d ( r ，c 1 ) 一吾且d ( r ，c ：) t 罢( 其存在性见【3 】) ，如图( 1 4 ) 所示： 7 中山大学硕士学位论文 d c 1 、， c 2 幽( 1 4 ) 那么译码器就不知道要把字r 纠正成c ，还是c ：。所有当错误模式p 的h a m m i n g 重 量w ( p ) 苫要时，译码器不能保证将每个收到的字，按唯一译码准则正确的纠正过 来。为了保证能唯一译码，传统的译码算法都是在错误模式e 的h a m m i n g 重量 w ( e ) ；乏 的情况下构造的。 设发送码字为c = c 。，c ，巳一，) ，在有噪音信道中传输时，信道产生了错误 模式e = 瓴，q ，e 一) ，接收端收到的信息( 字) r = ( r 0 ，一) ，其中一c j + e i ， i ；o ，1 ，l 一1 。假设线性码的奇偶校验矩阵为h ，那么r h 7 = ( c + e ) 日7 一 e h 7 = s ，称s 为伴随式。可以发现伴随式s 与码字c 无关，只与错误模式e 有关。 译码的任务就是将收到的字，纠正为发送端发送的码字c ，由上面的式子可以发 现只要把错误模式e ；( e o ，q ，e 。) 找出来了，就可以从c = r - e 得到发送端发送 的码字。 怎么找错误模式e ，就是译码理论中一个核心的问题，不仅要考虑算法的正 确性，还要考虑算法的运行所需的时间。对不同码已经发现了不同的译码算法， 但是传统的译码算法都是从伴随式所提供的信息，判断或计算错误模式e 的值。 下边分一般线性码的译码，大数逻辑译码和b c h 码的译码进行综述。我们最后 将介绍近几年来比较热门的对r s 码的列表译码算法。 ( 1 ) 一般线性码的译码 【n ，k ，d 1 码的矿个码字是一个子群。若以这个子群为基础，把n 维线性空问中 8 中山大学硕士学位论文 的z 个元素划分成陪集，如表( 1 1 ) 所示： 表( 1 1 ) 泌 岛e 2q 勺一- c lc l + qc 1 + e 2c l + qc l + 。 c 2c 2 + qc 2 + e 2c 2 + q c 2 + e q 一_ 0 巳+ qo + 8 2巳+ q c e r 4 由于伴随式s 只与错误模式e 有关，所以找错误模式e 的最原始的办法就是 将错误模式e 与伴随式s 的对应关系预先计算好，列成一个表，称这个表为译码 表，然后将这个表存储在译码器中。当我们收到一个字r 时，先计算得出r h 7 的 值，也就是伴随式s 的值，如果坍7 = 0 ，即坍7 = 0 ，所咀e = 0 ，那么认为码 字c 在信道传输中没有发生错误，收到的字r 就是码字c ；如果埘7 ，0 ，说明 错误模式e 一0 ，那么逐一查找译码表，找到伴随式s 所对应的错误模式e ，然后 由c = r e 得到发送码字，这样就完成了译码工作。 以上算法的缺点也比较明显。对于阮k 】码，当n ，k 比较大时，例如在二元 域f 上，当，l 一1 0 0 , k - 7 0 时，我们相当于有2 ”一1 0 9 个伴随式，要将这么多个伴 随式存放在译码器中是不现实的【1 】。 那么自然会问能不能从伴随式s 所提供的信息直接求出错误模式e 呢? 下边 要介绍的大数逻辑译码及b c h 码的般译码说明是可以的。 ( 2 ) 大数逻辑译码 大数逻辑译码是1 9 5 4 年r e e d ，在译r e e d m u k “r m ) 码时提出的一种较简 单的译码方法。由于算法比较简单，所以在实际中有广泛的应用。 其基本思想是：对一致校验矩阵h 进行适当的初等变换变成h7 ，称日7 为正 交于码元位c 7 的正交一致校验矩阵。所谓的正交于码元位c 7 的正交一致校验矩阵 9 中山大学硕士学位论文 就是：若码元位c 7 出现在变换后的正交矩阵日7 中的每一行，而其它的码元至多 在矩阵h7 中的某一行出现，则称h 7 为正交于码元位c 7 的正交一致校验矩阵。 比如说在二元域最= o ，1 中，码字c = c o ，c 1 ，c 。) 。假设码元位c 。的正交 一致校验矩阵为h 。汁算伴随式s 7 e h 。，我们通过计算伴随式s7 的分量( 伴随 式是个向量) 中为1 的个数来判断码元位c 。的值是不是出错。若为1 的个数等 于正交一致校验矩阵h 。的行的个数，那么码元位c 0 的信息出错，我们就把它纠 正过来。因此是通过计算伴随式s 7 的分量为1 的个数米判断是否出错。判断完 了码元位c 。后，我们再按照上面的方法判断码元位c ，是不是出错，一直下去，直 到码字c 的所有码元位判断完为止。那么最后我们就得到一个错误模式e ，从式 子ctr p 我们就对收到的字r 进行了纠错【2 】。 大数逻辑译码在求错误模式e = 瓴，e ，e n 一。) 的时候，是对错误分量e i ( i = o , l ，h 一1 ) 一位一位地求的，那么我们能不能通过伴随式的信息一次就将 错误模式e = ( e 0 e 1 ，e n 一。) 就求出来呢? b c h 码的译码算法就足这样的一个算 法。 ( 3 ) b c h 码的译码 b c h 码的译码一直是编码理论研究中最感兴趣的课题之。一个码能否在 实际中应用，往往取决于译码器是否简单、快速、经济和译码错误概率小。 设域c 上的i n ，k ，d b c h 码以a “，c t m 。+ i ，a “一! 为根，那么它的生成多项式 为： g ( x ) 一 一口“) o o t o o + 1 ) o a “1 ) 其中d 一2 t 一1 ，口乞为n 次本原单位根。假设发送端发送的码字为 c ( x ) t q ( x ) g ( x ) ，接受端收到的信息为r ( x ) t c 和) + p 0 ) ，其中错误模式 e ( x ) = e o + q 工+ + 巳一。x ”1 。如果信道中产生了f 个错误。那么 e “) - y t l x + y t 2 x + + y l 工 1 0 中山大学硕士学位论文 其中y ，i e 0 ，1 ，f ) 。那么伴随式 陋“。) ”1 ( ( x m o + 1 ) “。 陋“o 。1 ) ” y 4 ( a “y + y ，! ( a “) 7 2 + + y ( a “) y 4 ( 口”n + 1 ) + 托( 口”。+ 1 ) 7 2 + + 托( 口机+ 1 ) y l t ( 0 l m o + 2 t - 1 ) l l + ) ，b 似”2 “y ! + + y “。1 ) 一r ( a ) 一e ( a “) 。+ 。一，( o ”。“) tp ( 口“) 5 ：。= ，但”。一1 ) = e 似”2 “) 称口。，为错误位置，不妨设。f j = _ ，那么 、+ ) f j = ( a 。) “= ( _ ) ”，其中 i o ，1 ，2 f 一1 ，j1 1 2 ，f 。所以以上方程组变形为： s = y l 。x 一+ y l t y | ? x ， s 。、“一y l i x l ? 4 1 1 + yl 2 x l ? q 1 + y 【j x i “ 5 ，。n l ；托 “+ 。一1 + m ：x t ! “。+ 。一1 + + y - ”。 我们的目的是从上边丑个方程中求出2 t 个未知数儿，一，其中f - 1 ，2 ，t 。 直接求解以上方程组比较困难，分两步进行；首先解出错误位置，然后再求解错 误值，为此引进错误位置多项式6 ( z ) 。0 一_ 工) ( 1 一x l z x ) 0 一_ 工) ，若工一气，那 么6 ) 一0 。所以从d o ) t o 的根我们可以求出错误位置。具体的求法我们可以 参照【2 】 o ；o y y 0 ；o 中山大学硕士学位论文 1 3 3l i s t - d e c o d i n g 列表译码 如果我们要纠正r ，生芸个错误，在唯一译码准则下译码是失败的，原因就 在于存在收到的字，使得满足d ( ，c ) 一d 一的码字不止一个，这时译码器不知道要 输出哪个结果，其中d 为码c 的最小距离。如图( 1 - - 4 ) 所示。 但是对绝大多数的字r c ”来说，只存在唯一的一个码字与r 的距离最近。 而且对于个m ，七，d 】码来说，有很多字落在以码字为球心，乏 为半径的 h a m m i n g 球外，但以唯一译码为准则的算法却不能纠证它们，如图( 1 - - 5 ) 所 示： c jdc 2 f d 1 ) ，2 图( 1 5 ) 例如，在= o ，l ，2 ，3 ，4 ，5 ，6 ) 上，长为6 ，信息位为2 的r s 码是一个【6 ，2 ，5 】 码，是最优码。按唯一译码准则能纠正fs2 个错误。但是所有以码字为球一心， 以f 。2 为半径的h a m m i n g 球只包含了7 2 ( 四+ 6 + 6 2 四) 一2 8 2 7 3 个字，而域e 上6 维空问中字的个数为7 6 ，那么h a m m i n g 球所包含的字也就是能纠f 的字只 占了2 4 ，因此还有绝大多数的字是不能纠正的。 所以构造出能纠正f ，竿个错误的译码算法是有很大意义的。 e l i a s 5 于1 9 5 7 年、w o z e n c r a f l 6 - 于1 9 5 8 年分别提出了列表译码准则( l i s t 中山大学硕十学位论文 d e c o d i n g ) 这个概念，在这个准则下，对于收到的字r ，如果译码算法能输出一 个比较小的码字集，只要这个码字集里包含了发送端发送的码字c ，那么我们就 认为这个译码算法是成功的。将在第3 章综述由m a d h us u d a n 于1 9 9 7 年所提出 来的对r s 码的列表译码算法。 中山大学硕士学位沦文 第2 章域磊上的k l 七】循环码 2 1 循环码 循环码是一类最查要的线性码，由于它具有循环特性和优艮的代数结构，使 得它可以用多种简单而有效的译码方法。1 9 5 7 年p r a n g e 首先丌始研究循环码。 现在循环码已成为研究最深入、理论最成熟、应用最广泛的一类线性码。 定义：域c 上的一个线性码c 称为循环码( 也称为循环子空间) ，如果对任 意的码字( c 。，c i ，- - - c ，) e c ，字( q 。c 。，乞一：) e c ，其中c i e ，i = o ，1 ，n 一1 。 因为线性空间只“与域上的多项式剩余类环m r l 是同构的( 仅考虑 加法) ，所以我们可以通过多项式来研究循环码。 域e 上的m ，k l 懈q c ，其码字c 一( c o ，c ，c 。) 的码字多项式表示为： c ( x ) = c o x + c i x 2 + + c n l 石”一1 码字c 向右循环一位得到码字c7 = ( 巳_ l ，c o ，c n2 ) ，其所对应的多项式为： c o ) = c + c o x + + c n 一2 x 盹+ c o x 州 它相当于是c 0 ) 乘以工后，用m 0 ) = - 1 取模： x c ( x ) = c o x + q x 2 + + c n 一，一1 + q 一 一乞一1 + c o x + f i x 2 + + 矗一“_ 1 ( m o d x ”一1 ) 定理1 ：域e 上的线性码c 是循环码的充分必要条件是：c 是剩余类环 f , i x x “一1 的一个理想。 证明见【2 】，此处从略。 因为剩余类环e 【x 】一- 1 是主理想环，所以循环码c 是一个主理想，因此 存在唯一的一个次数最低的首一码多项式g ( x 1 ，使得循环码c 中的每个码字多 项式c ( x ) ( 以下除特别声明，c 0 ) 都是次数小于等于n - 1 的多项式) 都g ( x ) 中山大学硕士学位论文 的倍式。称g ( x ) 为循环码c 的生成多项式。 定理2 ：域e 上i n ，t 】循环码的生成多项式g ) 一定是- 1 的因式；反之， 如果多项式g ( x ) 为h k 次，g ( x ) i r 一1 ，那么g o ) 一定生成一个k 】循环码。 证明见【1 】，此处从略。 从前面的讨论知道，只要把循坏码的生成多项式g ( x ) 确定了，那么就能把 这个循环码构造出来。所以求解循环码的问题转换为构造生成多项式g ( x ) 的问 题。 那么怎么求生成多项式g ( x 1 呢? 我们分三种方法进行讨论。 2 1 1 将一1 分解成域上不可约多项式的乘积 怎样将一1 分解成域e 上的不可约多项式，见【3 】。设： x ”- 1 = z “) 正o ) 正“) 其中五( x ) 是域上的不可约多项式，那么域f q & n 长n n 的任一循环码都可以 通过选择一1 的因子作为生成多项式g ( x ) 生成。 2 1 2 求g ( x ) 的所有根，然后重构g ( z ) g ( x ) 的根有两种情况：一是没有重根，一是有重根。由于有重根的情况下 用g o ) 生成的码，比没有重根时生成的码通常要差，所以以后我们讨论的一般 都是g o ) 没有重根的情况。要求g o ) 没有重根也就必须要求矿- 1 1 1 。 定理3 ：在域上舻一1 没有重根的充分必要条件是( h ，q ) m l 。 证明见【3 】，此处从略。 由于域上的任意首一多项式可以山其在分裂域上的所有根唯一确定， 所以只要找出g o ) 所有的根，我们就可以把g g ) 重构出来。设g ( x ) 在域的某 1 6 中山大学硕士学位论文 个扩域0 上完全分解成g q ) 一o a ，x x a ：) 一口。) ，其中当i 一，时 a z a ，i ，j1 1 ，2 ，l k ，。设码多项式为： c 0 ) = c o x + q x 2 + + c k 一1 x “_ 1 则 c ( c t i ) = c o + c 1 口f 1 + + c n _ l c t i ”- 1i = 1 2 n k 即 1 a l 口l “一1 1 a 2 口2 “一1 1 一a 月一i “一1 c 0 c 1 - c n 一1 。h c 7 ：0 日为循环码c 的校验矩阵。( 其实只要我们确定了循环码的校验矩阵，我们就唯 一的确定了这个循环码，但在这里我们的目的是重构生成多项式g ( x ) ) 不妨设口，的最小多项式为m i ( x ) ，f 一1 ，2 ，n - k ，则9 0 ) 以口。，a ：，口。为 根当且仅当g ( x ) 能同时被o ) ，m ： ) ，m 。o ) 除尽。由前面的分析知，g o ) 是 所有码字多项式c ( x ) 中次数最低的首一多项式，所以 9 0 ) = l c m ( m 。o ) ，m ：0 ) ，m n 一。0 ) ) 怎么求最小多项式m 。o ) ，f - 1 , 2 , ，n 一女，见【3 】。 2 1 3 通过m a t t s 佃s 。l o m o n ( m s ) 多项式直接构造码多项式c g ) m a t t s o n s o l o m o n 多项式，是1 9 6 1 年由m a t t s o n 和s o l o m o n 在构造非系统 r e e d s o l o m o n ( r s ) 码时提出来的。它在构造码和译码中扮演着重要的角色。 从根的角度来讲，因为每个码多项式c o ) 都是生成多项式9 0 ) 的倍式，所 以g ( x ) 的所有根都是每个码多项式c o ) 的根；反过来，如果一个多项式在模 矿- 1 的情况下以g o ) 的所有根为根，那么它一定是g o ) 的倍式，也就是说这 个多项式就是一个码字多项式。每个码字多项式都以g ( x 1 的根为公共根，即 1 7 中山大学硕士学位论文 c 一 c o ) i c ( q ) 1 0 ，其中q 是9 0 ) 的根，iz 1 , 2 ，n 一| 】 ) ，那么以口。，a ：，a 。为根 ( 口，e f t ) ，而系数在c 上的多项式 c ( 工) = c o x + c l x 2 + + c n _ l x ”_ 1 有什么特点呢? 用离散f o u r i e r 变换构造出来的m a t t s o n s o l o m o n 多项式回答了 这个问题。 定义：设域c 卜的多项式 口0 ) = 口o + 以l z + + 口h 1 x ”- 1q 则它在域c 。上的m s 为： c ( x ) = c o 工+ 叩! + + q l x ”一1c j o 其中c j2 口 ) 2 三口“，口是域f m 上的甩次本原单位根，即= 1 。称 c - ( c o ，c 1 ，- ，c 。_ 1 ) 是n = ( 口o ，n 1 一日。1 ) 在域f 曾。上的离散f o u r i e r 变换a 定理4 ：在域上， ) 的系数口r 与它的谱多项式c 0 ) 的系数c ，有以下关 系： 其中i ，j = 0 ，1 ，n 一1 证明见【1 】，此处从略。 那么怎样利用m s 多项式构造域上的循环码呢? 设域。上的多项式集 q = 扣0 ) ) 满足以下两个条件： ( 1 ) 对任意的f ，口 ) ，a 是。上的雄次本原单位根。 ( 2 ) 对任意的口0 ) q ，其系数口，8 ，口全为零。 出于多项式的所有线性组合也满足上两个条件，因而q 一 口o ) ) 是域，上的一 个线性空问。而与q 一 口0 ) ，相应的m s 多项式集l l ，i c 0 ) 也必然满足以下两 个条件： ) 0 a 位 “ 1 一n = = c 口 ，_tl，-l 中山大学硕士学位论文 ( 1 ) c ( x ) 的所有系数c i ( 2 ) 对任意的c ( x ) e q , ，c ( a 1 ) ；0 ，其中，一1 , 2 ， 所以多项式集v = c 扛) 是域上的一个循环码。它的生成多项式为： g ( z ) = l c m ( m o ) ，m i ! ) ，7 l ( x ” 其中m ：，o ) 是a 1 在域上的最小多项式，j = 1 2 ，r 。 如果将c 0 ) 的多项式的系数从。限制在上，而c o ) 的系数= n ( a 。) ， 所以当石= l ，口，a2 ，a “1 时，口扛) 的取值要在上，这也就是浣 ( 口0 ) ) 9i ( 日o + 口l 石+ + 盘。一l 工”一1 ) 4 = a 0 。+ 口1 9 工4 + + a n _ l q x q 枷一1 ) = a o + a l x + + d 一i x ”一1 - 口仁) 比较项的系数，有口。- ( 口f ) 4 。 1 1 这样域上的任意循环码，都可以通过m s 多项式来构造。 2 2 两种特殊的循环码 2 2 1 b c h 码 从前面的讨论知道循环码由其生成多项式g ( x ) 的根唯一确定，那么循环码 的最小距离与这些根有什么样的关系昵? 具体来说，当我们需要构造最小距离 d = 6 的循环码时，它的生成多项式g ( x 1 的根要满足什么样的条件呢? b c h 码的 构造就回答了这个问题。 b c h 码是一类很重要的循环码，在现实中有很多应用。它于1 9 6 0 年由 r c b o s e 和d k r a y - c h a u d h u r i 、1 9 5 9 年由a h o c q e n g h e m 分别提出。 定义：域c 上的一个长为n 的循环码称为设计距离为6 的b c h 码，如果它 的生成多项式占o ) 是，声“1 ，p “2 的最小多项式的最小公倍数，其中p 是o 1 9 中山大学硕十学位论文 上的一次本原单位根。通常当f 一1 时，称为狭义的b c h 码。如果，l = q “- 1 ，也 即卢是域乞的本原单位根，那么称这样的b c h 码为本原b c h 码。 下面的定理5 说明了b c h 码的最小距离与它的生成多项式的根的关系。 定理5 ：设计距离为6 的b c h 码的最小距离d d 。 证明见【2 】，此处从略。 2 2 2 r e e d s o l o m o n ( r s ) 码 r s 码是h = q 一1 的b c h 码，所有是最简单的b c h 码。 定义：域只上的r s 码是一个本原b c h 码，其码k 以s q - 1 ，生成多项式 为9 0 ) = 兀1 0 一a 。) ，是域e 的木原元。 根据m s 多项式知道，假设口；( ，n ，q 一。) 露，其所对应的多项式为： a ( x ) = n o + 4 l x + + t l x 一1 那么 c = ( c o ，c i ，c n 一1 ) ic l 一口( 口) ，0 s i s n l ，n e f 是一个r s 码，它的生成多项式g ( x ) - 0 一a ) 一日2 ) 0 一口”) 。见【2 】。 2 3 域上的妇一1 ，七】循环码 从前面的讨论知道循环码用码