（计算机应用技术专业论文）置换码的界及构造的研究.pdf

摘要 长为n ，最小距离为d 的置换码( 阵列) 记为( n ，矗) 置换码，是关于某n 个元素 的置换的集合g ，并且对任意不同的x ，y g ，它们之问的汉明距离至少为d 。 令p ( n ，d ) 记为( n ，d ) 置换码的码元数量的最大可能值。若( n ，d ) 置换码c 的大小i g i = p c n ，田则称之为最优化置换码。p ( n ，田的值的研究被认为是置换码研究的基本问 题。 置换码曾在上世纪7 0 年代有过零星的研究，由于v i n c k ( c o d e dm o d u l a t i o nf o r p o w e d i n ec o l l l 】m u n i c a t i o n s ，p r o e i n t j e l e e c o m m u n ，v 0 1 5 4 ，n o 1 ，2 0 0 0 ) 提出置换码 可应用于电力线通信上的纠错编码，而重新引起了学术界的研究兴趣。本文主要对 置换码理论的最基本问题一置换码的上、下界和构造进行了深入研究。我们取得的 主要结果如下所列； 1 我们证明了一个关于p ( n ，d ) 和忍( 佗，d ) 的不等式。 2 我们给出t p ( n ，d ，加) 的若干基本性质，然后基于它们分别给, q l p ( n ，2 k ) 和p ( n ，2 七+ 1 ) 的新上界。当常数o l ，p 满足某些条件时，若d = 卢n n ，则新上 界渐近优于以往的上界。 3 基于j i a n g 和v a r d y 提出的图论框架，给出了p ( n ，的g i l b e r t - v a r s h a m o v 下界的 三个改进。 4 通过考虑覆盖球的交集，给出了p ( n ，d ) 的g i l b e r t - v a r s h a m o v 下界的二个改进。 5 提出了从( 礼，回置换码分别构造一1 ，d 3 ) 和一1 ，d 一2 ) 置换码的方法，由 此给出当n 和d 取某些情况时置换码的新下界。 6 提出两个由有限域上的分式多项式构造置换码的方法，并由此得到置换码的一 些新下界。 7 证明了阶为n ，最小度为d 的置换群和( n ，置换码的关系，由此得到置换码的 一些新下界。 8 给出了由二元码构造置换码的三个新构造，前两个构造建立 t p ( n ，d ) ，d p ( n ，d ) 和c p ( n ，d ) 之间的些令人感兴趣的不等式，后一个构 造比直接构造更加有效地幂j 用距离保持映射从二元码构造置换码。 9 广义码是各种具体码的抽象形式，包括置换码和二元码等。给出广义码 的g i l b e r t - v a r s h a m o v 界的一个简单新证明，接着证明了一个简单随机构造算法 只需要较低的复杂度就能以较大的概率得到较大的码而以前的a l t r u i s i t i c 算法 由于复杂度太高实际上难以实现。当简单随机构造算法应用于构造置换码时， 与k e e v a s h 和k u 提出的半随机构造算法比较，不仅没有苛刻的实现条件，而且 需要更少的时间。 l o 二元码和置换码有着密切关系。我们给出了二元码距离分布的几个新的线性不 等式，给出改进j o h n s o n 界的一个更加简单的新证明。 关键词：置换码，置换阵列，编码理论，广义码，二元码 a b s t r a c t a p e r m u t a t i o nc e d e ( a r r a y ) o fl e n g t hna n dm i n i m u md i s t a n c ed ，d e n o t e db y ( n ，回 p e r m u t a t i o nc o d e i sa s e to fp e r m u t a t i o n scf r o mg o m gf i x e ds e to fne l e m e n t ss u c ht h a t t h eh a m m i n gd i s t a n c eb e t w e e nd i s t i n c tm e m b e r s 】【y ei sa tl e a s td l e tp ( n ，d ) d e n o t e t h em a x i m u ms i 嚣o f 卸( d ) p e r m u t a t i o nc o d e ，a ( d ) p e r m u t a t i o nc o d ecs u c ht h a t i c l = p ( n ，d ) i sc a l l e do p t m a 1 1 1 es t u d yo f t h en u m b e r sp ( n ，d ) i sc o n s i d e r e dt ob et h e e s s e n t i a lp r o b l e mo f p e r m u t a t i o nc o d e p e r m u t a t i o nc o d e sa r cs o m e w h a ts t u d i e di nt h e1 9 7 0 s v m c k ( c e d e dm o d u l a t i o nf o r o o w e r l i n ec o m m u n i c a t i o n s p r o c i n t j e l e e c o m m u n 。v 0 1 5 4 ，n o 1 2 0 0 0 ) r e n e w e d i n 删i np e r m u t a t i o nc o d e sb yp r o p o s i n gi ta sa ne r r o rc o r r e c t i n gc o d ef o rp o w e r l i n ec o m - m u n i c a t i o n s ，i n t h i s p a p e r , w e f o c u s o n t h e m o s t e s s e n t i a l p r o b l e m s o n t h e o r y o f p e r m u t a t i o n c o d e s t h eb o u n d sa n dc o n s t r u c t i o n s o u rm a i nr e s u l t sa l ef i s t e da sf o l l o w e d ： 1 w e p r o v ea r e l a t i o n b e t w e e n e ( n ，d ) a n d 昂( n ，d ) 2 w eg i v es o m ee l e m e n t a r yp r o p e r t i e so fp ( n ，d ，叫) ，a n dt h e nu s et h e mt os h o wn e w u p p e rb o u n d so np ( n ，2 k ) a n de ( n ，2 k + 1 ) f o rc o n s t a n ta ，卢s a t i s f y i n gc e r t a i n c o n d i t i o n s , w h e n e v e rd = 口n 4 。t h en e wu p p e rb o u n d sa r ea s y m p t o f i c a l l yb e t t e rt h a n t h ep r e v i o u so n e s 3 b a s e do i lt h eg r a p ht h e o r e mf r a m e w o r k 卵e s e n t e db yj i a n ga n dv a r d y , w eg i v et h r c e i m p r o v e m e n t so v e rt h eg i l b e r t - v a r s h a m o vl o w e rb o u n d so ne ( n ，d ) 4 。b yc o n s i d e r i n gt h ec o v e r e db a l l si n t e r s e c t i o n ，w eg i v et w oi m p r o v e m e n t so v e rt h e g - i l b e r t - v a r s h a m o vl o w e rb o u n d so np ( n ， 5 b y p r e s e n t i n g c o n s t r u c t i o n s o f ( n 一1 ，d - 3 ) a n d 扣一1 ，d - 2 ) p e r m u t a t i o n c o d e s f r o m ( n ，d ) p e r m u t a t i o nc o d e s ，s o m e n g wl o w e rb o u n d sf o rp e r m u t a t i o nc o d e sa l eg i v e nf o r s p e c i a lc a s e sf o r 礼a n d d 6 w ep r e s e n tt w oc o n s f f u c t i o u so fp e r m u t a t i o nc o d e sf r o mf a c t i o n a lp o l y n o m i a l so v e r f i n i t ef i e l d ，w h i c hp r o d u c es o m en e wl o w e rb o u n d sf o rp e r m u t a t i o nc o d e s 7 w es h o war e l a t i o nb e t w e e np e r m u t a t i o ng r o u pw i t hd e g r e ena n dm i n i m a ld e g r e ed a n d ( n ，回p e r m u t a t i o nc o d e s ，w h i c hl e a d st os o m en e w l o w e rb o u n d sf o rp e r m u t a t i o n c o d e s 8 w ep r e s e n tt h r e en e wc o n s t r u c t i o n so f p e r m u t a t i o nc o d e sf r o mb i n a r yc o d e s ，i nw h i c h t h ef i r s tt w oc o n s t r u c t i o n sl e a dt os o m ei n t e r e s t e di n e q u a l i t i e so np m ，d ) ，d p ( n ，d ) a n dc p ( n ，d ) ，a n dt h et h i r dc o n s t r u c t i o ng i v e sl a r g e rp e r m u t a t i o nc o d e sf r o mk n o w n b i n a r yc o d e su s i n gp r e s e r v e - d i s t a n c em a p p i n ge o m p a r e dt od i r e c tc o n s t r u c t i o n 9 n 摇g e n e r a l i z e dc o d ei st h eg e n e r a l i z e df o r mo fc o n c r e t ec o d e i n c l u d i n gp e r m u t a t i o n c o d e s ，b i n a r yc o d e s ，e t a 1 w eg i v ean e ws i m p l ep r o o fo fg - i l b e r t - v a r s h a m o vb o u n d f o rg e n e r a l i z e dc o d e s ，a n dp r e s e n tas i m p l er a n d o mc o n s t r u c t i o na l g o r i t h mw i t hl o w e r c o m p l e x i t yw h i c hi sp m v e dt oo b t a i nl a r g ec o d ew i t hs i g n i f i c a n tp r o b a b i l i t y , w h i l et h e p r e v i o u sa l t r u i s i t i ca l g o r i t h mi st o oc o m p l e x i t yt ob er e a l i z e d c o m p a r e dw i t hs e m i - r a n d o mc o n s t r u c t i o np r e s e n t e db yk e e v a s ha n dk u ，t h es i m p l er a n d o mc o n s t r u c t i o n a l g o r i t h md o e sn o tr e q u i r et h es t r i c tc o n d i t i o n sf o rr e a l i z a t i o na n dn e e d $ l e s st i m e w h e ni ti sa p p l i e dt ot h ec o n s t r u c t i o n so f p e r m u t a t i o nc o d e s 1 0 t b eb i n a r yc o d eh a sc l o s e dr e l a t i o n sw i t hp e r m u t a t i o nc o d e w eg i v es e v e r a ln e w i n e q u a l i t i e sf o rd i s t a n c ed i s t r i b u t i o n so fb i n a r yc o d e s ，a n dp r e s e n t e da nn e wp r o o fo f t h ei m p r o v e dj o h n s o nb o u n d w h i c hi ss i m p l e rt h a nt h eo r i g i n a lo n e k e yw o r d s ：p e r m u t a t i o nc o d e s ，p e r m u t a t i o na r r a y s ，c o d i n gt h e o r y , g e n e r a l i z e dc o d e s ，b i - n a r yc o d e s 一1 1 1 主要符号对照表 z ，i z 1 0 最 s 娜( n ) & d ( x ，y ) a ( x ，c ) 以( x ) s u v p ( x ) 加，回码 ，m ，d ) 码 ( 行，吐幻) 等重量( 或常重量) 码 e c n ，回 p ( n ，d ，伽) d p ( n ，d ) c p ( n ， 局( 佗，d ) p 【n ，d l a ( 佗，回 t ( ”1 ，m ，般j 2 ，r t 2 ，妨 f i 】 1 m + e o ，1 ，7 一1 整数 单位置换 全0 向量 a 元有限域 集合f 2 上的所有置换及其结合运算构成的对称群 n 阶置换群 x ，y 问的汉呀( m m m i n g ) 距离 x 和码g 闾的汉明距离 x 的汉明重量 x 的支撑 长度为n 最小距离为d 的码 大小为m ，长度为n ，最小距离为d 的码 长为7 , ，最小距离为d ，重量为叫的等重量码 ( n ，d ) 置换码的最大可能码元数量 ( n ，d ，叫) 等重量置换码的最大可能码元数量 ( 竹，d ) 完全置换码的最大可能码元数量 ( 仡，d ) 循环置换码的最大可能码元数量 定义见( 1 1 ) 定义见( 1 2 ) ( n ，d ) 二元码的最大可能码元数量 定义见( 1 6 ) 取整函数 地板函数 天花板函数 满足m z 的最小非负整数 自然对数的底 主要符号对照表 d ，l ! 矿( 田 ( n ，d ) 子集合 定义见( 1 3 ) n 的阶乘 定义见( 1 4 ) 定义见( 1 5 ) 大小为k 的子集合 上海交通大学 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的作品成果。对本文的研究做出重要贡献的个 人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果 由本人承担。 学位论文作者签名：备揣。膨 日期：翻年剜日 上海交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 司意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和 借阅。本人授权上海交通大学可以将本学位论文的全部或部分内容编入有关 数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位 论文。 保密口，在一年解密后适用本授权书。 本学位论文属于 ， 不保密影 ( 请在以上方框电打“4 ”) 指导教师签名 醐。彳朋叩 恤 和 孙 侗 捌 万 者 年 作 吁 一 碲 凇 力 位 期 荨 日 第一章绪论 长度为n ，最小距离为d 的置换l i b ( p c r m u t a f i o nc o d e ) 或i 换阵歹f l ( p e r m u t a t i o na t - r a y ) 是某n 个固定符号集q 上的置换的集合c ，且对任意不同的x ，y c ，它们之间 的汉明距离至少为d ，即d ( x ，y ) = l 口q ：x ( a ) y ( n ) i d 。我们把长度为n ， 最小距离为矗的置换码，简写为( n ，回置换码，若其大小( 即码元数量) 为m 则简写 为( qm ，d ) 置换码。( n ，d ) 置换码的码元数量的最大可能值记为p ( n ，回，即 v ( n ，d ) ；m a x l e i ：c 是( 鸭d ) 置换码) 若( n ，d ) 置换码的大小达到p ( n ，d ) ，则称为最优置换码。如同其它码的研究，最优置 换码的大d p ( n ，奶是置换码理论研究的基本问题，这也是本文的主要研究内容。 置换码在上世纪7 0 年代曾有零星的研究，这期间的重要论文有【l ，2 ，3 ， 训，2 0 0 0 年v i n c k 瓯6 j 把置换码应用到电力线通信上的纠错编码方案后，重新引起 学术界的研究兴趣。 1 1 纠错编码理论研究简介 通信的目的是要把对方不知道的消息及时可靠地( 有时还需秘密地) 传送给对 方，因此。要求一个通信系统传输消息必须可靠且快速，在数字通信系统中可靠和 快速往往是一对矛盾。若要求快速，则必然使得每个数据码元所占的时问缩短、波 形交窄、能量减少，从而在受到干扰后产生错误的可能性增加，传送消息的可靠性 减低。若要求可靠，则使得传送消息的速率变慢或者增大延迟。因此，如何较合理 地解决可靠性与速度这一对矛盾，是正确设计一个通信系统关键问题之一。通信理 论本身也正是在解决这一对矛盾中不断发展起来的。所有的通信系统都可归结为如 图i i 所示的模型n 8 】： 在图1 1 中，信源编码器是把信源发出的消息如语言、图象、文字等转换成二进 制( 多迸制) 形式的信息序列，同时去掉了一些与传输信息无关的多余度。为了抗 击传输过程中的各种干扰，需要人为的增加多余度，使信号具有自动检错或纠错能 力，这种功能由图中的信道编码器完成。调制器的功用是把纠错码送出的信息序列 通过调制其变换成适合于信道传输的信号。数字信号在传输过程中，总会遇到各种 干扰而使信号失真，这种失真信号传输到接收端的接收机，进行解调，变成二进制 ( 多进制) 信息序列。经过信道译码器，对传输中产生的错误进行纠正，再通过信 源译码器恢复成原来的消息送给用户。 上海交通大学博士学位论文 叶翌圃l 巨乎嘞； 叫翌，圃! ：一，一一； 新宰i m 信磊缔j 箜趔 我们所关心的是图中的信道编、译码器两个方框，为了研究方便，上述模型可 简化为图1 2 ： 图1 2数字通信系统模型 1 9 4 8 年s h a n n o n 在他的开创性论文 9 1 “通信的数学理论”中，首次阐明了在有扰 信道中实现可靠通信的方法，提出了著名的有扰信道编码定理，奠定了纠错码的基 石。 s h a n n o n 编码信道定理： 定理i 1 ：每个信道具有确定的信道容量c ( 它标志该信道最大传输信息的能力。 例如，对于二元对称信道，c = 1 + p l 0 9 2 p + q l 0 9 2 9 ) 对于任意的e 0 及给定 的r ，0 冗 c ，必存在一个分组长度n 足够大而信息率为r 的码。当采用最大似然 译码准则时可使错误译码概率仇 e 以上定理证明好码是存在的，人们就自然地试图去构造这些码。编码理 论中的一个重要概念是所谓汉明距离的概念。假设向量x = ( x 0 ，靠一1 ) ，y = ( g o ，弧一1 ) z 2 ，那么它们闻的汉明距离为 d ( x ，y ) = m 驾：x y i ) 一2 一 望 翌m 悭 雹叭 护 乎 第一章绪论 一个分组码c 的最小汉明距离是指 d ( 。m 。i n 。d ( x , y ) x # y 下面的定理给出了判定分组码纠错能力的标志。 定理1 2 ：分组码a 的纠错能力为的充分必要务件是 2 芒+ 1 sd ( c ) 2 t + 2 推论1 1 ：分纽码。的纠错能力至少为的充分菇要条件是 a ( c ) 2 t + 1 从以上定理和推论我们看到，要增大码的纠错能力，必须构造那种分组码c ， 使d ( g ) 尽可能地大；同时，为使码的信息率r 尽可能地大，还需要求礼k ( 礼为码 长，七为信息位) 这就是编码理论的中心问题。换言之，如果给定码字长和码的 最小距离，码应含有尽可能多的码字。对编码中最基本的二元码，记a ( n ，田为长度 为n ，最小距离为d 的码的最大码字数量，那a a ( n ，d ) 的值以及构造尽可能大的码的 研究是组合编码理论的中心问题【对其它类型的码，例如置换码、多元码以及各 种具有特殊性质的码，给定长度和最小距离的码的最大码字数量以及构造尽可能大 的码的研究同样是组合编码理论的中心问题。 对二元码和多元码的组合编码理论研究已经有了半个多世纪的历史，并从基 本问题延伸出对诸多相关问题的研究，例如，对同一类码的纵向研究有：码大小 的上界o i , t z l 、下界 1 3 , 1 4 , 1 5 , 1 6 1 、构造【1 7 j 、距离分布( d i s t a n c ed i s t r i b u t i o n ) 【1 9 1 、覆 盖半径( c o v e r i n gr a d i u s ) f 2 n 2 ”、多覆盖半径( m u l t i c o v e r i n gr a d i i ) 、重量分布( w e i g h t d i s t r i b u t i o n ) 2 3 ，2 a 等，所研究的码的类型也从基本码扩展到了具有各种特殊性 质的码，例如：常重量码嘲、双重界重量码嘲、线性码嗍、非线性码吲、 覆盖码( c o v e r i n gc o d l s ) 2 5 冽、常分量码( c o n s t a n t - c o m p o s i t i o nc o d e s ) 3 ”、等距离 码( e q u i d i s t a n tc o d e s ) 0 2 等，另一个方向是从二元码扩展到多元码，以及我们所研究 的置换码和各种具体码的抽象广义码【3 3 】等。 纠错码的编码方案技术的主要发展过程大致分以下几个阶段。 5 0 年代一6 0 年代初：这是纠错码的提出、发展一直到奠定线性分组码的理 论基础阶段，即早期阶段在此期间最重要的成果是提出了纠正多个随机错误 一3 一 上海交通大学博士学位论文 的b c h 码、卷积码的序列译码等，并出版了第一本系统叙述纠错码理论基础的书一 e r r o r - c o r r e c t i n gc o d e s r 3 5 】。 6 0 年代初一7 0 年代初：这是纠错码发展最为活跃的时期，是编码理论，特别是代 数编码理论日趋成熟完整，卷积码的编译码得到极大发展，纠错码的实际应用问题 开始受到重视，并取得一定成果的重要阶段。这也是纠错码发展最为迅速，成果最 多的阶段。最主要的成果有门限译码、b c h 码的迭代译码、卷积码的v i t e r b i 译码算 法等。在此期间内最有代表性的专著是b e r l e k a m p 写的a l g e b r a i cc o d i n gt h e o r y 【划及 其它专著口”& 3 9 1 。 7 0 年代一至今：纠错码在实际应用中得到了更大的发展。大规模集成电路和微机 的迅速发展，为纠错码的实用打下了坚实的物质基础。7 0 年代末、8 0 年代初 2 0 世 纪) ，u n g e r b o e c k 把编码与调制相结合提出了网格编码调制( t c m ，船e l l i s - c o d o d m o d u l a t i o n ) 技术l 帅】是编码理论的又一重要里程碑。继t c m 之后，1 9 9 3 年b e r r o u ， g l a v i e u x 和t h i t i m a j s h i m a 发现的t u r b o 码是又一重大突破【4 ”。对t u r b o 码的研究发 现t u r b o 码其实就是一种低密度校验码，因此在1 9 6 2 年由g a l l a g e r 提出但长期未受重 视的低密度校验码 4 2 , 4 3 重新引起人们的研究兴趣，并成为新的研究热点。 编码理论的研究不仅对编码本身有着重要意义，对其它领域也有着直接或间接 的深入影响。例如，编码理论已被应用于构造认证码 4 4 , 4 5 ，“s , 4 r j ，公钥 4 8 4 9 5 0 5 1 , 矧、 私钥密码系统 5 3 烈5 5 1 ，一些译码方法被用于流密码的分析1 5 6 , 5 7 ，s s l ，组合编码理论 已成为组合数学的一个重要分支，并与组合数学相互促进，譬如结合方案( a s s o c i a t e s c h e m e s ) 与码的线性规划求上界方法互相促进发展 5 9 , 6 0 。 1 2 置换码的研究意义及其应用 车富编码理论：置换码和其它编码方案有着密切关系，对置换码的研究可进一步丰 富编码理论。 应用于信道纠错： 置换码结合键控多频调$ 1 ( m u l t i t o n ef r e q u e n c y s h i f tk e y i n g ) 适用于 以下的信道纠错： 1 信道噪声类型不以白高斯噪声为主，而是一种非平常的、难以预测并混合 了多种噪声一包括背景噪音，冲击噪音，非同步的冲击噪音和永久频率 干扰；例如电源线信道【6 l ，蝴。 2 某些频率深衰落的频率选择信道。文【6 3 】的仿真结果表明，在某些信号噪 音区域，f c f r e i r a 和v i n c k 提出的置换格形码方案 6 4 ，硎优于卷积码方案。 分组密码设计： 文【6 6 拂! 置换码应用到分组密码设计中。 一4 一 第一章绪论 应用于组合数学： 置换码的理论研究部分属于组合数学的一部分，同时深入研究发 现与组合数学中的一些重要概念有着密切联系，比如( n ，礼) 置换码等价于n 阶拉 丁方，rn - 1 分( n ，住一1 ) 置换码和大小为r 的两两正交n 阶拉丁方可互相转换。 1 3 置换码研究现状 目前对置换码的研究仍然欠缺，且主要集中在置换码的上下界( 即p ( n ，回的上下 界) 、构造等基础理论问题上，置换码的编码方案只有最j e l f e r r e i r a 等人脚】提出的格 形编码。 置换码的上界的研究现状：置换码的基本上界有d e z a v a n s t o n e 界【3 】和球包界鲫。 目前己知【1 1 对( n ，n ) ，( n ，2 ) ，( m 3 ) ，( g ，q - - 1 ) ，( g + l ，口一1 ) ，( 1 1 ，8 ) ，( 1 2 ，8 ) 置 换码( 其中口为素数的幂乘) ，可达到d e z a v a n s t o n e 界。类似于二元码，置换 码也可通过求线性规划问题找出上界嘲，而且一般比d e z a - v a n s t o n e 界和球包 界更好，但是由于线性限制条件的系数难以计算，只适合长度不大于1 0 的情 形。 置换码的下界研究现状：置换码的基本下界有g i l b e r t - v a r s h a m o v 界【4 】，对某些特殊 情形，可通过构造的方法得到更好的下界，主要由严格自传递群构造、交换环 构造、两两正交拉丁方构造、有限域上的置换多项式构造、计算机搜索方法给 出。 置换码构造的研究现状：置换码的构造可分为显性构造和计算机搜索两种方法。 其中显性构造方法有： 1 b l a k e 【i 】提出的由作用在大小为他的集合上的严格七传递群构造( 佗，n 一詹+ 1 ) 置换码方法，所得到的码大小达到最大。 2 k l c v e 呻l 提出的由交换群构造( n ，n 1 ) 置换码的方法。 3 c o l b o u r n 嗍等人提出的由两两正交拉丁方构造( n ，n 1 ) 置换码的方法。 4 c h u 咖等人提出的由有限域上的置换多项式构造法。 5 w a d a y a m a 和v i n c k1 7 1 , 7 z l 提出的构造长度为2 n 的置换码的多层次法。 6 d i n g 口3 】等人提出的构造( n ，n 一1 ) 置换码方法。 7 f l i 和k l c v e 7 4 1 给出的两种由已知置换码和口元码构造更长置换码的方法。 8 c h u 6 7 1 等人给出的由七元码、置换码和截面包( t r a n s v e r s a lp a c k i n g ) 共 同构造更长的置换码的方法。 一5 一 上海交通大学博士学位论文 9 c h a n g 等人1 7 5 , 7 6 1 提出的距离保持映射、距离增加映射及s w a r t 等人 研和h u a n g 等人网提出的更广义的距离映射的定义及其构造，并把 该这类映射用来由二元码构造置换码。已有的距离映射构造方法有递归构 造邮，7 6 , 7 8 ，直接构造 7 5 , 7 6 , 7 9 8 0 8 ，多层次构造 计算机搜索方法最早由d e z a 和v a n s t o n e 使用并找到( 6 ，5 ) ，( 1 0 ，9 ) 置换码的下界； 系统化的搜索方法有c h u 等人m 提出的圈搜索、贪婪算法和自同构法，以 及k c c v a s h 和k u 【8 2 1 提出的半随机构造算法。其中前三个方法均给出了新的下 界，最后一个方法仅具有理论价值。 置换码编码方案的研究现状f e f r 如等人 6 4 , 6 5 1 结合距离映射和置换码，通过把礼长 二元序列映射成m 长置换序列来构造格形置换码。 1 4 关键问题 一l 。如同二元码，置换码的最大可能值大小， 1 p p ( n ，d ) 的值的研究是置换码理论的 中心问题，置换码的上下界和构造的研究均围绕此问题进行。 2 置换码的编码方案研究刚起步，目前只有最近f e r r e i r a 等人提出的格形编码，可 预测将是置换码研究的下一个焦点问题。 3 由于编码方案的研究刚起步，潜在应用空间很大 1 5 基本定义、记号 本节我们介绍在全文中使用到的定义、符号。在全文中，我们把汉明距离简称 为距离，汉明重量简称为重量。 1 5 1 置换码的基本定义、记号 对任意相同大小的集合q ，显然，分别由q 和q 上的所有置换及其结合运 算形成的对称群s f m ( q ) 和s y m ( n ) 同构，因此为简化问题，我们一般只讨论玩= o ，1 ，佗一1 上的置换，并令岛表示s 娜( z 。) 。我们也可以把置换a 岛写成扎一元 序歹i j ( a o ，0 1 l ，( 1 n - - 1 ) 的形式，其中m = a ( i ) 。特别地，为简洁起见，我们把单位置 换( 0 1 n 一1 ) 写成1 。 令c 为( 田置换码。c 中的置换也称为a 的码元或码字。不失一般性，我们总 是假设1 c ，并且在大多数情况下。竹一元序列( 向量，阵列) 的下标从0 开始， 对不从0 开始的情况我们会特别说明，或可根据上下文明显辨别出来。对任意置 一6 一 第一章绪论 换x & ，a ( x ，g ) 表示x 和e 之问的汉明距离，即， a ( x ，c ) 2 赌c e d ( x ，c ) o 置换x = ( x o ，z 1 ，一1 ) & 的支撑定义为中不被x 所固定的点的集合，即 a 磊：甄1 ) = 0 磊：x ( i ) 口 x 的汉明重量记为 ( x ) ，定义为x 的支撑的大小，e p z 中不被x 固定的点的数量。 p ( n ，d ) 的概念可进一步推广对qg ，记 忍( 凡，d ) = ( g i ：c 是( 扎，d ) 置换码，c q ( 1 1 ) 对平凡情形q = & ，p ，d ) = p n ( n ，d ) 。 定义p i n ，d 一1 】为 p - ，d 一1 】= m a x l i t i ：f & ，v x ，y r ，d ( x ，y ) d 一1 1 ( 1 2 ) 我们将在第3 章证明p ( 竹，d ) 和p k ，d 一1 】有着密切的联系。 对置换x 鼠，如果不存在不动点，即对任意o 戤，x ( a ) ，则称x 为七长完 全置换( d e r a n g e m e n t ) 。令仇记为七长完全置换的数量，并约定d o = 1 。那么 玖刮圭i = o 譬= 阿 ( 1 3 ) 设e 是一个伽，d ) 置换码，我们称x s n 被码字c g 覆盖，如果有a ( x ，c ) d ； 且晶中所有被码字c 覆盖的置换构成的集合记为b ( c ) ，并称为c 的覆盖球。那么 | b ( c ) h ( 州- 1 ) = ；d - 1 风 ( 1 4 ) 我们称置换x 被e 覆盖，若有a ( x ，回 而且晶中所有被c 覆盖的置换构成的集合记 为b ( g ) ，并称为c 的覆盖球。 几类具有特殊性质的置换码： 等重量置换码定义( 拜，d ，叫) 等重量置换码是码元重量为”的( n ，回置换码，并 记( d ，伽) 等重量置换码所能达到的最大码元数量为p ( n ，正叫) 。 一7 一 上海交通大学博士学位论文 完全置换码若c 是( n ，回置换码，且其所有置换均为完全置换，则称c 是( 礼，d ) 完全置 换码，i e i 的最大可能值记为d p ( 回 循环置换对置换x & ，如果对。瓦， o ( n ) ：i = 1 ，佗 = z n ，则称x 为n 长 循环置换( c m u a rp e r m u t a t i o n ) 。若c 是( n ，d ) 置换码，且其所有置换均为循环置 换，则称c 是( 竹，d ) 循环置换码，i 纠的最大可能值记为e p ( 礼，d ) 。 1 5 2 二元码的基本定义及记号 令z 2 = o ，1 ，趁记为所有n 长二元向量的集合。对x ，y 忍，d ( x ，y ) 记 为x ，y 的汉明距离，即d ( x ，y ) 是向量x ，y 不同值的位置的个数；记。是全0 向 量；叫t ( x ) = d ( x ，o ) 定义为x 的汉明重量，也即伽t ( x ) 是x 中l 的个数x 十c z 2 ， 若对任意不同的c l ，c 2 c ，d ( c 1 ，c 2 ) d ，则称c 是长度为礼最小距离为d 的二元码， 简记为( ，d ) 二元码。令a ( 礼，d ) 为( 礼，d ) 二元码所能达到的最大码字数量，即 a ( n ，d ) = m a x i c i ：c 是( n ，d ) 二元码) 对b = ( b o ，h ，k 一1 ) z ；的支撑记为s 唧( b ) ，定义为 s u p p ( b ) = 0 ： z ，l ，兢= 1 ) ， 显然w t ( b ) = l s u p 妒( b ) l 趁中以任意一向量x 为中心，半径为d 的“球体”的体积，即殇中与) 【距离曼d 的 向量数量为 晰加圭 i = 0 。 几类具有特殊性质的二元码： ( 1 5 ) 等重量二元码( d ，叫) 等重量二元码定义为( n ，d ) 二元码，而且每个码字重量为加a 定义a ( n ，d ， ) 为( d ，叫) 等重量二元码所能达到的最大码字数量即 a ( n ，d ，钾) = m a x i e i ：c y g ( n ，d ，彬) 等重量二元码， 双重界重量二元码( 叫1 n l ， t o 2 ，n 2 ，d ) 双重界重量二元l i b ( d o u b l y - b o u n d e d - w e i g h t c o d e ) 定义为( 礼l + 锄，1 + 忱，d ) 等重量二元码，而且前佗1 个位置至多有撕个1 ， 后他个位置至少有地个1 。定义r l ，n l ，地，啦，d ) 为( 伽l n l ， w 2 ，j 2 2 ，d ) 双重界重 一g 一 第一章绪论 量二元码能达到的最大码字数量，即 t ( w l ，n 1 ，t t ，2 ，t t 2 ，d ) = m a x l q ：c 为( 彬l ，n l ， w 2 ，n 2 ，d ) 双重界重量二元码 ( 1 6 ) 1 5 3 七一元码的基本定义及记号 对x ，y z 2 ，d ( x ，y ) 记为x ，y 问的汉明距离，定义为x 和y 取不同值的位置的个 数。长为n 最小距离为d 的一元码记为( n ，d ) 七一元码，定义为殁上的子集合d ，而 且对任意不同的x ，y c ，汉明距离e ( x ，y ) d 。若( n ，d ) 七一元码的大小为m ，则 称为( 竹，m ，d ) k - 元码。对x z 2 ，其汉明重量定义为x 中非。元素的个数。若( 竹，d ) 七一元码e 中每个码字的重量相等且为，则称为( 忍，杰钟) 等重量后一元码。设疗= n o4 - 礼l + + 一1 ，若( n ，d ) k - 元码中每个码字t 扣i ( i z k ) 出现的次数均为啦，则 称e 为( n ，d ，【珊，一1 】) 等分璺一元码。 1 6 论文选题及内容安排 本文主要研究置换码的基础理论问题，即置换码的上下界及构造问题，论文内 容安排如下： 第2 章对置换码的理论研究进行了详细综述。 第3 章研究置换码的上界：给出了关= j z p ( n ，d ) 和p n ( n ，d ) 的一个不等式，在证明 t p ( n ，d ，伽) 的一些基本性质的基础上，分别给出p ( n ，2 ) 和p ( n ，2 k + 1 ) 的上界，最 后证明若常数a ，卢满足某些条件，当d = f i n n 时，新上界渐近优于以往的上界。 第4 章研究置换码的一般下界，即g i l b e r t - v a r s h a m o v 界：其一，基 于j i a n g 和、，a r d y 1 3 1 提出的把编码中求下界问题转化为图论中求最大独立数问题的模 型，给出了尸( n ，印的三个改进g i l b e r t - v a r s h a m o v 界，后两个为g i l b e r t - v a r s h a m o v 界改 进的渐近形式；其二，通过考察码字的覆盖球的交集，给出了g - i l b e r t - v a r s h a m o v 界的 另两个改进。 第5 章研究置换码的构造以及特殊情形下的新下界，给出了置换码的几类新构造 和新下界： 两个由扎长置换码构造n 一1 长置换码的新方法，从而给出n ，d 取某些特殊情形时 的新下界； 两种由有限域上的分式多项式构造置换码的新方法，由此给出新的下界： 证明了阶为n ，最小度为d 的置换群和( 回置换码的关系，由此绘出新的下 界； 一q 一 上海交通大学博士学位论文 三种由二元码构造置换码的新方法； 一种简单随机构造算法。 第6 章研究了和置换码有着密切关系的广义码和二元码：对广义码，给出了广义 码的g i l b e r t - v a r s h a m o v 界的一个简单新证明以及一个低复杂度而有效的简单随机构造 算法；对二元码，给出了一些关