（运筹学与控制论专业论文）可辨性父码的新进展.pdf

中英文摘要 缠醴是一门发展迅猛的年轻学科，确切地说它诞生于1 9 4 8 年，广泛应 用于数学、通讯、工程和计算机科学等领域编码理论可以认为是电子技术 飞速发展以后。针对当代数学通讯和数字存储的具体需要，于五十年代发展 起来，并成为- - f - 面目全新的应用数学研究编码理论通常应用代数工具。特 别是有限域和线形代数方面的知识本文的工作，主要利用图论的方法，考 察一类具有特殊性质的码，这类码在软件、通讯的保密性中有重要作用假 设c 是长为n 的g 一元码，a ，b 为其两个码字其中a = ( a l ，a 2 ，。) ，b = ( b 1 ，b 2 ，k ) 如果存在c = ( e l ，c 2 ，c n ) ，且c i o t ，b i ( i = 1 ，2 ，n ) ， 那么就称c 为a ，b 的子码，a ，6 为c 的父码码c 具有可辨性父码是指对g 中码字的任意子码c 都能在口中确定c 的至少一个父码，这种性质称为有 父码可辨性，简称为i p p 记所有长为n 的口一无i p p 码0 的最大个数为 f ( n ，g ) ，即f ( n ，口) = m a x i c l l c q “，ch a si p p ，i q i = g 我们主要是 研究具有此性质的码c 的最大个数f ( n ，口) h e n kd l h o l l m a ne t 【l 】已给 出了f ( n ，q ) 的一些界姜文 3 1 得到了f ( 4 ，口) 的上界q 2 ，n o g a a l e r te t 【2 】 完成了f ( n ，口) = o ( q 2 ) 的证明本文主要运用图论及组合的方法，按极小距 离( 最小的海明距理1 4 记为d 0 ) 分类研究了f ( 4 ，q ) 的准确值，而且得到了 它的编码方法_ 隹要结论如下z o ) d o = 3 ，设宣= 1 2 k 十3 t + r ( k 0 ，0 t 3 ，0sr 2 ) 。，i4 8 k + 1 2 t ，1 2 口，r = 0 。 i4 8 k + 1 2 t + r + 2 ，1 2 sq ，r 0 ( i i ) d o = 4 ，f 4 ，司= 口r v a b s t r a c ti f ci saq - a r yc o d eo f l e n g t hna n daa n dba r et w o c o d e s w a r d s ， t h e nci sc a l l e dad e s e n d a n to f aa n db i f q o ，b i ，f o ri = 1 ，2 ，礼，w e a r ei n t e r e s t e di nc o d ecw i t ht h ep r o p e r t y t h a t ，g i v e na n yd e s c e n d a n tc ，o n e c a l l a l w a y si d e n t i f ya tl e s to n eo ft h ep a r e n tc o d e w a r d si nc h e n dd l h o l l m a n ne t 1 1s t u d i e dt h eb o u n d so nf ( n ，q ) ，t h em a x i m a lc a d i n a l i t yo f ac o d ecw i t ht h i sp r o p e r t y ，w h i c hi st h ei d e n t i f i a b l ep a r e n tp r o p e r t y s u c h c o d e sp l a yar o l ei ns c h e m e st h a tp r o t e c ta g a i n s tp i r a c yo fs o f t w a r e t h e v a l u eo ff ( 3 ，q ) a n di t s e n c o d i n gm e t h e dh a db e e ng o ti n 吼t h i sp a p e r 2 c o n t i n u eh e rw o r ko nf ( 4 ，n ) a n do b t a i n e di t sa c c u r a t ev a l u ea n de n c o d i n g m e t h e d 关键词：码；码字；父码；子码；正则码；父码可辨性；图；子图 第一节引言 假设e 是一个长为n ，字母集为q 的码字集，即c 驴，其中f q i = q 对y a ，b q ”，a = ( a l ，a 2 ，) ，b = ( b 1 ，b 2 ，k ) ，这里称a i ，b i 分别为 a ，b 的第i 个坐标，定义a ，b 的子码集d ( a ，b ) 为 d ( a ，b ) = 霉q “i z = ( z 1 ，z 2 ，z 。) ，x i 啦，魄) ，i = 1 ，2 ，礼) 对码c ，定义其子码集伊为 c = u d , 6 c ( a ，b ) ，( 口b ) 例如，假设码c 是长为4 - - _ 元海明码【4 】，则c = 霹 4 1 若码c c 而且c d ( a ，6 ) ，( a 6 ) ，其中a c ，b c ( a 6 ) ，则称 a ，b 为c 的父码一般地，伊的码字有几对父码，平凡的例子就是码c 的 码字自己称码g 具有父码可辨性( i p p ) 是指，对y c c + ，在c 中它的父 码中至少有一个可以辨认换句话说，v c 口，j 7 r ( c ) g ，使得c 的每对父 码都含有码字7 r ( c ) 我们主要研究具有i p p 码g 的最大码字数，定义为 f ( n ，q ) = m n x i c f l c q ”，ch a si p p ，| e f = 心 定义1 设a q n ，b 驴，定义a 和b 的距离d ( a ，6 ) 为 d ( 口，b ) = i a l lst n ，啦玩) 1 定义2 一个非平凡码g 的极小距离定义为 d o ( c ) = m i n d ( a ，b ) l a ab c ，a 6 ) h e n k d l h e l l m a n ne t 1 1 研究了f ( 礼，g ) 的一些界当礼= 4 ，q 3 时，f ( 4 ，g ) 的上界在姜文 3 1 中得到，另外n e g a a l e n e t 2 1 证明了f ( 4 ，q ) = 。( 口2 ) n a l o n r a d u k e ，e t 1 8 一 1 2 1 等研究了码c q n 中每个码字c 具有t 个坐标满足i p p 性质的最大阶数，这篇文章中给出了极小距离为3 ，4 的r ( 4 ，q ) 的情况与编码方法，主要结论如下： 3 ff 【4 ，4 】= 1 0 ，f 4 ，5 】= 1 1 ，f 【4 ，6 】= 1 8 ，f 【4 ，7 】= 1 9 ， 脚】= 慨f 4 + 8 1 嚣州4 。9 1 1 2 = 2 7 ，盘节3 9 即1 1 卜4 。 【4 8 k + 1 2 t + r + 2 ，q 1 2 ，r 0 第二节引理 引理2 11 1 1 一m 码c 具有i p p 当且仅当 i p p l ：n ，b ，c c ，a ，ba n d ca r ed i s t i n c t 兮o r8 0 7 t l ei 1 ，2 ，3 ，4 ) a i ，饥a n dqa r ed i s t i n c t i p p 2 ：a ，b ，c ，d c ， o ) n c ，d ) = o 冷f o rs o m ei 1 ，2 ，3 ，4 ) ， o ，氐 n q ，哦 = 0 如果q = 2 ，码字数不小于3 的码没有i p p 性，这由i p p l 易得故现 在假设口3 ，字长为4 的码e ，当q = 3 时，f ( a ，3 ) = 9 下面考察具有 i p p 的此码g 的最大码字数f ( 4 ，g ) ，而且假设码i cj q + 1 n 对于此类码g 应用图论方法比较容易讨论f ( 4 ，g ) 为了研究码g ，我 们考察其对应着色图c 的结构这样来构造码g 的对应着色图g ：它的顶 点集为码c 的码字集，当码字a ，b 的第个i 坐标相同时就连接a ，b 并且着 边色i ( i = 1 ，2 ，3 ，4 ) ，我们称码字c c 的度为它的对应着色图g 的顶点c 的度一个非平凡码g 如果所有码字的度相同则称之为正则码( 即其对应 着色图为正则图) ，否则称为非正则码以后记指标集j 为 1 ，2 ，3 ，4 ) 对码 c 的各个坐标所用字母加以区别标记，用q 表示c 中第i 个坐标的字母集 ( i ，) ，码g 也可称作一个旧1 ，q 2 ，q 3 ，q 4 ) 码令s 为码a 的一个连通 分支，并且着i 一色，则称s 为( i ) 色分支，显然s 是码g 的一个子码集 其余集e s 也是g 的子码集 4 引理2 2 对于f ( 4 ，g ) ， ( i ) f ( 4 ，3 ) = 9 ；( i i ) f ( 4 ，q ) q 引理2 3t 蜀c d ) 对于v c 0 ，总存在n o = 礼( ) ，使得当孔n o + 1 时就有 n 2 5s f ( 4 ，n ) e n 2 ( i i ) v i i ，i 2 i ( i l 2 ) f z cf ( 3 y e ) ( ( 驴z ) a ( y i ，= x d ，) a ( 敬：= 。i ：) ) ) k 12 n 一1 引理2 4 国对于f ( 4 ，口) ， f ( 4 ，q ) sf ( 2 ，q 2 ) = q 2 第三节主要结果 这里对于g q 4 按极小距离d o 1 分类讨论f ( 4 ，q ) 3 1d o = 4 的情况 假设码e q 4 ，当d o = 4 时，其对应着色图c 中任意两点间没有边相 连，也即孤立点图为了构造满足要求的码字集，这里引入如下定义以及相 关结论： 定义3 礼个不同元素的无重复k 序列中，任意两个序列 ( a l ，a 2 ，o k ) ，( b l ，6 2 ，6 k ) ， 对于v i 1 ，2 ，一，) ，如果啦= b i ，则称啦，b i 为同位元 命题3 1 1 ( i ) n 个不同元素长度为k 的无重复序列中。任意两个序列没有 同位元的最大个数为n ； ( i i ) n 个不同元素长度为k 的无重复序列中，任意两个序列恰有一个同 位元的最大个数为n 一1 证明：( i ) 假设满足条件的序列的个数至少为n + l ，则由鸽笼原理【6 】可得必有 一种元素在同一位置出现至少两次，此时即至少有一对序列有一个同位元， 5 与已知矛盾；而且对n = 1 ，2 ，3 ，n ) ，可以这样构造s = ( 1 ，2 ，3 ，) ， ( 2 ，3 ，4 ，- 一，k + 1 ) ，( k + 1 ，k + 2 ，一，2 k ) ，( n ，1 ，2 ，一，k 一1 ) ) ，易 见i s i = n ，而且满足条件，从而得证 ( i i ) 应用与前面构造码g 的对应图a 的方法，来构造此序列s 的对应 着色图s ，则该图s 为顶点数为i s i 的完全图易证得该图只能为1 一色完 全图，否则与已知矛盾不妨假设该图为( 1 ) 一色图，即该序列中除了第一 位外，余下k 一1 个位置没有同位元，则满足条件的序列个数也即余下n 一1 的个不同元素的长度为k 一1 的无重复序列，由( i ) 得最大个数为n 一1 从 而得证 定理3 1 任意码g q 4 ，当d o = 4 时f ( 4 ，q ) = q 证明：当码g 驴的极小距离d 0 = 4 时，由定义知道图c 是阶为i c i 孤 立点集，又由命题3 1 1 可得lci q 例子3 1 例子令q = 1 5 时，由以上的证明可构造如下的d o = 4 的码g 为： 3 2d o = 3 的情况 ( 3 ，1 ，1 ，2 ) ( 8 ，6 ，6 ，7 ) ( 1 3 ，1 1 ，1 1 ，1 2 ) ( 4 ，2 ，2 ，3 ) ( 9 ，7 ，7 ，8 ) ( 1 4 ，1 2 ，1 2 ，1 3 ) ( 5 ，3 ，3 ，4 )( 6 ( 1 0 ，8 ，8 ，9 )( 1 ( 0 ，1 3 ，1 3 ，1 4 ) ( 1 当d o = 3 时，其对应着色图g 中任意两点间至多有一条边相连为了 研究该情形时码c 的f ( 4 ，n ) 值，引用姜文定义的码g 的效率e ( 8 ) = lci 川q ll + iq 2i + iq 3i + lq 4i ) 吼记j 厶为阶是n 的完全图【5 】如无 特殊说明，以下记法和定义按前面所述为准，有关图论的其它概念参考文献 【5 】 命题3 2 1 在图g 中，任意三角形的边色相同或彼此互异 证明：在图g 中任取三角形，设其兰顶点分别为a ，b ，c 若存在i 使得a l = b i = g “d ，则由码g 的极小距离3 可得唧，b ，q 0 i t ) ) 中任意两个 彼此互异，即此时该三角形边色相同，此时c ( 。) = 3 l o ；若存在t 五a i = b i ，b j = c j ( i ，j j ) ，那么第三边色显然不同于t ，j ，否则与d o = 3 矛盾，故 6 、 吣 印j 毛 r 9 1 4 吼鸟 4 ，1 ，1 ，d 1) ) o 1 6 1 m 宙m 1 一互偿盯0 ，-iiiliill、 | | g a k = c k ( i i ，j ) ) 即此时该三角形边色彼此互异，此时c ( 。) = 1 3 可 见当三角形边色彼此互异时效率最高 命题3 2 2 对于图c 中任意完全子图k 4 ，最高效率g ( 8 ) = 2 5 证明：记图c 中四边形为| s ( i ) 如果图s 的边色为1 一色时，加上两条对角线即是1 一色j 厶，此时 g ( 8 ) = 4 1 3 2 5 ； ( i i ) 如果图s 的边色为2 一色时，只能是两条对边分别同色，否则将与 d o = 3 矛盾f 若调整对角码字的第三字母使得l 口3f = 2 则可得3 一色蚝， 此时g ( 。) = 2 5 ；或者令iq 3 | = iq 4 | = 3 ，则可得4 一色尬，此时也有 e ( 。) = 2 5 ； ( i i i ) 如果图s 的边色为3 一色时，则必有两边同色，此时可得1 一色娲， 又由命题3 2 1 为得到第二条对角线只能着色为第四色，此时c ( 。) = 4 1 1 2 5 ( i v ) 如果图s 的边色为3 一色时，则与i p p 2 矛盾综合以上情形可得 g ( 。2 5 命趣3 2 3 对于因c 中任意完全子图j b ，最高效率c ( 。) = 5 1 1 证明，( i ) 如果子图j b 的边色为1 一色时。c ( 。) = 5 1 6 5 1 1 ； ( i i ) 如果子图j g 的边色不是1 - 色时，如果j b 有一个1 一色硒时，由 命题3 2 1 可知第五个顶点只能与其余最多兰个点之间有边相连，而且边色最 多只能为其余三色，不可能构成飓，对于此类五边形，c ( 。) = 5 1 4 5 1 1 ； 因此该j 如中最大的1 一色子图只能为j 臼，那么当有一个1 一色凰和九 个3 一色j b 时，g ( 。) = 5 1 1 ；当有两个1 一色j 6 和八个3 一色妫时， e 扣) = 5 1 2 5 1 1 ； 综上得证 命题3 2 4 在图d 中，四种边色均出现 证明：令s 为( 锐，锐，旗，硪) 一码，则有 ( i ) 假设图c 中所有的边着色为一种，不妨设为1 色，此时s 是一个 1 一色团，那么s 的码字的第二，三。四坐标均互异，而且在图g s 中的其 它码字相应坐标上不重复出现，显然有l q i l = 1 ，l s i = i 砚l = l q ：1 = l q 扎 ( i i ) 假设图g 中的边着色为两种，不妨设为1 色，2 色，那么s 的码 字的第三，四坐标均互异，而且在图口s 中的其它码字相应坐标上不重复 7 出现。故有l s i = i q j i = l q ：| ( i i ) 假设图g 中的边着色为三种，不妨设为1 一色，2 一色，3 一色，同 理s 的码字的第四坐标均互异，故有l s i = l q 4 1 综合以上三种情形可得i c isq ，这与假设l c i q + 1 矛盾，因此在图 c 中四种边色均出现 为了构造相应的i p p 码，我们需要一些有关代数方面的知识，这里未加 说明的名词可以参考文献【l 铷有以下结论： 命题3 2 5 如果n ( 为素数) 元集合s = 1 ，2 ，- 一，他) ，| m ，t n ( 自然数 集) ，v z s ，定义一个从s 到s 的函数，： ，：z 卜。，z 三e + 口( m o dn ) 令，( “) ( 盘) = ，( ，( m - 1 ) ( $ ) ) ( m 2 ) 那么则有， ( )，( s ) = s ；0 i ) v z 只i 暑ly = ，( m ) ( $ ) ，m es l = n ； ( i i i ) v z l ( ) $ 2 最，( ”j 1 ) ，( “) ( 茁2 ) 说明：这些结论由代数的知识可得，这里不再累述 对于任意一个码字集岛，当d o = 3 时，任意两点之间不会超过两条边， 因此任意三个彼此不同的码字满足条件i p p l ，下面先来考虑d o = 3 的最大 码字集数p ( 4 ，口) 首先研究码g 为正则码的情况，有以下结论： 定理3 2 假设码q 是字长为4 的口元正则码且d o = 3 ，那么则有 f 4 ( 4 ，q ) = 3 q 证明：证明：首先由命题3 2 4 可得仅当图a 的每个顶点位于4 一色团的 交点时码g 达到最大，注意到每个顶点在一个团内的度最大为q ，这个结论 可由命题3 1 1 得，假设此团为i 一色团，则此团的个数不会多于3 ，否则与 d o = 3 矛盾! 即此时g 是具有3 个阶为口的团j 乙v c q 4 ，若c 叠y ( g 1 ) ， 则可由命题4 知必然存在d ，使得c ，c i 有两个同位元，这与d o = 3 矛盾，因 此f + ( 4 ，q ) = 3 q 例子3 2 例子令q = 1 5 时，由定理的证明可得d 0 = 3 的q 一元匀称码a 为：，7 j l 8 c l = ( 0 ，0 ，0 ，1 ) ( 0 ，1 ，1 ，2 ) ( 0 ，2 ，2 ，3 ) ( 0 ，3 ，3 ，4 ) ( 0 ，4 ，4 ，5 ) ( 0 ，5 ，5 ，6 ) ( 0 ，6 ，6 ，7 ) ( 0 ，7 ，7 ，8 ) ( 0 ，8 ，8 ，9 ) ( 0 ，9 ，玩1 0 ) ( 0 ，1 0 ，1 0 ，1 1 ) ( 0 ，1 1 ，1 1 ，1 2 ) ( 0 ，1 2 ，1 2 ，1 3 ) ( 0 ，1 3 ，1 3 ，1 4 ) ( 0 ，1 4 ，1 4 ，1 5 ) ( 0 ，1 5 ，1 5 ，0 ) ( 1 ，0 ，1 ，0 ) ( 1 ，1 ，2 ，1 ) ( 1 ，2 ，3 ，2 ) ( 1 ，3 ，4 ，3 ) ( 1 ，4 ，5 ，4 ) ( 1 ，5 ，6 ，5 ) ( 1 ，6 ，7 ，6 ) ( 1 ，7 ，8 , 7 ) ( 1 ，8 ，9 ，8 ) ( 1 ，9 ，1 0 ，9 ) ( 1 ，1 0 ，1 1 ，1 0 ) ( 1 ，1 1 ，1 2 ，1 1 ) ( 1 ，1 2 ，1 3 ，1 2 ) ( 1 ，1 3 ，1 4 ，1 3 ) ( 1 ，1 4 ，1 5 ，1 4 ) ( 1 ，1 5 ，0 ，1 5 ) ( 2 ，1 ，0 ，0 ) ( 2 ，2 ，1 ，1 ) ( 2 ，3 ，2 ，2 ) ( 2 ，4 ，3 ，3 ) ( 2 ，5 ，4 ，4 ) ( 2 ，6 ，5 ，5 ) ( 2 ，7 ，6 ，6 ) ( 2 ，8 ，7 ，7 ) ( 2 ，9 ，8 ，8 ) ( 2 ，1 0 ，9 ，9 ) ( 2 ，1 1 ，1 0 ，1 0 ) ( 2 ，1 2 ，1 1 ，1 1 ) ( 2 ，1 3 ，1 2 ，1 2 ) ( 2 ，1 4 ，1 3 ，1 3 ) ( 2 ，1 5 ，1 4 ，1 4 ) ( 2 ，0 ，1 5 ，1 5 ) 用以上面的例子说明q 不满足i p p 2 记其中三个1 一色团分别为蜀= ( 0 ，礼，n ，n + ) ，乃= ( 1 ，n ，n + ，竹) ，乃= ( 2 ，n + ，n ，n ) ，这里札+ 兰( n + 1 ) ( m o d 口) ，0 札，qs1 5 取( 0 ，n ，n ，n + ) ，( 0 ，t ，t ，t + ) ，( 1 ，u ，u + ，u ) ，( 2 ， + ，u ， ) c 1 ( n t ( m o d 口) ) ，依次相连构成四色四边形，由环排列可得四色有6 种着色方式， 由对称性可知不同构的着色方式只有3 种：( 1 2 3 4 ) ，( 1 3 2 4 ) ，( 1 2 4 3 ) 下面分别 讨论： ( i ) 若边色为( 1 2 3 4 ) 型，则有 i t 三 + ( r o o dg ) i t 兰 + 1 ) ( r o o dg ) u 兰u + ( m o dg ) = 争 u 三( 让+ 1 ) ( r o o dq ) 辛三礼+ 3 ( m o d 口) 【u 三矿( m o c lq )【钍三( n + 1 ) ( r o o dq ) 即此时满足t 兰n + 3 ( m o c lq ) 就有一个四色四边形，这与i p p 2 矛盾! 比如 令n = o ，t = 3 ，“= 2 ，u = 3 ，码子( 0 ，0 ，0 ，1 ) ，( 0 ，3 ，3 ，4 ) ，( 2 ，3 ，2 ，2 ) ，( 1 ，1 ，2 ，1 ) 即是 9 ：t=三v(m篙odq ) 暑兮t = - - v ( m o dq ) = 暑= ，t - = n ( m o d q ) 窿戳辛惟糍：，：= ，t = - - n ( m o d q ) 这里p i 三【p l - 4 - ( i 一1 ) 。】( l d dn ) ，1 。sn ，i = 2 ，3 ，4 证明：对于已知条件，定义一个从到的函数，： ，：戤三洳l + ( 1 1 ) x ( m o d 竹) 这里p l n = o ，1 ，2 ，托一1 ) ，1sz 仃，i = 2 ，3 ，4 由命题3 2 5 可 得对p 1 n ，码字集合i ( p 1 ，p 2 ，p 3 ，p 4 ) ) l = n 而且当p l 取遍时就有 i ( p l ，p 2 ，p 3 ，p 4 ) ：0 p l n 一1 ) 1 = 舻，从而得证 但是q 不是i p p 码对p 1 n ，码字集合 p l ，耽，p a ，m ) ) 的对应着色图 为( 1 ) 一色团，当p l p j 时，码字集合 ( p 1 ，p 2 ，p 3 ，p 4 ) ，( 硝，p 2 ，p 3 ，p 4 ) ) ，d o = 3 ， 否则有p l 兰p ；( m o dn ) ，矛盾! 故c 1 满足i p p l 下面证明不满足i p p 2 由q 的构造可得有n 个( 1 ) - 色团，n = 0 ，1 ，2 ，n 一1 ) ，令其码 字为 ( o ，m ，f ，p ) c 2 n 4 ，a ，m n ，f 三( 2 m a ) ( m o d 礼) ，p 兰( 3 m 一2 a ) ( m o d n ) 1 0 不妨取码字( a ，m ，f ，p ) ，( a ，u ，u ，枷) ，( c ，z ，y ，z ) ，( b ，e ，f ，9 ) g ，依次相连构成 四色四边形，由环排列可得四色有6 种着色方式，由对称性可知不同构的着 色方式只有3 种：( 1 2 3 4 ) ，( 1 3 2 4 ) ，( 1 2 4 3 ) 下面分别讨论： ( t ) 若边色为( 1 2 3 4 ) 型，则有 a b ，b c ，c a ( m o d n ) m u ( m o d n ) 让三x ( m o dn )辛6 ( m 一让) 兰( 4 a b 一3 c ) ( m o d 礼) y 三f ( m o d n l g 兰p ( m o d 礼1 即此时满足6 ( m u ) 三( 4 a b 一3 c ) ( m o dn ) 就有一个四色四边形，这与 i p p 2 矛盾i 比如令a = 0 ，b = 3 ，c = 1 ，m = 0 ，“= 1 ，即是码字( 见后面例 子) ( 0 ，1 ，2 ，3 ) ，( 0 ，2 ，4 ，6 ) ，( 1 ，2 ，3 ，4 ) ，( 3 ，3 ，3 ，3 ) ( i i ) 若边色为( 1 3 2 4 ) 型，则有 a b ，b c ，c a ( m o d 佗) m u ( m o d n ) 钉三y ( m o d ，1 ) = 6 ( m t ) 兰( o 一4 6 + 3 c ) ( m o dn ) 。三e ( m o dn 1 g 兰p ( m o d n l 即此时满足6 ( m u ) 兰( a 一4 b + 3 c ) ( m o dn ) 就有一个四色四边形，这与 i p p 2 矛盾l 比如令a = 3 ，b = 0 ，c = 1 ，m = 5 ，u = 4 ，即是码字( 见后面例 子) ( 3 ，5 ，7 ，9 ) ，( 3 ，4 ，5 ，6 ) ，( 1 ，3 ，5 ，7 ) ，( 0 ，3 ，6 ，9 ) ( 俐) 若边色为( 1 2 4 3 ) 型，则有 a b ，b c ，c a ( m o d n ) m u ( m o d n ) 札三= ( r o o dn 1 g 三z ( m o d n 1 l 三f ( m o d n l 号6 ( m 一“) 兰( 3 a + b 一4 c ) ( m o dn ) 即此时满足6 ( m 一扎) 三( 3 a + b 一4 c ) ( m o dn ) 就有一个四色四边形，这与 i p p 2 矛盾! 比如令a = 1 ，b = 3 ，c = 0 ，m = 6 ，u = 5 ，即是码字( 见后面例 子) ( 1 ，6 ，0 ，5 ) ，( 1 ，5 ，9 ，2 ) ，( 0 ，5 ，1 0 ，4 ) ，( 3 ，7 ，0 ，4 ) 例子3 3 例子，取n = 1 1 时，由定理3 2 的证明可得d 0 = 3 的q - 元匀称 码q 为( 这里t 为模n 值) ： 岛= 三行的省略号分别为： ( 0 ，t ，2 t ，a t ) ，( 1 ，t + 1 ，2 t + 1 ，3 t 十1 ) ，( 1 0 ，t + l o ，2 t + 1 0 ，3 t + 1 0 ) 从上面的讨论我们可以知道， 如下结论： 定理3 4 假设d 0 = 3 ，q 4 ， 当q 4 时，f ( 4 ，q ) 是达不到q 2 的，因此有 f 4 ，g 】 q 2 由f ( 4 ，3 ) = 9 可得此三元海明码( 记作h ( 4 ，3 ) ) 是最好的码，因为其 对应着色图是阶为9 的完全图，四种边色均出现，而且( 1 ) ，( 2 ) ，( 3 ) ，( 4 ) 一色 团均为4 个易见此海明码为正则码，而且g ( e ) = 3 4 非匀称码c 以这 样的海明码为子码时达到最大，因此下面考虑构造以海明码为子码的非匀称 码，直到不能再加入码字为止通过分类讨论可以得到以下结论： 定理3 5 假设码c 是字长为4 的g 一元非园嵇码，并且 d 0 = 3 ，q = 1 2 k + 3 t + r ( 0 sk ，0 s t 3 ，0 sr 2 ) ，那么月l | 有 证明： ( i ) 4sq 1 1 、， 、j u 1 0 0 1 ， o l 加 ， ， 0 m 0 if 、lj 8 9 0 9 o o ，1 ， 0 ， 0 d 棚 q 0 1 l ，l 、j 6 7 5 4 5 3 2 3 l ， ， ， 0 l 0 ，l 1 ，【、j 3 4 2 2 3 1 1 2 0 0 1 0， 坶 i | 一一q 孔一 生mh ； “卜 q m 0 电电 小国 蜘 u 疗0 一 = = 一他 一吼墨 4 4，i 即球醚h地跪一+ | l l l 地拢叫删十十 4 4 女州州钙够 ，、【 | l 酊qh 当q = 4 = 3 + 1 时，可以构造一个海明码日1 ( 4 ，3 ) 及一个孤立码字 n = ( o d ，0 4 ，n 4 ，a 4 ) 若还有码字c = ( c 1 ，c 2 ，c 3 ，c 4 ) ，则必然有d ( o ，c ) + d ( c ，h ) = 4 ( v t 日1 ) ，这与d o = 3 矛盾故有f 4 ，4 = 1 0 同理有f 【4 ，5 】= 1 1 当q = 6 = 3 x2 时，可以构造二个海明码皿( 4 ，3 ) ，玩( 4 ，3 ) ，则有 f 4 ，6 】= 1 8 同理有f 【4 ，7 】= 1 9 ，f 4 ，8 】= 2 2 ，f 4 ，9 】= 2 7 当口= 1 0 = 3 x 3 + l 时，可以构造三个海明码凰( 4 ，3 ) ，岛( 4 ，3 ) ，凰( 4 ，3 ) ， 下面用余下的一个字母及另外三个字母h i j 凰“= 1 ，2 ，3 ，j = 1 ) 由命题 3 1 1 构造4 个码字，同理j = 2 ，3 ( 危1 j 。， 2 j 。， 甜l ，) n h l j 。，h 2 j 。，h 3 j 。，) = 0 ，j l ( ) j 2 1 ，2 ，3 ) ) 时可构造8 个码字经过计算有f 4 ，1 0 = 3 9 同理 有v 1 4 ，1 1 1 = 4 0 ( i i ) 1 2 口j ，t ，r , 1 七，0 t 3 ，0 r 2 ，使得口= 1 2 k + 3 t + r 当r = 0 时，首先构造4 七十t 个海明码皿( 4 ，3 ) ，1 i 她+ t ，下面用 三组4 + t 个字母h q 甄，j l ( # ) j 2 1 ，2 ，4 七+ 好，( 1 j ，h 2 j ，h 3 j ，) n l 如，h 2 j 。，h 3 j 。， = 0 ，) 应用命题3 1 1 构造( 4 + t ) x3 个码字，则有 f 4 ，口】= 4 8 k + 1 2 t 当r = l 时，同上构造4 南+ t 个海明码甄( 4 ，3 ) ，1si 墨4 k + t ，下面用 三组4 七+ t 个字母h q 风，j l ( 1 ，2 ，4 + t ) ，( l j 。，h 2 j 。，h 3 j 。，n ( h u ， ，h a j ：， = 0 ，) ，每组再加上余下的一个字母应用命题3 1 1 构造 ( 4 + t + 1 ) x3 个码字，则有f 4 ，口】= 4 8 k + 1 2 t + 3 当r = 2 时，同上构造4 七+ t 个海明码甄( 4 ，3 ) ，1s i 4 k + t ，下面用 三组4 + t 个字母h i j 凰，j l ( ) j 2 l ，2 ，4 + t ) ，( h l j 。，h 2 j 。，h 3 j ，) n 九i 如，h 2 j 。，h 3 j 。，) = d ，) ，如果同上用三组4 + t 个字母h q 皿，j l ( ) j 2 1 ，2 ，4 + 略，( l j ，h 2 j 。，h 3 j ， n h l j 。，h 2 j 。，h 3 j 。) = 0 ，) ，每组再加上 余下的2 个字母，应用命题3 1 1 构造( 4 七+ t + 2 ) x3 个码字，则会出现 d ( c l ，c 2 ) = 2 ，矛盾故此时仅比r = 1 时多一个码字，即f 【4 ，g 】= 4 8 k + 1 2 t + 4 = 4 8 k + 1 2 t + r + 2 从而原命题得证 例子3 4 例子，取g = 3 5 ，由定理3 3 的证明可得d o = 3 时口= 1 2 2 + 3 3 + 2 ，f 4 ，3 5 】= 4 8 x2 + 3 3 + 2 = 1 3 6 ，非匀称码g 为( 参见下页) ： g = ( 0 ，0 ，0 ，1 ) ( 2 ，2 ，1 ，1 ) ( 4 ，3 ，4 ，3 ) ( 3 ，5 ，5 ，3 ) ( 8 ，7 ，6 ，6 ) ( 7 ，8 ，6 ，8 ) ( 9 ，1 0 ，1 0 ，1 1 ) ( 1 1 ，9 ，1 1 ，1 1 ) ( 1 3 ，1 3 ，1 4 ，1 3 ) ( 1 5 ，1 5 ，1 5 ，1 6 ) ( 1 7 ，1 7 ，1 6 ，1 6 ) ( 1 9 ，1 8 ，1 9 ，1 8 ) ( 1 8 ，2 0 ，2 0 ，1 8 ) ( 2 3 ，2 2 ，2 1 ，2 1 ) ( 2 2 ，2 3 ，2 1 ，2 3 ) ( 2 4 ，2 5 ，2 5 ，2 6 ) ( 2 6 ，2 4 ，2 6 ，2 6 ) ( 2 8 ，2 8 ，2 9 ，2 8 ) ( 3 0 ，3 0 ，3 0 ，3 1 ) ( 3 2 ，3 2 ，3 1 ，3 1 ) ( 0 ，3 ，6 ，9 ) ( 1 5 ，1 8 ；2 1 ，2 4 ) ( 3 0 ，3 3 ，0 ，3 ) ( 1 0 ，1 3 ，1 6 ，1 9 ) ( 2 5 ，2 8 ，3 1 ，3 4 ) ( 5 ，8 ，2 0 ，2 3 ) ( 2 9 ，2 3 ，2 6 ，2 9 ) ( 0 ，2 ，5 ，8 ) ( 1 ，0 ，1 ，0 ) ( 0 ，2 ，2 ，0 ) ( 5 ，4 ，3 ，3 ) ( 4 ，5 ，3 ，5 ) ( 6 ，7 ，7 ，8 ) ( 8 ，6 ，8 ，8 ) ( 1 0 ，1 0 ，1 1 ，1 0 ) ( 1 2 ，1 2 ，1 2 ，1 3 ) ( 1 4 ，1 4 ，1 3 ，1 3 ) ( 1 6 ，1 5 ，1 6 ，1 5 ) ( 1 5 ，1 7 ，1 7 ，1 5 ) ( 2 0 ，1 9 ，1 8 ，1 8 ) ( 1 9 ，2 0 ，1 8 ，2 0 ) ( 2 1 ，2 2 ，2 2 ，2 3 ) ( 2 3 ，2 1 ，2 3 ，2 3 ) ( 2 5 ，2 5 ，2 6 ，2 5 ) ( 2 7 ，2 7 ，2 7 ，2 8 ) ( 2 9 ，2 9 ，2 8 ，2 8 ) ( 3 1 ，3 0 ，3 1 ，3 0 ) ( 3 0 ，3 2 ，3 2 ，3 0 ) ( 3 ，6 ，9 ，1 2 ) ( 1 8 ，2 1 ，2 4 ，2 7 ) ( 3 3 ，0 ，3 ，6 ) ( 1 3 ，1 6 ，1 9 ，2 2 ) ( 2 8 ，3 1 ，3 4 ，1 ) ( 8 ，2 0 ，2 3 ，2 6 ) ( 2 3 ，2 6 ，2 9 ，3 2 ) ( 2 ，1 ，0 ，0 ) ( 1 ，2 ，0 ，2 ) ( 3 ，4 ，4 ，5 ) ( 5 ，3 ，5 ，5 ) ( 7 ，7 ，8 ，7 ) ( 9 ，9 ，9 ，1 0 ) ( 1 1 ，1 1 ，1 0 ，1 0 ) ( 1 3 ，1 2 ，1 3 ，1 2 ) ( 1 2 ，1 4 ，1 4 ，1 2 ) ( 1 7 ，1 6 ，1 5 ，1 5 ) ( 1 6 ，1 7 ，1 5 ，1 7 ) ( 1 8 ，1 9 ，1 9 ，2 0 ) ( 2 0 ，1 8 ，2 0 ，2 0 ) ( 2 2 ，2 2 ，2 3 ，2 2 ) ( 2 4 ，2 4 ，2 4 ，2 5 ) ( 2 6 ，2 6 ，2 5 ，2 5 ) ( 2 8 ，2 7 ，2 8 ，2 7 ) ( 2 7 ，2 9 ，2 9 ，2 7 ) ( 3 2 ，3 1 ，3 0 ，3 0 ) ( 3 1 ，3 2 ，3 0 ，3 2 ) ( 6 ，9 ，1 2 ，1 5 ) ( 2 1 ，2 4 ，2 7 ，3 0 ) ( 1 ，4 ，7 ，1 0 ) ( 1 6 ，1 9 ，2 2 ，2 5 ) ( 3 1 ，3 4 ，1 ，4 ) ( 2 0 ，2 3 ，2 6 ，2 9 ) ( 2 6 ，2 9 ，3 2 ，0 ) ( 0 ，1 ，1 ，2 ) ( 2 ，0 ，2 ，2 ) ( 4 ，4 ，5 ，4 ) ( 6 ，6 ，6 ，7 ) ( 8 ，8 ，7 ，7 ) ( 1 0 ，9 ，1 0 ，9 ) ( 9 ，1 1 ，1 1 ，9 ) ( 1 4 ，1 3 ，1 2 ，1 2 ) ( 1 3 ，1 4 ，1 2 ，1 4 ) ( 1 5 ，1 6 ，1 6 ，1 7 ) ( 1 7 ，1 5 ，1 7 ，1 7 ) ( 1 9 ，1 9 ，2 0 ，1 9 ) ( 2 1 ，2 l ，2 1 ，2 2 ) ( 2 3 ，2 3 ，2 2 ，2 2 ) ( 2 5 ，2 4 ，2 5 ，2 4 ) ( 2 4 ，2 6 ，2 6 ，2 4 ) ( 2 9 ，2 8 ，2 7 ，2 7 ) ( 2 8 ，2 9 ，2 7 ，2 9 ) ( 3 0 ，3 1 ，3 1 ，3 2 ) ( 3 2 ，3 0 ，3 2 ，3 2 ) ( 9 ，1 2 ，1 5 ，1 8 ) ( 2 4 ，2 7 ，3 0 ，3 3 ) ( 4 ，7 ，1 0 ，1 3 ) ( 1 9 ，2 2 ，2 5 ，2 8 ) ( 3 4 ，1 ，4 ，7 ) ( 2 3 ，2 6 ，2 9 ，2 3 ) ( 2 9 ，3 2 ，0 ，2 ) ( 1 ，1 ，2 ，1 ) ( 3 ，3 ，3 ，4 ) ( 5 ，5 ，4 ，4 ) ( 7 ，6 ，7 ，6 ) ( 6 ，8 ，8 ，6 ) ( 1 1 ，1 0 ，9 ，9 ) ( 1 0 ，1 1 ，9 ，1 1 ) ( 1 2 ，1 3 ，1 3 ，1 4 ) ( 1 4 ，1 2 ，1 4 ，1 4 ) ( 1 6 ，1 6 ，1 7 ，1 6 ) ( 1 8 ，1 8 ，1 8 ，1 9 ) ( 2 0 ，2 0 ，1 9 ，1 9 ) ( 2 2 ，2 1 ，2 2 ，2 1 ) ( 2 1 ，2 3 ，2 3 ，2 1 ) ( 2 6 ，2 5 ，2 4 ，2 4 ) ( 2 5 ，2 6 ，2 4 ，2 6 ) ( 2 7 ，2 8 ，2 8 ，2 9 ) ( 2 9 ，2 7 ，2 9 ，2 9 ) ( 3 1 ，3 1 ，3 2 ，3 1 ) ( 3 4 ，3 4 ，3 4 ，3 4 ) ( 1 2 ，1 5 ，1 8 ，2 1 ) ( 2 7 ，3 0 ，3 3 ，0 ) ( 7 ，1 0 ，1 3 ，1 6 ) ( 2 2 ，2 5 ，2 8 ，3 1 ) ( 2 ，5 ，8 ，2 0 ) ( 2 6 ，2 9 ，2 3 ，2 6 ) ( 3 2 ，0 ，2 ，5 ) 第四节探讨问题 以上我们研究了d 0 = 4 ，3 的两种情况，对于其余的情况还有待进一步 探讨当d 0 = 2 时，码c 的对应着色图a 中任意两点间至多有两条边，由 引理2 3 ( i i ) 可得此时最大码字数不超过f ( 4 ，0 + 2 q 一1 ，这里f ( 4 ，q ) 为 d 0 = 3 时的最大码字数；当d o = 1 时，码c 的对应着色图c 中任意两点间 至多有三条边，猜想此时最大码字数f ( 4 ，q ) = o ( q 2 ) 参考文献 f 1 】h e n kd l h o u m a n n ，j a c kh v a n ，j e a n - p a u ll i n n a r t za n dl u d om g m t o l h u i z e n ，o nc o d e sw i t ht h ei d e n t i f i a b l ep a r e n tp r o p e r t y , j c o m b i t h e o r l s e r i e sa ，v 0 1 8 2 ( 1 9 9 8 ) ，1 2 1 1 3 3 【2 n o g aa l o n ，e l d a rf i s c h e ra n dm a r i os z e g e b y ，p a r e n t i d e n t i f i y i n gc o d e s ，j c o m b i t h e o r y ，s e r i e sa ，v 0 1 9 5 ( 2 0 0 1 ) ，3 4 9 - 3 5 9 【3 1 3j i a n gw e n ，n e wr e s u l t so nc o d e sw i t ht h ei d e n t i f i a b l ep