（概率论与数理统计专业论文）二元互补2重量码的阈值问题.pdf

二元互补2一 重量码的闭值问题 黄劲 南开大学数学科学学院 一九九九年三月 中文摘要 二元码的检错性能在编码理论中占有重要的地位，码的不可检 错误概率是反映数字通信系统性能的一个重要参数。二元等重码作 为检错码得到了广泛的应用。 二元2 一 重量码作为等重码的推广也有 重要的应用。 关于 编码理论和检错码的一般知识请参阅f5 1 z 1 图， 等 重码和2 一 重量码方面的文章请参阅 8 1 一 1 5 o 为了衡量检错码的好坏，引进了检错好码和最优检错码的概念 ( 定义1 和2 ) ， 但检错好码和最优检错码很少。 在实际应用中， 信道 错误概率p 很小， 为此， 文6 1 引进了闭 值的概念( 见定义3 ) 。 只要 p b ( c ) ， 那么该码仍然有较好的特性， 适合用于实际信道。 本文 首先讨论了 二元互 补2 一 重量 码( 二 、 2 , zu , n - w ) 的闭 值的极 限行为， 然后给出了一般二元等重码( n , 2 6 , 叫 的阐 值的下界，最后 讨论了 最优二元等 重码( n , z , 2 ) 在区间o , e ( c ) 中 的 单调特性。 关键词: 检错码，不可检错误概率，闹值，二元2一 重量码 o n t h e u n d e t e c t e d e r r o r p rob a b i l i t y t h r e s h o l d o f b i n a r y ( n , 2 ，二 一 w ) 2 - w e i g h t s c o d e s j i n h u a n g s c h o o l o f ma t h c ma t i c s , n a n k a i u n i v e r s i t y ma r c h . 1 9 9 9 ab s t r a c t s t u d y i n g t h e e r r o r - d e t e c t i n g a b i l i t i e s o f b i n a r y c o d e s i s a n i m p o r t a n t b r a n c h i n c o d i n g t h e o r y .t h e u n d e t e c t e d e r r o r p r o b a b i li t y o f a n e r r o r - d e t e c t i n g c o d e i s o n e o f t h e m a j o r p a r a m e t e r s f o r e v a l u a t i n g t h e e f f i - c i e n c y o f t h e d i 乡 t a l c o m m u n i c a t i o n s y s t e m s w i t h f e e d b a c k ,s u c h a s t h e a u t o m a t i c - r e p e a t - r e q u e s t ( a r q ) e r r o r - c o n t r o l s y s t e m . t h e b i n a r y n o n li n - e a r c o n s t a n t w e i g h t c o d e s h a v e b e e n w i d e l y u s e d a s t h e e r r o r - d e t e c t i n g c o d e s . t h e b i n a r y n o n l i n e a r 2 - w e i g h t s c o d e s h a v e a l s o b e e n a p p l i e d i n m a n y a r e a s a s t h e g e n e r a li z a t i o n o f c o n s t a n t w e i g h t c o d e s .f o r a g e n e r a l i n t r o d u c t i o n t o t h e t h e o r y o f c o d i n g a n d e r r o r - d e t e c t i n g c o d e s , w e r e f e r t h e r e a d e r t o 5 2 7 a n d i t s r e f e r e n c e s . p a p e r s o n t h e c o n s t a n t c o d e s a n d 2 - w e i g h t s c o d e s a r e li s t e d .( s e e 8 一 1 5 1 ) i n o r d e r t o e v a l u a t e t h e e f f i c i e n c y o f a n e r r o r - d e t e c t i n g c o d e , t h e c o n c e p t s o f g o o d e r r o r - d e t e c 七 i n g c o d e s a n d p r o p e r e r r o r - d e t e c t i n g c o d e s a r e i n t r o d u c e d ( s e e d e fi n i t i o n 1 a n d 2 ) . b u t t h e c o d e s w h i c h a r e g o o d o r p r o p e r f o r e r r o r - d e t e c t i n g a r e f e w . 0 n t h e o t h e r h a n d ,t h e c r o s s e r r o r p r o b a b i li t y o f t h e c h a n n e l ,p i s u s u a ll y v e r y s m a l l .t h e r e f o r e 8 ( c ) , t h e t h r e s h o l d o f c o d e c i s i n t r o d u c e d i n 6 ( s e e d e fi n i t i o n 3 ) . i f p g b ( c ) ,t h e c o d e c i s s t i ll e f f i c i e n c y f o r t h e p r a c t i c a l c h a n n e l . f i r s t w e s t u d y t h e t h r e s h o l d o f b i n a r y 2 - w e i g h t s c o d e s ( n , 2 , w , 。一二 ) w h e n n i s g r e a t ;s e c o n d l y w e g i v e o u t t h e l o w e r b o u n d o f b i n a r y c o n s t a n t c o d e s ( n , 2 s , w ) . f i n al l y w e d i s c u s s e d w h e t h e r pd ( c , p ) o f t h e o p t i m al b i n a r y c o n s t a n t w e i g h t c o d e ( n , 2 , 2 ) i s m o n o t o n e w h e n p i s i n 0 , o ( c ) i . ke y wo r d s : u n d e t e c t e d e r r o r p r o b a b i li t y , e r r o r - d e t e c t i n g c o d e s , t h r e s h - o l d , b i n a r y 2 - w e i g h t s c o d e 致谢 作者很感谢沈世槛教授， 符方伟教授三年来的精心指导。 他 们的指导使作者在三年中学到了深刻而系统的专业知识，同时 他们的敬业精神， 严谨的治学态度，在数学领域里不断探索的 精神深深地影响了我。 本论文是在两位导师的悉心指导下完成 的。 在本文写作过程中，教研室的诸位老师，本专业的诸位同 学给了我很多启发和建议，对此表示衷心的感谢。 同时感谢与我朝夕相处的杨军，张勇涛，赵晨晖，是他们 带给我三年偷快的学校生活。 第一部分: 预备知识 设为二元( 、m, 心码，矶( 2 ) 为二 元i t 维向量空间，咖( ， 今 表示向 量之间 的h a m m i n g 距离， 令: d 、 一 m k (- , 州。6 e c , d 拭a , 6 ) 二川，a 二。 , 1 , ， . , 7 t 称 d ; 。 为c的 距离分布。 记码在误码率为p的二元对称信道中的不可检错误概率 ( u n d e - t e c t e d e r r o r p r o b a b i l i t y ) 为几 ( c , p ) ，则 几d ( c , 川 =p d h (n ,6 ) ( 1 一 p ) -dr (u b ) 口 艺比灿 1一m 二艺d , ( 1 一 p ) ” 一 p ( 1 ) 定义1 : 称二元码 为检 错好码( g o o d f o r e r r o r d e t e c t i o n ) ， 如果冷e 0 , 1 / 2 凡d ( c , p ) 5几d ( c , 1 / 2 ) 果 如闪 定义2 : 称二元码为最佳检错码( p r o p e r f o r e r r o r d e t e c t i o n ) ， v p 钊。 ， 1 / 2 , p d ( c , p ) 是p 的单增函数。 定义3: 码c的闭值定义为 b ( c ) =m a x p 0 , 1 / 2 p d ( c , p ) 几,i ( c , 1 / 2 )饰 e 0 , 定义4: 如果二元二 长码的每个码字 7 u 1 ， : 并且码字数目 为最大可能值 ， 。 ， ，这里0 元恤 ， 2 , w , , w 2 ) 2 一重 量 码， 如 果还有e n , - (- w ; 二、 ， 则称 补( 7b , 2 , i v , 7 : 一 ， 。 )2 一 重量码。 则称 c为二 c为二元互 或、物 叼/才1、 为+ 量1矛 重几叭 的! 注: 显然， 当c为二元( , 2 , ?vi, w 2 ) 2 一 重量码时， c一定是非线性码， 为保证c的极小距离大于1 ，二 : 与， : 应至少相差2 ，所以在定义1 中我们设， : +1 。 ， 将c的每个 码字取反， 得到的是一个与c等价的2 - 重量码， 且其两个不同的重量和小于等 于。 ， 故我们 将二元非线性2 一 重量码简记为二元( 二 . 2 . v ) 1 , v u 2 ) 码， 这 里 ” 飞 。2一 ， 飞十 zu2 it 而 且 码 字 ” “ 二 ( 众 ) 十 ( 、rtw 2 ) 定义5 : 如果二元( vt , 2 6 , 叫等 重码的码字数目 在所有二 元( 二2 b 叫 等重码中达到最大可能值，则称为最优二元等重码。 第二部分: 主要结果 记c为码( 二 ， 2 , w 1 , w 2 ) ( 0 w t 、 。 : 一l . t t ， +、 ， : 三， ) 令 孔mo () 三。 三， :且 ， i i i i t 或 m 为整数 为小数 几州 定理1: 码c ( n , 2 , w l , w 2 ) ( u w , 的距离分布为 d 、 二f+g x i +从 其中 2 f 1 21 . ， ， ， +。 ，: tt.) 7. =4 , 1 , ! - . , n w, 冬-2 一丹山 几 一 7 0 1 g i 二m zm 1 口 2 7 t一 了 矛 ， ， 琴一2 从 二 w1n 一 w1 i + +s - w, z t 刃 a i +w x - w, a n 一 4 ! l 2 i +, 1 1 一 州2 m, =ma 二 m二 几叱 /矛.吸、 + 证明 : 记c , 为码( 二 ， 2 , w i ) , c 2 为码 n , 2 , w 2 ) di 二 m f ( d , b ) i +h; 3 定理证毕。 由定理1 ，我们很容易得到 推论1 “ 二元互补2 一 重量码( n , 2 , w， 一 、 ) ( d x a n - w-1 ) 的距 离分布为 门 -一 。 一 ( 2 ) ( n - iii2 ) 十 ( : xa2 2 ) ( 7l2 二 xtr2 ) 下面我们 考 虑二元互补2 一 重量 码( n , 2 , 、二 一 w ) ( 0 iv 7l - 71) - 2 ) 的闭值问题，令 二 =x ( n , w ) = ， =y ( n ， 二 )= 我们可以 这样考虑， 当p 较小时，p u d ( c , p ) 主要由d z p 决定， 因为 p d ( c , 0 ( c ) ) = p d ( c , 蚤 ) = 二 ( n , 叫， 那么 如 果b ( c ) 较 小， 就有 d z ( 8 ( c ) ) 、二 ( 二 ， 。 ) 因而b ( c ) 二y ( n , w ) 引理1 :( 见文!3 p .4 6 6 ) e - 1 八 s y ) . 一; 二 二 二 一 v 而 2 2 - 1 ( 2 ) 引理2:， ( 。 ， 、 ) 三1 1 1) 号 一1 证明 : 当二+1 2 1一门 、! 卜 了苦、 q自 /了才性1卫，.卫t飞、 一- 1一2 、.吸.，.矛了r y ( n , i v ) 2 ( niv ) 一 ;。 n .+ 1 2 x u ( n 一， 。 ) ， ( ， : ， ，十1 ) 2 ( x 1， 十1 ) ( 7 一， ， 一1 ) /矛.诬.1、 二 汽 门一你 y ( i l , 、。 十 1 ) 2 y ( n , w ) 2 a(n.一二 7a业a ( w十1 ) ( 。一 ，一1 ) 、ilj一儿 ?、一) ( ，。 7l ， ( 二+1 ) ( 、 一二一1 ) w + 1 n 一 ， 。 ) 2 2 ( 。一7 。 一1 ) 一 十 w (n - 2w : - 2 )2(7a + 1)2(n - w - 1 ) 十 (1u2 + 2w - 1)(n - 2w - 2) + 2u2 + tu - 1(w + 1)2 (n - w - 1) )1 所以 当1 as 2 - 1 时， ( n , w ) 随二的 增 大而增加 当n为奇数时，我们有 y ( 2 。 一 1 , w ) 2 y ( 2 。 一 1 , v - 2 ) 2 0 存在正整数 c ( n , 2 , 。 ， ， 一 、 。 ) ( ， 。 ， : ( ) 时 几j4 哎一 打 内. ，几1内田 、.1.，忿/ 一 1 了矛刃.、 q ( 1 一。 ) w / i u ( n一， u ) 2 b ( c ) 4 时) 十 男 晋 菩 (a 2 ( 2 ) n + ( 一 ，2(1 + 二 ， + x + (c + “ 一 ，( + 2c ) z ( )” + 登(一 ， (x 这时偶数n只需满足 二 ( 1 一。 ) 2 (i 2cms s/ ( ; ) “ 8 c ( 1 一* ) 2 了e 2 2-6 x c 2 e 一2 n -e 即 : 丝 j .科_ x x + k c 十生 ) 久 2 e 8 ( c +1 ) n) 取。 2 ( e ) 那么当 8c(1 一。 ) 28 ( c +1 ) 贫 f 2， ， .少、1 x a 1l n -一 、 为大于二 2 ( e ) 由( 3 ) 式易知若。 三 尹 的 偶数时f ; 1 a ( c , p - ) 二 。 ，存在、 : ( 。 ) ， 立。 综上所述，定理得证。 当。 t t 2 w 时，定理中的左边不等式成 前面的 定理是针对。 n4 的 情况， 我们可 进一步扩大二的范围。 定理3: 对于二元互 补2 一 重量 码c ( n , 2 二，、 一 二 ) ( w 。 ， 存在 正整 数川 日， 当 n “ ( : ) 时 立言 !ji ( 1 一* ) 2 ( ， 、 一 1 、叨 了 w ( n 一。 ) 2 n e ( c ) ( 1 +6 ) 、 、一w ) 2 - 砚一2 、.忍.，声/ 其 中4 w 的 证明 : 右边不等式的证明与定理2 中的证明相同。 汽曲 、.了 nlz.?j 21、 哎一 、.占了 下证左 先证明 n 一钊 一- 、里.r/ 1 。 一 。 + ， ) ， t 7三 ) - ， 一 二一 了 十1 ) ， 、一二 ) .丫|尹 ， 。 一j +1 +( 、一， ， 一ji- 1 ) 2 . / au + tt - w a 2/ 一 71)z l 2 一 了 + ttl 27 + 1) . 2 ! 一 ( : ) ) ( “ 丁 ) : ( : ) 1 l 为偶数时 牡 j1 1 .一7 幻 j p 2 + 一 觉 7 1 1 ) ( 1! ， ) 竺一” 了叮.几.、 l尹 登e 由定理2 中( 3 ) 式知 几武 c , p - ) 三 p 性 十 了 -17 了=1j 7 1 户 了) ( “ 、 ”) 尹n-2j 一!又月 + 兰 ( 合 ) ” + 二 ( 1 一 。 ) 2 ( 1 + 登 一 亡 。 十e j =; + 1 7 1 ) 宁 x 一牡i .7 j 尹 竺 一 2 ， 了矛百.吸、 ! 三 ( 告 ) “ + .t ( i 一 。 ) 2 ( 1 +) + 4x , ( i 十 。今 自 、几卫召了产 几-2?叶 2!、 其中 登 - t e j = t +1 p n - 2, 2 ) n-2 互 俞 .竹|了 钊 登 - w 一2 ( 当。 适当大时) 只需 寻找 “ ( - 2 ) ,6 ( c s ) m ( m ( ， 一 。 ) ) 合 砚曰 其中m为码字个数，c a 证明 : 记t 二 u - , ) f p s ) p . d ( c , p ) -i -2 - ( m f。 一 。 ) ) ) ) =艺d ; ( 1 一 。 ) ” 一 ， 而对于c ( n , 2 b 。 ) 。 、 : ( n.z ) ( ” z ) 几d ( c , p )三 鑫 ( mz ) ( 慈 ( 7 ) ( ( 1 一p ) ” 一 p t 、.尹 m 一三2 尸 z j ( 1 一 p y 【一 2 ， p 2 , 二月、艺倒 丈一丈- 几d ( g , t ) ， ， : j ( ，一。 a ) ( ， ) “ 饥 j ( 。 一? ， ) j ( 了 i ) 2 _ m - 1( z 止一 ( :。 ) 盖 ( ,. ( a 一i ) 1m 一 1 2 0 a ( .7 !) 2 1 m 一1 c a 一 2 - c b m 一 1 11一勺 c d 只 . o. 州c ) 证毕。 ( c a ) ( 7 n ( n 一 7 2 ) ) 1 对于最 优二元( n , 2 8 , w ) ( 见定义5 ) 由于 nw 了1、一、.尹 n 一w ( g i l b e r t b o u n d , 4 ) 势- m 很容易有以下结论: 推论3: 对于最优二元( n , 2 6 , 叫等重码c， 有 b ( c ) 全 ( z 0 l eb ( c a ) zm ( 7 n ( 。 一 m .) ) 2 其 中 c a 一 e- a 命 g = h t - 1 17 ( , a ) ,- (二 n - m ) ) 1 接下来我们想了 解在区间0 , d ( g ) 中，p , ,d ( c , p ) 的单调特性， 下面给出了一个特例，一般的情况可以进一步探讨。 定 理 5: 对 于 最 优 二 元 等 重 码(， “ 、 2 ) ) ， 当、 全 1时p ,d ( c , p ) 在区间0 , 8 ( c ) ! 中 单 调 递 增， 且s ( c ) 、是 证明: 当。 为 偶数时 ， 对于 最 优二元 等 重 码( n , 2 , a ) ， 它的 距离 分 布为 : 2 二0 ; 1 , 、 j 为奇数 )l2 所以 鑫 l jj= z (异 ) ( 一 是 ) 一 z ( : ) (是 ) (卜 2ln !”一2i ( : ) (是 ) ( 一 27l ) n-2 ( 卜 2 ) “ 一 1 !( + n -22) 2-几 c d 几 1一夕 由 弓 i理 1 知 : ( 。 ， 与 l _ 世 2 . 一 了 之 3 4 . 8 1护 解不等式 所以， : 3 5 时 p ,d (c . n ) p ,d (c , 2 几山一刀 。 又 o (c ) 、 兰 。 p a ( c , p ) 在0 , o ( c ) 中 单调递增。 7 l 为奇数时， 类似可证、 4 1 时p . d ( c , p ) 在 0 , h ( c ) 中单调递增， 且o ( c ) 4 0 时，定理成立。 当、 1 7 时，o ( c ) 2 / n。 证毕。口 注 : 因 此 当 二 : 1 7 时 ， 我 们 可 以 方 便 地 求 出 码(n . 2 , !剖 ) 的 14 值 。 下面这张表给出了当 的闭值，其中w ( c ) 三 1 7 ” 5 0 时 ， 最 优 二 元 等 重 码恤 ， “ ， 剖 ) b ( c ) 0 1 ( c ) +0 .0 0 0 1 。 nb ( c ;) n 乡 1 ( c ) n =1 70 . 1 0 8 9n =1 80 . 1 0 3 2 n =1 9。0 9 1 5n =2 00 . 0 8 7 2 n=2 10 . 0 7 8 4n =2 20 . 0 7 5 0 n =2 30 . 0 6 8 3n=2 40 . 0 6 5 5 n=2 50 . 0 6 0 2n =2 60 . 0 5 8 0 n =2 70 . 0 5 3 7n =2 80 . 0 5 1 8 n =2 90 . 0 4 8 2n =3 00 . 0 4 6 7 n =3 10 . 0 4 3 7n =3 20 . 0 4 2 4 n =3 30 . 0 3 9 9n=3 40 . 0 3 8 7 n =3 50 .0 3 6 6n =3 60 .0 3 5 6 n =3 70 . 0 3 3 7n =3 80 . 0 3 2 9 n=3 90 . 0 3 1 2n =4 00 . 0 3 0 5 n =4 10 . 0 2 9 1n=4 20 . 0 2 8 4 n =4 30 . 0 2 7 1n=4 40 . 0 2 6 5 n =4 50 . 0 2 5 4n =4 60 . 0 2 4 9 n =4 70 . 0 2 3 9n=4 80 . 0 2 3 4 n=4 90 . 0 2 2 5n =5 00 . 0 2 2 0 i 3 总结 本文首先讨论了 二元互补2 一 重量码( 、2 、 一 : 。 ) 的阂值的极 限行为， 可以 看出它的阂 值的 极限行为是清楚的; 然后给出了一般二 元等重码 ( ，2 6 叫 的闭值的下界，这可以用来比较方便地估计这类 码的团值的范围， 来检验这类码是否适合用作实际信道的检错码; 最 后 讨论了 最 优二 元 等 重 码( n , a , n ) 在区间0 , s ( c ) 中 的 单 调特 性， 从 结论可以 看出 大多数 这类码在区间10 , o p1 中 是单调递增的， 利用 这个单调特性可以方便地用计算机求出这类码的闭值，而且从表中 可看出o ( c ) 都比 较大， 比 通常的信道错误概率p 大 得多( 一般来讲 p 任( 功 一 “ ， 1 0 - a ) ) ， 至 于其 他类型的最优等重码( n , 2 叫也可 类似讨 论码在区间 0 , 8 ( c ) 中的单调特性。 re f e r e nc e s 1 f . w. f u , t o r l e i v k l o v e ,a n d s . t . x i a , o n t h e u n d e t e c t e d e r r o r p r o b a b i l i t y t h r e s h o l d o f m - o u t - o f - n c o d e s o n t h e b i n a r y s y m m e t r i c c h a n n e l 2 s . r o m a n , c o d i n g a n d i n f o r m a t i o n t h e o r y , b e r li n : s p r i n g e r - v e r l a g , 1 9 9 2 . 3 w. w. p e t e r s o n a n d e .j . w e l d o n ,j r e r r o r - c o r r e c t i n g c o d e s , c a m - b r i d g e , ma s s . : mi t p r e s s , 1 9 7 2 4 a . e .b r o u w e r ,j .b .s h e a r e r ,n .j . a . s l o n e ,a n d w. d . s m i t h , a n e w t a b l e o f c o n s t a n t w e i g h t c o d e s ,i e e e t r a n s .i n f o r m. t h e o r y . v o l i t - 3 6 , p p . 1 3 4 4 - 1 3 8 0 , 1 9 9 0 . 5 f .j .m a c wi l h a m s a n d n . j .a . s l o n e , t h e t h e o r y o f e r r o r - c o r r e c t i n g c o d e s , n o r t h - h o ll a n d p u b li s h i n g c o m p a n y , 1 9 7 8 6 t . k l o v e , r e e d - m u l l e r c o d e s f o r e r r o r d e t e c t i o 工 ; a h e g o o d , t h e b a d , a n d t h e u g l y , i e e e t r a n s . i n f o r m. t h e o r y . v o l i t - 4 2 , p p . 1 6 1 5 - 1 6 2 2 , 1 9 9 6 7 t . k l o v e ,a n d v .k o r z h i k , e r r o r d e t e c t i n g c o d e s , g e n e r a l t h e o r y a n d t h e i r a p p li c a t i o n i n f e e d b a c k c o m m u n i c a t i o n s y s t e m s . b o s t o n :k l u w e r a c a d . p r e s s , 1 9 9 5 . 8 x . m .wa n g , e xi s t e n c e o f p r o p e r b i n a r y ( n , 2 ， 二 ) c o n s t a n t w e i g h t c o d e s a n d 、 c o n j e c t u r e . s c i e n c e i n c h i n a , s e r i e s a ( i n c h i n e s e ) , v o l . 1 7 , n o . 1 1 p p . 1 2 2 5 - 1 2 3 2 , 1 9 8 7 9 x . m .w a n g , t h e u n d e t e c t e d e r r o r p r o b a b i l i t y o f c o n s t a n t c o d e s , a c t a e l e c t r o n i c a s i n i c a 扛 n c h i n e s e ) , v o l . 1 7 ,n