（基础数学专业论文）环z2α上线性（负）循环码的汉明距离和lee距离.pdf

北京交通大学硕士学位论文中文摘要 中文摘要 摘要：循环码是一类非常重要的线性分组码，它建立在严格的代数理论基础上。由 于它编译码迅速，具有较强的纠错和检错能力，而在实践中具有重要作用。p r 龃g e ( 1 9 5 7 ) 和b e r k e l a m p ( 1 9 6 8 ) 分别首先开始研究有限域上的循环码和负循环码，直 到上世纪9 0 年代，n e c l l v ( 1 9 9 1 ) 和h 蛐l m 湖( 1 9 9 4 ) 通过有限环上的线性码构造 出著名的非线性码如k 诎码和p 弛p 村a t a 码，有限环上的码才受到广泛关注。此 后，许多学者从不同方面研究了环上的码。 汉明距离与码的纠错能力和检错能力密切相关，同时由于码的l 距离使得 从( 掣，l e e 度量) 到( 砺，h 彻珈i n g 度量) 存在一个等距同构映射一g r a y 映射，因此 汉明距离和l e e 距离具有重要的研究价值。嘞e ra b u a l r u b ，a l ig h r a y e b 和r o b e r t h 0 e h m k e ( 2 0 0 4 ) 得到了环五上2 长循环码的汉明距离和【j e e 距离的界。h a iq d i n h ( 2 0 0 5 ) 研究了环历。上2 长负循环码的汉明距离，并提出了关于此问题的一个猜想。 本文主要研究环z 争上( 负) 循环码的距离。在介绍了循环码，汉明距离，l 距离的 有关概念和性质后，首先研究了环z 2 4 上掣长的负循环码的汉明距离和l e e 距离， 其次研究了这类码的汉明重量分布。最后研究了环历上2 长的循环码的汉明距 离和l e e 距离。主要研究结果如下： ( 1 ) 证明了h a iq d i n h 提出的关于环z 叠上2 长负循环码的汉明距离的猜想是 正确的，从而得到了这类码的汉明距离的准确值。进一步，得到了这类码的l e e 距 离的准确值和码( + 1 ) 2 。( ” ) 1 ) ( 1 七口一1 ) 的汉明重量分布。 ( 2 ) 得到了环蜀上2 i 长循环码的汉明距离的准确值。对于这类码的l 距离， 给出了上下界，特别得到了码j = ( + 1 ) ) ( o t 2 。) 和码j = 2 扛+ 1 p ) ( o m 2 5 1 的l 距离的准确值。 关键词：线性码；循环码；汉明距离；l 距离；汉明重量 北京交通大学硕士学位论文 a b s t r a c t a b s t r a c t a b s t r a c t ：c y c u cc o d 明h g 咒g o o da i g e b r 8s t r u c t i 鹏龃d 甜eo n eo ft h e m 0 8 ti 瑚【p o r t 觚tc l a s so fl i n e a rb l o d kc o d 翻t h e yh a 聘i m p o r t 跗ta p p u c a t i o n 8b y v 矾u e t h e i rh i g h8 p e e do f e n c o d i n g 衄d d e o o d i n ga n ds t r o n gc 8 p a c i t y0 fe r r 钟 咄t i 叫瓤l dd e 七e 吐i o n p r 8 叫驴6 碍tb e g 眦t ob t u d yc y d kc d d 嘲o v 材6 n i t e 矗e l di n 1 9 5 7 衄db e r l 烈a m p 鼬tb b 9 8 nt 0b 撇堪t i g b 沁n e g a c y c l i cc o d 馏o 、憎丘n j t e 丘e l di n 1 9 6 8 b u tt h ec o d 鹤o v e r 觚t er i n 舻d i 血tr e c e i v e d 础l c ha t 蛔1 t i o ni i n t i lt h e1 9 9 0 s d u et ot h ew o r k 8o fn e c h a 盯i n1 9 9 1a n dh 明l m o n 8i n1 9 9 4 w h i c h8 h o w e dt h 砒 w e u - l c | 1 0 w nn d n n n e 盯c o d e 8 日u c h 柚k e r d o d ka n dp 陀p 8 r a t ac o d 村eo o 瑚t m c t e d 曲ml i n e a rc o d 铝o 、，e r 觚t e 血咿s 蛐汜t h e n ，m 锄yr e 盹a f c h 哪h 啪s t 砌e dt h e c o d 髑a v e rr i i l 9 8f 而m 鲫e r e n t 舶p e c t s h a m m i n gd i 8 t a n c eh 8 8ac l er e l a t i o n 8 h i p 硒t ht h ea b i l i 留o fe 玎o rc o r r e o t i o na n dd e t e c t i o no fc o d 韶n 坨a n w h n ed l i et 0i 鹿d i s t a n o et h e r ee 幽t 8ai 8 0 m e t 啊g r a ym a p p i n g ，b e t w e e n ( 纠，l e em e 删1 r e m e n t ) a n d ( z ，h 卸瑚【i n gm e 嬲u 净 m e n t ) ，h e n c e f o r t hh 锄衄1 i n gd i b t a n c e 蛆di j e ed i s t a c e 盯eo fi m p o r t 眦tr e s e 甜c h v a l u e i n2 0 0 4 ，呦a b u a k l b ，a l ig l l r a y e ba n dr 0 b e r th o e h m l 【e0 b t a i 呻dt h e b o l m d 蛆t h e h 锄m i i 堰d i 8 t a n c e8 n d l d i 8 t 觚c e o fc y c l i cc d d 明o f l 髓g t h 2 。o v e r 衄历1 1 12 0 0 5 ，h 撕q d i 血8 t u d i e dt h eh 锄蛐i n gd i 8 t a n o eo fn e g 叼r c h cc o d 鹤o f k n g t h2 o v 盱r i n g 忍。觚dp m p e dac o n j e c 乞1 l r ea b o u t 蛐p r o 龇m t h et h e 8 i 8 i sd e v o t e dt ot h e 幽t 觚c eo f n e g a c y c u c 觚dc y c u cc o d e sa v 盯r i n gz 茹觥e r8 0 m e 姚i t i o n s 锄dp r o p e n j 器0 nq ，c c o d 岛，h 锄m i n gd i s t 船o e 衄di | e ed i s t 舱o e i n t r o d u o e d ，t h eh 锄蛐1 i 1 1 9d i 8 t 阻c e 龃di j e ed i 8 t a n c eo fn e g 舵y c u cc o d e bo fl 阻g t h 2 。a v e rr i n 伊易。肌d 肌b b e q l 删yt h eh 衄珊血gw e i g h td i s t 曲u t i o no ft h e 8 ec o d 皤 盯ei n v 鹤t i g a t e d f i 玎a l l y ，t h eh 和1 埘i i n gd i j s t a n c e8 n dl d i j s t a n 0 f 呵c cc o d 鹊o f l e n g t h2 。o v e rr i n g 历黜8 t u d i e d m a i n 瑚1 1 l _ t bo f t h i 8w o r ka 阳硒f o l l a w ： ( 1 ) w bp r o v et h ec o n j e c t u p r o p e d 坶q d i n ha b o u tt h eh 锄m i n g 曲t a n c e o fn e g a q ，c l i cc o d e 8o fl e n g t h2 o v 日r i n gz ia r ec 0 盯e c t ，觚dt l 陀r e b yo b t a i nt h e o 海c t 词u eo fh 锄n m 王n gd i s t a n o e0 ft h e 解0 0 d 朗m o r v e r ，w eg a i nt h e 仞硌c tv a l u e o fl d 培t a n c eo ft h e c o d 凹觚dt h eh a 衄i n gw e i g h td i s t r i b u t i o no fc o d 鹪 ( ( z + 1 ) 2 。( 4 一耐一1 ) ( 1 o 一1 ) ( 2 ) w j0 b t 8 i nt h e 既8 c tv a l u e0 fh 锄1 m i n gd i s t a n c eo fc y c l i c d 0 fl 印g t h 北京交通大学硕士学位论文a b s t r a c t r o v 凹r i n g 互f o rt h el d i s t 觚o ft h 船ec o d ，w ea t t a i nt h eu p p 盯觚d l o w e rb o l m d i i lp m i c i d 缸，w eg a i t h e 白【毗d u eo fl d i 8 t a n c eo fc o d j = ( 扛+ 1 ) ) ( o t 2 ) 眦d ，= ( 2 b + 1 ) m ) ( 0 m 8 2 令 - 2 丘 2 = ， 町 + z 毗 一瑚 = 疗 北京交通大学硕士学位论文3 环邑。上长为2 的负循环码的距离和重量分布 和 c - 0 ) = ，1 ( z ) + ，2 0 ) 十+ 如( z ) 则“功= 2 4 1 c l p ) 由于魂一毋一l 2 一，s 1 如+ 2 i 一一1 ，勃一1 勖+ 2 ”一l ，因此，当 j 时， ( z ) 每一项的次数不同于办( z ) 每一项的次数我们把 多项式c l ( z ) 的系数写成一个矩阵： l 啦- - i 口2 - 一 a = i 1 ： 口2 一- 一 三爰l 。， d 2 - 一2 口1n o l 0 2 一 一2 口1 咖，一 其中矩阵a 的第，行对应乃( 功的系数易知，c 1 0 ) 的汉明重量( 同时c ( x ) 的汉明重量) 是a 的非零元的个数 因此码c l ( $ ) 的最小汉明重量依赖于l ( z ) 的系数我们断 言 ( 。) 至少有两个非零系数否则，令 ( z ) = ，其中 是正整数所以 + 1 ) g ( ) ； ，这与矿是单位但p + 1 ) 9 ( z ) 是幂零元相矛盾因此，矩阵a 至少有两列满足列的 每一个元都是非零元因此，钍w ( c ( $ ) ) 2 2 = 2 1 ，从而d ( q ) 2 + 1 令a = ( z + 1 ) ) ，其中t = 掣( n 1 ) + 箸2 。_ j 由定理2 5 ，我们可得d 目( a ) 2 1 对任意的i ，t o i t ，我们有： ( 0 + 1 ) ) = a c c = ( ( z + 1 ) ) c c b = ( ( z + 1 ) ”) 因此， 2 + 1 d ( c b ) d ( e ) d ( q ) 2 1 所以，d ( g ) = 2 1 4 由本节命题和文献【8 】中定理4 1 l ，易。上2 长负循环码的汉明距离被完全确定 我们把它完整的写为一个定理 定理3 4 对于z 五上2 。长的负循环码g = ( + 1 ) ) 精( ，其中i o ，1 ，2 ，2 口) ，汉明距离为： d 日( e ) 1 。如果o 2 。( o 一1 ) ， 妇( e ) = 2 ，如果2 ( o 1 ) + 1 i 2 ( d 1 ) + 2 一1 妇( a ) t 2 + 1 ，对于1 七s 一1 ，如果掣( o 一1 ) + 1 2 1 + 1 2 一 1 ) + 蒿2 一。 北京交通大学硕士学位论文 3 环历上长为2 ，的负循环码的距离和重量分布 幽( q 印。如果i = 2 8 3 2易上长为的负循环码的k 虻距离 码字口= ( 4 1 ，口2 ，) z 茹的i 脚重量，记为蚍( 口) ，是指： n 毗( o ) = 慨n “，铲一n ) 。 i = 1 两个码字口= ( o l ，d 2 ，) ，b = ( 6 1 ，6 2 ，k ) 的l 距离，记为丸( o ，6 ) ，是指 n d 工( n ，6 ) = m t n ( ( n 一以) 州脚，( 玩一o ) 仂础) i = l 码c 的l e e 距离( l e e 重量) 是指任意两个码字问的最小【船距离( 非零码字的最 小l e e 重量) 由l e e 距离的定义可知，研究线性码的l 距离等价于研究线性码 的i 脚重量 引理3 5 码( 岔) 的l e e 重量为2 ，其中0 l n 1 证明 易知码( 2 ) 中的非零码字为c ( $ ) = 2 乏葛1 勺，其中勺忍一且 勺( 1 j 掣一1 ) 不全为零那么： 2 。一l 2 一l t 比( c ) = m 伽( 2 白，2 4 2 白) = 2 仇伽( 白，字一一白) j ；oj = 0 由于码( 2 ) 的汉明重量为1 ，因此t p ) 2 - 显然码( ) 中含有l e e 重量为2 的码 字。所以t 儿( e ) = 2 引理3 6 对于1 n 一1 。当2 。a 一1 ) + l j 2 5 t 时。码c = 0 + 1 ) ) 的l e e 重量删l ( e ) 证明 当2 0 一1 ) + 1 j 柳时，( ( z + l y ) 2 ( 0 + 1 ) 2 ) = ( ) 由引 理3 5 德 虮( ( 扛+ 1 ) ) ) 伽乜( ( 2 ) ) = 岔 引理3 7 验( 詹) ( 后1 ) 上的码p + 1 ) 的l e e 重量为2 引理3 8 对于1 is 。一1 ，当2 。0 1 ) + 1 js2 。i 时，t ( = 毗( ( 扛+ 1 ) ) ) = 分 证明 由引理3 6 知，我们只需证明毗( ( 0 + 1 ) r o 一1 ) + 1 ) ) 2 由于 ( ( $ + 1 ) 2 。o 一1 ) + 1 ) = ( 2 一1 ( z + 1 ) ) 1 2 ! ! 星奎望丕堂堡主堂垡堡塞 ! 堑垒：土量垄! ：堕鱼煎墅堕笪堕壅型重量坌塑 那么对于该码中的任一码字一1 啬1 皿，口z 尹1 ，我们有 = ，r 嘞口( 2 一1 啦，2 4 一分一1 啦) 伽 护一i = 一1 而n ( n i ，2 件l 一啦) - 一 。 由引理3 7 可得：盘1m i 挖瓴，+ 1 一啦) 2 因此： t ( ( ( z + 1 ) 2 。o 一1 ) + 1 ) ) 2 2 一1 = 2 疆 引理3 9 ( 1 ) 当2 。( 口一1 ) + 1 i 2 一1 ) + 穿一1 时，毗( ( ( $ + 1 ) ) ) = 2 n ； ( 2 ) 对于1 詹8 1 ，当2 。( o 一1 ) + 尝12 ，+ 1 i 2 ( n 一1 ) + 譬2 一j 时，毗( + 1 ) ) ) = 2 4 + 证明 对于码( + 1 ) ) 的任一码字，( 。) = 铲一1 盘1o ，其中啦忍由定 理3 4 ，当2 。( a 一1 ) + 1 i 2 ( o 一1 ) + 2 一1 时，有： 2 。一l 2 - 一l 忱( ，( z ) ) = 毗( 垆一1 啦) = m 讥( 铲一1 啦，2 0 一铲一1 啦) l = 加0 2 j l = 2 4 1 砌，l ，2 一啦) = 矿一1 垆一2 = 铲 f ；= o 啦0 对于1 七s 一1 ，当2 。( o 一1 ) + 墨l 字1 + l 2 ( 8 1 ) + 装：2 j 时， 2 ，一1 眦( ，o ) ) = 钆( 2 d 。1 8 ) = 0 = 俨= 铲蛳铲2 1 = 2 罐 m 0 注：当t = 2 o 一1 时，由文献【8 i 中命题4 4 知，毗( ( + 1 ) ) ) = 铲+ 综合上面的讨论，我们得到下面的定理 定理3 1 0 令码c 是易。上2 。长的线性负循环码。即： e = ( 0 + 1 ) ) 其中o 2 o 那么它的l e e 距离为： 1 3 以 一 2 锄 己 缈 i i z 皿 蹦：l 一 口 己 埘 北京交通大学硕士学位论文3 环历。上长为2 的负循环码的距离和重量分布 屯( g ) = 掌，对于1 七口一1 ，如果2 。 一1 ) + l 2 i 詹， d l ( c ) = 2 4 ，如果2 ( d 一1 ) + 1 i 2 。( 口一1 ) + 2 一1 屯( c ) = 2 m ，对于l 膏。一1 ，如果2 。( b 1 ) + 乏墨1 2 一j + 1 i 2 。( 0 一1 ) + 糟掣一。 如( c ) = o ，如果t = 2 口 例3 1 ：考虑五上长为1 6 的负循环码g a l 。i 8 环赫的理想为：( ( z + 1 ) ) 。其 中 o ，1 ，3 2 ) 在下面的表各中，我们列出了这些码及其汉明距离和l e e 距 离 表1 厄上长为1 6 的负循环码 l 码的生成子码字数如也 l码的生成子码字数 d h九 0 + 1 ) o 2 弛11 1 7 0 + 1 ) 1 7 2 1 524 1 扛+ 1 ) 1 2 3 1 l21 8 扛+ 1 ) 1 8 2 1 424 2 扛+ 1 ) 2 2 l21 9 0 + 1 ) ” 2 1 32 4 3 + 1 ) 3 2 122 0 扛+ 1 ) 2 1 224 4 + 1 ) 4 2 2 8122 1 扫+ 1 ) 2 1 2 1 124 5p + 1 ) 5 2 2 7l22 2 扛+ 1 ) 船 2 1 024 6 仕+ 1 ) 6 2 2 6122 3 0 + 1 ) 船 2 924 7 + 1 ) 7 2 箱l22 4 0 + 1 ) 舶 2 824 8 + 1 ) 8 2 2 4122 5 扛+ 1 ) 衢 2 748 9 + 1 ) 9 2 2 3122 6 0 + 1 ) 2 6 2 648 1 0 0 + 1 ) 1 0 2 船122 7 向+ 1 ) 2 7 2 548 1 1 + 1 ) 1 1 2 2 1122 8 0 + 1 ) 镐 2 448 1 2 + 1 ) 1 2 2 l22 9 0 + 1 ) 2 。 2 3 8 1 6 1 3 0 + 1 ) ” 2 1 9123 0 p + 1 ) 2 281 6 1 4 0 + 1 ) 1 4 2 1 8123 1 + 1 ) 3 1 21 63 2 1 5 0 + 1 ) 1 5 2 1 712 3 2 + 1 ) 3 2 1o0 1 6 + 1 ) 1 6 2 1 612 3 3易。上长为2 ，的负循环码的汉明重量分布 文献【8 】中考虑了部分z 叠上2 长的负循环码的重量分布本节我们考虑当1 1 4 北京交通大学硕士学位论文3 环历上长为2 的负循环码的距离和重量分布 七o 一1 时，码( + 1 ) r “一妨一1 ) 的汉明重量分布 引理3 1 1 当l 2 一l 时，封c 蓦一1 证明由于 晓q = 坠堂等幽 = 罕罕：竽2 垂罕 2 t 。t 丁2 土乓下 令七= 2 m - - “k ，其中1 七i ，m 为奇数，m t s 那么： = 垂写产 = 1 “ 易知每项2 ”m m 为奇数，从而n ：l p m 一) 为奇数，因此q 。l 是奇数1 引理3 1 2对于非负整数6 和c 。铲一( 1 ) 6 + 铲。c o ( m d d 2 8 ) ，其中6 为 奇数且6 8 2 s 2 令 六( z ) = 饥一，j = 1 ，2 ，2 。 穹0 和 c 1 ( 茹) = ( z ) + ，2 0 ) + + j 知0 ) 则c ) = 2 c 1 0 ) 由于巩一巩一1 2 ”，2 i 一1 2 ”。+ s 1