（应用数学专业论文）有限环上纠错码的rosenbloomtsfasman距离研究.pdf

有限环上纠错码的r o s e n b l o o m t s f a s m a n 距离研究 摘要 设ccf 是一个线性码令玎= m s ，m ，s 都是正整数，则c 中元素可以看成 是域上的一个矩阵户= ( 功) ，1 抠m ，1 _ ，j ，p u f q 定义p 的 r o s e n b l o o m t s f a s m m a 重量( 简称为r t 重量，或p 重量) 为： w ( p ) = m a x j i p ，o ) f = l 对任意的乞上的矩阵只q ，定义尸，q 的i 玎距离为( 尸，q ) = w n ( p - q ) 当j = 1 时， 它就是一般的h a m m i n g 距离，可见r t 距离是一般的h a m m i n g 距离的推广， 是一种非h a m m i n g 距离因此对它的研究显然是有理论意义与实用价值的，这 已经引起了国内外编码与密码学者的极大关注 码的各种重量分：布一直是编码理论的一个重要的研究方向无论是在域上 还是环上，利用线性码的码字的各种重量分布来研究其对偶码的相应重量分布 都是很有意义的 本文研究了有限环上线性码的r t 距离和r t 重量的分布问题分别定义了 环m 。( 最+ 蜗) 、鸠。( z 4 ) 上线性码关于r t 距离的各种重量计数器，给出了其 上线性码关于各种重量计数器的m a c w i l l i a m s 恒等式：并对二元码定义了一种 r “义r t 重量，研究了广义r t 重量的性质，确定了一些常见类型码的广义r t 重量的值最后，对全文作了一个总结，并对未来可能的发展方向提出了一些 有待研究的问题 关键词：线性码；对偶码；r t 距离；广义r t 重量；重量计数器；m a c w i l l i a m s 恒等式 r e s e a r c ho nt h er o s e n b l o o m t s f a s m a nm e t r i c o fe r r o r - c o r r e c t i n gc o d e so v e rf i n i t er i n g s a b s t r a c t l e tccfb eal i n e a rc o d e l e t 刀= m s ，ma n dsb e i n gp o s i t i v ei n t e g e r s t h e nt h ee l e m e n t so fcc a nb ev i e w e da sm a t r i c e s p = ( 既) ，1 f m ，l 歹j ， w i t he n t r i e si n 只t h er o s e n b l o o m t s f a s m a nw e i g h t ( r t ，o rp ，i ns h o r t ) o fp i sd e f i n e da s ： m w ( p ) = m a x jl 岛0 ) i = 1 a n dt h er tm e t r i co fpa n dqi sd e f i n e da sp ( p ，q ) = w ( 尸一q ) f o rs = 1 ，t h e r tm e t r i ci sj u s tt h eu s u a lh a m m i n gm e t r i c w ec a ns e et h a tt h er tm e t r i ci sa n o n h a m m i n gm e t r i ca n di s ag e n e r a l i z a t i o no ft h eu s u a lh a m m i n gm e t r i c ，s ot h e s t u d yo fi t i sv e r ys i g n i f i c a n tf r o mb o t hat h e o r e t i c a la n dap r a c t i c a lv i e w p o i n t t h e r eh a sb e e nar e c e n tg r o w t ho fi n t e r e s ti nc o d e sw i t hr e s p e c tt ot h i sr tm e t r i c t h ew e i g h td i s t r i b u t i o no fc o d e s ，i nac l a s s i c a lc o d i n gt h e o r y ，i sa ni m p o r t a n t i n v e s t i g a t i o nf i e l d w h e t h e ri nf i e l d so ri nr i n g s ，u s i n gw e i g h td i s t r i b u t i o no fl i n e a r c o d e st oe x p l o r et h ew e i g h td i s t r i b u t i o no ft h e i rd u a lc o d e si sv e r ys i g n i f i c a n t i nt h i sp a p e r ，t h ed i s t r i b u t i o no fl i n e a rc o d e sw i t hr e s p e c tt ot h er tm e t r i ca n d t h er tw e i g h to v e rf i n i t er i n g si se x p l o r e d s o m ek i n d so fw e i g h te n u m e r a t o r sw i t h r e s p e c tt ot h er tm e t r i co v e r 坂。，( 五+ 衍) 2a n d 鸩。，( z 4 ) r i n g sa r ed e f i n e d ，a n d t h ec o r r e s p o n d i n gm a c w i l l i a m si d e n t i t i e sa r ep r o v e nt o o a l s o ，ad e f i n i t i o no ft h e g e n e r a l i z e dr tw e i g h t so fb i n a r yc o d e s i s o b t a i n e d ，b a s i cp r o p e r t i e s o ft h e g e n e r a l i z e dw e i g h t sa r ed e r i v e d ，a n dt h ev a l u e so ft h e s ew e i g h t sf o rw e l l k n o w n c l a s s e so fc o d e sa r ed e t e r m i n e dt o o a tl a s t ，w es u m m a r i z et h ep a p e r ，a n dp u t f o r w o r ds o m ep r o b l e m sw h i c hw i l lb es o m ed e v e l o p m e n t a ld i r e c t i o ni nt h ef u t u r e k e y w o r d s ：l i n e a rc o d e ；d u a lc o d e ；r tm e t r i c ；g e n e r a l i z e dr tw e i g h t s ；w e i g h t e n u m e r a t o r ；m a c w i l l i a m si d e n t i t y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成 果据我所知，除了文中特别加以标志和致谢的地方外，论文中不包含其他人已经发表 或撰写过的研究成果，也不包含为获得 金罄王些太堂 或其他教育机构的学位或证书 而使用过的材料与我一同3 2 作的同志对本研究所做的任何贡献均已在论文中作了明确 的说明并表示谢意 学位做作者擀币啦签字魄加坼, q ，7 日 i 学位论文版权使用授权书 本学位论文作者完全了解 金目巴王些太堂 有关保留、使用学位论文的规定- 有权 保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅或借阅本人 授权 金鏖互丝左堂 可以将学位论文的全部或部分论文内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文 ( 保密的学位论文在解密后适用本授权书) 孙q 搀 签字日期：一彦年多月，7 曰 f 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签 签字日 电话： 邮编： 致谢 三年的时间稍纵即逝，研究生阶段的学习生活虽然短暂，但却会影响着我 的一生 首先，我要衷心地感谓拇圪的硕士生导师朱士信教授几年来对我的教诲和支 持感谢朱老师给予我学业上的谆谆教导以及生活上的关怀和帮助朱老师严 谨的治学作风以及对学生热心指导，精心培养的精神将使我终身难忘值此论 文完成之际，谨向我的导师朱士信教授致以最诚挚的谢意! 同时，我要衷心地感谢所有的在研究生学习期间给予我悉心关怀和热心帮 助的数学系的老师们，感谢师兄李平、童宏玺、开晓山、施敏加、唐淼，师姐 王冬银、韩牟、王敏秋等感谢几年来与我朝夕相处的同学陈安顺、张道福、 宛金龙、姜光峰和孙琳等，与他们的讨论开拓了我的思路，使我在学习上和论 文写作中受益非浅 另外，我还要感谢我的父母，正是他们的默默付出和全力支持，才使我能 够顺利完成学业，在此表示我由衷的感谢 最后，还要感谢审阅硕士论文和出席硕士论文答辩会的各位专家学者，感 谢他们在百忙中给予批评指正 作者：许和乾 2 0 0 8 年3 月1 日 第一章绪论 1 1 引言 s h a n n o n 信息论的诞生是以其发表的通信的数学理论( am a t h e m a t i c a l t h e o r yo fc o m m u n i c a t i o n ) 【1 】为标志的。s h a n n o n 信息论不仅建立了信源和信道 编码定理，给出了有效性的极限，而且为人们明确地指出了实现有效而可靠的 通信的必由之路是数字化和编码，这是通信技术领域革命的数学或理论基础信 息论在研究信源和信道编码定理时所用的方法都是随机编码的方法，它是证明 定理的重要工具，但为非构造性的，因此不能提供具体的可实现的编、译码方 法根据s h a n n o n 的思想，由h a m m i n g 2 】( 1 9 5 0 ) 开始的可构造的编码理论在 2 0 世纪5 0 年代末和6 0 年代褥到了很大的发展，成为信息论中的一个重要分支 纠错编码理论h a m m i n g 、b o s e 、c h a u d h u r i 、h o c q u e n 曲e m ( b c h ) 1 3 - 5 】、 m a s s e y t 6 - 8 】、m a c w i l l i a m s t 9 - 1 1 1 、g o p p a t l 2 - 13 1 、n e c h a e v 14 1 、冯贵良【1 5 1 6 】等纠错码 理论专家先后给出了一系列设计好码和有效译码的方法而后，纠错码受到了 越来越多的通信和数学工作者，特别是数学家的重视，使纠错码无论在理论上 还是在实际中都得到飞速发展后来，h a m m o n s 等人证明了一些高效的二元非 线性码，如p r e p a r a t a 码、k e r d o c k 码等，可视为环z 4 上循环码在g r a y 映射下 的像，从而使环z 4 乃至更一般的有限环上的纠错编码理论的研究进入一个全新 方向 纠错编码理论的一个重要研究方向是码的各种重量分布r t ( 或p ) 重量 最初是n i e d e r r e i t e r 在研究数值积分中具有最优一致分布性质的点格时提出来 的它源于不规则分布理论的一个基本问题：怎样构造具有较小d i s c r e p a n c y 的 点集和序列? 具有较小d i s c r e p a n c y 的点集和序列在拟m o n t ec a r l o 积分以及数 值分析中都有很重要的应用因此，上述这个基本问题得到了广泛的关注，数 学家们提出了很多种构造方法构造方法之一是h a m m e r s l e y h a l t o n 构造法， 该方法的目的有两个：一是找到能快速实现的点集和序列，二是使两个著名的 d i s c r e p a n c y 界中的常数更小用构造好的格点的方法可以实现第一个目的，而 第二个目的相对难以实现直到19 8 2 年，f a u r e 提出了一个方法较好的达到了 第二个目的【7 1 利用有限域理论，n i e d e r r e i t e r 进一步改进了f a u r e 的方法，于1 9 8 7 年提出 了( t ，m ，s ) 一n e t s 和( t ，s ) 序列的理论【18 1 其中，( t ，m ，s ) n e t s 理论是构造s 维单位 块5 = 【0 ，1 ) 5 上具有小d i s c r e p a n c y 的点集的有力工具这里，为了叙述方便，我 们首先给出( f ，m ，s ) - n e t s 的定义，更详细的性质见参考文献 19 】 设f ，m ，s 和b 是整数，且0 f m ，s 1 ，b 2 ，j 一维单位块i 。= 【o ，1 ) 5 上一个含 有b ”个点的点集p 被称为一个6 一b a s e ( f ，m ，s ) - n e t s ，如果对1 5 = 0 ，1 ) 。上任意一 个型如下式的区间块j ，= 【q 6 一面，( 口+ 1 ) b - d , ) i = l 其中整数4 - 0 ，0 a ， r ) 个错误，则要求d t + e + l ： ( 4 ) 纠正f 个错误和p 个删除，则要求d 2 t + p + 1 因此今后也经常用 ，2 ，k ，d 】表示一个长为n ，维数是k ，最小( h a m m i n g ) 距 离为d 的线性码，而用( 珂，m ，d ) 表示一个长为, ，码字个数为m ，最小( h a m m i n g ) 距离为d 的非线性码对于一个加，k ，d 】线性码，若码字x = ( 而，屯，x n ) ， y = ( y l ，y 2 ，只) c ，则由线性空间的封闭性可知x + y c ，所以必有 d ( x ，y ) = w ( x + y ) 因此，一个 n 9 k ，d 】线性码c 的最小h a m m i n g 距离必等于码c 中非零码字的最小h a m m i n g 重量，由此可得知下定理 定理2 1 1 2 一个【刀，k ，卅线性码c 的最小h a m m i n g 距离等于c 中非零码字 的最小h a m m i n g 重量即 d = m i n w c x ) i g x c ，x 0 关于一个研，k ，d 】线性码c 的最小h a m m i n g 距离d ，还有如下非常重要的一 个定理： 定理2 1 1 3 ( s i n g l e t o n 边界) 设c 是一个m ，k ，d 】线性码，则：d n - k + 1 2 1 2 码的校验矩阵与生成矩阵 设c 是c 上的一个 刀，k 】线性码，c 的码字共有q k 个 如果设q = ( 2 1 19 q 2 ，) ，c 2 = ( c 2 l ，c 2 2 ，c 2 。) 9 j 9 q = ( c 七l ，q 2 ，) c 是上 的七个线性无关的码字；那么c 1 岛，吼构成线性码c 的一组基，由它可以生成 线性码c 中q k 个码字即对于c 中的每一个码字x = ( 毛，x ：，屯) ，总存在七个系 数a i ，口2 ，a k ，其中a ，e ，使得z = q q + 口2 c 2 + a k c t 即 x = ( 而，x 29o 9 x n ) = ( q ，a 2 ，a k ) c l ic 1 2 c 2 1 c 2 2 巳lc 七2 6 = ( a i ，a 2 ，a k ) g 厅 一 开 钆 显然g 是一个k 刀阶矩阵 定义2 1 2 1 称上述矩阵g 为线性码c 的一个生成矩阵 设x = ( 五，而，x n ) 刀，考虑矩阵方程g x r = 0 因为生成矩阵g 的秩是七， 方程的所有解构成e 的n - k 维解空间，设啊= ( 啊。，i i z i ：，啊。) ，坞= ( 岛，红：，如。) ， ，吃廿= ( - k , i 地：，h n - k n ) 是矩阵方程g x 7 = 0 的线性无关的一组解则对每一 个工霹有：x c 当且仅当 墩r ： 啊i 。 啊2 吃： 啊。 缟。 吃叱i一雌吃吨。 而 ： x 。 = 0 ， 即x c h x 7 = 0 定义2 1 2 2 称上述矩阵日是线性码c 的一个校验矩阵 定理2 1 2 1 设c 是一个 栉，k ，d 】线性码，日是它的校验矩阵，则h 的任何 d l 列都是线性无关的，且存在d 列线性相关，反之亦然 定义2 1 2 3 设c 是一个【，2 ，k ，d 】线性码，如果由c 构成的线性空间的一个子 集d 是霹的，( 1 ，七) 维子空间，则称d 是线性码c 的一个，维子码 2 1 3 线性码的对偶码及其重量分布 设x - - ( 五，x 2 ，毛) ，y = ( 乃，m ，儿) 碍，x 和y 的欧氏内积定义为 x y = 五乃+ 为此+ + 吒此 定义2 1 3 1 设c 是一个【刀，k ，d 】线性码，称 c 上= ) ，露l 砂= o ，魄c ) 为c 的对偶码。 显然( c 上) 上= c ，如果c 的生成矩阵是g ，校验矩阵为何，则c 上的生成矩阵 为日，校验矩阵为g 定义2 1 3 2 设c 是一个【，l ，七】线性码，令4 表示c 中h a m m i n g 重量等于i 的 码字的个数，我们称下面的序列 鸽，4 ，以) 7 为c 的h a m m i n g 重量分布( 或h a m m i n g 权分布) 定义2 1 3 3 码c 的h a m m i n g 重量分布计数器是指 w c ( x ，y ) = 4 x ”。y 7 = 矿”。m y “ i = o c e c 关于线性码c 与其对偶码c 上的h a m m i n g 重量分布计数器之间，我们有如 下著名的m a c w i l i a m s 定理 定理2 1 3 1 ( m a c w i l l i a m s 定理) 设cr ：上的一个i n ，明线性码，w c ( x ，y ) 和 ( x ，j ，) 分别是c 和c 上的h a m m i n g 重量计数器函数，则 - ( 五y ) = 而1 ( x + ( g 一1 ) y , x - y ) 特别地，取q = 2 即有关于二元【刀，k 】线性码c 的m a e w i l i a m s 定理： - ( x ，y ) = w c ( x + y , x - y ) 2 2r t 距离 2 2 1r t ( 或p ) 距离的定义 设cc 群是一个线性码令，2 = m s ，m ，占都是正整数，则c 中元素可以看成 是上的一个矩阵尸= ( 岛) ，l i m ，1 ，s5 ，巩 定义2 2 1 1 1 2 0 1 定义p 的r o s e n b l o o m t s f a s m a n 重量( 简称为r t 重量，或 p 重量) 为： w ( 尸) = m a x j l p , j o ) i = l 对v 的c 上的矩阵p ，q ，定义p ，q 的r t ( 或p ) 距离为p ( p ，q ) = w ( p q ) 当s = 1 时，此处定义的r t ( 或p ) 距离就是一般的h a m m i n g 距离 关于r t ( 或p ) 距离，有下面的的一些上下边界，详细结果及其证明可参 见文献 2 0 】 ( 1 ) s i n g l e t o n 边界：设c 是c 上一个( 甩，k ，d ) 码，其中 d = m i n w v ( x - y ) l v x ，y c ，x y ) 则：ksq ”州 ( 2 ) p l o t k i n 边界：设c 是上一个( 聍，k ，d ) 码，设万= d n 为相对最小距 离则： 万( k - 1 ) k ， 其帆# k = 1 - 1 扰，三g ( 3 ) h a m m i n g 边界：设c 是e 上一个( 门，k ，d ) 码， 则： k v o l ( s a _ , ) q “， r = 一j 其恸叫= h ，轰卸南9 点南g 娶 k 1 s ，嘶q 三】1 型如 b 。细 ( 4 ) g i l b e r t 边界：在以= m s 维线性空间霹中，对于v d ，0 d = o ，v p e c ， 易知c 上仍是m 。，( c ) 上的线性码 当s = 1 时，对于任意的行，眠。( e ) 上线性码c 及其对偶码c 上的尸重量计数 器满足： 定理2 2 2 1 f 2 1 1 啊z ) - 高( 1 + ( g - 1 汹哪最斋) 当玎= 1 时，对于任意的s ，蚝，( c ) 上线性码c 及其对偶码c 上的p 重量计数 器满足： 定理2 2 2 2 1 2 1 1 ( q z 一1 ) w e ( z ) + 1 一z = 1 c 上i z 。+ 1 ( g ( 1 一z ) 巧z ( j 二) + 够一1 ) 定义2 2 2 4 2 4 1 设尸= ( 岛) 脚鸠。，( ) ，= ( m o ，m 产l ，蚝o ，p 1 ) ，其中 1 i n ，o s - 1 ，定义鸠。( ) 上码c 的完全p 重量计数器为 ( ) = 埘川纠2 川蛾川式曼 j p e c 注意到上述重量计数器( 圪) 是一个含有n s 个变量的多项式，而且通过适 当的变化可以得到心。，( c ) 上码c 的p 重量计数器( z ) 于是有如下托。( e ) 上线性码c 关于完全p 重量计数器的m a c w i l l i a m s 恒 等式： 定理2 2 2 3 。2 4 1 设c 是m x ，( e ) 上线性码，则有： 坩) 穆崩蝼， = 而1 蚪nris-1(1+(g)ydi=0尸篆c 密矗1 = 0 ( 撬d 训 l ，；l j 【，( 工k c 七= lt y 一工， 1 0 更多关于r t 距离的内容及相关结果可参见文献 2 1 - 2 7 】 第三章环的化+ “黝上线性码关于r t 距离的 m a c w i l l i a m s 恒等式 文献【31 、3 2 】中引入了一种介于环z 4 与域只之间的四元素环e + 蜗，其中 z ，2 = 0 ，讨论了环只+ 幔上循环码的结构、译码问题及类型i i 码的性质同环z 4 相比，环e + 幔上的码具有编、译码简单和更易于实现等特点关于环e + 幔 本身的结构在文献【1 9 、2 0 】中均有详细描述，它是指剩余类环e “】0 2 ) ，其元 素分别记为0 ，1 ，u ，l + u ，若将u 视为z 4 环上元素2 ，1 + “视为元素3 ，则其乘法与 z 4 环上乘法一致若将u 视为域e = 0 ，1 ，2 上元素，l + u 视为2 ，则其 加法与域e 上加法一致，因而它分享了环z 4 与域只的一些良好性质u d a y a 等 首先将环e + 晦+ ”膏- 1 c 用于最优频率跳跃序列的构造，此类环上的编码理论 研究已成为一个热点【3 0 。3 5 】 r t 距离实际上是h a m m i n g l 距离的一种推广，因此对它的研究显然是有意义 的d o u g h e r t y 等在文献【2 2 】中给出了鸠。，( ) 上码关于t - p 重量计数器和h p 重量计数器i 拘m a c w i l l i a m s 恒等式在文献 2 5 】中，鸠。，( r ) 上( 其中r 为包含单 位元的有限交换环) 码关于完全p 重量计数器的m a c w i l l i a m s 恒等式也已给 出另外，在文献 2 6 - 2 7 】中，o z e n 等还证明了环鸠。，( r ) ( 其中r = r u l ( u 一口) ， a e ) 以及g a l o i s 环上码关于完全p 重量计数器的m a c w i l l i a m s 恒等式 在本章中，将完全p 重量计数器$ i 】l e e 重量及精确重量结合在一起，分别定 义并研究了鸭。，( e + 幔) 上码的l e e 完全夕重量计数器和精确完全p 重量计数 器，给出了互为对偶的两个鸠。( e + 幔) 上线性码关于这两种重量计数器所满 足的m a c w i l l i a m s 恒等式这两个重量计数器都比完全p 重量计数器优越，都包 含了更多的码字的信息，尤其是精确完全p 重量计数器，由它可以完全确定一 个鸠。( e + 幔) 上的线性码这些结果无论是对于编码还是对于译码都是很有 意义的 3 1 基本概念 1 2 为了方便起见，在本章中记r = 最+ 峨= o ，1 ，“，i = 1 + “) ，其中“2 = o 也可 记r = ( t o ，r 2 ，吃 ，其中，吒，r 2 ，吩分别表示r 中元素0 , 1 ，u ，“= l + u 设鸠。，( r ) 表示r 上所有的n s 矩阵组成的集合 设p = ( p o ，a ，见一1 ) m i 。( r ) ，定义p 的r t ( 或p ) 重量为 呐，= 叫州+ 1 嚣 对却，g m l 。( 灭) ，定义p ，q 的r t ( 或p ) 距离为：p ( p ，g ) = ( p 一譬) 进一步，设p = ( 墨，最，) 丁尥。，似) ，其中只= ( 只。，尼l ，一，b 产) m i 。，( r ) ， 1 j 刀，定义p 的r t ( 或p ) 重量为h ( 尸) = ( 只) 对卯，q 。俾) ，定 义p ，q 的r t ( 或p ) 距离为：p ( p ，q ) = ( 尸一q ) 定义3 1 1 0 2 6 1 m 。( 震) 的一个r 一子模c 是一个线性码 设cc 鸠。( r ) 是一个线性码，称 w a c ) = p c1w n ( p ) = r i ，0 r i t s ， 为码c 的p 重量谱，且定义相应的p 重量计数器为 ( z ) = w ( c ) ，= z 咐n 其中 设p = ( ，p l ，一，只一1 ) ，q = ( ，绣，q s 1 ) m i 。，( r ) ，定义p ，q 的内积为 j 一1 ( p ，g ) = 鼠玑1 - ， 进一步，设 p = ( 丑，最，只) r ，q - ( o , ，q 2 ，q ) r m 。( r ) ， e = ( p f o ，b i ，a ，一1 ) ，q = ( 吼o ，g ，l ，吼，。一1 ) m i 。，( r ) ， 1 f ， 定义p ，q 的内积为 = ( ( z ) ，q ( 石) ) = 巳一。( 只( x ) q ( x ) ) j i li = l 在上述定义中，若取s = 1 ，该内积即变为 与欧氏内积定义一致 ( p ，q ) = c o ( 鼻( x ) q j ) ) = b 。吼。， ，t ii = l 定义，：r 的h a m m i n g 重量为： w = 0 ：嚣 定义3 1 3 2 6 1 设p = ( 岛，a ，岛一1 ) r ”，y = ( y l ，以) ，定义r 一码c 的 完全p 重量计数器为： w e ( r ) = 片 n ) 硝 刮 定义3 1 4 2 6 1 设p = ( 日) 。蚝，( r ) ，= ( m 。，m 川，儿。，咒一1 ) ，其中 1 i 刀，0 j 冬s 一1 ，定义坂。( r ) 上码c 的完全p 重量计数器为 ( ) = 掰酬艘一蛾川k 生川 p e c 在上述定义中，若取疗= 1 ，s = 刀，并适当改变下标即可得定义3 1 3 另外， 通过适当变换还可以得到c 上的p 重量计数器 3 2 环m x s ( f 2 + u f 2 ) 上码关于r t 距离的l e e 完全p 重量计数器 为了将心。，( r ) 上码c 中码字的更多的信息包含到它的完全p 重量计数器 中，下面定义l e e 完全p 重量计数器的概念 定义3 2 1 2 9 1 对v r , r ，定义的l e e 重量为 f 0 i = 0 m ( ) = 1 ，i = 1 ，3 【2 ，i = 2 定义3 2 2 设p = ( 风，p l ，见一1 ) r ”，】，= ( 乃，儿，乩) ，定义r 一码c 的l e e 完全p 重量计数器为 l e e c ( i o = 妒慨谬m 睹m p c 定义3 2 3 设尸= ( 岛) 啪m ，。，( 尺) ，e ，= ( y l 。，乃产l ，”，儿。，只扩1 ) ，其中 1 i n ，0 ，_ ) ) ，( q ( x ” = 厂( q ) ) 孝( ( ( p ( x ) ，q ( z ) ) ) ) + 厂( q ( x ) ) f ( ( ( 尸( x ) ，q ( 石) ) ) g “) e c l尸( j ) e c g ( 工) t c 上 尸“) c 爿cl 厂( q ) ) q ( x ) e - c 1 于是得到如下螈。职) 上线性码c 关于l e e 完全p 重量计数器的 m a c w i l l i a m s 恒等式： 定理3 2 1 设c 是。( 尺) 上线性码，则有： 睹锄o ) 谐一瑞0 ，皖9 川 = 高_ 南( 珥n 罂s - i ( 1 2 ) n nn s - | p ( x ) c - ck = ll = o ( 器严川ioj = l ，却 j t 蝴 证明：在引理3 2 3 ，中取厂( ( q l ( x ) ，q ( x ) ) r ) ：n ni s - i 孵训，则 i = 1j = o 夕( p 。) ) ： 孝( ( ( p ( 工) ，9 ( x ) ) ) ) r n i n s - | 形锄) o ( x ) e m 。l ( r i ，l ( j 1 ) ) l “j = o = f ( ( p ( ( b ( x ) ，q 。) ) ) 。耽善( ( ( 暑( x ) ，g 。，一。x ”1 ) ) 川。，一。屹吼，- i 协o e j r吼, - z e r f ( ( ( 只( x ) ，吼。) ) 减。耽孝 ( ( ( x ) ，吼户工) ) 溉p l 毗- i o e rj i e r 由引理3 2 2 夕( ：p ( x ) ) = ( 1 + m 。) 2 一心a 一( 1 一m 。) k a 一( 1 + m 产1 ) 2 一托( a 。( 1 一m p l ) 心( 巩。 ( 1 + 虬o ) 2 一毗几川( 1 - - y n o ) 耽 i ( 1 + ，。一1 ) 2 一屹几”( 1 - y 。，卜1 ) 屹岛。 1 7 = n n 兀o - 1 ( ( 1 + ) 2 - w ( p l 州( 1 - y a ) m ，) ) = ( n nn s - i ( 1 + 虼) 2 ) 矗矗( 鲁) 吣州) j - lj = o k = l l - 0 1 十虼 再利用引理3 2 3 ，即得证定理 在上述定理中，若取丹= 1 ，j = 疗，并适当改变下标，则易得如下推论，即r 上线性码c 关于l e e 完全p 重量计数器的m a c w i l l i a m s 恒等式： 推论3 2 1 设c 是r 上线性码，q ( x ) = q o + 吼x + + g 州x 州，p ( x ) = p o + p l x + + 见一l x “1 r x ( x ”) ，贝0 有： 州乏妒谬锄) 孵i ) 2 高虫( + 咒y p 篆c k l _ 孑1 ( 1 - 瓦y k 删 在上述定理中，若取j = 1 ，并适当改变下标，则易得如下推论，我们称之 为r 上线性码关于精确l e e 重量计数器的m a c w i l l i a m s 恒等式： 推论3 2 2 设c 是r 上线性码，q ( x ) = q o + g l x + + g 柚x “，p ( x ) = p o + p t x + + 见一l x ”一r x l ( x ”) ，贝0 有： 。薹”聍锄) 砰。高( 冉( - + 咒) 2 ) p 委c 捌。1 十- y i k 严舢) 例1 ：设c = ( 0 ，0 ) ，( 甜，甜) ) 是r 上线性码，则由l e e 完全p 重量计数器定义可 得l e e c ( y ) = 1 + 订以，再根据定理3 2 1 经过计算可得 l e e c 。( y ) = i + 4 y l y 2 + 砍+ 记+ 姣记 另外，由c 求出其对偶码 c 上= ( 0 ，0 ) ，( 1 ，1 ) ，( 甜，“) ，( 1 + “，1 + “) ，( 0 ，甜) ，( z f ，0 ) ，( 1 ，1 + 甜) ，( 1 + 甜，1 ) ) ， 再由l e e 完全p 重量计数器定义也可得 l e e c ( ”= 1 + 4 y t y 2 + 开+ 露+ m 2 咒2 ， 二者结果是一致的因此，我们不必求出r 上线性码c 的对偶码c 上，即可利用 定理3 2 1 得到c 上的l e e 完全p 重量计数器 3 3 环x ，化+ 跖剐上码关于r t 距离的精确完全p 重量计数器 定义3 3 1 1 2 9 i 设v r ，定义其精确重量为屹( ) = i ，其中i = 0 ，i ，2 ，3 下面定义精确完全p 重量计数器的概念 通过该重量计数器，我们能够完全确定一个码例如，对于犯。，( r ) 上的码 c ，我们用y l o y o 吒y 斋y ：l y 2 0 2 _ y 3 0 0 _ y 3 0 l 以2 y 4 0 i _ y 4 0 1 y 乞即y t o 蚝y 斋y 2 1 y 3 2 y 4 0 表示码c 中r t 重量 为9 的码字 10 甜 1 + “l0 0 ol l0 0 一般地，用蝣7 o r ) 表示c 中一个矩阵的第f 行列对应的分量为r 中元 素r ，用多项式y 活q 0 孵鲁，圳y 嚣。以齿7 - l 表示矩阵 c = l 毫 定义3 3 2 设p = ( p o ，p i ，见一1 ) r ”，y = ( y l ，儿，儿) ，定义r 一码c 的精确 臣( 即= ”疗斤l ， p e c 定义3 3 3 设p = ( 岛) 舢鸠。俾) ，= ( m o ，乃产l 一，儿o ，蚝产1 ) ，其中 1 i n ，0 j f s - 1 ，定义鸠。，( 尺) 上码c 的精确完全p 重量计数器为 & ( ) = 蝣凡蛇挚川瑞一叫, s - i i ， p e c 在上述定义中，若取玎= 1 ，s = 挖，并适当改变的下标，即可得定义3 3 2 另 外，通过适当的变化还可以得到鸠。，( r ) 上码c 的l e e 完全p 重量计数器若取 s = 1 ，再适当改变下标，则可得如下的一个新的重量计数器： 砭( 】，) = ”砌盼n y 2 ， p e c 其中p = ( 风，p l ，见一1 ) r ”，】，= ( m ，j 1 29 9 n ) ，称之为r 上码的精确重量计数器 引理3 3 1 设为r 中固定的元素，取f ，为固定值，只( x ) = b o + a l x + 1 9 + 只，1 石川r x ( x 5 ) ，则有： ( 1 ) 善( ( 触) ) y 。= ( 1 + ( 一1 ) 螂 y ) ( 1 + ( 一1 ) 心仂y 2 ) ； 口e r ( 2 ) 孝( ( ( 只 ) ，口x ) ) y k 口= ( 1 + ( 一1 ) 中崩州 y ) ( 1 + ( 一1 ) h 功州y 2 ) 口e r 证明：( 1 ) 由定义可得： 善( ( 肛) ) y 吣= ( 1 + y ) ( 1 + y 2 ) ，= 0 ( 1 + y ) ( 1 一y 2 ) ，= 1 ( 1 一y ) ( 1 + y 2 ) ，= 材 ( 1 一y ) ( 1 - y 2 ) ，= l + u = ( 1 + ( 一1 ) m ，y ) ( 1 + ( - 1 ) k 声y 2 ) ： ( 2 ) 由( 1 ) 司得： 善( ( ( ( x ) ，口x ) ) ) y 口= 孝( ( c ( 只( x ) ( 口z 。) ) ) ) y 雌口 口e r口e c = 孝( ( b , s - l - t i 口) ) y 啡 口r = ( 1 + ( 一1 ) o n 一叫d y ) ( 1 + ( 一1 ) 局，州y 2 ) 于是得到m ( r ) 上线性码c 关于精确完全p 重量计数器的m a c w i l l i a m s 恒 等式： 定理3 3 1 设c