（基础数学专业论文）关于多位循环码书写方法的研究.pdf

j 关于多位循环码书写方法的研究 。 7 9 5 3 2 8 i i i i iii l ll lll lluli i y 1 i 1 9 5 7 年p r a n g e 首先引入了循环码的概念以及码多项式的表示方法，自此以 后，分组码的理论，特别是循环码的理论得到了迅速发展。循环码的显著优点是， 它的编码和伴随式计算可以用简单的具有反馈联接的移位寄存器来实现，另外， 由于循环码有良好的代数特性，人们可以用“代数这个强有力的数学工具对循 环码进行深入的研究，并找到各种简单有效的译码方法。符方伟在文献【l 】中研 究了循环码的周期分布的新的计算公式，王新梅，肖国镇在文献【2 】中对纠错码 的原理与方法进行了详细阐述；单亦先在文献 3 】中详细介绍了循环码的实现方 法及其在前向纠错中的应用，研究了循环码实现方法和应用原理；邓友娥在文献 【4 】中介绍了循环码纠错在编译码中的应用，分析了循环码的数学原理，探讨了 具有较强检、纠错能力的循环码实现方法；周宦银在文献 5 】中对传统的循环 码书写方法进行改良，并根据循环码的特点，总结出了书写循环码简单、方便又 不容易出错的方法。 作者的主要研究成果： 1 通过对已有的循环码编码方法研究、分析、总结，提出了一个新的二进制 多位循环码的书写方法； 2 总结了循环码从高位到低位“o ”和“1 ”的分布变化规律，同时结合了 循环码的对称变化规律，给出了另一个二进制多位循环码书写方法； 3 经过多方面的研究，结合卡诺图相邻两最小项具有逻辑相邻性，而且具 有直观清晰的特点。提出了一种k 变量( k 6 ) 时卡诺图的制作方法，并把 它应用到书写二进制多位循环码中。 关键词：循环码，编码，= 进制，卡诺图 、： w i t hr e g a r dt oan u m b e ro fw r i t i n gm e t h o d o fc y c l i cc o d e s ab s t r a c t 19 5 7 ，p r a n g ef i r s ti n t r o d u c e dt h ec o n c e p to fc y c l i cc o d e s ，a n dc o d e p o l y n o m i a lr e p r e s e n t a t i o n ，s i n c et h e n ，t h et h e o r yo fb l o c kc o d e s ， e s p e c i a l l yi nt h et h e o r yo fc y c l i cc o d e sh a sb e e nt h er a p i dd e v e l o p m e n to f t h es i g n i f i c a n ta d v a n t a g eo fc y c l i cc o d e si st h a ti t sc o d i n ga n dc a nb e c a l c u l a t e dw i t has i m p l es h i f tr e g i s t e rw i t hf e e d b a c kc o n n e c t i o n st o a c h i e v et h eo t h e r , b e c a u s ec y c l i cc o d e sh a v eag o o da l g e b r a i cp r o p e r t i e s ， o n ec a nu s e a l g e b r a ”i sap o w e r f u lm a t h e m a t i c a lt o o l st oc o n d u c t i n - d e p t hs t u d yo fc y c l i cc o d e s ，a n df i n dav a r i e t yo fs i m p l ea n de f f i c i e n t d e c o d i n gm e t h o d f uf a n gw e ii nt h el i t e r a t u r e 1 s t u d i e dt h ed i s t r i b u t i o n o f c y c l i cc o d e so f t h ec y c l eo fn e w f o r m u l a ，w a n gx i nm e i ，x i a og u oz h e n i nt h e l i t e r a t u r e 2 】o ft h ee r r o r - c o r r e c t i n gc o d e so fp r i n c i p l e sa n d m e t h o d sd e s c r i b e di nd e t a i l ；s h a ny ix i a ni nt h el i t e r a t u r e 【3 】d e s c r i b e di n d e t a i li nt h er e a l i z a t i o no fc y c l i cc o d e sf o r w a r de r r o rc o r r e c t i o nm e t h o d a n dt h ef i r s to fa p p l i c a t i o n s ，s t u d i e dt h er e a l i z a t i o nm e t h o da n d a p p l i c a t i o no fc y c l i c c o d et h e o r y ；d e n gy o u ei nt h el i t e r a t u r e 4 】 i n t r o d u c e dac y c l i cc o d ee r r o r - c o r r e c t i n gc o d i n ga n dd e c o d i n go ft h e a p p l i c a t i o ni nt h ea n a l y s i so ft h em a t h e m a t i c a lp r i n c i p l eo fc y c l i cc o d e s a r ed i s c u s s e dw i t h s t r o n gi n s p e c t i o n ，t h ec y c l e o fe r r o r - c o r r e c t i n g c a p a b i l i t yc o d ei m p l e m e n t a t i o nm e t h o d ；z h o uh u a n y i ni nt h el i t e r a t u r e 【5 】o ft h et r a d i t i o n a lw r i t i n gm e t h o di m p r o v e dc y c l i cc o d ea n di n a c c o r d a n c ew i t ht h ec h a r a c t e r i s t i c so fc y c l i cc o d e s ，c y c l i cc o d e ss u m m e d u pw r i t i n gas i m p l ea n dc o n v e n i e n tw i t h o u te r r o r - p r o n em e t h o d t h ea u t h o r sk e y f i n d i n g s ： 1 t h r o u g ht h ee x i s t i n gl o o pc o d i n gm e t h o d ，a n a l y s i s ，s u m m a r y , p r o p o s e dan e wb i n a r yc y c l i cc o d e so fw r i t i n gan u m b e ro fw a y s ； 2 s u m m a r i z e st h ec y c l i cc o d ef r o mh i g ht ol o w 0 a n d ”1 c h a n g e s o ft h ed i s t r i b u t i o n ，c o m b i n e dw i t ht h ec y c l i cc h a n g e so ft h es y m m e t r y c o d eg i v e nn u m b e ro f c y c l i cb i n a r yc o d ew r i t t e ni na n o t h e rw a y ； 3 a f t e re x t e n s i v er e s e a r c h ，c o m b i n e dw i t ht w oa d j a c e n tm i n t e r m k a r n a u g hm a pl o g i c a ln e i g h b o r s ，b u ta l s oc l e a ra n di n t u i t i v ef e a t u r e s a v a r i a b l ek ( 七6 ) ，t h ek a m a u g hm a pm e t h o do fm a k i n ga n da p p l yi tt o w r i t i n gan u m b e ro fc y c l i cb i n a r yc o d e k e yw o r d s ：c y c l i cc o d e s ，c o d i n g ，b i n a r y , k a r n a u g hm a p i 目录 第一章绪论l 1 1 循环码的基本描述- l 1 1 1 循环码的基本概念l 1 1 2 循环码的多项式表示2 1 2 循环码的矩阵描述4 1 3 循环码的研究背景、发展状况及现实意义6 1 4 论文的内容安排和主要研究成果7 1 4 1 论文的内容安排- 7 1 4 2 论文的主要研究成果7 本章小结8 第二章数学基础和编码学相关知识9 2 1 数学基础知识9 2 1 1 陪集及其性质9 2 1 2 剩余引理1 0 2 1 3 循环码与理想1 1 2 2 信道编码模型与译码1 1 2 2 1 信道模型- l l 2 2 2 最小距离译码1 2 2 2 3 最大释然译码1 2 本章小结1 3 第三章二进制多位循环码书写方法1 4 3 1 书写循环码的几种常见方法1 4 3 1 1 逐位异或计算法1 4 3 1 2 利用循环特性书写方法1 6 3 2 利用循环码的对称特性写法( 一) 1 6 i v t 3 3 利用循环码的对称特性写法( - - - ) 1 9 本章小结2 l 第四章对k 变量( k 6 ) 卡诺图制作方法的讨论2 2 4 1 卡诺图的简单介绍2 2 4 2 用卡诺图书写多位循环码及其限制2 2 4 3 制作卡诺图时对行列数的建议2 3 4 4 k 变量( k 6 ) 卡诺图的制作方法及应用2 5 本章小结2 6 结束语2 7 参考文献2 8 致谢- 3 0 攻读硕士学位期间研究成果3 1 v 关于多位循环码书写方法的研究 第一章绪论 自古以来编码学和数学就存在着密切的联系，随着现代科学技术的迅猛发 展，数字通信的应用越来越广泛。语音、图像、文字符号等各种信息都可以通过 数字通信系统进行远距离传输。由于数字通信的发展，数据的传输或存储越来越 大，与此同时，数据的出错概率也大大增加。保持数据的正确性，仅依赖于器件 和设备的可靠运算是不行的。为了纠正数据在传输的过程中出现的错误，信息应 具有某种冗余形式以保护数据，这促使了编码理论的产生和极大发展。、 根据不同的需要编码主要分两大类：信源编码和信道编码。信源编码是为了 使欲传输的信源信息在传输速率一定的条件下能更快、更多地传输，还要把数据 进行压缩，也就是通过信源编码去掉信息中大量多余部分，这样就可以极大地提 高传输效率。而编码过程中，我们更加关注于信道编码，因为，我们知道，信息 在传输的过程中受到来自各个方面的干扰。例如通信设备各个器件的缺陷和内部 噪音；信道中存在的各种干扰，如高频信道的衰落，天电干扰等等。所有这些干 扰都会影响传输的可靠性，否则如果不进行信道编码，直接把信息代码送入信道， 收到的信息就没有“可靠性”，而只有“可能性 。信道编码就是为了克服这些 干扰，增加传输可靠性的一门通信技术。设计信道编码的目的，就是在编码效率 一定的条件下，尽可能提高已编码信号的检错或纠错能力。或者说在保证一定的 检错或纠错能力的条件下，尽可能提高编码效率。 在数字通讯系统中，由于信道内存在的噪音、信道传输特性不理想造成的码 间串扰，信号误码是不可避免的，为了确保系统的比特误码率指标，误码通常采 用循环码来进行编码。因其任意两个相邻的循环码只有一个数字不同，具有很高 的可靠性，编码和解码设备比较简单，而且检错和纠错能也较强，所以广泛应用 于通信、军事等领域。虽然循环码理论发展至今已相当完善，但仍有许多问题值 得我们进一步去研究，因此对循环码的研究对今后编码理论的发展起着举足轻 重的作用。 1 1 循环码的基本描述 1 1 1循环码的基本概念 若已知一个( 7 ，3 ) 码y 的生成矩阵： 青海师范大学硕士学位论文 i l g = 10 io oo 1o ol 11 ol 1l 由g 生成的( 7 ，3 ) 码字如下表1 1 所示 表1 1 ( 7 ，3 ) 码信息组与码字 lo 11 01 信息组码字信息组码字 0 0 0 1 o 0 0 0 0 0 0 0 1 0 0 v 4 1 0 0 1 1 1 0 0 0 1 m 0 0 1 1 1 0 1 1 0 1 b 1 0 1 0 0 1 1 0 1 0 、v 20 1 0 0 1 1 1 1 1 0 v 6 1 1 0 1 0 0 1 o l l v 3 0 1 1 1 0 1 0 1 1 1 1 1 1 0 1 0 0 通过仔细观察这组码字发现，它的每个码字经过循环移位得到的7 维向量仍 是该码的码字，即该( 7 ，3 ) 码具有循环移位性质，例如v 3 = ( o l1 1 0 l o ) ，它循 环左移一位得到v 7 = ( 1 l1 0 1 0 0 ) ，再循环循环左移一位得到v 6 = ( 11 0 1 0 0 1 ) 等 等，由此不难得出循环码的定义 定义1 1 1 1 5 设y 是一个( 刀，k ) 的线性分组码，如果y 中任意一个码 字1 ，在每次循环移位后，得到的刀维向量仍是y 中的一个码字，那么我们就称y 是循环码。 这就是说，如果，= _ p 屹_ 2 ，v i ，v o ) 是y 的一个码字，那么 ( 1 ，疗一2 ，1 ，月一3 ，1 ，o ，v 咒一1 ) ，( 一3 ，一4 ，屹一1 一2 ) ，( ，屹一l ，v 2 ，m ) 等 也是y 中的码字，我们知道， ( 刀，k ) 线性分组码是n 维向量空间( 2 ”) 的 k 维子空间，因而，( 胛，k ) 循环码y 也是以维线性空间( 2 ”) 的一个k 维 子空间 定义1 1 2 1 5 】n 维线性空间圪( 2 “) 的一个k 维子空间y ，如果对于任 意y = ( 屹_ l ，v l - 2 ，v l ，v o ) v 都有1 ，= ( 吃一2 ，。一3 ，v b ，屹一1 ) v ，那 么我们就称y 为循环子空间 那么显然，( 刀，k ) 循环码y 是刀维线性空间( 2 4 ) 的一个k 维循环子 空间 2 关于多位循环码书写方法的研究 1 1 2 循环码的多项式表示 为了更进一步研究循环码，在此引入了代数理论的知识。我们用降幂排列的 多项式表示码字，例如，我们把表1 l 中的每一个码字，- - - ( ，v 5 ，v l ，v o ) 用 相应的多项式 ， 1 ，( x ) = v 6 x 6 + v 5 x 5 + + 1 ，l x + 1 ，o 来表示，显然这种关系式是一一对应的，即如果v ：v ，则码的多项式 吃( 功h ，反之亦然按照这样的对应关系，表1 1 中的每一个码字可以用 而且仅用一个相应的多项式来表示，具体如下表1 2 所示 表1 - 2 ( 7 ，3 ) 循环码与码多项式对应表 码字码多项式码字码多项式 0 0 0 0 0 0 001 0 0 1 1 1 0工6 + z 3 + 工2 + x 0 0 1 1 1 0 1x 4 + x 3 + x 2 + 11 0 1 0 0 1 1誓+ x 4 + 矿+ 1 0 1 0 0 1 1 1x 5 + 矿+ x + l1 1 0 1 0 0 1z 6 + x 5 + x 3 + 1 0 1 1 1 0 1 0 x 5 + x 4 + 工3 + x1 1 l o l o o x 6 + x 5 + x 4 + 工2 一般地，在( ，l ，尼) 循环码中，任意的一个码字v l = ( 屹- l ，屹_ 2 ，1 ，l ，) 的码多项式为v i ( x ) - y n l 矿一1 +y n 一2 x ”一2 + + ，lx + v o ，m 循环移位 一次得到，2 = ( 1 ，。一2 ，v 。一3 ，1 ，o ，1 ，川) 吃( x ) 2v n - 2 x ”一1 + v n 一3 x 4 2 + + v o x + v 。一l ， 模一1 ，即： ，它所对应的码多项式是 这相当于用x 乘以1 ，。( x ) ，然后取 x v l ( x ) = v n l ( 石“一1 ) + v n - 2 x4 1 - 卜+ v o 石+ v 疗一l 暑一2 x 剃+ + v o x + 一1 = v 2 m o d ( x “一1 ) 若v 2 再循环移位一次得到v 3 = ( 1 ，一一3 ，v 。一4 ，1 ，一一l ，1 ，一一2 ) ，它对应的码多 项式屹( x ) = 一3 x 川+ 匕一4 r 一2 + + 匕一l x + 一2 ，这相当于用，乘以1 ，i ( x ) ， 暑一3 石纠+ + 匕一l x + 屹一2m o d ( x 一1 ) 3 2 一一 y+x o 一 矿+ 、j i一 一 x ，l2一疗 矿 l l 、- 、 x _ 一 2 矿 ： x p 甘瓯 i 一 雎 x 模取后然 青海师范大学硕士学位论文 一般地，如果任一码字h = ( _ l 吃之，1 ，l ，) 循环移位i 次得到 k + l = ( 吃- l - i 屹一2 - f ，吃一f ) ， 那么它所对应的码多项式是 h + l ( x ) = 吃一l f x 万一1 + 屹一2 一f x 一一2 + + 吃一f，这就相当于是用 一 乘以 1 ，。( x ) ，然后取模，- 1 ，即： x 1 ，l ( j ) iv n - l - i x 开一1 + v n - 2 - i x ”2 + + 1 ，耳一f = y f + 1 ( 石) mo d ( x “一1 ) 。 1 2 循环码的矩阵描述 我们已知，给定x 8 1 的一个因式 g ( x ) = g n 一| | x 厅一七十邑一七一l x 再一七一1 + + g l x + g o ， 便可生成一个( ，l ，后) 循环码，即对于任给的一信息组聊= ( 肌k - i 聊h ，m a ，m o ) ， 对应的信息多项式为，z ( z ) = 一l x 七- 1 + 一2 x 眦+ + 铂x + ，作多项式乘积 1 ，( x ) = m ( x ) g ( x ) = m t l g n t 石”一1 + ( 聊l l g 月一i l + m i 一2 9 n 一) x 一2 + + mo g o ， 于是得到码字 1 ，= ( m 七一l g 万一| ，m t l g 一丘一l + m k - 2 9 秤一七，m o g o ) ( 1 ) 若用矩阵的形式表示式( 1 ) ，即为 1 ，= mg g = 卜g n - 一k - - i g o 岛 吕卜素岛靠i 蜀岛 4 ( 2 ) 关于多位循环码书写方法的研究 是非系统循环码的生成矩阵，若是要得到系统码的生成矩阵，只要对生成矩阵( 2 ) 作初等变换化成标准型即可，当然也可以直接由生成多项式生成系统码具体作 法是首先用乘圳 x n - k m ( 石) = m 七一l x 一一1 + m 七一2 石七一2 + - i - m o x 耳一七，2 然后用g ( x ) 去除r t m ( x ) ，设商和余式分别为g ( 曲和，( 曲，于是 x n - k m ( 工) = q ( x ) g ( x ) + ，( z ) ，a ( ，( x ) ) 刀一k ， 或者 g ( x ) g ( x ) = x “一七m ( x ) + ( 一，( x ) ) ( 3 ) 由式( 3 ) 我们知道x n - k m ( x ) + ( 一，- ( 算) ) 是g ( x ) 的陪式，因而明显是一个码多项 式，令 - r ( x ) = 一七一l x 一七一1 + + r l x + r o ， 于是码多项式 y ( x ) = x n - k m ( x ) - 4 - ( 一，( x ) ) = r n 七一1 x ”一1 + m 七一2 x 一2 + + m o x 一一七+ 一七一l x 行一七一1 + + x + r o 对应的码字 1 ，= ( m 七一l ，m 七一2 ，m o ，一七一l ，吒，) 是一个前k 位为原信息组，后n - k 位为监督元的系统码。 因此，用g ( x ) 构成系统码的步骤是，首先用石”去乘信息多项式所( x ) ，然 后用g ( x ) 去除x 驴。m ( x ) 得到余式r ( x ) ，则系统码多项式， v ( x ) = x n - k m ( x ) + ( 一，( x ) ) ， 这样，系统循环码的编码问题实质上就是以g ( x ) 为除式的多项式除法问题。 由此不难想象由g ( x ) 求系统码的生成矩阵g 的方法，可以先求出信息多项 式x k - ix k - 2 ，x ，1 的码多项式，即用g ( x ) 分别去除矿一，x 厅，一， 得到 5 青海师范大学硕士学位论文 ，叫= 绣( 功g ( x ) + 吃一j ( 力，a ( r k 一，( x ) ) a ( g ( x ) ) ， 其中i = 1 ，2 ，k ，令 ， 一一f ( x ) = ，h r ，t k l - i ) x ，- 1 + + 砰k - 0 x + h o ( 七一， 于是对应的码多项式 唯一f ( x ) = x 舻+ ( 一一f ( x ) ) = x 一。+ ，h ，( 一k l - o x ，_ 1 + + 硝七- o x + h o t 七。 、 将这k 个码多项式作为生成矩阵的k 行，很容易就可得到生成系统码的标准 生成矩阵，具体如下： 1 3 循环码的研究背景、发展状况及现实意义 任何事物的产生都有它一定得时代背景和现实意义，下面首先介绍一下循环 码问题的研究背景、发展状况及现实意义 循环码是一类非常重要的线性分组码，关于线性分组码的研究起始于汉明 ( h a m m i n g ) 和戈莱( g o l a y ) 的早期论文，汉明首先提出了二进制汉明码，而戈 莱和科克( c o o k e ) 则发展了多进制汉明码。1 9 5 3 年k i y a s u 已注意到线性分组 码与向量空间的子空间的关系。r e e d m u l l e r ( 1 蝴) 码是1 9 5 4 年由马勒( m u l l e ) 提出来的，同年里德( r e e d ) 发现了这类码的译码算法，1 9 5 7 年p r a n g e 首先 引入了循环码的概念以及码多项式的表示方法，自此以后，分组码的理论，特别 是循环码的理论得到了迅速发展。随着对循环码研究的不断深入，产生了大量很 有价值的文献。刘玉君编著的 1 5 】是一本详细论述了信道编码的基本教材，其中 对循环码作了深刻的描述，他的 1 7 则探讨了更为广义的循环码；m a e w i l l i a m sf j 的 2 3 】对纠错码作了重点介绍，j h v a n 林特的【2 6 】是一篇关于编码理论的优秀论 著；王开弘的【2 9 】论述了循环码的一种推广形式一常循环码等等。 编码学中，很多的理论和算法都是在研究循环码的过程中建立起来的，因此 6 d 动 ， 一 一 盯 俨秽 川 国 一 七 豇 矿俨妒 d 动 ，2聪杼鸩 d 刁 ，料杼础 o 0 1 o 1 0 l 0 0 。l = g 关于多位循环码书写方法的研究 对循环码的研究显得更加举足轻重。随着大型计算机网络的不断发展，计算速度 在飞速提高，对数据的传输和存储要求越来越高，与此同时，数据的出错概率也 大大增加。保持数据的正确性，仅依赖于器件和设备的可靠运算是不行的。循环 码就是一种编、译码都比较容易实现的分组码，而且可靠性高、便于在软硬件中 实现。因此在军事、商业、工程和政治领域都有着广泛的应用。 1 4 论文的内容安排和主要研究成果 本文详细阐述了线性分组码中一重要子类一循环码的发展状况及在应用 领域取得的主要成果，着重介绍了作者在这方面的研究及尝试，并提出了作者的 研究成果以及今后研究方向，希望能丰富和改进信道编码理论，更好地服务于其 它领域上的应用 1 4 i l 论文的内容安排 本论文共分为四章： 第一章简单介绍了线性分组码的产生背景，对循环码的基本数学描述作了简 单的介绍，并对循环码的性质、研究背景、发展状况及现实意义作了阐述，为之 后的内容做好铺垫。 第二章是本文的基础理论部分，主要介绍了要用到的一些代数知识和编码学 知识。本文主要研究的是循环码编写问题，之后应用于编码学中。可见编码学和 数学尤其是代数知识有着很深的渊源，它们是息息相关、密不可分的，这也正是 本章首先给出一些基础理论的原因所在。 第三章是本文的核心内容之一，首先给出了多位循环码书写方法的个别案 例，如逐位异或算法等，接着作者结合前辈们的研究结果，分析总结循环码的对 称特性，提出了新的二进制多位循环码的书写方法，并对它们的优劣性，应用条 件作了详细的分析。 第四章是本文的核心内容之二，作者利用卡诺图有着特殊的几何相邻性和对 称相邻性，并总结分析了卡诺图在书写低于6 位循环码上的方法技巧，结合前 面一章的思想方法，提出了一种k 变量( k 6 ) 卡诺图的制作方法，也更好 地应用到更高位循环码的书写。 1 4 2 论文的主要研究成果 作者通过自己的努力研究和探索，取得了以下主要研究成果： 7 青海师范大学硕士学位论文 1 通过对已有的循环码编码方法研究、分析比较，基于循环码本身固有的 对称性，提出了一个新的二进制多位循环码编码方法，并对新老方法的优劣进行 了比较； 2 总结了循环码从高位到低位“0 和“1 的分布变化规律，同时结合了 循环码所特有的对称变化规律，给出了另外一种二进制多位循环码书写的新方 法； 3 经过多方面的研究，结合卡诺图本身所特有的相邻两最小项具有逻辑相 邻性，行、列各变量的取值都是采用循环的规律排列等特点，而且直观清晰。提 出了一种k 变量( k 6 ) 卡诺图的制作方法，并把它应用到书写二进制k 位 循环码中。 本章小结 本章节首先介绍了循环码的一些入门基本知识，如循环码的基本概数学描述 及其多项式表示，让它与我们所熟悉的数学知识联系起来，并在此基础上，介绍 了循环码的的矩阵描述，加深了对循环码的了解。接着简单介绍了循环码的研究 背景，和近代发展状况。最后，对本文的内容安排和作者在本文中取得的主要研 究成果做了阐述。 7 8 关于多位循环码书写方法的研究 第二章数学基础和编码学相关知识 编码学的研究工作必须建立在一定数学知识的基础上才能进行，循环码具有 很强的代数性质。陪集、平方剩余定理、循环码与理想等都是要用到的一些基本 数学工具，这些是我们研究编码设计的基础，可以把他们的很多思想、方法技巧 应用到编码工作中去。 2 1数学基础知识 2 1 1 陪集及其性质 定义2 1 1 1 5 】设日是有限交换群g 的一个子群，a 是g 的任意一个元素， 用a 去除日中的一切元素，所成的集合称为日在g 中的一个陪集，也简称日的 陪集，即： a i t = a h ih i t ， 例如，设g = e ，口，口2 ，口3 ，口4 ，口5 ) 是一个6 阶循环群，而日= e ，口2 口4 是g 的 一个子群，我们求日的陪集， p 日= 郫2 ，口4 = h ， a 2 h = 口2 ，口4 ，e ) = 日 a 4 h = 口4 ，郇2 = 日 口h = 郇3 ，4 5 ， a 3 h = 口3 ，口5 ，口) = a h ， e h = 口5 ，口，口3 ) = a h 陪集的一些主要性质： 1 - 如果a h则棚= h反之，若a i t = h则a h 这说明日也是日的一个陪集。 2 日的陪集中只有日是群，其他都不是群 3 若b a h 则a h = a t t ，即a h 可以由其中任一元所确定。 4 a h = b h 的充分必要条件是a 叫b i t 5 g 的子群日的两个陪集a i t 和b i t 必满足下列两个关系之一： a h = b i t 或者a h n 坍= o 9 青海师范大学硕士学位论文 2 1 2 剩余引理 定义2 1 2 8 】设p 为奇素数，且( 口，p ) = 1 若，r - a ( m o d p ) 可解，则称a 为模 p 的二次剩余否则，称a 为模p 的二次非剩余。 如：1 是所有奇素数p 的平方剩余，2 是模7 的平方剩余，因为1 2 = l m o d p ， 3 2 = 2 r o o d 7 。显然模p 的平方剩余要在模p 的剩余缩系 1 ，2 ，p 一1 中找，实 际上，只需在1 2 ，e o , j p 一1 中找即可，因为( p _ 口) 2 = p 2 2 a p + a 2 - - - a 2r o o d p 引理2 1 1 【8 】设p 为奇素数，口为与p 互素的任一整数即，( 口，p ) = 1 ，则 有： 。， ( 1 ) 若p = 4 k - 1 ，i ，吃，：，为2 j j 个模p 的二次剩余( 包括o ) ，则集合 ，；+ a 1 1 i 2 k ) 中有k 个二次剩余( 可能包括o ) 和k 个二次非剩余。 ，( 2 ) 若p = 4 k - 1 ，l l ，9 1 9 为2 k - 1 个模p 的二次非剩余，则集合 + 口f 1 f 2 k 中有k 个二次剩余( 可能包括o ) 和k 一1 个二次非剩余。 ( 3 ) 若p = 4 k + l ，i ，乞，+ i 为2 k + 1 个模p 的二次剩余( 包括0 ) ，则如果口 是一个二次剩余时，集合 + all i 2 k + 1 有k + 1 个二次剩余( 包括o ) 和k 个二 次非剩余；如果a 不是一个二次剩余时，集合 ，：+ ai1 i 2 k + l 有k 个二次剩 余( 不包括o ) 和k + 1 个二次非剩余。 ( 4 ) 若p = 4 k + l ，n i ，t 1 2 ，他“为2 j 个模p 的二次非剩余，则如果a 是一个 二次剩余时，集合 吩+ 口1 1 f 2 k 中有k 个二次剩余( 不包括o ) 和k 个二次非剩 余；如果a 不是一个二次剩余时，集合 珞+ al1 f 2 k 有k + 1 个二次剩余( 包括o ) 和k 1 个二次非剩余。 引理2 1 2 1 3 ( 中国剩余定理)：中国剩余定理是解某个方程组的一个 方法，假设m l ，研2 ，m r 是两两互素的整数，即( g e d ( m i , m y ) ：1 ，i j ) ，假设 a ，a ，a ，是整数，考虑下面的同余方程组： x = 口l ( m 0dm 1 ) x=a 2 ( m odm 2 ) x = a ，( m odm ，) 中国剩余定理证明这个方程组有唯一的模m = 碍他佛的解。 1 0 关于多位循环码书写方法的研究 引理2 1 3 1 1 5 1 ：假设p 是一奇素数，则在模p 的剩余缩系中有p 一个 模p 的平方剩余，n ( p 一个是模p 的非平方剩余。 例如，l ，3 ，4 ，5 ，9 是模1 1 的平方剩余，而2 ，6 ，7 ，8 ，1 0 是模1 1 的 非平方剩余。 两个模p 的平方剩余的乘积仍是模p 的平方剩余；一个模p 的平方剩余与一 个模p 的非平方剩余的乘积是模p 的非平方剩余；两个模p 的非平方剩余的乘积 是模p 的平方剩余。 2 1 3 循环码与理想 引理2 1 - 4 【2 】1 段设矿是g f ( q ) 上的【，z ，k ) 循环码，若令码多项式集合 ，( 7 ) = = 【v 。一x n - i + + v x + y 。i ( v 。一。，y 。，v 。) 多7 ) ， j g z _ , ，( 矿) 是同余类环兵【x l 尸( m ，) ，u ，v 则判决，就是v ， 1 2 j 镬 薯： 0 关于多位循环码书写方法的研究 由贝叶斯公式得到： 以，) ：型堕 。 p ( ，) 上式中的p ( v ) 是发送码字 ，的概率，一般假设y 中矿个码字是等概率发送，即所 有码字的先验概率相等，对所给定的接收码字，h ，) 是一个常数。 由于假设矿中的所有码字，的先验概率相等，因此后验概率p ( v ，) 最大就 等价于要求条件概率p ( ，) 最大，即如果对于一切f _ ，的f 均有 ， 尸( ，v ，) p ( ，v f ) ，m ， ，矿 则判决，就是1 ， 我们称p ( ，力为释然函数，这种译码方法称为最大释然译码n 钔，记为m i d 。 显然最大释然译码等价于最大后验概率译码。 本章小结 本章节所涉及到的内容是整篇论文的理论基础部分，有数学中的相关知识和 编码学中一些重要概念和引理。包括了陪集的概念、性质；剩余定理和循环码与 理想，接着简单介绍了信道编码中的信道模型，以及两种译码方法。这些也是后 面研究循环码的必备工具。 、 1 3 青海师范大学硕士学位论文 第三章二进制多位循环码书写方法 编码学中的很多编码方案都是基于对循环码的研究而来的，除了编码工作者 之外，由于循环码本身所具有的特性，它与其它很多学科都有着千丝万缕的联系， 它们是相辅相成的。在相互领域渗透的过程中又促进了各自的发展，因此很多其 它学科的专家、学者们对于多位循环码的书写方法有着很大的兴趣。伴随着越来 越多、各行各业的人们加入到研究多位循环码的行列中来，这对编码学的以后的 发展提供了极大的帮助。 本章首先给出几钟常见的多位循环码的书写方法，并对这些传统书写方法的 优缺点进行了分析，接着作者根据自己的研究探索，介绍了两种新的多位循环码 的书写方法，这两种新方法另辟蹊径，有它们的独到之处，相信更有利于循环码 的研究。 。 3 1 书写循环码的几种常见方法 正确地书写和编制循环码是很多电路设计的关键。但由于循环码的各位没有 权值，所以