（基础数学专业论文）四元拟循环码的研究.pdf

四元拟循环码的研究 中文摘要 早在上个世纪六十年代，就有关于拟循环码的研究近期，由于k a s a m i 证明 了拟循环码满足g i l b e r t - v a r s h a m o v 界因此，拟循环码的研究又重新引起了学者的 注意 本文在第二章中研究了有限域上单生成元的拟循环码单生成元的拟循环码及 其对偶码是拟循环码中研究最多的一种 s g g l l i n 在要求岔”一1 在玛扛】及五【司 中具有相同的分解的条件下，讨论了单生成元的拟循环码的结构及计数本文在一 般情况下讨论了单生成元拟循环码的结构，及计数，并给出了一个算法，对所有不 同的单生成元拟循环码分别给出了一个生成元 本文在第三章中研究了z 4 上的拟循环码，证明了z 4 上的长度为m n 的拟循环 码等价于个小的a _ 子模，其中a = z 4 m ( z ”一1 ) 在i n 为奇数的时候，所有 的拟循环码均可以分解为一些有限数目的循环不可约a _ 子模的直和并且，这样 的分解可以用来计算不同拟循环码的计数子和一些特别的子类最后我们给出了一 个决定任意拟循环码的对偶码的一般方法 关键词：四元拟循环码对偶码单生成元 作者：张学俊 指导老师：崔杰 s t u d yo nq u a s i - c y c l i cc o d e so v e rz 4 a b s t r a c t t h e r ea r er e s e a r c h e so rq cc o d e si n1 9 6 0 s r e c e n t l y , k a s a m is h o w e dt h a tq cc o d e s m e e tam o d i f i e dg i l b e r t v a r s h a m o vb o u n d a sar e s u l t ，t h er e s e a r c ho nq cc o d e sa t t r a c t s m a n ys c h o l a r s a t t e n t i o na g a i n i nt h es e c o n dc h a p t e ro f t h i sp a p e r ，w ed i s c 瑚st h e1 - - g e n e r a t o rq u a s i - c y c l i co v e rf i - n i t ef i l e d 玛t h e1 - g e n e r a t o rq u a s i - c y c l i cc o d e sa n dt h e i rd u a l sa r et h em o s tf r e q u e n t l y e n c o u n t e r e dq gc o d e si nt h el i t e r a t u r e s d g u j nd i s c u s s e st h ec o n s t r u c t i o na n dt h ee n r - m e r a t i o no f1 - g e n e r a t o rq cc o d e si nt h es p e c i a lc a s ew h e r et h ep r i m ef a c t o r i z a t i o no f z “一1i st h es a l ei nr e g l i n 吗m i nt h i sp a p e r ，w ew i l ld i s c u s st h ec o n s t r u c t i o na n d t h ee n u m e r a t i o no f1 - g e n e r a t o rq cc o d e si nt h eg e n e r a lc a s e ，a n dd e s c r i b ea na l g o r i t h m w h i c hw i l lo b t a i no n e ，a n do i l l yo n e ，g e n e r a t o rf o re a c h1 - g e n e r a t o rq cc o d e s i nt h et h i r dc h a p t e ro ft h i sp a p e r ，w ed i s c u s st h a tt h eq u a s i - c y c l i cc o d e so v e rz 4 ， q u a s i - c y c l i cc o d e so fl e n g t hi n i no v e rz 48 , r ee q u i v a l e n tt oa - s u b m o d u l e so fa “，w h e n a = z 4 矧( z “一1 ) i nt h ec a s eo fmb e i n go d d ，a l lq u a s i - c y c l i cc o d e sa r es h o w nt ob e d e c o m p o s a b l ei n t ot h ed i r e c ts u mo faf i x e dn u m b e ro fc y c l i ci r r e d u c i b l ea s u b m o d u l e s f u r t h e r m o r e t h ed e c o m p o s i t i o n sa r eu s e dt oe n u m e r a t et h ed i s t i n c tq u a s i - c y c l i ca sw e l la 8 s o m es p e c i f i cs u b c l a s s e s f i n a l l yag e n e r a lp r o c e d u r ew h i c ha l l o w sf o rd e t e r m i n i n gt h ed u a l 0 fa n yq u a s i - c y c l i cc o d ei sp r e s e n t e d k e y w o r d s ：q u a s i - c y c l i cc o d e so v e rz 4 ，d u a lc o d e ，1 - g e n e r a t o r i i w r i t t e nb yz h e n gx u e j u n s u p e r v i s e db yc u ij i e 苏州大学学位论文独创性声明及使用授权的声明 学位论文独创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进 行研究工作所取得的成果。除文中已经注明引用的内容外，本论文不含 其他个人或集体己经发表或撰写过的研究成果，也不含为获得苏州大学 或其它教育机构的学位证书而使用过的材料。对本文的研究作出重要贡 献的个人和集体，均己在文中以明确方式标明。本人承担本声明的法律 责任。 研究生签名：苤差馥日期：丝疸垒! z 学位论文使用授权声明 苏州大学、中国科学技术信息研究所、国家图书馆、清华大学论文 合作部、中国社科院文献信息情报中心有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本 人电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布( 包括刊登) 论文的全部或部分 内容。论文的公布( 包括刊登) 授权苏州大学学位办j 夸趣。 研究生签名：邀日 期：兰堑：丝! z 导师签名：整泰， 日期：加呸 2 7 第一章绪论 1 1 经典的纠错码 早在1 8 世纪后期，就有关于某个特定码的构造及解码算法的论文，如b c h 码 但是直到1 9 4 8 年s h a n n o n 的论文 3 0 1 的发表才标志着编码理论的建立在此之前， 人们一直以为减少信息传递中的误码率的唯一方法就是减少传输率显然，这是不 明智的s h a n n o m 在论文中引入了信遭容量的概念，并给出了信道容量的计算方 法同时，他证明只要传输率小于信道容量，就可以通过使用适当的编码方法，使 得误码率任意小 s h a n n o n 的工作给人们提出了一个问题：如何构造传输率充分接近于信道容量 的码? 尽管这个问题至今尚未得到完全解决，但事实证明寻求答案的过程更为重 要，因为在这个过程中产生了许多非常重要的编码技巧 有很多因素影响着信息传输中的可靠信，例如t 噪音，同步化，干扰，等等 经典的编码理论主要考虑的是噪音的影响它主要分为纠错码理论及g a u s s i a n 信遭 中信息的传送这里主要介绍纠错码理论的发展 经典的纠错码理论通常研究的是有限域上的编码，特别是在二元域上令玛 是含有q 个元素的有限域，丑7 是n 元向量空间叼中的任子集c 就是一个 编码，其中c 的元素称为码元，而叼中的向量称为字在卫翟引入h a m m i n g 重 量的概念，对于任意的x = ( z l ，z 2 ，) 卫翟，定义 w h ( x ) = i i ：q o ) l ， 称为x 的h a m m i n g 重量这个重量函数就决定了卫翟中的一个度量， d h ( x ，y ) = ( x y ) ，v x ，y 日 称为x 与y 的h a m m i n g 距离令 d = m i n d h ( x ，y ) lx ，y c ，x y ) 1 四元拟循环码的研究 第一章绪论 称为码g 的极小h a m m i n g 距离这样，一个纠错码g 就包含了3 个重要的的参 数：码长n ，码元个数igi ，及极小h a m m i n g 距离d ，通常计作，蚓，d ) 码 为了应用上的实现，一个好的纠错码还必须易于编码及解码通常我们会要求 码具有一定的代数结构，例如要求码c 是四的线性子空间。即所谓的线性码此时 码的势就由它的维数k 决定，我们通常用h 七，d 1 表示一个长度为n 维数为k ，极小 h a m m i n g 距离为d 的线性码线性码一直是经典的纠错码理论研究的重点在s h a u - n o n 的论文【3 0 】发表不久，g 0 1 a y 【1 2 】与h a m m i n g 1 4 分别构造g o l a y 码与h a m m i n g 码，他们是编码理论中非常重要的两类线性码后来，v a nu n t 【4 1 】，a i n o v i e r 及l e o n - t i e r 4 5 】证明了完备码只有h a m m i n g 码，g o l a y 码及二元重复码三类s l e p i a n 的工作 【3 2 】i 3 3 】， 3 4 】更是给线性码的研究打下了坚实的基础继于b c h 的研究【4 】，【5 】，p e r t e r - s o n 2 5 第一次证明了b c h 码实际上就是循环码一这是一类非常重要的线性码对于 线性码的解码，也有着大量的工作尽管s l e p i a n 3 0 给出了译码表的构造方法非常 简单，但对于较多的线性码却不是很实用p e t e r s o n 2 5 ，g o v e n s t e i n 与z i e r l e r 1 3 及 b e r l e k a m p 2 】相继研究了b c h 码的解码m a s s e y 在文献【2 l 】及【2 2 】中，对b e r l e k a m p 在【2 1 中提出的算法加以改进，最终形成了著名的b e r l e k a m p - m a s s e y 算法 由于每个码元代表着一条信息，故码元个数就决定了码的信息量的大欢诮饴 牍讨我们通常依旧的是极大似然译码理论，在这个理论中，极小h a m m i n g 距离 就决定码g 的纠错能力因此，在码长固定的情况下，码元个数及极小h a m m n g 距离就可以用来衡量一个码的好坏显然，码元个数及极小h a m m i n g 距离是相互 影响的，码元增多势必造成极小h a m m i n g 距离的降低人们关心的问题是，在给定 码长及给定h a m m i n g 距离的条件下，码元个数最多能达到多少，即所谓的码界问 题 【4 1 】中给出了关于码元个数各种下晃及上界这样，构造接近或达到某个界的 纠错码就成了人们关注的课题这里有两个突破性的进展，一是代数几何码，另一 个是非线性码的构造 代数几何码是前苏联数学家g o p p a 在8 0 年代前后( 3 9 】， 4 0 】对于两类线性码做新 的考察得到的这种码在理论上其性能超过了过去已知的码1 9 8 2 年，v l a d u t ，z i n k 等人【2 0 】用模曲线构造的代数几何码，其码元个数渐近地达到了v a r s h i m o v - g i l b r t 2 四元拟循环码的研究 第一章绪论 界此后，构造新的具有好的具有好的参数的代数几何码越来越引起人们的关注 并且，随着不断地对代数几何码译码算法的改进，使得代数几何码在应用上得以实 现也逐渐成为可能 d e l s a r t e 提出的结合方案理论，它使得纠错码理论与设计及组合学紧密的集 合起来利用结合方案理论，在1 9 7 0 年左右几个非线性码被构造出来。包括二元 n o r d s t r o m - r o b i n ，k e r d o c k , p r e p a r a t a ，g o e t h a l s ，以及d e l s a r t e - g o e t h a s 码( 见文献【1 0 】，i n 【i s ，【2 6 】， 4 l 】i ) 与相同长度及极小h 锄m i n k 距离的线性码相比，他们往往具有更多 的码元，有时甚至达到两倍以上这样，在具有相同纠错能力下，我们可以很大地 提高码的信息量 1 2 本文的内容安排及主要结果 本文在第二章中研究了有限域上单生成元的拟循环码关于有限域上拟循环 码，结果有很多早期，c h e n 等人【7 】，k a r l i n 2 4 ，及w e l d o n 【2 7 】分别建立了拟循环码 与循环移位寄存器，高次剩余码之间的联系k a s a m i 3 7 表明拟循环码满足g i l b e r t v a r s h a m o v 界近期。拟循环码的代数结构由抽象代数理论 1 6 】及模的g r o b n e r 基理 论【1 7 】分别得到单生成元的拟循环码及其对偶码是拟循环码中研究最多的一种， 见 3 8 】，【3 6 】及【2 9 】继于q c 码的研究， 3 1 】 【3 ，【2 8 】，s 9 1 l i n 9 】讨论了单生成元的拟循 环码的结构，计数并给出了一个算法，对所有不同的单生成元拟循环码分别给出了 一个生成元但是，他需要一个非常特殊的条件，即z “一1 在玛h 及蜗n h 中具 有相同的分解本文在一般情况下讨论了单生成元拟循环码的结构，及计数，并推 广了s d g u i n 9 给出的算法 虽然非线性码和线性相比，具有更高的信息量，但由于构造复杂，很难像线性码 样找到较为简单的编码和译码算法，这在很大程度上阻碍了非线性码在实际中的 应用人们一直在试图寻找更为简单的方法来描述这些非线性码n e c h n e v 2 3 首先 研究了四元序列，他通过四元序列的2 - a d i c 展开式构造了个二元非线性码，并证 明它与k e r d o c k 码的两次删减等价相继地，b o z t 猫等人【6 】与k u m a r 等人【1 9 】也研 究了四元序列，发现其中某些序列的2 - a d i c 展开式与k e r d o c k 码有着惊人的相似 3 四元拟循环码的研究第一章绪论 在上述工作的基础上。h a m m o n s 等人 1 5 j 在非线性吗的研究中取得了突破性的进 展，他们构造了一系列的四元线性码，包括四元k e r d o c k ，p r a o p a r a t a ，g o e t h a l s ，d e l s a r t e - g o e t h a l s 及g o e t h a l 8 - d e l s a r t e 码，并证明了这些四元线性码在g r a y 映射f 的二元 像恰恰就是上述几个二元非线性码( 除四元p r e p a r a t a 及g o e t h a l s 码) 在此之后环 上的编码问题引起了人们越来越为广泛的关注，如p l e s s 与q i a n 4 2 】研究了四元循 环码的结构，并证明剩余类环z 4 ( 矿一1 ) 是主理想整环，z h e - x i a nw a n 【4 4 】给出 了伽罗华环上循环码的结构本文在第三章中证明了四元拟循环码可以分解为一些 循环码的直和，并利用这个分解，讨论了拟循环码的计数，并且给出了拟循环码的 对偶码的代数结构及计算方法 4 第二章单生成元拟循环码 2 1 单生成元拟循环码的计数 令蜀为有限域，m ，n 为正整数，且( m ，口) = 1 令c 为玛上长度为m n 的线 性码，满足 v ( c o o ，c l o ，一，一t 。o ；c o l ，c n ，一l ，1 ；c o ，m 一1 ，c 1 , ：1 1 1 , - - 1 ，一l ，m 一1 ) c 爿 ( c o ，m 一1 ，c l , r n , - 1 ，- ，c ”1 ，m 一1 ；c ，c l o ，- 一，c n 一1 ，o ；t m 一2 ，q ，m 一2 ，c n 一，m 一2 ) e c ( 2 1 ) 则称c 为拟循环码令r = 蜀m 0 “一1 ) ，且舻是r 的外直和，定义一一对应 m ：叼“一皿“ 鱼2 ( a 0 0 ，a i o ，a n - l ，o ；a 0 1 ，口1 l ，6 t n - i ，l ；一；a o ，m i ，8 l 。m t ，+ ，一i ，m t ) - 斗垒( 。) = ( a o ( 。) ，口1 ( 墨) ，c h l ( z ) 其中。如) = 妻a 玎一，则( 2 1 ) 等价于 v 盟( 鸳) = ( o o ( 霉) ，o l ( 嚣) ，d n l ( 。) ) 皿( g ) ：= = 亭嚣垒( z ) = ( 8 0 ( 正) ，z a l ( z ) ，一，z c h l ( z ) ) 雪( g ) 因此，g 为拟循环码当且仅当皿( g ) 是r n 的k - 子模若我们将c 与田( g ) 等同起 来，则拟循环码可以直接定义为舻的r - 子模 令盟( z ) = ( a o ( z ) ，0 1 ( 。) ，口。一】( z ) ) r n ，则 r 垒( 。) = 、【口( z ) 垒( 。) = d ( z ) o ( z ) ，a ( 茁) o l ( z ) ，一，n ( z ) 口n 一1 ( 。) ) 称为单生成元拟循环码，生成元为o ( z ) 本文中均假设z m 一1 = 9 ( z ) 0 ) 及 ( 。) = l ( 。) 2 ( z ) k ( z ) ，其中垃( z ) 为 玛l 司中度为e i 的首一不可约多项式并且g ( z ) 玛渊令s = 腰 q - i z ( z 一1 ) 及 r = 吗h ( 一一1 ) 四元拟循环码的研究第二章单生成元拟循环码 定理2 1 令瓦( z ) = 簧措，i = l ，2 ，r ，则存在沁( 。) ， v i c z ) 吗吲，满足 沁( 。) i ( 茁) + ( 嚣) 五t ( 。) = 1 令o i ( z ) = 1 一九( z ) ，k ( z ) ，则 ( 1 ) e lc x ) ，易( 。) 为s g ( z ) 中两两正交的非零幂等元； ( 2 ) o d z ) 为疏( 。) 的单位元，并且s 商( z ) = s o i ( z ) ； ( 3 ) 记p ( 。) = o l ( z ) + + 啡( $ ) ，则o ( z ) 为勋( z ) 的单位元； ( 4 ) s 9 ( z ) = s 元( 。) o os r ( z ) ； ( 5 ) 对于所有的l = 1 ，r ，映射 为一个可定义的环同构 z f 0 【。】( ( z ) ) ，( 。) + ( h i ( x ) ) s h i 忙) - _ ，( z ) 仇( z ) ( 2 2 ) 口 证明( 1 ) 显然，吼( 。) e0 ( r o o dh j ( z ) ) ，j i ，o i ( z ) 暑1 ( r o o d 札( z ) ) ，以及o i ( t ) 葺 0 ( r o o dg ( z ) ) 因此吼( z ) 2eo i ( ) ( m o d ”一1 ) ，即在勖( z ) 中日i ( z ) 2 = 吼( z ) 所以o i ( z ) 为s g ( z ) 中的非零幂等元并且对于任意的i j 有o ( z ) o j ( z ) 兰0 ( m o d ( z ) ) ，= 1 ，2 ，r 以及巩( 。) 易( ) i0 ( m o d9 ( g ) ) ，因此巩( z ) 码( z ) 三0 ( m o dz ”一1 ) ，即在 s 9 ( g ) 中口i ( ) 如( z ) = 0 ( 2 ) 对任意：，( z ) s 元( g ) ，有，( $ ) 吼( 嚣) i ，( z ) e0 ( m o d7 u ( z ) ) ，j i ，( z ) 巩( z ) 兰 ，( z ) ( m o d ( z ) ) ，以及，( z ) 巩( z ) 10e ，( 。) ( r r t o d9 ( 2 ) ) 贝0 ，( $ ) 巩( z ) i ，( z ) ( m o d 。“一 1 ) ，即在赢( z ) 中有f ( x ) o i ( x ) = ，( z ) 因此巩( z ) 为娇i ( z ) 的单位元，并且有蕊i ( z ) = 即i ( z ) ( 3 ) 对任意，( z ) 鳜 ( z ) ，均有，( z ) 日( z ) ；，( z ) 易( z ) ；，( 。) ( m o db ( z ) ) ，j = l ，r ，以及，( z ) 口( 。) e0i ，( z ) ( m o d9 ( z ) ) 贝0f ( z ) o ( z ) i ，( t ) ( m o d $ 一1 ) ，即在 曲( z ) 中有，( z ) 日( z ) = ，( z ) 由此o c = ) 为勋( 。) 中的单位元 ( 4 ) 对任意，( z ) 曲( 。) ，由( 2 ) 和( 3 ) 得，( z ) = ，( 。) 口( z ) = ，( 。) e l ( ) + + ，( 。) 啡( 霉) 靠1 ( z ) + + 疏( z ) ，则s g ( z ) = 娇1 ( z ) + + 5 需( z ) 假设0 = ，l ( ) + - i - ，r ( 甸，其中 ( z ) 赢t ( ) 伺乘上瓯( 甸，我们有0 = 五( z 溉( z ) = ( 。) j = 1 ，2 ，r ， 因此s 9 ( z ) = s 元l ( z ) o - o s 群( 。) 6 四元拟循环码的研究 第二章单生成元拟循环码 ( 5 ) 对任意f l ( x ) + ( k ( z ) ) = ，2 ( 。) + ( z ) ) ，均有，l ( z ) 一，2 ( z ) 兰0 ( m o dh ( ) ) ， 则f l ( 霉) 巩( z ) 一，2 ( 。) 巩( z ) 妻0 ( m o d $ “一1 ) ，即在鳜( 嚣) 中，( 。) 巩和) = ，2 ( 。) 哦( z ) 显然，( 2 2 ) 为一个环满同态又对任意，( z ) + ( 屯( g ) ) 玛n 旧( 凡( 。) ) ，在疏( 。) 中满足，( $ ) 巩( 霉) = 0 ，即，( z ) 巩( 。) 兰0 ( m o d 。“一1 ) ，则，( z ) ；0 ( m o d 啊( 。) ) 因此 ，( ) + ( k ( z ) ) = ( 氐( $ ) ) 故( 2 2 ) 为一个同构 口 记定理2 1 中o ( z ) 和o i ( z ) 均为玛m 中多项式，则我们可以对r a ( z ) 进行直和 分解 定理2 2 令8 ( z ) ，o i ( z ) r g ( z ) 均如定理( 2 1 ) 中所示，则有p ( 和o i ( x ) 分别 为r g ( z ) 和蕊 ( 。) 中的单位元而且， ( 1 ) 毋( z ) = r l ( ) o or ，( 。) ； ( 2 ) 对任意的i = 1 ，2 ，r ，映射 正；m ( k ( 。) ) r 矗( z ) f ( x ) + ( h i ( x ) ) _ + ，( z ) 巩( z ) 为一个可定义的环同构 令阢= 筛( 。) 一( o ) ，江1 ，2 ，r ，以及 w = a i ( x ) + + a ，( 。) i a i ( x ) 嘶) s g ( z ) ( 2 3 ) 口 i 一l 引理2 3 令a ( 。) = o ( $ ) a i 玛n m ，其中啦( z ) 玛吼，以及，( $ ) 玛雠 i = u 则，( z ) i ( a ( z ) ，z “一i ) 当且仅当，( z ) l ( a o ( 。) ，一，a n - 1 ( z ) ，z ”一1 ) 证明假设，( z ) i ( a ( 。) ，。”一1 ) ，则对某个b ( z ) 玛n m 有a ( z ) = ，( z ) b ( z ) 假设口( 。) = n - i 如( z ) 其中b l ( 。) 玛渊，则a ( 嚣) = 美n 如) a _ 蓉，( 。) 氐( z ) l = ul = ul = u 因此a i ( z ) = f ( x ) b i ( m ) ，i = 0 ，1 ，n 一1 故，( z ) 1 【蜘( ，d i ( $ ) ，a o , - - l ( 曲，一一1 ) 反之显然 7 口 四元拟循环码的研究第二章单生成元拟循环码 引理2 4 令a ( ) = 啦( z ) 啦勋( z ) ，其中a i ( z ) 玛h ，则a ( z ) w 当且仅 当( 口o ( z ) ，a d z ) ，a n - l ( z ) ，。”一1 ) = 9 ( 嚣) 证明假设a ( z ) w ，则a ( ) = a i ( z ) + a 2 ( z ) + ，+ 4 ( $ ) ，其中也( z ) 隈则 对所有i = l ，r ，均有a ( z ) 蔓a ( z ) 0 ( m o d ( 。) ) ，即h i ( z ) x a ( z ) ，由引理2 3 知 h i ( z ) x ( a o ( z ) ，a l ( z ) ，a r t - 1 ( z ) ，z “一1 ) 显然9 ( ) i ( o o ( ) ，口l ( z ) ，a n l ( z ) ，。竹；一1 ) 因此( a o ( z ) ，a l ( z ) ，a n - 1 ( z ) ，z 一1 ) = 9 ( z ) 反之，假设( a o ( x ) ，o l ( ) ，a t , - l ( z ) ，z “一1 ) = 9 ( 。) ，则g ( z ) ia ( z ) ，因此a ( z ) s g ( 。) 由定理2 1 的( 4 ) 知a ( z ) 可以唯一的记为a ( z ) = a ( z ) ，其中a i ( x ) s i ( z ) 如果对某个i 有a ( z ) = 0 ，则a i ( z ) a i ( x ) i0 ( m o dk ( 。) ) ，即( 嚣) ia ( 。) 由引理2 3 知h i ( x ) i ( a o ( z ) ，a d z ) ，a n - - 1 ( ) ，扩一1 ) = 9 ( z ) ，矛盾因此a i ( x ) 0 ， = l ，r ，故a ( o ) w 口 类似引理2 4 可得 引理2 5 令a ( 。) ：莹。( 。) 啦鳜i ( 。) ，其中啦( 嚣) 吗吼则a ( z ) 职当且 仅当( a o ( z ) ，a l ( z ) ，a n 一1 ( z ) ，z “一1 ) = 元( 。) c 3 因为瓦( 。) 在m 中不可约，则由( 2 3 ) 知矗毛( z ) 型玛 z 】( k ( z ) ) = 玛。t ，为有 庐个元素的有限域令( 蕊i ( 。) ) + = 蕊i ( z ) 一( o ) ，为厩( 。) 中单位组成的乘法群 对i = l ，2 ，r ，定义暇上关系一： a ( 霉) 一b ( 。) 车= 3 p ( x ) ( 矗硪( z ) ) + ，使得a ( z ) = p ( z ) b ( 。)( 2 4 ) 很容易证明一为个珉上的等价关系对任意的a ( z ) 眦，把a ( z ) 的等价类表 示为五( 。) ，且令 、 为等价类集合 i 瓦= 再( z ) la ( z ) w d ( 2 5 ) 引理2 6 令( 哟( 茁) ) 为r g ( x ) 中的单位组成的乘法群，p ( z ) r gc z ) ，则 p ( z ) ( 勋( z ) ) 当且仅当( p ( 。) ，z “一1 ) = 9 ( z ) 8 西元拟循环码的研究第二章单生成元拟循环码 证明假设p ( z ) ( r g ( 。) ) ，由定理2 2 的( 1 ) 知p ( = p 1 ( z ) + + p r ( $ ) ，其中 p ( z ) ( r ( 。) ) + ，则p ( ) ep ( 。) 0 ( m o d h t ( 。) ) ，i = l ，2 ，r ，即 ( z ) 庙( 霉) 因此 ( p ( o ) ，“一1 ) = 9 ( ) 反之，若白( z ) ，。“一1 ) = 9 ( z ) ，由定理2 2 的( 1 ) 知假设p ( z ) = p l ( z ) + + p r ( z ) ， 其中p ( z ) 厩i ( z ) ，则p ( z ) 三p ( 。) 0 ( m o d h t ( 。) ) ，因此p ( ) ( r g ( 茹) ) ，故p ( z ) ( 励( ) ) + 口 引理2 7 对任意a ( z ) 毗，i - ( 。) i = 证明定义 庐：( 蕊( 。) ) + +万( z ) p ( z ) - p ( x ) a ( x ) 显然，咖为一个满射对任意p l 【z ) ，p 2 【z ) ( f 躐( 。) ) ，若p 1 0 ) a 【z ) = p 2 ( z ) a ( z ) ，则 有l ( 。) 一p 2 ( z ) ) a ( z ) ：o 假设a ( 。) ：基8 i ( $ ) a ，其中啦( z ) 玛圈，故( z m 1 ) i ( p 1 ( z ) 一p 2 ( z ) ) o ( z ) ，i = 0 ，i ，n 一1 由弓1 理2 5 得( 口o ( z ) ，口l ( z ) ，q n - - l ( z ) ，。“一1 ) = 毛( z ) ，因此k ( 石) i ( p 。( 。) 一p 2 ( z ) ) ，则在( 蕊i ( z ) ) + 中有p l ( z ) = p 2 ( 故毋为个 双射所以由定理2 2 的( 2 ) 得i 万( ) i ( 蕊( ) ) i = 铲一1 口 由定理2 1 的( 5 ) 知l 慨l = g “q 一1 ，再由引理2 7 可得 推论2 8 对i = 1 ，2 ，r i 厩i = 2 q ：! c 坚i _ i 口 令= 一w l 一w 2 谚r ，则l 谚卢i 卉= l q e 盟i - i 定理2 9 令= go 为一个以 ( $ ) 为p c p 的单生成q c 码) ，则存在个 万到的一一映射p 此以 ( z ) 为p c p 的单生成q c 码的个数为直篆等 证明定义 妒：一w + ( 五l ( 。) ，瓦( z ) - 斗，鱼( z ) 其中记a ( 。) = a l ( 功+ + 4 ( ) s g ( ) 为a ( z ) = 啦( z ) q ，以及垒( ) = 9 四元拟循环码的研究 第二章单生成元拟循环码 ( a o ( z ) ，8 l ( 霉) ，一1 ( z ) ) 因为a ( z ) 矾，a ( x ) w ，由引理2 4 知( a o c ) ，口l ( 。) ， ，口。l ( z ) ，z “一1 ) = 9 ( z ) ，则逝( 。) 为以 ( ) 为p c p 的单生成元q c 码，即 逝( z ) e 对任意( 页l ( z ) ，瓦( z ) ) ，( 百l ( z ) ，耳( 。) ) w = w l i - r ，若 口l ( 。) ，瓦) = l ( z ) ，耳( z ) ) ，则对 = 1 ，2 ，r ，存在乳白) 使得取( z ) ( r h i ( x ) ) 以及a ( 霉) = a ( z ) 最( z ) 令p ( x ) = p l ( z ) + + 肼( z ) r g ( z ) ，由同构( 2 3 ) 知p ( z ) 为( 励( 。) ) + 中的单位由引理2 6 得( p ( 。) ，z ”一1 ) = g ( 岱) ，因此( p ( 。) ， ( 茁) ) = 1 令a o ：) = a ( 。) ，b ( z ) = e 且( 。) ，则由定理2 1 的( 4 ) 得a ( 甸= p l ( z ) b l ( z ) + + p ，( $ ) b r ( 。) = p ( z ) b ( 茁) 记a ( 。) 和b ( z ) 为a ( ) = eo i ( 。) a 和b ( z ) = ebi(x)a_i71,- n 一l 因而垒( 。) = p ( z ) ( z ) ，所以施( z ) = r 猷z ) 故妒为一个可定义的映射 对任意( 五l ( z ) ，再( z ) ) ，( 吾l ( 。) ，耳( z ) ) 形，若逝( z ) = 魄( z ) ，则存在 p ( 喝m ，( p ( ， ( $ ) ) = 1 使得垒( ) = p ( 功( ，因此a ( z ) = p ( z 归( z ) 由定理2 1 的( 1 ) 中勋( 。) 的直和分解，有a i ( x ) = p ( 。) b ( z ) = p ( z ) 仇( z ) b i ( z ) j = l ，2 ，r ，其中 o i ( x ) 为定理2 1 中觚( 。) 的单位元因为( 。) ，$ ”一1 ) = i ，则p ( z ) o i ( z ) r 蕊( 霉) 以及 p ( 。) 巩( g ) 0 ，即p ( ) 吼( z ) ( 冗毫( z ) ) 所以在职中有五( 。) = 甄( z ) ，i = 1 ，2 ，r ， 因此，( 五( 。) ，墨( z ) ) = ( 瓦( z ) ，- g r ( z ) ) 所以1 ；f ，为个单射 最后对任意r a ( z ) e ，其中垒( 霉) = ( 口o ( z ) ，a l ( 。) ，o 。一l ( 。) ) ，以及( 口o ( z ) ， o l ( ) ，a n l ( 。) ，。”一1 ) = 9 ( 。) 令a ( z ) = e ( $ ) o q ，由弓f 理2 4 知a ( z ) w i = 1 记a ( 。) 为a ( z ) = a i ( x ) ，其中a i ( x ) m 则( 页1 【z ) ，瓦( 。) ) w 以及 妒( 页t ( r ) ，瓦( z ) ) = 逝( z ) 所以妒为一个满射 口 2 2单生成元拟循环码的生成元 我们仍然记 ( z ) 亍 l ( z ) 2 ( 。) k ( z ) ，其中 l ( 。) ，k ( z ) 为玛【司中不可约 多项式对i = 1 ，r ，假设也( z ) 能够分解为 h i ( z ) = 7 k l ( z ) ，( z ) ，k ( 。) ， 其中k 1 ( z ) ，。h ( 。) 为玛n 【司中首一不可约多项式不失一般性，假设为h l ( z ) 在蜀n 某个扩域上的根，则 1 n 四元拟循环码的研究第二章单生成元拟循环码 1 ( 嚣) = ( 。一) ( 茹一矿) ( z 一9 2 “) ( 霉一g ( 出一1 h ) 其中d i 为满足。= 的最小芷整数因为 ( 。) 为吗m 中以为根的度为龟的 不可约多项式，我们有 ( z ) = ( 嚣一) ( z f 9 “) ( 。一2 2 ) ( z 一9 。一1 ) 其中e i 为满足一= 的最小正整数则e in 画，所以南i 函另一方面，因为 9 。南：f ，我们有也i 南因此d i _ 南故h n ( z ) ，h i ( g ) 均为玛。矧中度 为凼l 南的多项式，且= ( e ) 类似定理2 1 有 定理2 1 0 令砖= 考高，i = 1 ，t r j = i ，h ，则存在b ( 。) ，( z ) 码n 满足b ( z ) ( z ) 十( z ) 砖( z ) = l 令( z ) = 1 一b ( z ) ( z ) ，则 ( 1 ) 对i = 1 ，r , b i l ( z ) ，p t ，觑( z ) 为s 藏( ) 中两两正交的非零幂等元； ( 2 ) 令吼( z ) 为定理2 1 中鳜i ( z ) 的单位元，并且吼( 动= 日i l ( z ) + - i - 巩，h ( 。) ； ( 3 ) ( z ) 为s 玎( z ) 以及鳜村( z ) = 即玎( z ) ； ( 4 ) s h i ( $ ) = s 矗n ( z ) o os 亢 ；( 。) ； ( 5 ) 对j = 1 ，映射 为一个可定义的环同构 喝n m ( ( z ) ) 斗 s 玎( z ) ，( z ) + ( 玎( z ) ) h ，( z ) 8 玎( z ) 口 定理2 1 1 记矾如( 2 5 ) 所示当i = 1 ，由定理2 1 0 的( 5 ) 知s 码( z ) 为有矿d 个元素的有限域，令哟( 。) 为s 玎( z ) 的本原元记厶= 案导，以及 r = o o ，0 ，1 ，一，口“由一2 ) 则元素 几t ( 。) “+ 仉，抖1 ( z ) “+ 1 + + 仉，舡( $ ) 。h ( 2 6 ) 四元拟循环码的研究 第二章 单生成元拟循环码 1 t 岛，0 i ts 厶一l ，“l ，嵋n ，构成i 瓦的一个完全表示集合 ( 我们约 定啊( 茹) 。= o ) 证明( 2 6 ) 中的元素个数为 w 州”拍一陬卅+ 舶= 籍= 矾 因此我们要完成证明只需要证明它们属于识的不同等价类对任意 以及 a ( z ) = 仉t ( 岔) “+ 巩，蚌l ( 。) “+ 1 + + 丌i 。h ( 茁) - b ) = m m ( z ) 厶+ 以，廿+ l 如) 厶+ 1 + + r r i , k i ( 。) 以 其中l “，厶厶一i ，i t + 1 ，k ，厶+ 一， 。i i ，若页( 。) = 百( 。) ，则存在 p ( $ ) ( r i ( 写) ) 满足 a ( 。) = 仉t ( 。) + 以，蚪i ( 。) 。件1 + + f r i , k ( z ) h = p ( 茹) ( 7 r i ( g ) 知+ 丌i ，埘+ l 【茁) ”+ 1 + 十几，h ( z ) ，轧) = p ( z ) 7 n 加( z ) ，o + p ( 茁) 仉，w + l ( 嚣) ，o + 1 + + p ( $ ) 丌，( z ) l 记巩t ( z ) “( s 矗n ( 。) ) + 以及p ( z ) 丌 。( z ) 知( s 五。( 。) ) + ，则由定理2 1 0 的( 4 ) 知一定有 t = 和在( 疏t ( z ) ) + 中有丌i t ( 岔) “= p ( z ) 仉t ( z ) ，因此p ( z ) 口n ( z ) = ：一 由定理2 2 的( 2 ) 知p ( z ) ( 蕊i ( z ) ) 笺卫饶，则p ( 。) 一一1 = 吼(