（概率论与数理统计专业论文）一类有限环上的mac+williams恒等式.pdf

华北电力大学硕士学位论文摘要 摘要 环上的编码理论是近年来编码理论研究的热点。因为某些定义于环上的线性循环码， 其非线性映射的二元象是性能优秀的非线性码。该文研究了一类非常重要的环咒+ 乱r + + u b l 昂上线性循环码及其对偶之间的m a c w i l l i a m s 恒等式。该文首先定义了环r + u 毋上线性码的对称重量计数多项式，然后利用环b + 让b 上函数的离散h 鲫d a m a r d 变换， 建立了其上线性码与其对偶码的对称重量计数多项式之间的m a c w i l l i a m s 恒等式。并进一 步将上述结论进行了推广，定义了环b + 乱b + + u 七一1 昂上线性码的对称重量计数 多项式，导出了此环上线性码及其对偶码的对称重量计数多项式之间的m a c w i l l i a m s 恒等 式。 关键词：线性码m a c w i l l i a m s 恒等式h a d a m 鲫d 变换对称重量计数 a b s i r a c i c o d e so v e rd n g sh a v er e c e n yr e c e i v e dag r e a td e a lo fi n t e r e s t 锄o n gc o d i n g 廿l e o r i s t s b e c a u s es o i i l ee x c e l l e n tb i n a 巧n o m i n e a rc o d e sc 锄b co b t a i n e df 幻mt h eb i n a 巧i m a g e s0 fm e l i n e a rc o d e so v e rn n g s 蚰d c ra n o i l l i n e 盯m p i nt l l i sp a p e r t i l em a c w i l l i 锄si d e n t i t ) ，b e t w e e n t h cl i n e a rc o ( 1 e 觚di t sd u a lo v e r t i l er i n g 昂+ 缸b + + 铲一1 昂i sd i s c u s s e d as y m m e t r i z e d w e i g h te n u m 咖r o ft l l el i n e a rc o d eo v e rt l l er i n g 昂+ u 昂i sd e f i n e di nt l l i sp a p e r b yu s i n g m ed i s 讹t eh a d a n l a r dt r a i l s f o m a t i o n ，as y m m e t r i z c dm a c 晰l l i 锄si d e n t i t yb e t w e e nt l l el i n e a r c o d e 孤di t sd u a lo v e rm e 渤g b + u 易i sg i v e n f u n l l 咖0 r e ，m ea b o v e r e s u l t si sg e n e m l i z e d t 0t l l er i n g 昂+ + t 正七一1 昂t h es y m m e t r i z e dw e i g h te n u m e r a t o ro ft l l el i n e a rc o d eo v e rt l l e r i n g 乃+ 心易+ + 乱七一1 昂i sd e f i n e d ，a u l dt 1 1 es y m m e t r i z e dm a c w i l l i 锄si d c n t i yb e t w e e nt t l e n n e a rc o d ea n di t sd u a l0 v e r 恤咖gb + t 正昂+ + u 七一1 昂i sa l s og i v e nb yu s i n gas i i i l i l a r d i s c r e t eh a d a m a r dn 锄s f b n n a t i o n k e yw o r d s ：l i n e a rc o d em a c w i l l i 锄si d e n t i t y h a d a m a r dt r a n s f o 唧 s y m m e t r i z e d w e i 曲te n u m e r a t o r l iy r u ( a p p l i e dm a t h m a t i c s ) d i r e c t e db yp r o f c h e nl u s h e n g p r o f g ug e n d a i l l l 华北电力大学硕士学位论文摘要 摘要 环上的编码理论是近年来编码理论研究的热点。因为某些定义于环上的线性循环码， 其非线性映射的二元象是性能优秀的非线性码。该文研究了一类非常重要的环咒+ 乱r + + u b l 昂上线性循环码及其对偶之间的m a c w i l l i a m s 恒等式。该文首先定义了环r + u 毋上线性码的对称重量计数多项式，然后利用环b + 让b 上函数的离散h 鲫d a m a r d 变换， 建立了其上线性码与其对偶码的对称重量计数多项式之间的m a c w i l l i a m s 恒等式。并进一 步将上述结论进行了推广，定义了环b + 乱b + + u 七一1 昂上线性码的对称重量计数 多项式，导出了此环上线性码及其对偶码的对称重量计数多项式之间的m a c w i l l i a m s 恒等 式。 关键词：线性码m a c w i l l i a m s 恒等式h a d a m 鲫d 变换对称重量计数 a b s i r a c i c o d e so v e rd n g sh a v er e c e n yr e c e i v e dag r e a td e a lo fi n t e r e s t 锄o n gc o d i n g 廿l e o r i s t s b e c a u s es o i i l ee x c e l l e n tb i n a 巧n o m i n e a rc o d e sc 锄b co b t a i n e df 幻mt h eb i n a 巧i m a g e s0 fm e l i n e a rc o d e so v e rn n g s 蚰d c ra n o i l l i n e 盯m p i nt l l i sp a p e r t i l em a c w i l l i 锄si d e n t i t ) ，b e t w e e n t h cl i n e a rc o ( 1 e 觚di t sd u a lo v e r t i l er i n g 昂+ 缸b + + 铲一1 昂i sd i s c u s s e d as y m m e t r i z e d w e i g h te n u m 咖r o ft l l el i n e a rc o d eo v e rt l l er i n g 昂+ u 昂i sd e f i n e di nt l l i sp a p e r b yu s i n g m ed i s 讹t eh a d a n l a r dt r a i l s f o m a t i o n ，as y m m e t r i z c dm a c 晰l l i 锄si d e n t i t yb e t w e e nt l l el i n e a r c o d e 孤di t sd u a lo v e rm e 渤g b + u 易i sg i v e n f u n l l 咖0 r e ，m ea b o v e r e s u l t si sg e n e m l i z e d t 0t l l er i n g 昂+ + t 正七一1 昂t h es y m m e t r i z e dw e i g h te n u m e r a t o ro ft l l el i n e a rc o d eo v e rt l l e r i n g 乃+ 心易+ + 乱七一1 昂i sd e f i n e d ，a u l dt 1 1 es y m m e t r i z e dm a c w i l l i 锄si d c n t i yb e t w e e nt t l e n n e a rc o d ea n di t sd u a l0 v e r 恤咖gb + t 正昂+ + u 七一1 昂i sa l s og i v e nb yu s i n gas i i i l i l a r d i s c r e t eh a d a m a r dn 锄s f b n n a t i o n k e yw o r d s ：l i n e a rc o d em a c w i l l i 锄si d e n t i t y h a d a m a r dt r a n s f o 唧 s y m m e t r i z e d w e i 曲te n u m e r a t o r l iy r u ( a p p l i e dm a t h m a t i c s ) d i r e c t e db yp r o f c h e nl u s h e n g p r o f g ug e n d a i l l l 声明户忉 本人郑重声明：此处所提交的硕士学位论文一类有限环上的m a c w i l l i a 麟 恒等式，是本人在华北电力大学攻读硕士学位期间，在导师指导下进行的研 究工作和取得的研究成果。据本人所知，除了文中特别加以标注和致谢之处 外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得华 北电力大学或其他教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 学位论文作者签名：主妻! 墨 日期：竺! 堑：兰! 兰尘 关于学位论文使用授权的说明 本人完全了解华北电力大学有关保留、使用学位论文的规定，即：学校 有权保管、并向有关部门送交学位论文的原件与复印件；学校可以采用影 印、缩印或其它复制手段复制并保存学位论文；学校可允许学位论文被查 阅或借阅；学校可以学术交流为目的，复制赠送和交换学位论文；同意学 校可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容。 ( 涉密的学位论文在解密后遵守此规定) 作者签名：查! 亟 日期：2 纽丘金：蕴 、 、 导师签名：王爱。垂塾么笈驻扒 日 期：幽盈匿 幺 华北电力大学硕士学位论文 第一章引言 纠错码是信息科学的基石之一。为了保证信息能够准确无误的被传输和存储，对数 据进行纠错编码是一个必不可少的步骤。迄今为止，最为常见的纠错码都是二元纠错码。 一个长为n 的二元纠错码是向量空间曰的一个子集合，一个长为n 的二元线性纠错码是向 量空间曰的一个子空间。码中的向量们称为码字。两个码字之间互异的分量个数称为它 们之间的汉明距离。一个码中码字的汉明距离的极小值称为该码的极小距离，它反映了 该码的纠错能力。如果一个二元线性码的极小距离为d ，那么它可以检查出d 一1 个错误， 并且纠正其中的i 簪1 个。一个n 长的码的码率定义为码字个数除以n 后再取以2 为底的对 数。编码理论的一个重要问题就是在限定码字之间的极小距离为一个整数d 的条件下，寻 找码率最大的码【l 】【2 】。 线性码由于容易构造、编码和译码，一直以来都是人们研究的重点。然而在1 9 7 0 年 左右，几种二元非线性码的构造改变了人们的看法。这几种非线性码在拥有和线性码相 同的长度和极小距离的情况下，所包含的码字个数却达到了线性码的两倍以上! 具有代 表性的有n o r d s t o 锄r a b i n 码，p r e p a f a t a 码，k e r d o c k 码，g o e m a l s 码等 3 】。然而这些非线性 码性能虽好却有一个致命的问题就是构造、编码和译码都非常的困难。这种困难一直困 扰着编码学家们。这个时候一个有趣的发现就是p r e p a r a t a 码的重量计数多项式是相同长 度的k e r d o c k 码的重量计数多项式的m a c w i i l i a m s 交换，然而k e r d o c k 码和p r e p a r a t a 码并不 互为对偶码。 令人震惊的成果出现在1 9 9 4 年。h a i 砌o i l s 【3 】等人的杰出工作表明，k e r d o c k 码可以 通过一个称为c h y 映射的变换从环纽上的一个循环码得到【3 】【4 】，而环z 4 上k e r d o c k 码的对 偶码在g r a y 映射下的二元象是p r e p a r a t a 码。这说明二元域上非线性码的构造可以转化为 环魂上线性循环码的构造，这大大降低了非线性码构造、编码和译码的难度。这个发现是 重要的，它打开了编码理论研究的新方向一环上的编码理论。从此以后，很多编码学家 们将它们的研究重点从域上转移到环上来。越来越多的性能优异的非线性码被人们所发 现。由于解码的过程仍然比较困难，非线性码距离实际的应用仍然有一段距离。然而，非 线性码的优越性是不容质疑的，编码理论的明天正在于非线性码。 本文的研究针对环上的线性码的一个重要问题：线性码及其对偶码的重量计数多项 式之间的m a c w i l l i a m s 恒等式。我们知道衡量一个码的性能的最重要的参数是极小距离， 而线性码的极小距离等于它的极小重量。码的重量计数多项式刻画了码的重量分布，是 研究码的重量分布的有力工具。所谓的m a c w i l l i a m s 恒等式是由m a c w i l l i a m s 首先发现的 存在于个码及其对偶码的重量计数多项式之间的等式关系。利用m a c w i l l i a m s 恒等式可 以很容易的从一个码的重量计数多项式得到其对偶码的重量计数多项式。这大大简化了 华北电力大学硕士学位论文 某些码的重量分布的研究过程。 m a c w i l l i a m s 【5 】给出了域r 上线性码汉明重量的m a c w i l l i a m s 恒等式，l ( 1 e m m 在文 献 6 】中把此恒等式推广到模七剩余类上，c o n w a y 和s l o a n e 在文献【7 】中给出了对称形式 的m a c w i l l i a m s 恒等式。文献【8 】研究了环么上对称形式的m a c w i l l i a m s 恒等式。文献 9 】研 究了环足+ u 局【1 0 】上的m a c 、矾l l i a m s 恒等式。据本文作者所知，这是对于形如r + 缸r 一 类环上线性码的m a c 、m l l i a 麟恒等式的首次研究。但是此环存在着到魂的乘法同态，它 与【8 】的结果基本一致，因此不具有一般性。随之而来的问题是定义在任意有限环上的m a c w i l l i a m s 恒等式是否存在? 环b + u b 是非线性编码中最为重要的一类的环之一，包含了 环见+ u 昂，咫+ u 忍等几种最为重要的环。本文研究了定义在此类环上线性码的m a c 、m l l i a i i l s 恒等式。进而将已有的结论推广到更为一般的一类环昂+ u b + u 七一1 b 上【l l 】【1 2 】 1 3 】 【1 4 】上。此环常用来进行最优频率跳跃序列的构造，因此对于它的研究具有一定的现实意 义。 2 华北电力大学硕士学位论文 第二章基本概念 同域相比，环的代数结构也许不够“完美 ，因为环上存在着零因子。但是环是远 比域普遍的代数结构，m c d o n a l d 【1 5 】曾经语言，将环做为编码研究的一般平台更为妥 当。h a m m o n s 【3 】等人后来的发现证实了这一点。 2 1 环的定义 首先介绍一下我们所要研究的环 t = 昂+ 缸昂+ + 钍一1 b = 0 0 + 口l u + o k l 铲一1 l 啦b ，i = o ，1 ，七一1 ) 其中p 是素数，忌2 ，昂是一个有限域。在编码理论研究中，通常取昂为z p ，下面的论述 中我们一律使用有限域乙，以下不在赘述。环r = 昂+ 缸耳是环t 当= 2 时的情形。 域昂上的加法和乘法用符号0 ”和“0 ”来表示。定义环t 上的加法“+ ”和乘法“”为： 对v x = 印+ 口1 乱+ + 口七一l 舻，y = 6 0 + 6 l h + + 酞一1 钆一1 t x 十y = 0 0o6 0 + ( o lo6 1 ) 心+ + ( 口七一lok 1 ) t 知一1 巧 =( 口0 + n l u + + 口七一1 钍七一1 ) ( 6 j d + 6 l t 正+ + k 一1 乱七一1 ) m o d 乱七 = ( ( 吼o ) ) 牡吖) m o d u 七 t j p 是t 上礼元组的集合，也即是p = ( z l ，z 2 ，z 住) 陬瓦l = l ，n ) 。 2 m 的任一个非空集合e 称为丁上一个码，简称为t 码，扎是该码的长度。p 上的n 元组 称为字，c 中的n 元组称为c 中的码字。 c 7 和c 都是t 上长为扎的码。如果c c ，c 称为c 的子码。 定义p 上的加法“+ 为对v x = l ，娩，z n ) ，y = ( y 1 ，沈，) p ， x + y = 0 l + 玑，z 2 + 蚴，z f i + 孙) p 关于上面定义的加法构成一个阶为p 七n 的加法交换群。p 的一个子群称为? 上一 个佗长的线性码，称为t 线性码。 对v x = ( z l ，z 2 ，z n ) ，y = ( 1 ，耽，) p ，x 和y 的内积定义为： x y = 【z l y l + z 2 沈+ + z 几玑) 3 华北电力大学硕士学位论文 如果x y = 0 则称x ，y 相互正交。 令c 是t 上一个n 长的t 线性码，定义 c 上= x p i x y = o ，v y c ) 容易验证c 上也是p 的一个子群，因此也是一个t 线性码，称为c 的对偶码。如果 cc 萨，c 称为是一个自正交码。如果c = 萨，c 称为是一个自对偶码。 2 2 完全重量计数和完全重量计数多项式 首先我们引入完全重量计数的概念。c 是n 长的t 码，n 是t 中的一个元素，也即是 o = 口o + + o 七一l u 七一1 8 t 0 ，i = o ，1 ，七一1 ) 对于v x = l ，沈，z n ) p ，定义x 在。的重量为 其中6 是k r o n e c k e r 函数： = 吉竺蓁： 码c 的完全重量计数多项式( c o m p l e t ew e i 曲te n u m e r a 的r ) 定义为是含有矿个未知数 凰，耳一l + + ( p 1 ) 铲一1 的n 次多项式： 眠( ，一i + 嘶_ 1 ) 扩t ) = 群水 c ct r 完全重量计数多项式通常记为： 舢e c ( ，x p 一1 + + ( p 1 ) u ) = 眠( 弱，砗一1 + + 扫一1 ) 小一i ) 2 3 对称重量计数和对称重量计数多项式 如果两个t 码c l 和岛拥有完全相同的纠错能力，则将此两码视为等价的。关于码的等 价的定义有多种，为了方便起见，在这里我们使用数乘等价( s c a l a rm u i t i p l ee q u i v a l e n t ) 的 定义。关于码的等价，请参阅【l 】【1 6 】。 定义2 1 【1 6 】令仃是一个关于n 个位置的置换。对于l = l ，2 ，礼，令 死：t _ t 表示对t 中元素s 乘以一个非零f 也不是零因子j 的刻度f s c 口刎啦： m s = q t s 4 o 如 n 汹 i i x o 埘 华北电力大学硕士学位论文 那么如下映射： p ：p_p p ( c 1 ，c 2 ，岛) = ( 丌1 ( 劬( 1 ) ，丌2 ( ( 2 ) ) ，7 h ( ( n ) ) ) 称为一个n 维单调变换m d 砌册工f 鲫讲m d ，l d ，l 湖f m ，l s 励册口f f d ，z j 定义2 2t 上两个【，m 】线性码c l 和已称为是数乘等价的，如果存在一个n 维单调变 换“使得 p ( c 1 ) = 已 这里肛( c 1 ) = 肛( c ) l c c 1 ) 数乘等价的t 一码，其完全重量计数多项式可能不同。例如环忍+ u 乃( 环t 的一种) 上 两个数乘等价的码c l = ( o ，o ) ，( u ，乱) ) 和岛= ( o ，o ) ，( 2 u ，2 u ) ) 其完全重量计数多项式分 别为：粥+ 霹和瑚+ 硫。为了使得数乘等价的码拥有完全相同的重量计数多项式，我 们引入“对称重量计数”的概念。 首先对环t 中的元素做一个划分。 定义2 3 划分环t 中元素为如下三个集合： d o = 0 ) ，d l = 订 o ) ，伤= r 订 “示性”函数( ) 定义为： j ( o ) = i 如果o 皿，t = o ，1 ，2 定义2 4 对称的重量计数多项式r j y m ，l g 毗已dm 硝g 胁绷h m p r 口f d 肚 s 叫e c ( 弱，五，尥) = 伽印( 墨( o ) ，蜀( 1 ) ，蜀( p 一1 + u ( p 1 ) + + ( p 1 ) 矿一- ) 命题2 1 如果两个t 码岛和c 2 是数乘等价的，则他们拥有完全相同的对称重量计数 多项式 证明由于c 1 和c 2 是数乘等价的，因此存在从c l 到岛的单调变换p 使得： ， p ( c 1 ) = 岛 对v c = ( c 1 ，) c 1 ，在已中存在着唯一的码字p ( c ) 与其对应： p ( c ) = ( 7 r l ( c 口( 1 ) ) ，7 r n ( c 矗( n ) ) ) 已 对v s 岛，歹= 0 ，1 ，2 ， 死s2 口 s 因为q t 既不是零也不是零因子，根据d i 的定义可知 q t s 岛 华北电力大学硕士学位论文 因此 肛( c ) 对应的对称重量计数多项式为： 因此 ，( 巩s ) = ( s ) = 歹 vv 人j ( 万t ( 1 1 ) ) ) j ( ( c 。( 。) ) ) 五( 郇) ) ( 坼) ) 蜀( c 。) 局( c ，i ) s 叫e c 。( ，墨，恐) = s 叫e c 2 ( ，墨，五) 6 华北电力大学硕士学位论文 第三章环r = 昂+ 乱昂上线性码的m a c w i l l i a 麟恒等式 首先我们研究环r = b + 缸b 上的码。环r 是环丁当后= 2 的情形，因此上面对于丁的 结论对于环兄都成立。类似的，我们将环兄上的码称为r 一码，口的一个加法子群称为一 个r 线性码。由码c 的完全重量计数多项式不难看出，它刻画了码c 中码字重量分布的 情况。m a c w i l l i a m s 恒等式是一个码和它的对偶码的重量计数多项式之间满足的等式。使 用m a c w i l l i a m s 可以大大的简化寻找一个码的对偶码的重量分布的过程。 3 1 内积展开函数 定义3 1 定义函数7 l ( ) 是从r = 昂+ 乱昂到整数z 的映射，对比= a + 阮： 7 - ( z ) = 7 i ( n + 乩) = o + 6 定义内积展开函数j ( ) 是从冗到复数域c 的： 了 ) = e r ( 童) 2 弧p v z r 那么v ) 【= ( 。1 ，z 2 ，z n ) ，y = ( 3 1 ，耽，) 兄， ( 3 1 ) j ( x y ) = ，( z 1 3 1 ) ，( z n 蜘) ( 3 2 ) 注：由( 3 1 ) 容易导出( 3 2 ) ，并且上述内积展开是唯一的； 设x = ( 。l ，z 2 ，。n ) ，y = ( 爹l ，沈，) 舻，则x ，y 的内积为 x y2z l 玑+ z 2 抛+ + z n 蜘 记 并且令 其中七1 ，如z 。那么 z 1 暑，1 2o l + 6 1 u z 2 耽= 口2 + 6 2 u z n = + 6 n 乱 8 l + 口2 + + = 8 log 2o 0 盘n + 是1 p 6 1 + 6 2 + + 6 n = 6 1o 6 2o 0k + 尼2 p 7 华北电力大学硕士学位论文 引理3 1 证明 j ( x y ) = 了( z 1 可1 + z 2 耽+ + 。竹骱) = j ( ( o l + 6 l u ) + + ( o n + 6 礼u ) ) ，( ( 8 lo a 2o o8 竹) + ( 6 1o 幻o ok ) t 上) e ( ( 口l 。口2 。) + ( 6 1 。6 2 。k ) ) 等 e ( 口l 。n 2 。口n ) 十七1 p + ( 6 l 。6 2 。k ) + 七2 p ) 等 e 似l + 口2 + + 口n + 6 l + 6 2 + + 6 n ) 等 e ( 口l + 6 1 ) 等e ( 口2 + 6 2 ) 等e ( 口n + h ) 等 = ，( z l 可1 ) j ( z 2 耽) j ( z n ) j ( 后) = oj ( 七) = o 詹r七t r j ( 后) = 七r d z b z p 厂厂 | 一 j ( o + 沈) e ( 口+ 6 ) 譬 篆挈筹 j ( 尼) = j ( 乱。) 知t r 口z ：fe ；2 而 z r 一 口磊 1 一e 2 州 = 一 1 一e 2 r p =0 3 2 推广的h a d a m a r d 变换 定义3 2f 推广的h 口如m 口埘变换【1 7 】j ，是定义在印上取值于 c 弱，x 1 一，x o 一1 “( p 1 ) ) 】 的函数，的黜m 口磁变换定义为： 8 ( 3 3 ) r撅 y，jy x ， 炒 l l x 华北电力大学硕士学位论文 定理3 2 设c 是r 上长为礼的线性码，v x ，y 舻 证明 ，( x ) = x c 当y c 上时， ，( x ) = x c 上 j ( x y ) ，( y ) ，( y ) j ( x y ) + ，( y ) y c 上 x c y r n c j _ ，( x y ) = j ( z l 型l + z 2 抛+ z n 如) t ，( x y ) x c = l ，( z l 耖1 ) j ( z 2 可2 ) ，( z n 3 h ) 一p 警鍪1 r ( z 玑) = ep 一= 1 、 =1 最后一个等式成立是因为由x y = o 知 所以 因此 z i 玑三0 m o d p 丁( 甄玑) = m p m z ，( y ) ，( x y ) = 蚓，( y ) y c 上 x c y c 上 当y 舻c 上时，设c 为r 上h ，纠线性码，假设c 的一个生成矩阵为： g = ( 至) 其中9 1 ，9 2 ，甑都是r 上1 行礼列的向量。 设z 的信息位为a = ( 0 1 ，) ，那么。= a g x y = ( o g ) y = ( n l ( g l y ) + 0 2 ( 9 2 y ) 8 ( g 七y ) ) 9 ( 3 4 ) 对八 触 l 一眵 + y，y xj 缈 触 汹 华北电力大学硕士学位论文 因此 y r n c 上 ，( y ) j ( x y ) x c = ，( y ) 了( n l ( g y ) + 0 2 ( 9 2 y ) + + 吼( g 妊y ) ) y r n c 上 o l rd 2 ro 七r = ，( y ) j ( n l ( g l y ) ) j ( o 。( 9 2 y ) ) ，( 钒( g 七y ) ) y r n c 上 口l r 0 2 rd 知r ：f ：一 y f 卜c 上 =0 隐m 旭隆m 如删) 5 ， 口l r口k 只 最后一个等式成立是因为对于式( 3 5 ) 中的任一个积项都满足 j ( 吼( y ) = o 口r 分情况讨论如下： c 弱e1 歌y = o ，( 3 7 ) 式显然为0 ； c a s e2g i y = 尼乱，七= 1 ，2 ，p 一1 ，由于 ( n + 阮) 尼u = o 惑“o 乙 当吼跑遍r 时，啦慨y ) 按照相等的概率取值 七牡七= o ，1 ，p 一1 ( 3 6 ) ( 3 7 ) 根据引理3 1 司知( 3 7 ) 式为o ： c 邪e3 y 托，七= o ，1 ，p 一1 ，当口t 跑遍r 时，锄( y ) 是r 中元素的一个置换，根 据引理3 1 可知( 3 7 ) 式为0 。 综合以上可知 ，( x ) = l c i ，( y ) x c y c 上 即 1 荟，( y ) 2 高薹舡) y c 上 x c 也即是 三，( x ) 2 高薹舡)x c 上 x c 华北电力大学硕士学位论文 3 3 环r 上线性码完全重量计数的m a c w i l l i a m s 恒等式 定理3 3r 完全重量计数的 纪c 啪z z 泐淞恒等式j 设c 是r 上n 长线性码，c 上是只的对偶 码，则 伽e c 上( ，x l ，五( p 1 ) 托( p 1 ) ) ) 高倒e c ( 篆j c 。忌，拖，篆，c 一1 + 乱。一1 m 七，托) c 3 固 证明对v x 舻，令，( x ) = 潆x x f l x 狴i 茄警硝划，我们首先计算，( x ) 的 h a d 锄a r d 变换，( x ) ，( x ) = j ( x y ) ，( y ) y 舻 y 舻 j ( x y ) 带y x 严x 翟黼y 根据j ( ) 的性质，如果x = l ，z n ) ，y = ( 秒1 ，玑) 舻，那么可以将内积展开为 已知对于钝冗 ，( x y ) = j ( z 1 秒1 ) 了( z 2 耽) j ( 。n 孙) ( y ) = 瓦，掣l + 以，抛+ + 以，珈 其中6 是k m n c c k e r 函数，那么，( 。) 可以写成 ，( x ) = ( ，( 聊) 霜mx p x 长蒜黜产1 ) y r l ( j ) 对帆x 卜栅黜，“) w ，虬) 睡删，兄) n j 兄 嘶( 正) ( 篆删氘) 最后一个等式成立是因为z 中等于歹的分量以恰有哟 ) 个。 l l 华北电力大学硕士学位论文 对于v c c ， 根据定理3 2 和上式可知 ，( c ) = 群。c x y l c x 善搿三；) ) c = 带群水x 娑i 鬻爿：；( c ) = m ) 2 高善缸) = 高三玉( 篆j c 歹后，虬) 嘶忙 2 高倒e c ( 善，c 。惫，虬，篆j c l 忌，溉，篆j c 一l + 乱叫) 七) 风) 3 4 对称重量计数的m a c w i l l i a m s 恒等式 引理3 4 集合d t 由定池? 给出，那么在环冗= b + 钆昂中 d 0 = o d l = 后i 七= 阮，6 z p o ) ) d 2 = 忌i 七= n + 阮，o 名 o ，6 磊) 2 j ( 七) = 1 ；j ( 七) = 一1 ；j ( 忌) = o 七d 0七d l七d 2 i 如果i ，j d l ，f = o ，1 ，2 ，那么 j ( i 七) = j ( 歹尼) s = o ，1 ，2 七d 七d 。 证明( 1 ) 是显然；( 2 ) 的证明与引理3 1 类似；只需证明( 3 ) 。令 屉= 尼1 + 七2 u ， = 口+ 阮，j = c + d 仳， 凫1 ，忌2 ，o ，6 ，c ，d z ； 华北电力大学硕士学位论文 则 同理可得 j ( 嘲= j ( 嘲十j ( i 七) + j ( = ，( o ) + j ( + j ( i 尼) = 1 + j ( + j ( i 后) 一、一 、 下面分情况进行讨论： c 嬲e 1i ，歹d o 时： ，( 歹七) = 1 + j ( 歹七) + j ( 歹尼) 七r七d l知。d 2 ，( = j ( 歹七) = _ _ 1 ) j ( o ) = p 一1 七d l凫d l ，( 鳓= j o 七) = 2 一p ) j ( o ) = p 2 一p 七d 2七d 2 因此命题成立； c 嬲e 2z ，j d 1 时，对i = 口+ 阮做讨论可知，由于 口= o ，6 磊 o ) 若尼d l ，( t 七) =，( ( 阮) ( 乜u ) ) 七d l 幻z ；t o l = p 1 ) j ( 0 ) = p l 若尼d 2 ，( = 七d 2 j ( 乩( + 如钆) ) 七1 z ； o ) 七2 z p = ，( 6 七t u ) 乜z p 七1 乃t o = p ，( 6 后l 也) 七l z p o = p j ( t ) d 1 = 一p 因此对j d l 做同样讨论可知命题成立； 1 3 华北电力大学硕士学位论文 c 鼬e 3i ，歹d 2 时，对i = o + 阮做讨论可知，由于 若七d l o 名 o ) 6 名 j ( 砌=j ( ( 。+ 乩) 尼。u ) 七d l 乜z j o ) = ，( 乜口u ) 乜名 0 = 邢) d l = 一1 若七d 2 j ( = j ( t ) = o 七d 2t d 2 等式成立是因为当z ，七d 2 时，令七取遍d 2 ，则 i 七l 尼d 2 ) 是d 2 的一个置换。对歹做 讨论可得同样结论。因此对于t ，歹d 2 的情况，引理3 4 ( 3 ) 也是成立的。 综上可知，引理3 4 成立。 定理3 5f 对称重量计数的m a c 惭盯肠船恒等式j c 是兄上礼长的线性码，那么 s 叫e c 上( ，x 1 ，恐) = 高s 叫e c ( 凰+ ( p 一1 ) 墨十扩一p ) 恐，弱+ 。一1 ) 墨一竭，一x ) 证明定义“示性函数”n ) ：讹觑 ，( o ) = t ，o r ，主= o ，1 ，2 。 5 叫讧( 弱，墨，尥) = 倒e c 上( 墨( o ) ，局( 1 ) ，蜀( p l + u ( p 1 ) ) ) = 高舢e c ( 篆j c 。尼，局c 蛳篆j c l 七，蜀c 协，篆了c c 一1 ，+ u 一1 m ，托c 妫) = 高伽e c ( 娄丕j c 。尼，咒，妾丕了c 白一1 + 。一1 m ，托) c 3 习 l 。i 8 = o 翩：i ) js = o 七z ) 若t j 对应的元素属于同一个集合眈，根据引理3 4 ( 3 ) 可知 j ( 哟凰+ j ( 蚴x 1 + ，( i 尼) 托= j ( 歹后) 凰+ j ( j 忌) x - 七d 0七d l七d 2 七d 0七d 1 + j ( j ) 恐 七d 2 1 4 华北电力大学硕士学位论文 也即是 那么 c 3 渤= 高s 谢e c ( 妻轰叩妨墨嵩丕驰竞风砉丕即老，恐) 2 南s 叫e c ( + 一1 ) x 1 + 舻一p ) 恐，弱+ ( p 一1 ) x 1 一p 恐， 一x - ) 最后一个等式成立是根据引理3 4 。 推论3 6 环易+ u f 2 上线性码的l 如c m z z 谊脚恒等式 9 】为： s 叫e c 上( 凰，x l ，咒) = 南s 伽e c ( + x l + 2 恐，凰+ x l 一2 ，一x 1 ) 证明将p = 2 代入定理3 5 验证即可，这与【9 】中的结果一致( 注意我们所使用的字母 的顺序有所不同) 。 推论3 7 环r + u b 上线性码的 亿c 懒f z 泐淞恒等式为： 删e c 上( 蜀，x l ，恐) 2 亩s 叫e c ( + 2 x l + 6 ，+ 2 墨一3 恐，一x 1 ) 证明利用定理3 5 立得。 3 5 例子 我们将通过一个例子来展示定理3 5 的应用。 例子环尼+ 让乃【1 8 】【1 9 】上一个线性码c 的 如c m z f 肠m j 恒等式 环玛+ 铭玛= 玛心j 舻上长为2 的线性码c = ( 2 铭，钍) ，( 珏，统) ，( o ，o ) ，其完全重量计 数多项式为： 删e c ( 弱，墨，恐讹却+ 2 ) = 搿+ 2 k 恐u 对称形式的重量计数多项式为： 舢e c m ，x 1 ，恐) = 弼+ 2 砰 根据推论3 7 ，我们可以容易的求出码c 的对偶码c 上的对称重量计数多项式 s 彬e c 上( 弱，x l ，砭) 2 高s 叫e c ( + 2 x l + 6 恐，+ 2 x l 一3 咒，一x 1 ) = 去s 加e c ( + 2 x l + 6 恐，+ 2 x 1 3 尼，凰一x 1 ) = 去( ( + 2 x l + 6 恐) 2 + 2 ( + 2 x l 一3 托) 2 ) = 粥+ 4 研+ 1 8 砑+ 4 x l x 批以 胁 2 鲫 = k 派 以 慨 2 枷 华北电力大学硕士学位论文 下面我们验证结果的正确性，首先我们求出c 上，再按定义求c 上的对称重量计数多项 式： c 上是由 g = ( 三三) 生成的线性码，它的所有码字为如下所列： c = ( o ，o ) ，( 1 ，1 ) ，( 2 ，2 ) ，( u ，u ) ，( t + 1 ，t + 1 ) ，( 让+ 2 ，札+ 2 ) ，( 2 u ，2 t 上) ， ( 2 u + 1 ，2 u + 1 ) ，( 2 t 正+ 2 ，2 也+ 2 ) ，( 0 ，钆) ，( 1 ，u + 1 ) ，( 2 ，+ 2 ) ， ，2 u ) ， ( 牡+ 1 ，2 乱+ 1 ) ，( 乱+ 2 ，2 让+ 2 ) ，( 2 u ，o ) ，( 2 u + 1 ，1 ) ，( 2 u + 2 ，2 ) ，( 0 ，2 u ) ， ( 1 ，2 u + 1 ) ，( 2 ，2 + 2 u ) ，( 让，0 ) ，( u + l ，1 ) ，( u + 2 ，2 ) ，( 2 牡，u ) ，( 2 u + 1 ，u + 1 ) ， ( 2 + 2 u ，钆+ 2 ) 再由对称重量计数多项式的定义可得： s 叫e c 上( 拖，x 1 ，咒) = 瑶+ 4 研十1 8 碹+ 4 x 1 与我们按照推论3 7 求出的结果完全相同，但是计算量增加很多。 华北电力大学硕士学位论文 第四章环t = 昂+ u 昂+ + u 七一1 昂上的m a c w i l l i a m s 恒等式 我们将第三章中有关环兄上线性码的结论推广到环丁上。我们知道环r 是环丁的一种 特例，因此有关环t 上相应结论的证明思路和环r 完全类似。为了简便起见，我们只写出 关键步骤。 4 1 引理 定义4 1 定义内积展开函数，( ) 如下：对于 比= 0 0 + 啪1 + + u 七一1 n 七一l t 定义 j ( c ) ：e ( 旨m ) 等 ( 4 1 ) 对v x = l ，z 2 ，z n ) ，y = ( 秒1 ，沈，) p 有 了( x y ) =j ( z l 可l + z 2 驰+ + z n ) = j ( z 1 秒1 ) ，( 。n 3 h ) ( 4 2 ) 注：由( 4 1 ) 式可以容易的得出( 4 2 ) 式；上述内积展开是唯一的，其证明过程类似于 环乃+ u b 的情形，对于 比l = 口o + o l “+ + o _ | b l 铲，可l = 6 0 + 6 1 u + + 6 七一1 铲一1 丁 令 啦+ 6 t = 毗。玩+ t 印，如z ，i = o ，后一1 则 了( 。1 + 爹1 ) =了( 知o + ( 8 1o 6 1 ) 铭+ + ( g 南一lok 一1 ) 铭知一1 ) ：e ( 留( 毗。6 ) ) 等 ：e ( 留心。挑) + 譬t t p ) 等 ：e ( 留( a t + 6 t ) ) 等 =j ( z 1 ) j ( y 1 ) 因此对于v x = ( z 1 ，z 2 ，z n ) ，y = ( 可1 ，可2 ，鼽) p ，有 j ( x y ) = j ( z l