（应用数学专业论文）有限环上线性码的结构及其秩的研究.pdf

有限环上线性码的结构及其秩的研究 摘要 本文主要讨论有限环上的线性纠错码 就编码理论研究的两个热点 环上码 的结构 性质和码字的秩和极小生成元集做了一些工作 具体内容如下 1 给出了四元素环最 蜗上线性码的生成矩阵的结构 其中v 2 v 证明 了该环上线性码的g r a y 象仍然是线性的 而且证明了互为对偶的线性码的g r a y 象仍是互为对偶的 进一步给出了该环上的线性码及其对偶码的各种重量的 m a c w i l l i a m s 恒等式 2 给出了环e 蜗上长度为2 的循环码以及 1 循环码的秩和极小生成 元集的具体表达形式 证明了该环上码长为2 8 的一类循环码在g r a y 映射下的象 是循环码 并给出了该环上长为2 的线性循环码的g r a y 象仍是循环码的一个充 要条件 3 给出了环z 上长度为 的循环码及其对偶码的结构 并给出了该环上循 环码的秩和极小生成元集的具体表达形式 4 讨论了环 嵋 1 和有限链环r 上奇长度h 的循环码 负循环 码以及它们的对偶循环码的结构 给出了这些环上循环码的秩和极小生成元集 的具体表达形式 关键词 线性码 循环码 g r a y 映射 理想 生成矩阵 秩 极小生成元集 r e s e a r c ho ft h es t r u c t u r ea n dr a n ko fl i n e a rc o d e s o v e rf i n i t er i n g a b s t r a c t i nt h ed i s s e r t a t i o n t h ea u t h o rm a i n l ys t u d i e st h es t r u c t u r e p r o p o s f f i o n r a n k a n dt h em i n i m a lg e n e r a t i n gs e to fc o d e s w h i c ha r et w oh o tt o p i c so ft h es t u d yo f e r r o r c o r r e c t i n gc o d e s t h ed e t a i l sa r eg i v e n 韶f o l l o w s 1 w e 丘r s t l yg i v et h es t r u c t u r eo fg e n e r a t o rm a t r i x e so ft h el i n e a rc o d e so v e r r i n ge 1 嘎 s e c o n d l y w en o to n l yp r o v et h a tt h eg r a yi m a g e so ft h el i n e a rc o d e s o v e rr i n g e 1 蝇a r ea l s ol i n e a rc o d e s b u ta l s op r o v et h a tl h eg r a yi m a g e so ft h e m u t u a ld u a ll i n e a rc o d e sa r ea l s om u t u a ld u a ll i n e a rc o d e s t h i r d l y w ep r e s e n t v a r i o u sf o r m u l a so ft h ec o d e sw e i g h tb e t w e e nc o d e sa n dt h e i rg r a yi m a g e s a n dt h e n g i v et h e i rm a e w i l l i a m si d e n t i f i e s 2 b yd i s c u s s i n gt h es t r u c t u r eo fr e p e a t e d r o o tc y c l i cc o d e sa n d 1 c y c l i c c o d e so v e rr i n g e z 幔 w eg i v e st h e i rr a n k sa n dm i n i m a lg e n e r a t i n gs e t s a n d p r o v et h a tt h eg r a yi m a g eo fo n ek i n do fc y c l i cc o d eo v e re 蜗o fl e n g t h 2 8 i sc y c l i cc o d e s a n de s t a b l i s ht h es t r u c t u r eo fl i n e a rc y c l i cc o d e so v e r e 幔o f l e n g t h2 w h e nt h eg r a yi m a g e sa r ec y c l i cc o d e s 3 w ep r e s e n tt h eg e n e r a t o r so fc y c l i cc o d e sa n dt h e i rd u a lc y c l i cc o d e so v e r r i n g z p i x x 矿一1 a n ds t u d y t h er a n k so f t h e s ec o d e sa n dt h e i rm i n i m a lg e n e r a t i n g s e 乜 4 w cd i s c u s st h es t r u c t u r e so fc y c l i cc o d e s n e g a c y c l i cc o d e sa n dt h e i rd u a lc y c l i c c o d e so f o d dl e n g t ho v e rt h ef i n i t ec h a i nr i n gr a n d z 峨 卜1 a n dw e a l s oe x p l o r et h er a n ko f t h e s ec o d e sa n dt h e i rm i n i m a lg e n e r a t i n gs e t s k e y w o r d s l i n e a rc o d e c y c l i cc o d e i d e a l g r a yi m a g e g e n e r a t o rm a l r i c r a n k m i n i m a lg e n e r a t i n gs e t 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果 据我所知 除了文中特别加以标注和致谢的地方外 论文中不包含其他人已经发表或撰写 过的研究成果 也不包含为获得 金自 王堡太堂或其他教育机构的学位或证书而使 用过的材料 与我一同工作的同志对本研究所做的任何贡献均己在论文中作了明确的说明 并表示谢意 学位论文储签名 施锄 签字日期 唧年 月护日 学位论文版权使用授权书 本学位论文作者完全了解金世王些盍堂有关保留 使用学位论文的规定 有权保留 并向国家有关部门或机构送交论文的复印件和磁盘 允许论文被查阅和借阅 本人授权台 蟹王些太堂可以将学位论文的全部或部分内容编入有关数据库进行检索 可以采用影印 缩e p 或扫描等复制手段保存 汇编学位论文 保密的学位论文在解密后适用本授权书 学位论文作者签名 袁白效力谚导师签 签字日期 加 7 年6 月善日 学位论文作者毕业后去向 工作单位 通讯地址 签字日 电话 邮编 7 e 夕7 舌 致谢 值此论文完成之际 我要向我的导师朱士信教授致以最衷心的感谢 他严 谨的治学态度和渊博的学识 宽广的胸怀和豁达的处世之道给我留下了深刻的 印象 并将成为我以后学习和工作中的楷模 是他不断的鼓励与亲切的指导给 了我信心并帮我指引了研究方向 进而顺利完成了论文的写作 并在此过程中 受益非浅 在学习期间 受到了苏化明老师 刘丽老师 等很多老师所给予的 关心 支持和帮助 他们的教学思想 教学风格和高尚的品德都给我留下了深 刻的印象 同时也是我学习的楷模 我在此十分感谢与敬佩他们 三年的学习中 师兄弟给了我很多的支持与帮助 大家共同学习 激烈讨 论 度过了难忘的三年时光 在此感谢他们 感谢理学院的计算中心为我提供了这么好的一个学习环境 特别感谢计算 中心的王墨林老师 陈梨君老师 王皖平老师 戚昊琛老师 何先枝老师给了 我许多的帮助 她们认真工作的态度和热情服务的精神都给我留下了深刻的印 象 感谢评阅 评议硕士论文和出席硕士论文答辩会的各位专家学者 感谢他 们在百忙中给予的批评指正和宝贵意见 最后 感谢我的家人以及女朋友在我研究生学习阶段对我提供的物质帮助 和精神鼓励 正是由于她们无私的帮助和奉献 才使我在研究生阶段全身心的 投入到学习之中 我愿在未来的学习和研究过程中 以更加丰厚的成果来答谢曾经关心 帮 助和支持过我的所有老师 同学 朋友以及家人 作者 施敏加 2 0 0 7 年5 月 1 1 纠错编码理论 第一章绪论 编码理论 或者纠错码理论 是信息理论的一个专门分支 其理论基础由 数学支撑 在实际应用中 它的发展则源于现代通信技术与电子计算机技术中 差错控制研究的需要 因此 这一领域既是通信工作者也是数学工作者研究的 热点 随着信息技术的发展 编码理论得到了迅速的发展 现在我们利用计算 机进行复杂运算时 不再担心结果的可靠性 但是在计算机概念刚提出时 曾 经有人提出如下反驳 在计算机这样一个复杂系统中 外界噪声的干扰是不可避 免的 只要噪声使得计算机中任一部件发生一次错误 最后的运算结果都会变 得面目全非 因此可以断言利用计算机进行复杂运算是不可能的 这一困难后 来是如何克服的呢 编码在这过程中起了关键性的作用 什么是编码 编码 更准确鲍说 信道编码 指的是 通过引入冗余信息 使得在一部分比特发生 错误下 仍有可能按照一定的规则纠正这些错误 以实现无失真地传送和处理 信息 举一个最简单的重复码为例 我们可以将信号0 编码为0 0 0 信号l 编码为 1 1 1 这样如果最多只有一个比特发生错误 譬如 0 0 0 变成了0 0 1 我们仍然可 以按照少数服从多数的原则 找出错误的比特就是第三个比特并纠正该错误 纠错编码理论是上世纪四十年代末i 妇s h a n n o n h a m m i n g g o l a y 等人创立1 2 吲 在 实际应用中 它的发展则源于现代通信技术与电子计算机技术中差错控制研究 的需要 美国数学家s h a n n o n f e l 9 4 8 年所发表的著名论文 am a t h e m a d c a lt h e o r y o fc o m m u n i c a t i o n d 2 1 中提出了著名的受干扰信道编码定理 从而开创了一门现 代科技中具有重大意义的崭新学科一信息论 i n f o r m a t i o nt h e o r y 1 9 9 8 年 国际上还专门为s h a n n o n 这一开创性文章举行了五十周年庆典 h a m m i n g 和 g o l a y 在五十多年前分别发表的论文 e r r o rd e t c 枷n ga n de r r o rc o r r e c t i n gc o d e s 田 和 n o t e so nd i g i t a lc o d i n g s 中 提出了从充分利用检验元的观点来看 是最佳 的纠正二元序列中一位错和三位错的完备码 p e f c c tc o d e s 开创了与应用相结 合的编码理论方法的研究 可以说 信息理论的发展和编码方法的成长始终是 相互依赖 相互促进的 h a m m i n g 曾经说过 从逻辑上来说 编码理论导致信 息理论 信息理论则为适当的信息编码提供了所能达到的限度 睁埘 事实上 信息论的应用从底层的通信到电子的损耗都涉及到编码理论 所以说 a l g e b r a i c c o d i n gt h e o r yi s ab r a n c ho fe n g i n e e r i n gw i t hr o o t si nm a t h e m a t i c sa n d a p p l i c a t i o n st oc o m p u t e rs c i e n c e 1 3 1 编码理论主要包括以下两个方面 以保证数字信息传输和处理的可靠性为 目的的差错控制编码 e r r o r c o n t r o lc o d i n g 又称信道编码 c h a n n e lc o d i i l 曲以提高 数字信息传输 存储处理的有效性为宗旨的信源编码 s o u r c ec o d i n g 差错控 制编码技术类别繁多 应用面广 通常所使用的编码理论中的 编码 指的就 是差错控制编码译码技术 每一个通信系统都依赖有效的编码技术 差错控制 编码技术也是伴随着数字通信业务的发展而发展起来的 因此在相当长的一段 时间内 编码的要求和编码译码器的结构特点 都体现了数字通信技术的特征 这就是要求码率高 冗余度小 以便在串行信道中保证尽可能高的通过能力 编码译码器的速度只要能跟上信号在串行信道上传送的节拍就可以 在这种工 程技术背景下 以有限域和代数为基础 以循环码为代表 以线性反馈移位寄 存器为主要编码译码器件的代数编码技术得到迅速发展并且日臻完善 其中象 b c h 码 r s 码以及h a m m i n g 码 g o h y 码等都是应用广泛的代数码 从结构上来 看 差错控制编码一般可以划分为分组码 b l o c kc o d e s 和卷积码 c v o 面o n c o d e s 两大类 所谓分组码 是首先将来自信源的信号分成若干消息组 每个消 息组由j i 位连续的信息符号组成 编码器接收一组消息并按一定规则将之变换 为一组较长的刀位 拧 七 码字符号输出 这种结构不同于卷积码 卷积码是利 用编码器接收一个连续的信号流并在编码后相应地生成一个连续的输出流 由 于卷积码类在工程技术中的实用性 使得通信工程工作者们更倾向于卷积码类 的研究 近年来通信工程工作者们在t u 如码上的研究热潮反映了这一特点 分 组码则以其较完美的数学特点吸引了更多编码理论和理论数学研究者 1 2 纠错码的发展史 迄今 纯错码已有五十多年的历史 其发展过程大致分为以下几个阶段 2 0 纪5 0 年代至6 0 年代初 主要研究各种有效的编 译码方法 奠定了线 性分组码的理论基础 提出了著名的b c h 码 同时也给出了纠错码的基本码限 这是纠错码从无到有得到迅速发展的年代 2 0 纪6 0 年代至7 0 年代初 这是纠错码发展过程中最为活跃的时期 不仅 提出了许多有效的编译码方法 而且注意到了纠错码的实用化问题 讨论了与 实用有关的各种问题 所有这些问题的研究为纠错码的实用打下了坚实基础 在此期间 以代数方法特别以有限域理论为基础的线性分组码理论己趋成熟 2 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 码所能达到的性能 这是纠错 码历史上具有划时代意义 在这期间大规模集合电路和微机的迅速发展 为纠 错码的实用打下了坚实的物质基础 因而与实用相关的各种技术及有关问题得 到了极大关注 并在实用中取得了巨大的成功 自2 0 纪8 0 年代初至今 g o p p a 等从几何观点讨论分析码 利用代数蓝线 构造了一类代数几何码 在这些码中 某些码的性能达到了s h a n n o n 码所能达 2 到的性能 由于代数几何码是一类范围非常广的码 在理论上已证明它具有优 越性能 因而受到了编码理论研究者 尤其是代数几何学家的重视 使代数几 何码的研究得到迅速发展 取得了许多成果 自上世纪7 0 年代末以来 纠错码 技术已开始渗透到很多领域 利用纠错码中的许多编 译码原理和方法 与通 信系统中其它有关技术相结合 得到了一些令人惊喜的结果 如 纠错码与调 制技术相结合所产生的t c m 技术 已作为国际通信中标准技术而推广使用 纠 错码与密码结合 可以构造出一类既能加密签名 又具有纠错功能的密码系统 纠错码与信源编码相结合的结果 使得通信系统更为有效与可靠 不仅如此 纠错码中的许多译码思想和方法 与神经元网络中的能量函数有密切关系 可 以用来解决神经元网络中的一些闯题 因此 可以预料 随着科学的进步和实 际需要 纠错码理论必将迸一步发展 它的应用范围必将进一步扩大 1 3 目前研究的现状 当前 关于编码理论的研究 以下几个方面是近年来比较活跃的 1 环上 码 2 代数几何码 3 纠错码应用于密码学 4 t u r b o 码 5 s p a c e t i m e 码 6 量子纠错码及量子密码 下面简述一下有限环上码的结构 性质以及码 字的秩和极小生成元集的研究现状 有关某些具体的研究现状在后面的具体章 节有所涉及 研究有限环上不同码字的一般结构和对码字集合进行分类是有限环上的纠 错码理论研究中的两类热点问题 环e 蜗 e l 匠是介于环z 4 与域e 之阃 的一种四元素环 因此分享了环乙 域e 的一些好的性质 所以此类环上的编 码理论研究成为继乙之后又一研究热点 为了对一个确定长度的码字的集合进 行分类 需要对这些码字逐个的考虑 特别是在研究这些码的距离分布时 对 码c 中的每一个非零的码字作一详尽的研究是必要的 遗憾的是这在实际中是 很难办到的 因为当码长以较大时 计算的复杂性很大 而研究这类循环码的 秩和确定其极小生成元集可以在很大程度上降低计算的复杂性 因此研究循环 码的秩及其它们的极小生成元集是很有意义的 s 把v e nt d o u g h e r t y t l 首先定义 了四元素环凡上码的秩 即对该环上任一长度为栉的码c 定义其秩为c 的极 小生成元的个数 记为r a n k c 它的自由秩为c 的自由见一子模秩的最大值 记为f r a n k c 若心上码c 中含有4 k 2 b 个码字 记c 为怔 t 型码 则秩 为毛 如 自由秩为毛 一般来说 如果码c 的自由秩与它的秩相等 例如当 毛 0 时 称码c 为自由码 当然所有的域只上的码字都是自由码 在确定不同环上码字的结构方面 特别是当码长为奇数的情形 前人已经 散了不少工作 c a l d e r b a n k l 等人给出了环z 上循环码的结构 后来p r a m o d k a n w a d l 6 1 等人又给出了不同的证明方法 朱 1 7 1 等人给出了有限链环 c t l 巴 h 只上循环码的结构等等 当码长为偶数或者素数的方幂时 最近讨论也很多 譬如 t a b o r a b u a l r u b t 垌等人讨论了乙上长度为2 的循环码 的结构 证明了该环上理想的生成元可能不止一个 即理想不一定是主理想 t b l a c k f o r d t g 通过离散的傅立叶变换的方法给出了z 上奇偶长度循环码及其 对偶码的结构 而且还讨论了这些码字的极小李重量和自对偶码 在最后还提 出一个公开的问题 如何研究z 上长度能够被p 整除的循环码2 后来s t e v e n t d o u g h e r t y m l 等人又将其推广到偶长度上 然而讨论这些环上循环码的秩和它 们的极小生成元集却相对较少 最近t a h e ra b u a l r u b t 2 l 等人讨论了z l 上长度为 2 的循环码的秩和极小生成元集 后来 a b u a l n l b 阱 又讨论了环z 乙以 及z 2 呸 封2 2 2 上任意长度的循环码及其对偶码的结构 迸一步确定了它们的 秩和极小生成元集 1 4 本文的主要内容 就目前信息科学中纠错码研究的几个发展方向来说 t u r b o 码以及s p a c e t j m e 码这两个研究方向涉及更多的是有关通信工程方面的技术问题研究 而 数学工作者们更多讨论的则是代数几何码与环上码的理论研究 作者在纠错编 码理论部分主要对环上的码做了部分研究 本文主要讨论了有限环上线性码的结构以及它们的秩和极小生成元集 具 体内容如下 1 给出了四元素环e 峨上线性码的生成矩阵的结构 其中v 2 v 证明了该 环上线性码的g r a y 象仍为线性码 而且证明了互为对偶的线性码的g r a y 象 仍是互为对偶的线性码 而这一性质在z j 上不成立 2 定义了环e 蜗上码字的李重量分布的概念 利用域五上线性码和对偶码 的重量分布的关系及g r a y 映射 绘出了该环上线性码与对偶码之闻各种重 量分布的m a c w i l l a m s 恒等式 3 考虑环e 幔上长为z 的循环码结构 证明了环e z 幔上码长为2 的一类 循环码在g r a y 映射下的象是循环码 并给出了环e 蜗上长为2 的线性 循环码的g r a y 象仍是循环码的一个充要条件 4 通过对环最 蜗上长为2 的循环码与 1 一循环码的结构的讨论 给出了 它们的秩和极小生成元集 5 定义了环f q 证q r f q 上循环码的秩的概念 其中疋为含有q 个元素的有 限域 g p p 即c 的特征 为素数 s e 为正整数 且 t p 1 确 立了该环上码长为奇数n 的循环码及其对偶码的结构 证明了该环上所有的 理想均是主理想 而且给出了该环上循环码及其对偶码的结构的另一种表达 形式 最后给出了该环上循环码的秩与极小生成元集 6 定义了有限链环r 上循环码及其负循环码的秩和极小生成元集 通过研究有 4 限链环上循环码及其负循环码的结构 给出了有限链环r 上循环码及其负循 环码的秩和极小生成元集 这些内容韵研究对进一步丰富纠错码在有限环上的理论及构造一些性能较 好的码都有一定的指导意义 特别是对确定码字的距离分布以及解码均有重要 的指导意义 第二章有限环上线性码的结构 从1 9 4 8 年s h a n n o n 开创纠错码理论以后 人们利用有限域理论脚 作为工 具 建立了系统的有限域上的纠错码理论 这些理论在文献 5 l l 中有全面的研究 近年来 编码理论中的一个突破性的进展是h a m m o n s 等人在文献田1 中证明了一 些高效黔二元非线性码 掘p r e p a 蹦a 码 k c r d o c k 码等可视为环z 上循环码在 g r a y 映射下的像 而且他们还解决了在编码理论中一个古老而公开的问题 即 证明了非线性二元p r e p a r a t a 码和k e r d o c k 码满足m a c w i l l i a m s 恒等式 文献 2 7 l 一 q l l a l 锄a r y c o d e s 的出版标志着环乙上的纠错码理论已有了基本框架 随后 环乙上的纠错码理论进入全面发展时期 这些成果导致了近年来环乙乃至更一 般的有限环上的编码理论的研究进入一个全新的研究方向 2 1 环f 2 v f 2 上线性码及其对偶码的二元象 2 1 1 预备知识 士 0 l v 1 v 0 1 v14 v 0 0 0000ol v 1 y l 0 l 1 1 vllo1 1 y v01 v 0v l v0l 1 1 01 4 v01 4 v1 4 vl 1 1v10 这个环可以看作域e 上维数是2 的向量空间 而且 o 1 o i o 1 1 形 成环丑的三个子空间 而且子空间 o 1 l 是五的一个子环 由中国剩余定理 r 兰最 e 兰f d v 环只仅有两个极大理想 o v 和 o 1 v 因此足 是局部环 其中v 和l v 是r 的两个零因子 特征为2 环r 上的线性码c 是指 定一模肜的一加法子模 对r 中任意的z 恐 r 舅 儿 定义 z 与 的内积为z 玉y l 矗y 若x y 0 则称x 与y 正交 设c 是环 且上长为j l 的线性码 令c 扭e 彤瞳 y o 对v y e c l 则容易证明c 1 也是环丑 上长为n 的线性码 称为线性码c 的对偶码 若环五上线性码与其对偶码相等 即c c 1 则称c 为环五上的自对偶码 2 1 2 环r 上的线性码及其对偶码的生成矩阵 设q c 2 均是环r 上长为n 的线性码 若c l 通过坐标置换 必要时将码元v 与 l v 互换 能得到码c 2 则称c 1 和c 2 为环r 上等价的线性码 类似于文献口7 1 中的讨论 可以证明 命题2 1 五上任意一非零的线性码c 都等价于一个由 f 一 b q 1 d 2l 缸i 0 0 0 0 0 1 b 嚣v zj 眨 i 1 j 7 所生成的线性码 其中暑且c i 4 d 2 e 均为域e 上的矩阵 此时也称码c 的生 成矩阵为 2 1 式 显然码c 中共包含4 2 b 2 b 个码字 上面的生成矩阵 2 1 与环z i 五 峨上码的生成矩阵相比 在形式上都 有较大的差别 主要是因为在环z 4 和环五 哇上分别只有一个零因子2 和 而在环r 上有两个零因子v 和l v 所以和其它两个四元素环相比 讨论该环 上的生成矩阵要复杂一些 下面的命题2 2 讨论了命题2 l 中码c 的对偶码的 生成矩阵的结构 命题2 2 若c 为命题2 1 所设的r 上任一非零的线性码 则其对偶码c 1 的 生成矩阵为 fc i 科 哇 c i l f 乇 毛 乞 毛 1 日 i 0屹0 i 2 2 i 1 v 爿 o v t 00 j 其中4 占 c l 日 d 2 e 均为域岛上的矩阵 显然码c 1 中共包含矿吨也吨垆步个 码字 证明设以 2 2 为生成矩阵的r 上的线性码为c 因g h 0 很明显有 c s f l 成立 下面只要证明c 1 量 即可 即只要证明对 v c 如 乞 气 c l 有c c l c 2 c 成立 先把 2 2 式的前 7 岛 也 岛 行的某些线性组合加到c 上 可得到如下形式 一2 如 气 l 吒 屯 气屿 i 气啦 屯 o o t 其中码字一中后 茏一 南 岛 个位置为0 由于c 与 2 1 式中后毛行正交 故有 屿 气幔 b 必然全为0 或v 再将 2 2 中的中间岛行的某些线性组合加到 c 上 可将c 化为如下形式的码字 c l 气 吒 i 幔 o o 其中码 字c 中后n k 屯 个位置0 又c 与 1 式中的中间岛行正交 故有 气 p 气 b 全为 或l v 将 2 2 式后毛行的某些线性组合加到 上 可将 化为如下形式的码字 蛾 气 o o 其中 后 l 一缸个位置0 又 与 2 1 中前与行正交 散有q 气全为0 因此码o c c 如 c 2 c 敛命题2 2 成立 2 1 3 环r 上线性码及其对偶码的g r a y 象 对于环盖上任一元素名 均可表示为五 r 力 w 其中r z g 五 则可定义从r 到露的g r a y 映射 中 a 乃 g 五 r 五 若令 7 s 似 五 m 则有 o 句 五 j a 很明显对任意的工 r 有 既x 矿 似力 而且对vx y e r 有呒 x y 吒 力 d 中 功 a o f y 引理2 1 对环盂上任一个线性码c 它的二元象中 c 是距离不变的 证明因为c 是线性的 所以对任意的 c c c 甜 f c 又因c 关于李 重量是不变的 且r 的特征为2 显然 睨 d p c 睨 c i c e c v u c 那么有 矿 中 o 力 l v c c l 形 m 一o d o o o 呦i v c c 或似 力j v c e c 耳l q 一力l v c e c k q o i v c e c 既 o l v c c 矿 中 c l v cec v o u em c 1 因此环五上任一个线性码c 的二元象中 c 是距离不变的 引理2 2 1 h y e r 则有0 0 力 o 功 0 0 2 v x y e 置 贝u 有 r d o 聊 m y 证明 1 记x r 对 w 砷 y r y v q y 则有 o x 斜r r y v q x g 力 r 孽 磅 g 力 砖 y 垂 d 力 2 是 1 的自然推广 由此显然有 定理2 1 若c 为r 上长为行的线性码 其生成矩阵如 2 1 式所示 则o c 的生成矩阵的形式为 a 00 00 oo b d l e 00 o0 00 00 厶 0 oo oo bd i4 d 2 0 g 2 3 是长为2 n 的线性码且中 c 为域五i i 勺 2 n 2 与 如 岛 线性码 其中矩阵 彳 b c d l d 2 e 均为域最上的矩阵 证明假设c 为r 上长为玎的线性码 由引理2 2 知 够 为域e 上长为2 竹 的线性码 而中 q 是由r 上矩阵 厶 嘭 1 v k o o 4 v a 1 坊a 磁 o 丑 v b 1 谚b o 1 订 d i 吗 1 d l v d 2 1 d l 峻 1 q 1 v e 的行向量的二元象的一些线性组合所生成的 因为矩阵彳 b c d i d 2 e 均为域e 上的矩阵 故有 s o a bd l v d 2 abd i d 2 s abd i 哆 ab 叠毛ab 蜀 易j o 吨谢访v o l 鸣 r 吨谢访蚂 蛾 s 吨v av b d l v d 2 o 00 0 ab 叠 d 2 l m 1 1 厶 1 v a 1 十1 占 1 v x d l 让 2 7 1 v 1 v 4 1 v b o 棋d i 哆 j 1 v 1 彳 i 口 1 顶d l 峨 j j 帆a 口q0 0 0o 0 1 0 吨0 嵋 r0 吨0v c s0 屹0v c o 0 00 0 k0c i 中 o0 1 v k 1 v e o0 1 乇 1 功e s o0 1 v 气 1 v e 1 00 e0 0 0o 又因为l 气a b4 abd 1 d 2 o 00 0 气abd 1 d 2 a b d l 000 0 因此o c 是由 2 3 式的行向量的一些线性组合所生成的 而 2 3 式中各 向量显然是线性无关的 故 2 3 式是o c 的生成矩阵 下面的定理证明了互 为对偶的线性码的g r a y 象仍是互为对偶的线性码 而这一性质在乙上不成立 定理2 2 设c 为皿上长为栉的线性码 c 1 为其对偶码 则o c 与o c 1 为 域e 上的对偶码 证腭因c 为震上长为撑的线性码 则由引理2 2 知辔 o 与o c 1 均为域 e 上的线性码 若记o c 的对偶码为 c 1 下证o c o c 1 vc i i 仨c 吃 眨 c 1 其中 毋e 曰 f l 2 则因c 与c 1 互为对偶码 故岛 c 2 0 贝0 吃 o i 9 2 吒g l g 1 9 2 o 故 o c 1 o c 2 吒 g l 恐 9 2 吃 2 巧吃 鼋2 s q l 鼋i q 2 0 又因为g r a y 映射m 为双射 故 c 三 c 1 另一方砸 由定理2 1 知 o c 为域ei 1 约 2 n 2 墨 镌十毛 线性码 故 c 上为域f z c 的 2 n 2 n 2 畸一如一 七3 线性码 故 o 上i 2 2 2 吨吨 下面只要证明l o c 1 l 2 2 2 h b i l l y 若c 1 为r 上长为n 的线性码 其生成矩阵如 2 2 式所示 则利用类似于定理 2 1 的证明过程 同理可计算出中 c 1 的生成矩阵为 9 彳7 q t a 7 e 矿 d 7 o o 其中矩阵一 b q d l d 2 e 均为域e 上的矩阵 则易知l m c 1 j 2 2 4 2 吨吨 即有 p c 1 1 l c 上i 故m c 1 c 1 2 2 环f z h f 2 上的线性码及其对偶码的m a c w i l l i a m s 恒等式 2 2 1 引言 无论是有限域还是有限环上的编码理论 利用线性码的码字的各种重量分 布研究其对偶码的相应重量分布都是一个十分有意义的研究课题 在文献啪 中 m a c w i l l a m s 给出了有限域e 上线性码的h a m m i n g 重量的m a c w i h a m s 恒等式 文献 2 7 中对环五上的码的各种重量的m a c w i l l a m s 恒等式进行了较系统的阐述 文献网确定了z 上线性码的对称形式的m a c v l l a m s 恒等式 但环五 岷上的 线性码的各种重量计数公式以及m a c w i l l 矗a s 恒等式却很少有人讨论 文献1 3 仉 3 1 3 4 中只是利用环e 蜗研究t y p en 的自对偶码以及一些模格的构造问题 对v x x l x 2 毛 彤 定义码字x 的李重量为职 妻暖 毛 称码字 百 x y 的李距离为 d l 似力 睨o 一力 若用畔 力表示码字善中李重量为 i i 0 l 2 的码字个数 贝h 有 睨 x q 力 2 口2 0 r e 峨中元素的汉明重量和李重量如下表 磊 1 幔 汉明重量李重量 0oo l12 v l1 1 4 v1l 上一部分 2 1 节 我们讨论了环r 上的线性码及其对偶码之间的关系 在这 一部分 先定义了环五 嘎上码字的李重量分布的概念 利用域五上线性码和 对偶码的重量分布的关系及g r a y 映射 给出了环r 上线性码及其对偶码之间的 各种重量之间的m a e w i l l i a m s 恒等式 2 2 2r 上线性码及其对偶码的m a c w i l l i a m s 恒等式 定义2 1 设c 是月上长为露的线性码 若用尽 i 0 l 2 2 n 表示c 中所 有李重量为i 的码字个数 则称 岛 e 马 为码c 的李重量分布 称 吨 o o o k o o 气矿 o o o 甜玎 矿 o o 矿矿 矿 0 呜 o o o k o 矿o o t o o o l e e c x y 艺马彳 为码c 的李重量计数公式 显然有l e e c x y y x z 一吨扣 y w l c 类似地 我们也可定义r 上线性码c 的对称重量计数公式 冬 s w e c x 五 五 蛩 矸 霹 以及码c 的h a m m i n g 重量计数公式 h a m c x n x 1 一 屹 订 其中阡 q c 致 c 称为码字c 的h a m m i n g c 重量 关于以上这几种重量计数公式 我们有 定理2 3 1 l e e c x r s w e c 工2 x y y 2 2 h a m c 工 r s w e c x y d 证明根据定义2 1 有 s w e c x 2 x y y 2 x 砜 硼 y 坪 x n 一吒扣 y w o l e e c x y s w e c x y y x o y 啡 p o x 忡 y h a m c x 对于环震上任一元素a 均可表示为a r 坶 其中 五 晕 2 e 则 可定义从r 到碍的g r a y 映射 o 丑 r g 似 五 令5 q z r 则有 o a 五 s 旯 对v x e r 有 x 形 o 而且对v x y e r 有 睨 x y a a x y d 中 工 d m o 这个映射可推广到r 上向量x 的g r a y 映射 设任意一个向量x 而 x e r 其中五 i l 2 n 定 义 柳 g 吼 吼 则o x x g x r x 下面我们进一步讨论环r 上长为栉的线性码c 及其对偶码c 1 与它们的 r a y 象中 c 及其o c 的码字之间的各种重量之间的关系 定理2 4 设x y r 记矿 m 为碍 上码字中 z 的h a m m i n g 重量 d e o x 中 r 为嘭 上码字o z 中 r 的h a m m i n g 距离 则有 1 既 柳 矽 中省 2 d l x y d o x 零 证明设x 五 恐 x d 其中蕾 i i 2 玎 直接验证有 呒 墨 o 即呒 主 q l 故有 形 幻 矽 聊 g 幻 d 形 r 妁 g 幻 柳 矿 吼 i l i r i 矿 吼 呒 呒 柳 l 硝i 码 九 z y 既 x y 睨 z l 中 z y 矿 中 x y d 中 x m 定理2 5 设c 是r 上一长为疗的线性码 c 上是其对偶码 o c 为其g r a y 象 且中 c 是只上长为2 拧的线性码 则 1 c 的最小李重量等于o c 的最小h a m m i n g 重量 2 l e e c x y c 置r 3 l e e c o x 南k 印 x y z y 证明 1 由定理2 4 即得 2 由定理2 4 知 l e x y x 2 帆 y 毛甜 x h 毋 羚y 眠9 c 强 f t x y 3 因为o c c q o c 1 是最上长为2 n 的二元线性码 且也是互为对偶的 故由 文献p 5 1 中的式 2 j 9 知 一 置 芦呙r r o z y z n 而由 2 知 l e e c x r a x y 另一方面 又因中为双射 则i c i 睁f m 故有 厶 何 功2 一 皑 2 声砑1 c 2 亩如e c y z y 推论2 i 设c 是r 上长为 的线性码 c 上是其对偶码 则r 的李重量分布 碱 e 岛 与c 1 的李重量分布 成 碍 鹾 有如下关系 耳 高 2 i j z b i p t i 2 n 其中丑 f 2 力 为k r a w t c h o u k 多项式 其中丑以珂 一1 顶ih n i 证明l e e c x y 层x 2 一 而 x 4 x 其中4 为 二元线性码中 c 的重量分布 则由定理2 5 中 2 知 4 属 f 0 1 2 n 若设中 c 的对偶码o c 1 的重量分布为4 则也有4 群 i o i 2 n 而由 文献 3 5 中 2 3 式知4 雨去页姜4 最 i 2 n 故有犀 丽1 萎2 n 马最 f 2 一 定理2 6 若c 是r 上长为疗的线性码 c 1 为其对偶码 则有 1 跏缸o k 五 五 南跏宅 五 2 五 五 五一五 五一2 五 五 2 h a r a c z y 而i h a m c x 3 y x 一 证明 1 令局x 2 五 耵 置 y 2 t 由定理2 3 定理2 5 中 3 知 s w a x o 置 x 2 l e e c 工 功 南上廿吃 x y x n 丽1 x y 2 峨忙 z 即吒 卜il o l o s c 南萎 盯州咖州 一l 州咖2 州 2 南萎 2 州 x 2 一y 2 r 扣 x 一圩吲订 击 x 2 2 x y p 删 z 2 一y 2 州d z 2 2 x y y 2 州订 击 2 x x d 州4 x o x d 州 墨一2 墨 置严 南跚c 五 2 五 墨 墨一置t 蜀 2 五 置 2 由 1 和定理2 3 中 2 即得 1 2 2 2 3 应用举例 例1 c o o v v 是r 上长为2 的线性码 一方面 我们可以不必求 出c 上 便可以知道c 上的李重量分布 方法i 由定理2 5 中 3 知 工 似 d 2 商k e c x r x y 2 主善马 z y 脯一叫 圭 媵 y 2 一玎1 x 2 x 3 y 2 x 2 y 2 2 盯3 故c 1 的李重量分布为聪 l 碍 骂 骂 2 e 1 方法i i 由李重量分布的定义有工8 龟暖 功 芝4 x r i j 2 2 故 岛 置 1 由群 去 e 丑 f 4 知 层 1 碍 e 骂 2 毯 1 方法 c 1 是由g i 生成的 c 1 o o l 1 v v 1 v l v 0 v o o 1 v n 1 1 v 由定义直接得出 血红 x d 2 x 3 y 2 x 2 y 2 2 p 故群 l 碍 燧 骂 2 耳 l 以 上三种方法的计算结果完全一致 2 3 环f 2 u f 2 上长度为2 的循环码的g r a y 映射象 文献m 3 n 6 e 引入一种介于环乙与域e 之间的四元素环e 鸩 讨论了环 e l 幔上循环码的结构 译码问题及t y p ei i 码的性质 同环z 4 相比 环 e 蜗上的码具有编 译码简单更易于实现等特点 关于环e 幔本身的结 构在文献 3 6 3 7 均有详细描述 它是指剩余类环e u l u 2 其元素分别记为 0 1 l u l 若将 视为z 4 环上元素2 l u 视为元素3 则其乘法与z 4 环上 乘法一致 若将 视为域互 o l 磊芦2 上元素多 l u 视为多2 则其加法与域 只上加法一致 因而它分享了环乙与域只的一些良好性质 c a r l e t 在文献 3 9 1 中 通过b o o l e a n 函数在z 0 环上定义了g r a y 映射 研究 了码在z 0 环上的性质 在文献t 3 9 1 中t a p i a r e c i i l a s 探讨了z 环上 1 2 循 环码 而l i n g 在文献 中研究了z 环上o p 循环码 d o u g h e r t y 在文献 2 日 中 通过在e 蜗环上定义一个g r a y 映射 得到了t y p e 码在e 十峨环上 的一些重要的结果 本文基于墨 t e 上码长为z 的循环码的结构 4 l 证明了环最 蜗上码长 为2 的循环码的一种形式在g r a y 映射下的象是循环码 确定了长为2 在g r a y 映射下的象为循环码的线性循环码的结构 下文中若不易发生混淆 r 与z 上的加法运算都用 表示 否则乙上 用 o 表示 定义2 2 任意口 r 可写成口 r u q 其中r q z 2 令中 口 g 9 0 r 称映射o 五哼乏为r 上的g r a y 映射 类似的可定义掣 召的g r a y 映射为 o 4 q o 吼 吼 1 q o o g l o i 日0 i o 1 其中口 瓴 q q 1 q 巧 r j 吼 z 2 i 0 1 n 1 当4 用多项式 a x a o a z x a 2 x 2 矿4 来表示时 e p c a x 1 x 9 0 r o 其 中a x o 钾 工 r 力 g 功 z 2 m i 不难验证g r a y 映射为双射 事实 上 若a e z a q 6 0 也 屯 贝0 i 藿 1 口 1 崛o a o o u a j q o6 1 l l l o 阮 1 定义2 3 循环映射o r 专科定盯 口o q i a o q 口 2 五上长为刀的线性循环码c 与r x l x 一1 中的理想 问可通过以下映射建立同 构关系甲 4 砌 a o 码 以 1 t 其中a x a o a l x a 2 x 2 g n 1 3 f 1 因此 本文中c 与 不加严格区分 记墨 r x l x t 恐 z 2 x 一1 1 1 2 以下 同 定义2 4 设口 皿 口 功