（应用数学专业论文）环上码深度的研究.pdf

环上码深度的研究 摘要 近些年来，很多从事编码理论的研究者将研究的兴趣从有限域上的编码理论 转移到有限环上，尤其是五一码的研究。 在1 9 9 7 年，t e t z i n o n 在【1 4 】中，对域上码引进了深度的概念介绍了一些 性质，给出了计算域最上码字深度的递归算法，c j m i t c h e l l 在 1 5 中对e 上线 性循环码的深度谱进行了研究。在2 0 0 0 年，l u o 在【1 6 】中给出了域只上码字深 度的递归算法。 本论文对环上码的深度分布算法进行了研究，主要结果如下： 第一：建立了有限环z 4 上的深度分布理论。本文定义了有限环z 。上码字的 深度和码的深度分布，给出了有限环乙上码字的深度和码的深度分布的一些性 质，研究了z 4 上线性码和线性循环码的深度谱，证明了4 k , 2 。z 型线性码的深度谱 至少含有毛+ k ：个非零值，和一类4 型线性循环码的深度谱为 n ，聆一1 ，疗一k + 1 ) ，研究了一类特殊类型z 4 一负循环码的深度谱；利用组合数 学、图论和数论知识，给出了两种计算有限环z 。上码字深度的递归算法。 第二，定义了环z 一上码字的深度，研究了z 一线性码的深度分布的性质， 给出了一种计算环z ，的码字深度的递归算法。 关键词：z 。循环码；z 。二负循环码；z ，一线性码；深度；深度谱 t h es t u d yo f d e p t ho fc o d e so v e rr i n g a b s t r a c t i nr e c e n t y e a r s ，m a n yr e s e a r c h e r so nc o d i n gt h e o r ya r e i n t e r e s t i n g i n s t u d y i n gc o d i n gt h e o r yo v e rf i n i t er i n g s ，e s p e c i a l l yi ns t u d y i n g z d c o d e i n19 9 7 ，t e t z i o n i n t r o d u c e d d e p t h o fc o d e so v e rf i e l d s a n ds o m e p r o p e r t i e si n 1 4 ，h ea l s og a v et h er e c u r s i v ea l g o r i t h m sf o rc o m p u t i n gt h e d e p t h o fc o d e w o r d so v e r e i n 15 】，c j m i t c h e l ls t u d i e dt h ed e p t hs p e c t r u m o fc y c l i cc o d e so v e r i n2 0 0 0 ，l u o g a v e t h er e c u r s i v e a l g o r i t h m s f o r c o m p u t i n gt h ed e p t ho fc o d e w o r d so v e rf i e l d c i nt h i sd i s s e r t a t i o n ，w es t u d y t h ed e p t hd i s t r i b u t i o no fl i n e a r c o d e so v e rr i n g sa n da l g o r i t h m so fe o d e w o r d s o v e r r i n g s ，a n dt h em a i n r e s u l t sa r ea sf o l l o w s ： i t h e o r y o fd e p t hd i s t r i b u t i o no fc o d e so v e raf i n i t e r i n gz 4 i s e s t a b l i s h e d w ed e f i n et h ed e p t ho fac o d e w o r da n dt h ed e p t hd i s t r i b u t i o no f c o d e so v e raf i n i t er i n g z 4 ，a n dg i v ean u m b e ro fp r o p e r t i e so nt h ed e p t ho f c o d e w o r d sa n dt h ed e p t hd i s t r i b u t i o no fc o d e so n r i n gz 4 ，a n di ti sp r o v e dt h a t t h ed e p t hs p e c t r u mo fl i n e a rc e d e so f t y p e 4 e , 2 岛h a sa tl e a s t k l + k ，n o n z e r o v a l u e s ，a n d t h e d e p t hs p e c t r u m o fl i n e a r c y c l i c c o d e so f t y p e 4 i s n ， t 一1 ，- 一，疗一k + 1 ，a n d s t u d i e st h ed e p t h s p e c t r u m so f a s p e c i a lt y p eo f z 4 一n e g a c y c l i cc o d e s b yu s i n gc o m b i n a t o r ym a t h e m a t i c s ，t h e o r yo fg r a p h a n dn u m b e rt h e o r y ，t w or e c u r s i v ea l g o r i t h m sf o rc o m p u t i n gt h ed e p t ho fa c o d e w o r do nr i n g z 4 a r ep r e s e n t e d 2 t h ed e p t ho fae o d e w o r do v e rr i n g z i sd e f i n i t e d ，a n dan u m b e r o f p r o p e r t i e so fd e p t hd i s t r i b u t i o no f l i n e a rc o d e s o v e rr i n g z p k a r es t u d i e d - a r e c u r s i v ea l g o r i t h mf o rc o m p u t i n gt h ed e p t ho fc o d e w o r d so v e rr i n g z ，i s a l s og i v e n k e yv o r d s ：z 4 一c y c l i c c o d e ；z ，一c o d e ；五一n e g a c y e l i c c o d e ； d e p t h ；d e p t hs p e c t r u m 合肥工业大学 本论文经答辩委员会全体委员审查，确认符合合肥工业大学硕士 学位论文质量要求。 答辩委员会签名：( 工作单位、职称) 拂私坝 甄荞矽勤 c 动力z 分 苏2 颞协千 导 ，勿 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得佥毽王些本堂或其他教育机构的学位或证书而使用过的材料。与我一同工作 的同志对本研究所傲的任何贡献均己在论文中作了明确的说明并表示谢意。 学位论文作者签字：重宏至签字日期：弦旷年f 月锣日 学位论文版权使用授权书 本学位论文作者完全了解盒a 墨王、业友堂有关保留、使用学位论文的规定，有权保留并向 t 国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅。本人授权金g b 王些盘 ! l 可以将学位论文的全部或部分论文内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文者签名：翟 雾墨导师签名 签字日期：叮年r 月以日签字日期 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话 邮编 致谢 在这三年的研究生学习阶段，我的导师朱士信教授不仅在学业上对我进行 耐心的指导，而且还在生活上给予我很大的帮助。朱老师严谨的治学态度、宽 广的胸怀和豁达的处世之道，都是学生学习的楷模。在此，作者向导师致以最 诚挚的敬意和衷心的感谢! 在本人学习期间，还得到了各任课老师的热心的关怀和无私的帮助，师兄 弟们的鼓励和帮助，在此，向他们表示深深的谢意。 最后，感谢父母和兄长多年的大力支持和照顾，在我研究生学习阶段对我 提供的物质帮助和精神鼓励。正是家人的无私的帮助和奉献，才使我在研究生 阶段全身心的投入到学习之中。 作者：童宏玺 2 0 0 5 年5 月 第一章绪论 1 1引言 1 9 4 8 年s h a n n o n 在他的开创性论文“am a t h e m a t i c a l t h e o r y o f c o m m u n i c a t i o n ”中，首次阐明了在有扰信道中实现可靠通信的方法，提出了著 名的有扰信道编码定理，奠定了纠错码的基石。自此以后，h a m m i n g 、s l e p i a n p r a n g e 等人在上世纪5 0 年代初，根据s h a n n o n 的思想，给出了一系列设计好 码和有效译码的方法。以后，纠错码受到了越来越多的通信和数学工作者，特 别是数学家的重视，使纠错码无论在理论上还是在实际中都得到飞速发展。 迄今，纠错码已有五十多年的历史，其发展过程大致分为以下几个阶段： 上世纪5 0 年代至上世纪6 0 年代初，主要研究各种有效的编、译码方法， 奠定了线性分组码的理论基础，提出了著名的b c h 码，同时也给出了纠错码的 基本码限。这是纠错码从无到有得到迅速发展的年代。 上世纪6 0 年代至上世纪7 0 年代初，这是纠错码发展过程中最为活跃的时 期。不仅提出了许多有效的编译码方法，而且注意到了纠错码的实用化问题， 讨论了与实用有关的各种问题，所有这些问题的研究为纠错码的实用打下了坚 实基础。在此期间，以代数方法特别以有限域理论为基础的线性分组码理论已 趋成熟。 上世纪7 0 年代至上世纪8 0 年代初，这是纠错码发展史中具有极其重要意 义的时期。在理论上以g o p p a 为首的一批学者，构造了一类g o p p a 码，其中一 类子码能达到s h a n n o n 在信道编码定理中所提出的s h a n n o n 码所能达到的性能， 这是纠错码历史上具有划时代意义。在这期间大规模集合电路和微机的迅速发 展，为纠错码的实用打下了坚实的物质基础，因而与实用相关的各种技术及有 关问题得到了极大关注，并在实用中取得了巨大的成功。 自上世纪8 0 年代初以来，g o p p a 等从几何观点讨论分析码，利用代数曲线 构造了一类代数几何码，在这些码中，某些码的性能达到了s h a n n o n 码所能达 到的性能。由于代数几何码是一类范围非常广的码，在理论上已证明它具有优 越性能，因而受到了编码理论研究者，尤其是代数几何学家的重视，使代数几 何码的研究得到迅速发展，取得了许多成果。自上世纪7 0 年代末以来，纠错码 技术已开始渗透到很多领域。利用纠错码中的许多编、译码原理和方法，与通 信系统中其它有关技术相结合，得到了一些令人惊喜的结果。如：纠错码与调 制技术相结合所产生的t c m 技术，已作为国际通信中标准技术而推广使用： 纠错码与密码结合，可以构造出一类既能加密签名，又具有纠错功能的密码系 统：纠错码与信源编码相结合的结果，使得通信系统更为有效与可靠。不仅如 此，纠错码中的许多译码思想和方法，与神经元网络中的能量函数有密切关系， 可以用来解决神经元网络中的一些问题。因此，可以预料，随着科学的进步和 实际需要，纠错码理论必将进一步发展，它的应用范围必将进一步扩大。 1 2 本文的主要内容 随着纠错码理论的进一步发展，有限域上编码理论已发展的较为完备，因 此有很多从事这方面研究的研究者把研究兴趣转移到有限环上的编码理论的研 究，它现在是研究熟点，比如：z 4 一码以及z 。一码等等。 ， 本文在简单介绍了编码理论的一些背景，介绍了乙一码中的些相关内容 后，主要研究下面几个方面： 第一，研究环z 。上线性码与线性循环码的深度谱，证明了4 k , 2 b 型线性码 的深度分布中至少含有髓+ k ：个非零值，并给出了两种特定类型线性循环码的 深度谱，研究了一种特殊类型乙一负循环码的深度谱。 第二，通过定义环乙上码字的深度，研究了码字深度的一些性质，给出了 计算环z 。上码字深度的两种递归算法。 第三，定义了环z 。上码字的深度，给出了计算环z 一上码字深度的递归算 ，r 法。 2 一 2 1 线性分组码 第二章域上的线性码聃3 2 1 1 分组码豹基本概念： 在数字通信中，经常利用纠错码来进行差错控制，其中一类重要的纠错码 就是分组码。 定义2 1分组码是对每段k 位长的信息组，以一定规则增加，= 开一k 个 校验元，组成长为”的序列：h ，c l ，一，o 一。) ，称这个序列为码字( 码组，码矢) 。 在二进制情况下，信息组共有2 个，因此通过编码器后，相应的码字也有2 个， 称这2 个码字的集合为( n ，) 分组码。 ，z 长序列的可能排列总共有2 ”种( 每一n 长序列称为n 重) ，而( n ，k ) 分组码 的码字集合只有2 种，所以分组码的编码问题就是定出一套规则，以便从2 ”个 以重中选出2 。个码字。不同的选取规则就得到不同的码。 定义2 2两个n 重x ，y 之间对应位取值不同的个数，称为它们之间的汉明 距离，用d ( x ，y ) 表示。 定义2 3n 重x 中非零码元的个数，称为它的汉明重量，简称重量，用w ( x ) 表示。 定义2 4 k ) 分组码中，任两个码字之间汉明距离的最小值，称为该分 组码的最小汉明距离矾，简称最小距离或。m 如i n 朋p ( 墨”) 。 也是( 珂，的分组码的另一重要参数，它表明了分组码抗干扰能力的大小，为 方便起见，今后玩简称为d 。 2 1 2 线性分组码 一个陬k 】线性码，是把信息划成k 个码元为一段，通过编码器变成长为n 个 码元的一组作为陋，k 】线性分组码的一个码字。若每位码元的取值有口种( q 为 素数幂) ，则共有q 个码字，若9 2 个码字集合构成了兄上所有n 重构成的玎维线 性空间的一个k 维线性子空间，则称它是一个h k 】线性分组码，简称为【栉，k 】线 性码。 定义2 5 i n ，k 】线性码是只上撑维线性空间v o 中的一个七维子空间以。由 于该线性子空间在加法运算下构成阿贝尔群，所以线性码又称为群码。 3 因线性分组码是分组码的一类，因此有关分组码的参数，如码率，码字的 距离与码的最小距离，码字的重量等定义，对线性分组码均适用，这里不再赘 述。 显然，七，d 是分组码的两个最重要参数，因此今后我们用【挖，七，d 】( 或 n ，k 】) 表示线性分组码，而用( n ，m ，d ) 表示码字数日为m 的任何码。 n ，k ，d 】分组码是一个群码，因此若码字c ：，c 2 i n ，k ，d 】，则由群的封闭性知 c l + c 2 胛，k ，d 】，即q + c 2 也必是m ，k ，d 】分组码的一个码字，所以码字q ，c 2 之间 距离d ( c 。，c ：) ，必等于第三个码字q + c 2 的汉明重量，因此，一个 h ，k ，d 分组码 的最小距离必等于码中非零码字的最小重量，由此可得到： 命题2 1 【疗，k ，川线性分组码的最小距离等于非零码字的最小重量 即d = r a i n w ( c ，) c i 【，z ，t 竹 2 1 3 线性码的生成矩阵与一致校验矩阵 i n ，k ，棚分组码的编码1 0 7 题就是在n 维线性空间中，如何找出满足一定要 求的，有2 个矢量组成的k 维线性空间或者说，在满足给定条件下，如何 从已知的k 个信息元求得r = 疗一k 个校验元。这相当于建立一线性方程组，已知 k 个系数，要求”一k 个未知数，使得到的码恰好有所要求的最小距离d 。 若定义一个如一) r 阶矩阵h 满足； h c 7 = 0 7 ( 2 1 ) 或：c - h7 = 0( 2 2 ) 其中c 为k ，i 】的任一码字；日的每一行向量均线性无关，则称h 为码【n ，k 】的一 致检验矩阵。 显然打矩阵的每一行代表一个线性方程的参数，它表示求一个校验元的线 性方程，故若日确定了，则码 h ，k 也就确定了。 另一方面，【n ，k ，d 】分组码的2 个码字组成了一个女维子空间，因此这2 个 码完全可由k 个独立向量所组成的基而张成。 若将这k 个独立向量作为行向量写成矩阵形式，则称该矩阵为线性码 【n ，k ，d 】的生成矩阵。若线性码h k ，d 】生成矩阵为g ，k 个信息元组成的信息组 为研，则有： c = m g( 2 3 ) 将( 2 3 ) 式代入( 2 1 ) 有；日g = 0 ( 2 4 ) 将( 2 3 ) 式代入( 2 2 ) 有：g h 7 = 0 ( 2 5 ) 即g 与日的行生成的空间互为零空间。 - 4 2 1 4 对偶码 【h ，七，d 】码是，z 维线性空间的一个i 维子空间。，由一组基即g 的行张成， 由线性代数知识可知，它的零空间必是一个n t 维的线性子空间。，并由 ”一七个独立向量张成，由( 2 4 ) 、( 2 5 ) 式可知，这”一个向量就是日矩阵的行， 因此，若把矩阵看成是h n 一七，d j 码的生成矩阵，而把 h ，e ，棚码的g 看成是它 的检验矩阵，则我们称由g 生成【h ，d 线性码c 与由日生成的线性码 c 1 行，拧一七，d 】为对偶码，相应地，称。与吒。互为对偶空间，由此可如下定义 对偶码。 定义2 6 设线性码c n ，七，d 】，则它的对偶码c 1 垒扛，。，对所有y c ， 使x - y = 0 ，式中x y 表示x 与y 的内积。 若c = c 1 ，则称码c 为自对偶码。 显然，自对偶码必是【2 m ，m ，卅形式的线性码。 2 2 循环码 循环码是一类最重要的线性码，它具有严谨的代数结构，又具有循环的特 性，从而性能易于分析，且编译码电路尤其是编码电路简单且易于实现，现今 已发现的大部分线性码与循环码有密切联系，因此循环码特别引人注目，对它 的研究也比较深入和系统化。 2 2 1基本概念： 定义2 7 一个n 重子空间k 。c k ，若对任一v = ，口l ，一，) 圪恒 有h = g 。，一：) k ，。则称圪。为循环空间或循环码。 2 2 2 码的多项式描述： 显然b 上所有h 重构成一个线性空间，其中每个向量是分量取自砟上的 ”重，若将每个”重和系数取自r 上的多项式相对应： n 重：( 口o ，口l ，- 一，口。一i )q e 多项式：口o + 口1 工+ + c l n _ l x ”1 = f ( x ) 则它们之间建立了一一对应关系，由有限域理论知，所有次数小于n 次的多项 式一定在模拧次多项式f g ) e m 的不同剩余类中，即 ，g ) e 蟊o + 口1 x + + 口。一l x “一1 j ( m o df ( x ) ) 因此，圪中每一个”重都与耳上次数低于九次的一个多项式相对应，并必 5 在模f g ) 的某一剩余类中，而在模f ( x ) 的运算中，模f ( x ) 的剩余类构成一多项 式剩余类环f j x i ( f ( x ) ) ，若在该环中再定义一个数乘，即 c 口b ) = p 口o + c 口l x + + c a ”一l x “- 1 c c 则可以证明模f 0 ) 的剩余类构成个厅维线性空间，称为剩余类线性结合代数。 在【巩k 】循环码中，码字( ，吼，口。) 的多项式表示为 口g j = + n l x + + a n - i x ”，它循环移位一次后所得码字为k 吼，d ) ，相应 x 的多项式表示为a l g ) = a n _ 2 x ”1 + a n _ 3 x ”2 + + x + d ，相当于d ( x ) 乘以x 后用 f g ) = x ”一l 取模，即： 翮b ) = 口月一l x ”4 - - + a t x 2 + a o x 三a n - 2 x “_ 1 + - 十口o x + 盯月一1m o d l x ”一1 j 因为在模x ”一1 情次。下z ”；1 ，所以 期6 ) = a n - 2 x ”_ + 一十口o x + d 。一i 若在k 一2 x ”1 + + x + d ，1 剩余类中，以最低次数m x ”1 + + a o x + d h 多 项式作为该类代表元，则循环码就可用m o d x ”一l 的多项式表示。 命题2 2以多项式x “一1 为模的剩余类线性结合代数中。其一个子空间 k 。是一个循环子空间( 循环码) 的充要条件是。是一个理想。 由此可得：一个循环码是模x ”一1 多项式剩余类线性结合代数中的一个理 想，反之，其中的一个理想必是一个循环码。 定义2 8 生成多项式g ( x ) 是模x ”一l 剩余类代数中，一个理想的次数最低 的非零首一多项式，它是理想或循环码的生成元。 命题2 3 e ( g 为素数或素数幂) 上的l ，k i 循环码中，存在有唯一的 一k 次首一多项式占g ) = x ”。+ g 。一，x “1 + + g ；x + g 。，每一码多项式c 扛) 都是g 扛) 的倍式，且每一个蔓”一1 次的g ( x ) 倍式一定是码多项式。 由此可知：k ，叫线性码是循环码的充要条件是：它是模x “一1 多项式剩余类 线性结合代数中的一个理想，且理想中只有一个次数为h 一生成元g ，所以 这是一个主理想，理想的维数即循环码的信息元个数等于。 下面讨论主理想生成元d 工) 应满足的条件： 命题2 4 c 上k ，七】循环码的生成多项式g g ) 一定是r 一1 的因式： x ”l = g ( x ) h ( x ) 反之，若g g ) 为n k 次多项式且g g 】，- 1 ，则该g b ) 定生成 一个k k l 循环码。 2 2 3 循环码的生成矩阵、校验矩阵 由前知x ”一1 = g ( x 协g ) ，若设g g ) 为”一k 次多项式，则矗( x ) 为t 次多项式， 则以g g ) 为生成多项式所组成加，七】循环码中：g g ) ，糟扛x ，x “g g ) 等女个码多项 式必是线性无关的。可以由这些码多项式所对应的码字构成循环码的生成多项 式g ，即 6 g ：= 鼬g 鼍, , - k - l 兰 g lg o - g o 岛矗n 墨l 岛制一茜岛l 其中g g ) = g o + g l x + + g 。一 x ”。 若设 b ) = h k x + + ，则可验证，循环码的一致检验矩阵为 何= 风 九 由该式可看出，矩阵的行完全由矗b ) 的系数决定。故称矗g ) = 工“一1 9 0 ) 为 该循环码的校验多项式， 另外，若记五g ) = + h k 一。x + 垃( 称j i + g ) 为矗g ) 的互反多项式) 则有： 由校验多项式 g ) 的互反多项式 + g ) 生成的加，n 一】循环码与由生成多项式为 g g ) 生成的k ，| | 】循环码互为对偶码。 7 卜 一h f。_。-_。h 趣 3 1z 。一线性码”。 第三章乙一码 3 1 1 基本概念 设z 。为整数z 模4 的环，n 为一个正整数，刃是z 4 上, 维数组的集合，即 z ：= ( x l i 一，屯) 1x ，z 4 ，i = 1 ，n ，所有的“0 ”n 重( 0 , 0 ，o ) 和所有的“1 ”1 1 重( 1 ，l ，1 ) 分别记作0 ”和1 4 。 z ：的任何一个非空的子集合被称作一个四元码，或z 。一码或环z 4 上的码， n 为码的长度；刃中的一个刀维数组称作字，四元码c 中的一个r 维数组称为c 的一个码字。 对所有的( ，工：，如) 、 。，乃，以) 刃定义分量和： ( x 1 ，x 2 ，- ，x 。) + ( y l ，y 2 ，一y 。) = ( 石l + y l ，x 2 + y 2 ，一，工。+ y 。) 那么z ：就可以看作阶为4 ”的一个加法a b e l i a n 群。 定义3 1z ：的任何一个子群称为一个四元线性码，简称z 。一线性码。 对所有的x = ( 而，x 2 ，x n ) ，y = ( m ，y 2 ，) z ：，定义内积： x y = x y l + x 2 y 2 + + x y 月 如果x y = 0 ，那么称x 与y 是正交的。 设c 是一个长为n 的四元线性码，定义 c 1 = 任鬈l 工y = 0 ，对任意协c 易验证，c 1 是刃的一个子群。因此，c 1 也是一个四元线性码，称作c 的 对偶码。 两个长为以的四元码c t 和c ，称作等价的，是指通过坐标置换以及改变某些 坐标的符号( 如果需要的话) ，c ，与c ：能够相互转化。一些四元码仅由于坐标 置换而不同，称作置换等价的。 对于加法群z ：，由于它是阶为2 2 的n 个循环子群的直和，故z ：被称作( 2 2 ) “ 型。 一个长为n 的四元线性码是刀的一个子群，它的阶是2 的方幂，因此我们 可以说一个四元线性码的型。显然等价的四元线性码有相同的型。四元线性码 的型有下列几种形式( 2 2 ) ”，( 2 2 ) “2 ，2 8 或2 0 。以后我们将( 2 2 ) “型简写作4 ”型 f 2 2 1 m 1 2 “，型简写作4 ”2 ”型。 8 3 1 2 生成矩阵 首先我们做一个约定，如果能够从前后关系辨别清楚，z ，中元素0 ，1 也可 以看作z 。中元素o ，l ，字工= 0 。，z ：，屯) z ? 可看作字x = x ，x ：，) z ：，z ：一 矩阵m ( 即z ：上矩阵) 可看作z 。一矩阵m ( 即乙上矩阵) ，因此，如果m 是 一个z ：一矩阵，那么2 m 就是一个确定的乙一矩阵。 定义3 2 设c 是一个长为押的z 4 一线性码，g 为乙上一个k x ”的矩阵， 如果g 的行能生成c ，且由g 的行所构成的集合的任何一个真子集都不能生成 c ，则称g 为c 的一个生成矩阵。 命题3 1任何含非零码字的z 。一线性码c 都置换等价于以矩阵 r ，。ab 、 g ：f 02 i 。2 fj ( 3 - ” l。j 、7 为生成矩阵的z 。一线性码。其中，”，b 分别表示，i 。，k ：k ：的单位矩阵，a ，f 是 乙矩阵，b 是z 。一矩阵，那么c 就是一个为4 h 2 b 型a b e l i a n 的群，包含2 碣+ 也 个码字，且c 是一个自由z 。一模等价于k ，= 0 。 命题3 2以( 3 1 ) 为生成矩阵的乙一线性码c 的对偶码c 1 的生成矩阵为： f 一b 一f a f ，。一h 一 ：1 l 州 21,：0j 其中, 为c 的码长。则c 1 为一个4 “ 2 。：型的a b e l i a n 群，含有2 2 n - 2 k t 。t 个码字。 3 1 3 g r a y 映射 在环上编码研究中，g r a y 映射是一个非常重要的映射，它把环上码与域上 码建立了一一对应的关系，在译码中也起着非常重要的作用。 为了定义g r a y 映射，我们首先按照下表定义口，声，五为z 到z 2 上的映射： 对于x = g 1 ，x 2 ，工。) z 口( z ) = ( a ( t ) ，a ( x o ，岱( 矗) ) 卢( z ) = ( ( 五) ，卢( 而) ，( 矗) ) ，( x ) = ( ，( ) ，( 屯) ，r ( 矗) ) 9 定义g r a y 映射妒：刃一z ；” x ( ( x ) ，( x ) ) 显然，妒是从刃到z ；上的双射，对任意x z 4 ，妒( x ) 称作x 在妒作用下的二 元像。 3 2z 。一循环码”1 定义3 3长为聆的四元循环码c 是指具有性质： 【c o ，c l ，c ) c = 孛忙，c o ，c 1 ，c n - 2 ) c ( 3 3 ) 的四元线性码c 。简称为z 。一循环码。 我们可以做下面的双射 z ：_ z 4 x l ( x ”一1 ) ( 口o ，a 】，口。一1 ) 争a o + a l x + 口。一】x “1 + ( x ”一1 ) ( 3 4 ) 为了简单，把a o + a l x + 群“x “+ ( x “一1 ) 简写作a o + q x + 口x ”1 。在映射 ( 3 4 ) 的作用，z 。一循环码c 的像仍记作c ，那z , 码字( c 0 ，。i ，一，c 。) c ，在双 射( 3 4 ) 的作用下，变成c ( 工) = c o + c i x + + c x ”1 ，将c ( x ) 也称作为c 的码字。 性质( 3 3 ) 等价于 c o + c i x + + c n - i x ”q c jx ( c o + c i x + + c n _ l x “- ) c 因此，我们有 命题3 3z ：的一个非空集合是一个z 。一循环码等价于它在( 3 4 ) 的作用 下的像是剩余类环z 4 x j ( x ”一1 ) 的一个理想。 因此，长为珂的z 4 一循环码就可以看作是剩余类环z 4 p 】( x ”一1 ) 的理想。所 以以后我们说z 4 一循环码c 的生成多项式就是指c 在环z 。【x 】( z “一1 ) 中对应理 想的生成多项式。 命题3 4当珂为奇数时，环z 4 x l ( x 4 1 ) 为主理想环。 命题3 5 ”设c 为长度为奇数i q 的z 。一循环码，那么c 为4 + 型等价于c 在环z 。【叫o ”一1 ) 中对应的理想的生成多项式p ( x ) 能整除z “一1 且 d e g ( p ( x ) ) = ，z k 。 3 3z 。一负循环码m 定义3 4长为聆钓四元负循环码c 是指具有性质： 1 0 ( c o ，c l ，c ) cj ( 一c ，c o ，c l ，- c m ) c 的四元线性码c 。简称为乙一负循环码。 命题3 6 c 为长为 的z 。一负循环码等价于c 的多项式表示是剩余类环 乙 x 】o “+ 1 ) 的一个理想。 因此，以后说z 。一负循环码c 的生成多项式是指c 在环z 4 【x 】0 ”+ 1 ) 中对应 理想的生成多项式。 命题3 7 设h 为奇数， a ) 环z 。【x o ”+ 1 ) 是主理想环。 b ) 设c 为长为n 的z 。一负循环码，c 的多项式表示是由常值多项式或 g o ) = 口( x ) 6 ( x ) + 2 1 1 所生成的理想，其中，在z 4 嘲中，x “+ 1 = 盯( x ) 6 ( x ) c ( x ) 且口( 工) ， 6 ( x ) ，c ( x ) 是两两互素的多项式。 c ) c 为4 6 。d 。o ”2 8 。榔 型。 由z 4 一负循环码、互一循环码的定义及性质，我们有 定理1 1 ”设c 为长为奇数n 的z 。负循环码，那么c 为4 型等价于c 在 环z 。肛】 ”q - 1 ) 中对应的理想的生成多项式p ( 能整除x ”+ 1 且有 d e g ( p ( x ) ) = n k a 证明作映射 m ：z 4 x 】( j “一1 ) h z 4 【x ( x “+ 1 ) 口( x ) - - 口( 一x ) 当n 为奇数时，m 是环的同构 1 9 ，命题2 3 ，由乙一循环码及z 。一负循 环码分别与环z 。 x 】( x ”一1 ) 、z 。【x ( x ”+ i ) 中理想对应关系知，z 。一负循环码c 的m 的原像c 为z 。一循环码，且其生成多项式为p ( 一x ) 。由命题3 4 知， p ( - x ) l0 ”一1 ) 且d e g ( p ( - x ) ) = 一k ，c 为4 型，从而c 也为4 型，且 p ( x ) f ( x “+ 1 ) ，d e g ( p 0 ) ) = n - k 。即定理得证a 第四章环上线性码深度的研究 e t x i o n 在文献 1 4 1 中首先定义了线性码的深度及深度谱，给出了计算2 元 线性码的码字深度的算法，证明了g 元k k 】线性码的深度谱恰好由k 个非零值 组成；m i t c h e l l 在 15 中研究了2 元线性循环码深度；l u o 等在 1 6 中给出了计 算q 元线性码的码字深度的算法，并研究了一些计算问题。这些研究结果可广 泛应用于域上的纠错码理论研究，如文献 2 1 】给出了利用码的深度分布求码的 周期分布方法，并确定了码长为2 的幂次的扩展码和扩展循环码的周期分布； 又如文献 1 4 利用深度分布给出了构造新码的方法和码的一种新的等价分类方 法，因此，研究线性码、循环码的深度分布是有价值的，但上述研究都是域上 码的深度研究，下面我们研究环上的线性码的深度问题。 4 1z 。一线性码的深度分布 4 1 1 z 。一线性码的深度谱 定义4 1 对v ：= ( z 。，x ：，) 虿 定义微分算子d ： d x = ( x 2 一x l ，x 3 一z 2 ，x h x 。一1 ) 称使d 。z = 【0 ”。 成立的最小非负整数为x 的深度，记为d e p t h ( x ) ；若没有这样的i 存在，则令工的深度为 。 显然，由定义，我们有0 d e p t h ( x ) s 行，且对v x ，y 刃，v k z 4 有， d 0 + y ) = d ( x ) + d ( _ y ) ，d ( k x ) = k d ( x ) ，故微分算子d 是一个线性算子。值得注意 的是，在域上，舡( 七0 ) 与z 有相同的深度，而在环z 。上，此结论显然不成立， 如d e p t h 2 “ 1 ，但d e p t h ( 2 2 ”】) = d e p t h 0 4 】= 0 ；又如d e p t h ( 0 2 0 0 2 ) = 5 ，但 d e p t h ( 2 ( 0 2 0 0 2 ) ) = d e p t h 0 5 _ 0 。 定义4 2 设c 是环z 上长为n 的码，用d 表示c 中具有深度为i 的码字 的个数，则称集合 d o ，d i ，- ，d 。) 为码c 的深度分布，称集合 j ld f 0 , 1 i s n 为 码c 的深度谱。 文献【1 4 】证明了域c 上i n ，明线性码c 的深度谱恰好有k 个非零值，但此结 论在环z 。上不一定成立。 定理4 1 设c 是4 k 2 t 型乙线性码，则c 的深度谱中至少有k l + 如个非零 值。 证明设c 的生成矩阵为 一1 2 。 ha b i j2 2 a2 b l 为生成矩阵的线性码，则g 是c 的子码。 f 彳马i 10 气fl 为生成矩阵的z ：线性码，其中马中各元素是b 中相应元素模2 的值，则 v 口c 2 当且仅当2 a c i 又由于c 2 是z 2 线性码，c l 是五线性码，且对v 口z ；，在z ，中d 口：0 当 且仅当在z 。中d ( 2 a ) = 0 ，故d e p t h ( 2 a ) = d e p t h ( a ) ，因此c 1 与c 2 有相同的深度分 布。由文献 】4 】中定理】知，g 的深度谱恰好含有k ，+ 也个非零值，所以c 。的 深度谱恰好含有k ，+ 后：个非零值，又c i 是c 的子码，故c 的深度谱中至少含有 七l + k ：个非零值。证毕。 雕 l o o 2 2 j 为生成矩阵的k l e m m 码为是4 1 2 2 型线性码，容易计算得k l e m m 码k 。的深度谱 恰好含有3 个非零值l ，2 ，3 ，其中k ，+ l = 3 ；但以 1 0 1 1 0 2 0 j 为生成矩阵4 2 型z ；线性码的深度谱含有3 个非零值1 ，2 ，3 ，但3 t + 七，：2 ， 即域上线性码的深度理论对环z 。上线性码不一定成立。 推论4 。1 对于2 型z 。线性码，其深度分布恰好含有个非零值。 推论4 2 对于4 2 岛型，长为以的五一线性码其对偶码的深度分布至少含 1 3 ， 4 1 2 z 。线。陛循环码的深度谱 文献 15 给出了域上线性循环码的深度谱的一些结果，本小节我们讨论z 。 线性循环码的深度理论。由于环上编码问题的复杂性，本小节仅讨论4 t 型或2 也 型线性循环码。 引理4 1 设c 是一个长为疗的z 4 线性循环码， 2 “】诺c ，若c 中所有非零 码字中最长的零游程的长为f ，则c 的所有非零码字的深度最小值大于n 一，一1 。 证明 设x = ( x i ，x ：，工。) 是线性循环码c 中一个非零码字，记 t x = ( x 2 ，x n , x 1 ) ，贝0t x c 。由于【2 ” g c ，则 1 “】c ，【3 ”】g c 。贝0 y = t x x = x 2 一工f ，x 3 一t ，- 一，x n x ，一i ，而一x n 】c ，且 y 0 。 贝u d x = ( 工2 一，玛一x 2 ，x 。一一。) 是c 中非零码字y 的连续的h 一1 个分量。同 理，d 2 x = d ( d x ) 是c 中非零码字砂一y 的连续的 一2 个分量，令5 = ”一f 一1 ，则 d x 是c 中某非零码字的连续的n s 个分量，由于n s = “l ，又c 中所有非 零码字中最长的零游程的长为，则d 5 x 0 ，即d e p t h x j = h 一，一l ，从而得证引 理。 定理4 2设g ( x ) 是长为n 的4 2 型乙线性循环码c 的生成多项式。且 g ( 工) 不整除2 ( x ”1 + + x + 1 ) ，则c 的深度谱为 月，片一1 ，门一k + 1 ) 。 证明 由于c 是4 型z 。线性循环码，则c 的生成矩阵具有形式( ，。彳) 。对 v 口c ，若码字口中含有长为k 的零游程，设口= 0 l c 。0 c m + l 已) ，由于c 是 循环码，故= ( o c m + l c n c i q ) c 。若( a l a 女) ( ，女a ) = ，则( a l a t ) = 0 ，从 而c m + 【一c 。= c 【一一f = 0 ，即a = 0 ，即码c 中非零码字的最长零游程为 k l 。又g o ) 不整除2 ( x ”1 + + x + 1 ) ，则【2 ” g c ，由引理4 1 知，码c 的所有非 零码字的深度的最小值大于”一( k 一1 ) 一l = 一k 。由定理4 ，l 知，码c 的深度谱 中至少有k 个非零值，故码c 的深度谱为伽，月一1 ，n k + 1 ) ，证毕。 引理4 ，2 设c = ( ，。1 ，一，c ) 是z | 线性循环码c 中的码字，其对应多项式 为c ( x ) = c o x ”1 + c l x ”2 + ? + 矗一i ； 则d 。c 的”一i 个分量依序等于 c ( 工) 一1 ) ( m o d x ”一1 ) 的x n - ix n - 2 - ，一系数。 证明利用d 的定义，对i 用数学归纳法即可证明。 在z 。【卅中，由于对任何非负整数m ，恒有 2 ( x 2 ”+ 1 ) = 2 ( x 一1 ) 2 4 成立，故o 一1 ) 2 11 2 ( x 2 “1 一1 ) ，则对任何自然数k 2 ”+ 1 。恒有 ( z 1 ) f2 ( x 2 ”1 1 ) 。 定理4 3 设n = 2 ”1 ，k 2 ”+ l ，则以g ( x ) = 等苎_ 导为生成多项式的线性 1 ，“1 、 一 q l j 循环码c 的深度谱为 l ，2 ，k 。 证明对v c c ，则对应的多项式 一1 4 c ( x ) = ，( x ) g ( x ) = f ( x ) 由弓l 理4 2 矢口，d 。c 的行一k x ”1 ，工”2 ，x 的系数。 由于 等( m o d x - 1 ) 个分量依序等于o 一1 ) c ( x ) ( m o d x ”一1 ) 的 - 1 加( 川产m ) 等= l 1 ) z m o d x - 1 2 f ( x ) ( x0 ( m o d x )( x ) c ( x ) = ( x 一1 ) 2 ，( x ) 弓! ：三= ”一1 ) z) 即d