（基础数学专业论文）有限链环上线性码的rosenbloomtsfasman（rt）度量.pdf

北京交通大学硕士学位论文 中文摘要 中文摘要 摘要 j 幻s e 曲f d d m 一2 1 s n s m 彻 简称胛 度量是一种不同于日n m m 讯g 度量的 度量 可以应用在均匀分布上 有利于更好的了解码的结构 自1 9 9 7 年m y u r o s 即一 b 1 0 0 m 和m a7 i k f 抽m a n 定义了域上码的j 玎度量以来 不少学者对船度量进 行了深入的研究并且得到了一些有意义的结果 使得域上线性码j 日度量的研究 逐渐完备 近几年来很多从事编码理论研究的学者将研究兴趣从域上转移到环上 来 m e h m e to z 和h 丘ms i 印首先研究了b m 矿 上线性码关于j 四度量的 一些性质 本文将m e h m e to z e n 和i r f a ns i 印的结果推广到有限链环上 并重点 研究了四元环上线性码的j 汀度量 本论文共分五章 第一章 先简单回顾了代数编码理论的发展和国外学者对月r 度量的研究情 况以及本文的主要工作 第二章 介绍了文中所需的基本概念 重点介绍了j 汀度量 第三章 研究了有限链环上线性码和循环码关于j 玎度量的性质 第四章 对于特殊的有限链环五和尼 t 易 我们讨论了五和易 t 昂上的线 性码关于j 日度量的性质 第五章 总结本文的主要结果 并提出几个值得进一步研究的问题 关键词 有限链环 线性码 循环码 负循环码 对偶码 j 口度量 最大距离秩码 分类号 0 1 5 7 4 北京交通大学硕士学位论文 a b s t r c t a b s t r a c t t h er e n b l o o 加 t d 缸m 缸 s h o r t l yr t m e t r i ci 8an o nk 如 曲唱 m e t r i cw h j c hc a nb e1 l s e di nu n i f c 恤d i 8 t r i b u t i o a n db ep r o p i t i o l 玛t 0k n o wt h e s t r u c t t 肝0 f t h ec o d 鹤 m y u f h 即b l o 锄衄dm at s 缸m 衄d e 矗n e dt h er rm 酏r i c o v 盱6 e l d si n1 9 7 7 s o i n es c h o l 哪s t u d i e dt h e 硪1m 酏r i co v 盯6 e l 凼a n do b t a i n e da l o to fi m d o r t a n o er e s u l t s t h er e s e a r 出o fl i n e a rc o d ea b o 虹tr rm e t r i co r e r 五e l d s h 够a l r e a d yb e e no o m p l e t e d i nt h er e 期吐y e a r st h e8 c h o l 脚m a j o 舱di n d 髑 出mt h ei n t 蝴t i n g 丘o mf i d d st or i n 庐 m e h l e to z e n 强di 咖1s i a ps t u d i e d t h ep r o p e r t y l i n e a rc o d a b o u tr tm e t f i co v e r 日m 矿 i nt h i 8p 印e rw e 謇m e r a i i 髓dt h e 瑚l l l to f 日m 矿 t o 丑i i i t ec h 8 i n 咖擎 e s p e c i a n yt oq u a t 哪a 巧 r i n 擎 t h i 8d i s 吕e r t a t i o ni 8d i r i d e di n t o 丘v ep a r t 8 船f b l l d w 8 i nd l 印t e ro 北 w eb r i e 丑yr 鲥e wt h ed e v d o p m e n to fa l g e b r a i cc o d i n gt h e o r y a n dm 嘲1 t i m a i nr 郫t l l t 8o ft h i 8p a p 盱 i nc h a l t e r 忉吣 w ei n t r o d u c et h e0 0 n c 印t 8n e e d e di np a p e r e s p e c i a u yi n t r 伊 d u c et h et h er o s e 曲l o o n i t s f a s m a n l e t r i c t h ec h a p t e rt h r e ei 8t h e 丘瑙tm a i np a r t0 ft h ed i 鹪茁t a t i o n w es t u d i e dt h e p r o p 呐ro f l i n e 缸锄d 坷c h cc o d e sa b o u tr rm 嘶c 删e r6 n i t ec l l a i nr i n 伊 t h ec h a p t e rf o u ri 8t h e 舶o o n dm a i np a r to ft h ed i 韶e r t 8 t i w es t u d yt h e p r o p 盱锣o f l i n e 盯c o d 鹤a b o u t r t m e t r i c0 v e r 忍a n d 屁 钍尼 hc h a p t e r 矗v e w es i 加1 m a r i 踯t h em a i l lf i n d i n 窜i nt h i sp 叩 e r 瓶db r i n g f o r w 舭ds e v e r a li s s u e sw o r t b yo ff i l n h e rs t u d y k e y w o r d s 觚t ec h a i nr i n g l i n e 缸c o d e 呵d i cc o d e n e g a 码 c h cc o d e d u 8 lc o d e r o 舶 l b l o o m t s f h 锄a nm e t r i c m a d 皿 d j s t a n c er a n kc o d e c l a s s n o 0 1 5 7 4 学位论文版权使用授权书 本学位论文作者完全了解北京交通大学有关保留 使用学位论文的规定 特 授权北京交通大学可以将学位论文的全部或部分内容编入有关数据库进行检索 并采用影印 缩印或扫描等复制手段保存 汇编以供查阅和借阅 同意学校向国 家有关部门或机构送交论文的复印件和磁盘 保密的学位论文在解密后适用本授权说明 学位论文作者签名 走团圆 签字日期 删6 年i z 月f 7 日 导师签名 签字日期 少即停 胡f f 日 移纠 致谢 首先非常感谢导师江中豪教授 本论文的各项工作都是在江老师的悉心指导 和亲切关怀下顺利完成的 两年多来 无论是在基础课学习过程中 还是在论文的 选题 研究以及成文的过程中 江老师自始至终都给了我大量的支持和帮助 江 老师严格要求我的学习 并关心帮助学生在生活中遇到的困难 在此特向江老师 表示深深的敬意和感激 江老师严谨治学和指导学生的态度给我做了很好的榜样 这些对我今后的学习工作和生活都是用之不尽的财富 在此再向我的导师表示感 谢 在此也感谢在研究生期间给我以传道授业解惑和在生活学习上关心帮助我的 所有老师 诚谢各位专家和学者在百忙中审阅我的论文 诚恳接受您的宝贵意见 和建议 并期待您的批评和指导 最后 感谢父母在学习和生活上给予我的关怀和支持 李囡囡 2 0 0 6 年1 1 月 于北京交通大学理学院 北京交通大学硕士学位论文1 引言 1 1 编码理论的发展 1 引言 信息作为二十一世纪人类社会最重要的资源之一 已经成为推动社会进步的 强大生产力 信息的广泛传播和大量信息数据的处理使得作为信息论基础之一的 编码理论越来越受到科研工作者的关注和重视 1 9 4 8 年 s h 缸n o n 的 通信的数学理论 开创了纠错码理论的研究方向 揭示 了在通信系统中采用适当的编码后能够实现高效率和高可靠的传输信息 并得到 了信源编码定理和信道编码定理 奠定了纠错码理论的基石 1 9 5 0 年汉明码出现 后 人们把代数方法引入到纠错码的研究 形成了代数编码理论 代数编码理论 研究用适当的字母按特定要求 检错 纠错 保密等 去恰当地表示与传送信息 由 于纠错的需要 编码理论需要比较好的结构来支撑 尤其是代数中的向量空间结 构 有限域结构 群代数结构 环结构等等 以及组合论中的组合设计等许多方面 都被应用于编码中 使得编码理论发展成为数学学科中的一个非常活跃的 理论 体系较完整的分支 2 0 世纪5 0 年代至6 0 年代初 这是纠错码从无到有 得到迅速发展的年代 主要 研究各种有效的编码方法和译码方法 奠定了线性分组码的理论基础 1 9 5 2 年霍夫 曼首先构造了一种编码方法 即著名的霍夫曼编码 并证明了它是最佳码 1 9 5 9 年 和1 9 6 0 年 由b 0 s e c h a u d l l 诚和h o c q u 衄g h e m 提出纠正多个随机错误的循环码 即著名的b c h 码的构造方法 b c h 码是迄今为止所发现的一类最好的线性纠错码 类 在编码理论中起着重要作用 给出了纠错码的基本码限 2 0 世纪6 0 年代后期开始 人们把兴趣转移到与实际有关的编码问题上 1 9 6 8 年 埃利斯发展了香农一一费诺码 提出了算术编码的初步思想 1 9 8 2 年里斯桑内和 兰登一起将算术编码系统化 并省去了乘法算法 更为简化 便于实现 而著名 的i 广z 编码是齐弗和兰佩尔于1 9 7 7 年提出的 目前o z 编码已广泛用于计算机数据 压缩中 如在u n i x 中的压缩算法用的就是l z 编码算法 这一时期不仅提出了各种 各样的编码 译码方法 而且还研究了码的重量分布 译码错误概率等纠错码实 用化问题 所有这些问题的研究为纠错码理论的应用打下了坚实基础 在此期间 以有限域理论为基础的线性分组码理论已趋成熟 2 0 世纪8 0 年代至今 这是纠错码理论取得突破性发展时期 在此期间 开创 了代数几何码和有限环上的纠错码理论的新研究方向 在1 9 8 9 年 n e c h w v 研究 发现k e r d o c k 码通过某个映射可等同于环历上的循环码 这开创了纠错码的一个 新的研究方向一一环历上的纠错码的理论研究 掀起了有限环五上的纠错码理论 研究的热浪 从1 9 9 4 年至今 一系列有影响的论文 l 一4 1 发表 在1 9 9 7 年 万哲先出 版了世界第一本环五上的纠错码理论的专著一一 q t e r n 8 r g 0 d e s 从此以 北京交通大学硕士学位论文 1 引言 后 人们在深人研究环z 4 上的纠错码理论的同时 又开始研究一般的有限环磊和 其它有限环 如环尼 u 易 上的纠错码理论 现在 有限环上的纠错码理论和代数 几何码的研究方兴未艾 每年全世界都有成百上千篇学术论文发表 在进行理论研究的同时 编码理论也在多方面发挥了重要的实际作用 如 纠 错码与调制技术帽结合所产生的t c m 技术 已作为国际通信中标准技术而推广 使用 纠错码与密码结合 可以构造出一类既能加密签名 又具有纠错功能的密码 系统 纠错码与信源编码相结合的结果 使得通信系统更为有效与可靠 不仅如此 编码理论中的许多译码思想和方法 与神经元网络中的能量函数有密切关系 可 以用来解决神经元网络中的一些问题 代数编码理论在与试验设计 假设校验理 论的结合中也发挥了重要作用 在信息编码理论中有许多码的构造理论与方法 这些码在一定意义下具有正交性 因此这些码可以直接设计与构造实验设计表 另外 利用信息编码定理可以证明在假设检验中两类误差的指数下降性 并给出 了两类误差的下降速度 因此 可以预料 随着科学的进步和实际需要 编码理论 必将进一步发展 它的应用范围必将进一步扩大 1 2 本文的主要内容 由于编码和译码的需要 编码技术得到了进一步的发展 也使得编码成为实 用价值十分广泛的一门应用学科 随着计算机科学和通信技术的迅猛发展 它在 数字通信和信息领域中占有越来越重要的地位 其数学理论和技术发展也十分迅 猛深入 特别是利用代数工具对码的结构展开的研究是编码理论分支中的一个十 分热门的方向 因而对它的研究具有重要的理论和实际意义 本文主要研究了环上 的线性码的性质 在编码理论中有一个重要的概念就是汉明 h a 姗i n g 距离 h 卸m 血g 距离 与码的纠错能力和检错能力有密切关系 人们往往通过研究码空间的h a m m i n g 距离来研究码空间的纠错和检错能力 j 幻s e n 耐 m t s n s m n 几 简称船1 度量 是一种不同于日彻计n l n 9 度量的度量 可以应用在均匀分布上 文献 5 j 有利 于了解码的结构 1 9 9 7 年m y u r d s e n b l 0 0 m 和m at s f 够m 锄在文献 6 中定义了域上码的盯 度量 并给出了关于册度量的最小距离限 不少学者对兄t 度量进行了深入的 研究 文献 7 l 8 9 并且给出了一些有意义的结果 对域上线性码砸帔量的研究 逐渐完备 近几年来很多从事编码理论研究的学者将研究兴趣从域上转移到环上 来 m e h m e t0 z e n 和i r f 蛆s i 印在文献 1 0 1 中首先研究了日m 矿 上线性码关 于舰1 度量的一些性质 本文将文献 1 0 1 中的结果推广到有限链环上 在简单介绍了文中涉及到的基本概念后 本文主要进行了以下几个方面的研 究 2 北京交通大学硕士学位论文l 引言 1 给出了有限链环上线性码c 关于j 玎度量的标准生成矩阵 通过标准生成 矩阵来研究有限链环上线性码e 的盯度量 给出了有限链环上线性码关于j 玎度 量的最小距离限 引出了最大距离秩码的定义 并对线性码中船1 度量等于j d g j n 码字进行了计数 接着通过循环码和负循环码的生成多项式来研究这类特 殊的线性码的r r 度量 并给出了码长和有限链环的剩余域的特征互素的循环码和 负循环码以及他们的对偶码关于j 玎度量的性质 2 讨论了环五和易 t 兄上线性码的解度量 得到环五和毋 u r 上 线性码的船度量和它的剩余码 挠码的册度量之间的关系 并给出z 4 和易 u 尼上2 c 码长的循环码和负循环码关于册度量的性质 3 北京交通大学硕士学位论文 2 基本概念 2 基本概念 在本章中 我们介绍一下和本文相关的一些基本概念与基础知识 以便帮助 读者更好地理解后面章节的内容 如需获得更详细的内容 可查阅相关的参考资 料 2 1 线性码 根据校验元与信息元之间的关系纠错码可分为线性码与非线性码 线性码是 纠错码中最重要的一类码 它是讨论各类码的基础 至于非线性码 那只是一些 向量的集合 由于缺乏有力的工具 对非线性码的研究尚不成熟 本文主要研究 环上的线性码 环r 上的竹码长的码c 是舻的一个非空子集 若码c 是j p 的一个子模 则称e 为冗上的线性码 对线性码e 的任意码字c c 1 岛一1 定义它 的多项式 匈 c l z 岛一1 矿一l 在线性码里有两类特殊的线性码一循环码和负循环码 定义2 1 称线性码e 为循环码 如果对任意c 国 c 1 一1 e 有 1 国 g 2 c 定义2 2 称线性码c 为负循环码 如果对任意c c 1 龟一1 g 有 一c l 一1 匈 2 c 若c 为循环码 或负循环码 则通过e 中码字的多项式可将c 视为多项式环 乏i 或乏善 的一个理想 其中仃为码长 2 2 有限链环 有限域上的编码理论不仅理论上比较完备 而且这些理论已经广泛应用于通 信领域 近几十年来很多从事编码理论研究的学者将研究兴趣从有限域上的编码 理论转移到环上来 首先给出有限链环的概念 定义2 3 称有限交换环尉1 o 为有限链环 如果它的理想满足线性 包含关系 即若r 为有限链环 五 厶 厶为兄的理想 则五 c 如c c k 其中i l 为1 2 n 的某个排列 显然环z 为有限链环 是z 的理 想且 c c c c 称环r 的理想j 为主理想 如果j n 若环冗上每个理想都是 主理想 则称r 为主理想环 称环r 为局部环 如果它存在唯一的极大理想 4 北京交通大学硕士学位论文2 基本概念 引理2 1 对于有限交换环r 来说以下条件等价 1 r 是局部环且r 的极大理想m 是一个主理想 2 冗是局部的主理想环 3 兄是一个链环 证明 1 净 2 令 为刷挎理想 若 r 则j 可由单位元1 生成 若js r 则j m 由 1 知 m 可由兄中的某一元素n 生成 即m 因此存在七 使 得 所以昆黾局部的主理想环 2 辛 3 令r 是一个局部的主理想环 m 是引 臼极大理想 如是同拘 真理想 则 m 厶 m 所以存在z m 使得 五 其中j m 小 于口的幂零指数 故五 厶或屯 因此r 为一个链环 3 号 1 令r 是一个有限可交换的链环 显然厨孚在唯一的极大理想 即r 是 一个局部环 下证冗的极大理想m 是主理想 若不然 假设b c 是r 的两个生成元 且眶c 冗 面冗 则 垡 且 垡 与昆黾一个链环矛盾 所以m 是一 个主理想 因此条件 1 成立 口 由引理2 1 我们知道有限链环是局部环 冗为有限链环兮r 为有限局部主 理想环 以下本文中除特殊说瞻总令r 为有限链环 设m 为有限链环冗的极大理想 r o r 1 0 耳为r 的剩 余域 即k 兄 y 冗 则存在素数p 和整数8 t s t 使得i 刷 矿 i k i 矿 对 0 1 口 有i i i i 特别i 矧 i 耳i 即s 优 r 冗 o l 仃 为r 的全部理想 极大理想 y 月中的元素是冗中的零因子 吼1 兄中的元素是可逆元 引理2 2 1 1 l 对v r 矾 o 存在唯一的整数 使r 中 其中 可逆且 在m o dr 一下是唯一的 由引理2 2 我们给出有限链环兄中元素的类型的定义 并将它推广到舻上来 定义2 4 令o 冗 如果d 一6 且 y 不整除6 则称口在r 中的 类型为z 记为t f 口 z 同样如果对a r 有a 一b b r 且7 不整除b 则称a 在舻中的类型为z 记为t f 妒 a f 显然冗中的可逆元在r 中的类型为0 t 卯e r l i 1 2 口一1 若t f 卵 0 1 f 1 t 卵 f 2 则t 卯e 8 1 啦 m 伽 z 1 如 推广到舻上 有v c l 晚 舻 t 们 e c 1 l l t l f 尹e c 2 f 2 则t 鲫 e c 1 c 2 m l n f 1 如 2 3 r d s e n m d o m 一2 0 n 舯r l n n 压刚量 在编码理论中有一个重要的概念就是汉明 h 明珊i i i l g 距离 下面引入不同 5 北京交通大学硕士学位论文 2 基本概念 于月 n 7 l i 硼度量的胍e 他6 f d d m t o 如鲫m n 简称船 度量 定义2 5 令z p 1 现 酽 嘶 味誊 称 啊 功为z 的船重量或p 重量 定义2 6 2 缸1 与 帆 舻的船度量 户距 离 是 p z 毫 j 扛一们 其中茁一熏 z l 一玑 一舶 c 中所有非零码字之间的最小冗r 度量 或p 距离 记为d c 也称为关于 j 玎度量的最小距离 g 中所有非零码字的最小r t 重量 或p 重量 记为 咐 c 定理2 1 若g 为线性码 则商 回 w 回 证明 任取z 掣 c 则当z 与 取遍c 中的所有码字时芦一可也取遍了 e 中所有码字 所以我们有 d c m 讯4 p z f 厕几m 蛳0 一掣 删n 墨 z g 6 口 北京交通大学硕士学位论文3 有限链环上的线性码的船度量 3 有限链环上的线性码的j 口度量 j h e n m d d m n n 舢n 简称船 度量是 种不同于日册l m i 咖度量的度 量 本章主要研究有限链环上的线性码的胛度量 主要内容有 第一节给出了有限链环上的线性码关于盯度量的标准生成矩阵 并通过线 性码关于j 汀度量的标准生成矩阵来研究线性码的殿1 度量 第二节主要通过有限链环上循环码和负循环码的生成多项式来研究码关于 j 玎度量的性质 3 1 有限链环上的线性码的j 玎度量 本节主要讨论有限链环r 上的线性码的刀度量 线性码关于船度量的 标准生成矩阵在研究线性码的磁1 度量起着相当重要的作用 首先给出线性码关 于j 玎度量的标准生成矩阵 定义3 1 设g 是re 码长为他的线性码 r 上一个矩阵g 称为g 的生成矩阵 如果g 的行向量生成c 且g 的行向量的真子集都不能生成c 由文献 1 2 知道 r 上的线性码c 的生成矩阵等价于 可以交换列 如下形式 山 f o 7 a l oo i ii oo 如a 7 a 1 2 一y a l 3 y 2 铲如 oo a o i 一1 一r 1 口一1 y 1 口 铲a 2 i 一1f a 2 l r 1 k 一 r 1 也m 且 一1 由e 唯一确定 其中k o i 可一1 为觑 单位矩阵 定理3 1 设g 是r 上n 码长的线性码 则c 的生成矩阵等价于 g 巨至掣引 其中l 7 k m 一1 m 2 优1 n o 1s 七 证明 曰上线性码e 的生成矩阵的最后一列可以生成月的一个理想 由于 r 为主理想环 则存在m 使得生成矩阵的最后一列可由m 生成且g l o 通过行的初等变换可使g l 下面的项全为零 7 北京交通大学硕士学位论文3 有限链环上的线性码的j 玎度量 对于第 l 一1 列 它的后七一1 项生成冗的一个理想 该理想要么是零理想 要么是非零理想 当生成的理想是零理想时 则考虑第n 一2 列 当生成的理想是 非零理想时 则存在9 o 使得出 为这后一1 项的生成元 通过行的初等 变换可使出 下面的项全为零 依次类推 知结论成立 口 定义3 2称形如 1 的冗上线性码e 的生成矩阵为关于j 盯度量的标 准生成矩阵 称g 的类型为 一1 如果c 的标准生成矩阵中类型为i 的 行向量恰有臃个 i o t 一1 线性码关于船1 度量的标准生成矩阵 在本论文中发挥着重要的作用 下面 运用线性码关于j 玎度量的标准生成矩阵 求出一类特殊的线性码的盯度量 定理3 2 口为月上线性码 关于咫度量的杯准生成矩阵为g 如 1 若对于任意 1 i 七 鲕h 类型小于或等于同行中其他分量的类型 则 d a 竹k 锯 g 北京交通大学硕士学位论文3 有限链环上的线性码的皿 度量 对于一般的线性码我们有下面的引理 引理3 1 设c 是冗上 l 码长的线性码 g 的类型为 一1 则g 的最小p 距离 即d c 满足 d g n 一七 1 其中七为标准生成矩阵的行向量的个数 即膏 一l 证明 由定理3 1 知道 冗上的线性码c 的生成矩阵等价于如下形式 g 巨至引 001 让t 上 0 t o0 牡1 g io uot io1 o 让1o o l oo o t 牡oo 0o 为f 2 舻 上的线性码e 关于船1 度量的标准生成矩阵 满足每行的最后一非 零元的类型都小于或等于这一行向量的类型 但是d g 8 1 2 3 1 9 北京交通大学硕士学位论文3 有限链环上的线性码的j 盯度量 g i 为毋m 舻 上的线性码g 关于j 玎度量的标准生成矩阵 容易得到 d g 3 5 3 1 任 与e 为m d 兄码矛盾 u r 一y 一 咿 h 帆 n k m 知 n 一七 1 口 仕 吣 北京交通大学硕士学位论文 3 有限链环上的线性码的j 日度量 对任意 1 七 g 帆类型小于或等于同行中其他分量的类型 蚍表示生成矩 阵g 第 行的磁1 重量 或p 重量 则 山 1 a 仉一1 死 1 巩 1 奄 其中丌 矿 蝴 a i i l g 证明 山 1 显然成立 设 w n 1 n t 卯e n 1 f l 由m 类型小于或等于同彳亍中其他分量的类 型知 r n l o 争r 吼m l 0 争 r 口1 n r 冗 由i 一 捌 i j p 一 i 酽一 知 m 1 l 的个数为矿一t 以一1 又 妒 口1 1 d 1 n 1 2 口2 n 1 七d 七 n 营 啊 n 1 1 口1 n 故 j l 的个数为 丌1 1 霄2 巩 同理设 0 2 l t t 卯e 啦 f 2 可得 i r 啦 l t 的个数为 矿一1 4 刀叠一1 又 w 口2 2 0 硷 o 船 唔 口驰d 女 n t 甘妒 啦2 n 2 n t 故 j n t 的个数为 他一1 丌3 他 依次类推得钆 仇一1 坼l 巩 1 i 七 口 由定理3 4 我们可以得到如下推论 推论1设g 为r 上 l 码长的m d r 码 g 为c 的关于j 玎度量的标准生 成矩阵且对任意l 1 i 后 璺帆类型小于或等于同行中其他分量的类型 则 山 1 a 一 l 仉一1 死 l 7 礓 1 t 后 g 为历上的m d 月码 则由推论1 知 山 1 山 1 2 a 2 a 1 定义3 4 称r 上的线性码c 为自由码 如果它是r 上的自由模 推论2设g 为冗上礼码长自由的m d 兄码 g 为c 的关于解度量的 标准生成矩阵且对于任意l 1 i 蜘 类型小于或等于同行中其他分量的类 a o l a 一计l 矿一1 矿 知一 1 i 推论3 设g 为冠上佗码长的m d r 码 b 0 岛 0 0 j g 为e 的关 于j 口度量的标准生成矩阵且对于任意 1 岛 舰 类型小于或等于同行中 1 l 北京交通大学硕士学位论文 3 有限睦环上的线性码的明 度量 其他分量的类型 则 山 1 a 一 l 矿 一1 口扣 b 一日 1 i 岛 对于某一个 1 l 七 当叠帆类型大于同行中某一分量时 无一般方法求 有限链环兄上如 d c j 哟 需要具体问题具体分析 3 2 有限链环上的循环码的册1 度量 循环码是一类重要的线性码 它具有严谨的代数结构 其性能易于分析 特 别是目前已发现的大部分线性码与循环码的密切关系 它们中的大部分码都可以 归结于循环码 因此循环码特别引人注目 对它的研究也比较深入和系统 本节 主要通过循环码和负循环码的生成多项式讨论它们的船度量 给出r 上码长n 与k 的特征互素的循环码和负循环码及其对偶码关于j 口度量的性质 下面将研究当d 为乏 或乏 的主理想时 c 的j 玎度 量 定理3 5e 为r 上的陋 r l 循环码 负循环码 其中咖 p n r 且9 z 是首一的 则e 为m d r 码 证明 v c 霉 g c z o 则存在6 霉 o 使得c 0 6 z 9 z 由于 9 z 是首一的 因此 d e 9 9 z d e 9 c z 又因为9 0 c 则d g d e 口0 z 1 n r 1 所以g 为m d 冗码 口 对于任意 z 1 掣 可l 彤 定义它们的内积为 z 可 z l 掣1 称两个码字z 是正交的 如果z 0 r 上的线性码e 的对偶码 d 上 z i 岔 o 坳 c 由定理3 5 我们可以得到当c 为乏善 或乏害4 基的主理想时 g 的对偶码c 上关于船度量的性质 推论4g 为r 上的砷 r 循环码 负循环码 其中咖 9 z n r 且9 z 是首一的 则c 上为m d r 码 证明 先证g 为r 上的循环码的情况 负循环码的情况同理可 证 由9 z l 扩一1 知 存在 i l z r m 使得g z z 矿一1 且 是首一的 下 证g 上 北京交通大学硕士学位论文3 有限链环上的线性码的船 度量 显然 伊 反之任取 z c l l o 则在蒜中 z 9 z o 即妒一1 i z 口 z 故 z i z 所以c l l 因此g 上 由定 理3 5 知 d o 为m d r 码 口 若g 为r 上码长为t t 的循环码 负循环码 则c 为r 旧 r m 的理想 因此得到矿一1 与护 1 的因子对于研究循环码和 负循环码的结构很有帮助 当 l 与k 的特征不互素时 妒一l 与矿 1 的分解不唯一 如一一1 在五上可分解为 一一1 0 1 0 1 护 1 z 一1 一1 矿 2 霉一1 0 1 p 1 护 2 茁一1 因此对这种情况下有限链环上码的结构的研究还存在一定的困难 当竹与耳的特征互素时 矿一1 与矿 1 分解唯一 文献 1 3 给出了有限 链环上码长n 与k 的特征互素时 r 上循环码与负循环码的结构 下面研究码长 n 与k 的特征互素的循环码 负循环码 关于脚1 度量的一个重要性质 任取 r m l 护一1 记 竿 定理3 6 1 3 le 为r 上码长为n 几与k 的特征互素 的循环码 m 是冗的极大理想 r o 7 1 o 则存在多项式昂 乃 r 冗纠 使得 c 岛见 r 矿一1 特别存在多项式 0 厶 1 使得c 其中 舶 蚓矿吐 2 儡 蓦车2 利用文献 1 3 1 中的结果 可以得到r 上码长n 与k 的特征互素的循环码关 于j 日度量的一重要性质 定理3 7r 上码长n 与 的特征互素的循环码为m d r 码 证明 令g 是r 上的循环码 其中 厶一1 i 一 i i o i 矿一1 v c gc z 0 则存在f 功 使得c 功 f 一1 力 因此 d 叼 厶一 z d e 9 c z 北京交通大学硕士学位论文3 有限链环上的线性码的m 度量 又因为矿 1 二一1 句 c 则c f r c 向 二一l 功 1 又c o o o 故g 的标准生成矩阵中 行向量的类型为 的向量必出现在 a o t 一1 中 它共有n d e g 戽 1 个 即 n d e 9 氟 所以 如9 只 1 咖 n b 蜀 蚓等 7 l d 叼 丘一1 因此n 一七十1 咖 一1 1 如 回 故c 是肘d 冗码 口 由文献 1 3 j 我们可以知道r 上码长n 与k 的特征互素的循环码g 的对偶码c 幢 的结构 任取 r m 记 扣 1 功 显然 厶 矿蚴 向 1 肛 丘 1 功 z 出口 l 1 功 z 出9 丘 2 1 z 冀琵 印 力 1 z r 1 z 向 1 z 1 z 出口 矿口 定理3 8 1 1 3 设c 为r 上码长n 与k 的特征互素的循环码 g 其中晶f 1 r 矿一1 则 o 上 且在乏i 上有 1 宜 岛 o 其中 j o 口 1 4 m 艮 如 一 锄 瑚 七 北京交通大学硕士学位论文3 有限链环上的线性码的船 度量 2 丘 与骘互素 其中i o 钌 由定理3 8 我们可以得到r 上码长n 与k 的特征互素的循环码g 的对偶码c 的 另 种表示方法 定理3 9设g 为冗上码长n 与k 的特征互素的循环码 g 的对偶码为 c 止 则存在b 1 i l t 一1 r 使得 d 且b k 一1 满足 一 l k 一2 1 i j l o i 矿一1 a 证明 令k 日咒 f x f o 一1 显然 k 一1 l k 一2 i i i 矿一1 7 1 0 1 k l r m 对于2 l 口有 r 一件1 戽 r 1 局 最一1 乃 1 r r 讲1 昂 吃1 露l e r 一 日 距 瑶鼹 露 r 一 k i 1 昂鼹l 曰 又矗 凡 r 目刀 咒 7 l o 因此 i 上 反之7 i o 目露 o 赢 d 由定理3 8 知 或 与曰互素 则存在n 6 冗m 使得口或 6 0 1 所以 j l 目露 雅1 碱 6 巧 目匠 雅1 8 争 r 咒 r d b r k 磁 r l 以 日匠 髓 因此7 l l 7 或 目刀 磁1 7 g 上 依次类推得1 4 也 g 上 l 一1 所以 c l l 综上所述c 止 口 根据上述定理可以得到r 上码长n 与k 的特征互素的循环码c 的对偶码c l l 关 于彤馊量的一重要性质 1 5 北京交通大学硕士学位论文 3 有限链环上的线性码的舰 度量 码 定理3 1 0 设口为冠上码长n 与 的特征互素的循环码 则c 的对偶码c l l 为m d r 证明 由定理3 9 知 存在k j l l 一l r 吲 使得 1 9 上 且 k 一1 满足k 一1 i k 一2 i b l 矿一1 a v c z 伊 c o 则存在t z 使得c z t z k l z 因此 d e g k 一1 z c 印 c 如 又因为r 1j l l 一1 z 伊 则 d r 弘 d e 9 7 l 廿一l z 1 f e g 耳 1 咖 f 1 1 下证伊 o o o 显然 伊 要证明为直和 只需证明零向量表法唯一 设o 0 0 扁 d 1 z 7 赢 一l p r 一1 忘 两边乘以赢 得 d o 扁 扁 o 由于赢 为首一的 因此咖 z o 两边乘以疵 得 d z 儡 或 o 又由于赢 为首一的 所以n 1 功1 o 因此0 1 z 7 扁 o 同理可证 啦 z o z 2 一 口一1 所以啦 z 舌基m o 2 u 1 因此c u o o o 故c 1 的标准生成矩阵 中行向量的类型为 的向量必出现在 中 所以 竹一向 赢 n d e 9 扁 d e 9 晶 c 上的标准生成矩阵中行向量的类型为i 的向量必出现在 1 i 一1 中 它共有 l d 印 彪l 1 个 即 缸 n 一咖 彪 竹一咖 或一 1 d 叼 r 一件1 1 6 北京交通大学硕士学位论文 3 有限链环上的线性码的j 盯度量 所以 k 硒 一咖 赢讲 咖 昂 咖 b 州 d 印 晶b 风 n d e g f 1 因此n 一膏 1 咖 毋 l d 口上 故伊是m d 兄码 口 同理对负循环码也有类似的定理 定理3 1 1 1 3 ld 为r 上码长是n 加与 的特征互素 的负循环码 m 是r 的极大理想 r o r 一1 o 则存在多项式g o g 1 瓯 r m 使得 c g o g l 瓯 矿 1 特别存在多项式9 0 9 l 蜘一l 使得c 其中 酬 咄取 象 乜 蓦 2 定理3 1 2r 上码长 l 与彤的特征互素的负循环码为肘d 尉冯 证明同定理3 7 由文献 1 3 我们知道r 上码长n 与k 的特征互素的负循环码c 的对偶码g 上的 结构 定理3 1 3 f 1 3 l设g 为冗上码长n 与k 的特征互素的负循环码 g 其中g o g l 瓯 扩 1 则 伊 且在乏耋卑b 上有 1 幺 岛 o 其中 j o 订 2 与g 互素 其中 o 口 同样由定理3 1 3 我们可以得到冗上码长n 与k 的特征互素的负循环码e 的 对偶码c 的另一种表示方法 定理3 1 4设e 为月上码长行与 的特征互素的负循环码 e 的对偶码为 伊 1 7 北京交通大学硕士学位论文3 有限链环上的线性码的田度量 则存在碥 瞄 吒一1 r 使得 c 上 且碡 配一 满足砖一 i 砖一 i 1 i 矿 l 证明同定理3 9 定理3 1 5设e 为冗上码长n 与k 的特征互素的负循环码 则c 的对偶 码c 1 为m d r 冯 证明同定理3 1 0 综上所述我们可以得到如下结果 有限链环r 上码长n 与k 的特征互素的循环码和负循环码都是m d 剜玛 它 们的对偶码也是m d 尉玛 北京交通大学硕士学位论文4 四元环上线性码的船度量 4 四元环上线性码的船度量 四元环广泛的应用在编码理论中 不同结构的四元环有四个 本节主要讨论 环五和易 u b 上线性码的j 玎度量 4 l 五上线性码的刀度量 环互上任意线性码g 的生成矩阵等价于如下形式 吉爰岛 其中a 最 岛 d 为 o 1 矩阵 称码e 为珈2 b 型线性码 称a 如 刃l 动 忍 使得z 勿 g 为c 的剩余码 记作j 琵s c 称q 伽 刁1 2 z c 为c 的挠码 记作2 1 研 c a 的生成矩阵为 厶 ab 岛的生成矩阵为 台乏鲁 a 岛 j k s e 的维数是女l n r c 的维数是七1 且i r e s c i r e i 妒1 2 b 4 1 2 k l e 下面的定理将告诉我们五上的线性码的刀度量与它的剩余码和挠码的册度 量之间有什么关系 定理4 1 设e 为环历上的线性码 岛为e 的挠码 则如 c d 伤 证明 设d q 如 对于任意c g c o 存在c l 刁 c 2 z 使得 c c l 2 c 2 由剩余码和挠码的定义知 c 1 a 从而c 1 巴 于是 啊 c m o z 7 c 1 咐慨 w c 1 d 2 由于如 也 则存在c q 使w c 如 又2 c c 故 2 c w c 如 因此d c 如 口 推论5五上的线性码e 为肘d 尉玛铮g 的挠码为m d 月码 因此在五上得到c 的挠码岛关于删量的标准生成矩阵就可以求出e 的咫 北京交通大学硕士学位论文4 四元环上线性码的皿 度量 度量 由于q 的生成矩阵为 o 1 矩阵 因此伤为m d 屈玛的充要条件是岛的关于 j 玎度量的标准生成矩阵的最后一行的戤馊量为n 一七 1 n h 一如 1 即m k n 一奄 l 对于有限链环上线性码为m d 尉玛的充要条件不容易求出 但是我们可以求 出五上线性码为m d r 码的充要条件 由推论5 我们可以借助于g 的标准生成矩阵 得到历上线性码c 为m d r 码的充要条件 环五上2 c 码长的循环码和负循环码的结构已经比较明朗 下面我们将运用推 论5 的结论来讨论2 c 码长的循环码和负循环码的艘度量 并给出循环码和负循环 码关于磁1 度量的一个重要性质 首先由文献 1 4 l 给出五上2 8 码长的循环码的结构 定理4 2 1 1 4 j 设c 是五旧 的理想 1 若c 为主理想且g 中的元素的系数不为五中的单位 则 c 其中m 是使得2 1 z 叫屠于c 的最小整数 2 若g 为主理想且c 中的元素的系数互为中的单位 则 n 一1 g 铷 其中s 是e 中首项系数为1 的元素中次数最低者的次数 m 是使得2 1 z m 属于g 的 最小撼数且m s 2 3 若e 不是主理想 则 f n 一1 c o 其中s 是c 中首项系数为l 的元素中次数最低者的次数 m 是使得2 1 z m 属于e 的 最小整数且2 1 z 毛 定理4 3 五上2 c 码长的循环码都是m d r 码 证明 由定理4 2 知 对于乙上2 8 码长的循环码总有t d r g 因此由定理3 5 知 乳 r e 是m d r 码 由推论5 知结论成立 口 下面讨论2 码长的负循环码关于脚1 度量的的性质 由文献f 1 3 1 得到五上2 8 码 长的负循环码的结构 定理4 4 1 3 1 孙上2 e 码长的负循环码有 2 0 北京交通大学硕士学位论文4 四元环上线性码的j 玎度量 其中m o m 2 为l z 在z 矗 上的幂零指数 特别当m 2 时 五上2 c 码长的负循环码有 又由 知 z 4 上2 码长的负循环码有 o s 2 c 一1 定理4 5 历上2 e 码长的负循环码都是m d r 码 证明 当五上2 码长的负循环码口 o 8 擎一1 时 由定 理3 5 知 e 是m d r 码 当互上2 码长的负循环码c o s 2 c 一1 时 t 研 g 由定理3 5 和推论5 知 e 是m d r 码 结论得证 口 综合定理4 4 和定理4 5 我们可以得到如下结论 历上2 码长的循环码和负循环码都是m d 冗码 4 2 尼 t l 马上线性码的册度量 关于环b 钍易本身的结构在文献 15 1 6 1 1 7 中均有详细描述 它是剩余类 环局m t 1 2 环易 u 易的元素有 o 1 u 面 t l 且舻 o 若将 视 为历上元素2 l 视为元素3 则乘法与环互上的乘法一致 若将 视为域只 0 1 p 俨 上元素卢 1 u 视为元素俨 则加法与域只上的加法一致 因而它分享 了环五和域目的良好性质 显然环易 t 兄为局部环 最大理想是 o 牡 特征 为2 环尼 t 易上线性码的结构和历上线性码类似 环尼 钍乃上任意线性 码e 的生成矩阵等价于如下形式 台三玩 其中a b l 岛 d 为 o 1 矩阵 称码g 为4 虹2 b 型线性码 称q 1 扛 曰旧 露 使得z 让妒 g 为c 的剩余码 记作r e s g 称q 2 伽 露f 懈 研为e 的挠码 记作砌 e 研t 1 的生成矩阵为 ab 北京交通大学硕士学位论文 4 四元环上线性码的j 口度量 q 2 的生成矩阵为 台三0 显然q 1 q 2 q 1 m s c 的维数是h c i 2 2 切 c 的维数是h 如且i 船s c i i t d r i 2 2 h k 驴2 b 吲 由于互和尼 钍足的结构类似 则有下面的定理和推论 定理4 6g 为环易十t 见上的线性码 c 2 为e 的挠码 则如 回 d c 如 证明同定理4 1 推论6尼 忍上的线性码c 为m d r l 玛铮g 的挠码为m d 尉玛 由于c 的挠码q 2 的生成矩阵为 o 1 矩阵 因此q 2 为m d 冗码的充要条件是 q 2 的标准生成矩阵g 如 1 满足最后一行的腿量为 l 一 1 即m n 一七 1 因此由r 札尼上的线性码g 的挠码的生成矩阵就可以判断足 仳易上的线性 码g 是否为m d r 码 下面我们来讨论易 t l 易上2 c 码长的循环码和负循环码关于础1 度量的性质 由于尼 恳的特征为2 则z 铲 1 护 一1 因此昂 1 l 兄上2 码长的负循环码就 是循环码 首先由文献1 1 8 l 给出最 心 上2 c 码长的循环码的结构 定理4 7 1 8 设g 是 尼 t 如 m 的理想 1 若c 为主理想且c 中的元素的系数不为尼 让足中的单位 则 c 其中m 是使得t 1 十z 仉属于c 的最小整数 2 若c 为主理想且e 中的元素的系数易 t 毋为中的单位 则 g 其中s 是g 中首项系数为1 的元素中次数最低者的次数 m 是使得t 1 z 属于c 的 最小整数且m s 铲 3 1 若c 不是主理想 则 e 其中s 是c 中首项系数为1 的元素中次数最低者的次数 m 是使得u 1 z 属于e 的 最小整数且 1 z 毛 2 2 北京交通大学硕士学位论文4 四元环上线性码的j 汀度量 由上面的定理我们可以得到 对于足 t 足上2 码长的循环码总有 2 h q 因此对于易 足上2 c 码长的循环码我们有下面的结论 定理4 8 局 毋上2 唯 长的循环码都是m d r 码 同定理4 3 的证明 北京交通大学硕士学位论文 5 总结和展望 5 1 总结 5 总结和展望 j 幻s e 砌f d d m 一乳 d s m n n 简称磁1 度量有利于了解码的结构 是一种不同 于日o m l g 度量的度量 可以应用在均匀分布上 本文主要研究了有限链环上 线性码的刀度量 得到如下结果 本文主要通过线性码的生成矩阵来研究线性码的船度量 我们定义了有限链 环上线性码关于j 日度量的标准生成矩阵 由标准生成矩阵我们得到 有限链环上类型为 一1 线性码