（概率论与数理统计专业论文）无缀码的研究.pdf

摘要 摘要 数据压缩是信息论中一个重要的分支，具有极其广泛的应用背景特别地，变 长码编码又是数据压缩中的一项关键性技术本文对一种特殊的变长码一无缀 码一进行了研究既满足前缀条件又满足后缀条件的变长码称为无缀码无缀码 具有一些特殊的性质，这些特殊性质的应用极其广泛，因此这是一个值得重视的 研究领域 作者首先对无缀码的存在性进行了研究根据无缀码的不同类型一对称无缀 码和非对称无缀码，分别进行了不同的说明对于对称无缀码，作者给出了其存在 的一个判定条件和一个必要条件，对于非对称的无缀码，作者进一步对著名的；猜 想进行了研究，说明了在某些特殊的条件下，该猜想是正确的其次对可逆变长码 的同步性丢失问题进行研究，给出了解决该问题的办法，即利用同步码字来重获 同步性，并且由于使用了可逆变长码从而尽可能的减少了数据的丢失此外，本文 中亦给出了对称同步可逆变长码和非对称同步可逆变长码的构造算法最后通过 模拟结果说明了该算法能够相当有效的解决同步性丢失问题 关键词数据压缩，可逆变长码，前缀码，无缀码，同步性，i 一猜想 a b s 打a c t a b s t r a c t d a t ac o m p r e s s i o ni so n eo ft h ei m p o r t a n tp a r t si ni n f o r m a t i o nt h e o r ya n di ti s a p p l i e dw i d e l yi np r a c t i c e e s p e c i a l l y , t h ec o d i n go f v a r i a b l el e n g t hc o d e s ( v l c s ) i st h e k e yt e c h n i q u ei nd a t ac o m p r e s s i o n i nt h i sp a p e r , w er e s e a r c has p e c i a lk i n do fv l c s - - r e v e r s i b l ev a r i a b l el e n g t hc o d e s ( r v i 舱s ) r v l c sa r eo n et y p eo ft h ev l c sw h i c h a l eb o m p r e f i x f r e ea n ds u f f i x - f r e e t h e r e f o r e ，r v l c sa r ea l s oc a l l e df i x f r e ec o d e s t h ef i x - f r e ec o d e sa r eo fm a n ys p e c i a lp r o p e r t i e sa p p l i e dw i d e l y s oi ti sv a l u a b l et o r e s e a r c ht h ef i x f r e ec o d e s f i r s t l y , w er e s e a r c ht h ee x i s t e n c eo ft h ef i x - f r e ec o d e s a c c o r d i n gt ot h ed i f f e r e n t t y p e s t h es y m m e t r i cf i x - f r e ec o d e sa n dt h ea s y m m e t r i cf i x f r e ec o d e s ，w er e s e a r c h t h ep r o p e r t i e so ft h ee x i s t e n c e ，r e s p e c t i v e l y w ep r o p o s eas u f f i c i e n tc o n d i t i o na n da n e c e s s a r yc o n d i t i o no ft h ep r o p e r t yo ft h ee x i s t e n c et ot h es y m m e t r i cf i x f r e ec o d e s t ot h ea s y m m e t r i cf i x f r e ec o d e s ，t h ef a m o u si - c o n j e c t u r ei sr e s e a r c h e df u r t h e r , a n d w ep r o v et h a tt h ec o n j e c t u r em u s tb er i g h ti ns o m ec e r t a i nc o n d i t i o n s s e c o n d l y , w e c o n s i d e rt h ep r o b l e mo ft h ea c h i e v i n gs y n c h r o n i z a t i o no ft h ef i x - f r e ec o d e sa n d p r o p o s e as o l u t i o nt ot h i sp r o b l e m , i e d e p e n d i n go nt h es y n c h r o n i z i n gc o d e w o r d sw ec a na l s o r e s y n c h r o n i z ea n db e c a u s eo ft h eu s eo ft h ef i x - f r e ec o d e s ，t h el o s so ft h ed a t ac a n b e d e c r e a s e da sm u c ha sp o s s i b l e m o r e o v e r , t h ea l g o r i t h m so ft h ec o n s t r u c t i o no ft h e s y m m e t r i cs y n c h r o n i z i n gr v l c sa n da s y m m e t r i cs y n c h r o n i z i n gr v l c sa r ep r o p o s e d a tl a s t , t h es i m u l a t i o nr e s u l t ss h o wt h a to l l ra l g o r i t h m sc a nr e s o l v et h ep r o b l e mo ft h e a c h i e v i n gs y n c h r o n i z a t i o ne f f i c i e n t l y k e yw o r d s d a t ac o m p r e s s i o n ，r e v e r s i b l ev a r i a b l el e n g t hc o d e s ( r v l c s ) ，p r e f i x - f r e ec o d e s ，f i x - f r e ec o d e s ，s y n c h r o n i z a t i o n ，i - c o n j e c t u r e 南开大学学位论文版权使用授权书 本人完全了解南开大学关于收集、保存、使用学位论文的规定， 同意如下各项内容：按照学校要求提交学位论文的印刷本和电子版 本；学校有权保存学位论文的印刷本和电子版，并采用影印、缩印、 扫描、数字化或其它手段保存论文；学校有权提供目录检索以及提供 本学位论文全文或者部分的阅览服务；学校有权按有关规定向国家有 关部门或者机构送交论文的复印件和电子版；在不以赢利为目的的前 提下，学校可以适当复制论文的部分或全部内容用于学术活动。 学位论文作者签名：垅砭、 口d8 年多月习。e l 经指导教师同意，本学位论文属于保密，在年解密后适用 本授权书。 指导教师签名：学位论文作者签名： 解密时间：年月 日 各密级的最长保密年限及书写格式规定如下： 南开大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，进行研究工作 所取得的成果。除文中已经注明引用的内容外，本学位论文的研究成果不包含 任何他人创作的、已公开发表或者没有公开发表的作品的内容。对本论文所涉 及的研究工作做出贡献的其他个人和集体，均已在文中以明确方式标明。本学 位论文原创性声明的法律责任由本人承担。 学位论文作者签名：纥藏 7 0o 参年5 月= ；oe t 第一章引言 第一章引言 本论文对无缀码( f i x f r e ec o d e s ) 进行了研究，为了使读者对这一领域有一个 大致的了解，本章首先对无缀码的研究背景与研究意义，研究内容和研究现状作 简单介绍，最后介绍作者得到的主要研究成果和论文的结构安排 1 1 研究背景与研究意义 既是前缀性的又是后缀性的码称为无缀码( f i x f r e ec o d e s ) ，其中前缀性是 指码集合中的任何一个码字都不可能是其他码字的前缀，同样的，后缀性是指码 集合中的任何一个码字都不可能是其他码字的后缀，前缀性和后缀性也被称为 前缀条件和后缀条件也就是说无缀码的任何码字既不是其它码字的前缀也不是 其它码字的后缀与前缀条件和后缀条件的相似，无缀码所满足的这个条件称为 无缀条件，因此又常常称该码是无缀的或该码满足无缀条件s c h t i t z e n b e r g 1 6 】以 及g i l b e r t 和m o o r e 1 7 的论文最早的介绍了无缀码，当时无缀码被称为n e v e r - s e l f - s y n c h r o n i z i n gc o d e s 在其它文献中，无缀码也经常被称为a f f i x f r e ec o d e s ，b i f i x f r e e c o d e s 或者r e v e r s i b l ev a r i a b l el e n g t hc o d e s ( r v l c s ) 一般来讲，变长的前缀码经常被用于数据压缩但是由于无缀码具有前缀码 所没有的一些特殊性质，这就使得无缀码更加适合某些应用例如因为无缀码既 是前缀码又是后缀码，所以无缀码可以在两个方向上解码换句话说，由前缀码编 码而成的字符串只能从前向后依次解码，由后缀码编码而成的字符串只能从后向 前依次解码，而无缀码的特性表明由其编码而成的字符串能够以上述两个方向解 码 表1 1 字符c le 2c 3 x000 y 1 0 0 11 1 z1 10 111 0 1 第一章引言 例如，令c 1 = o ，1 0 ，1 1 ，c 2 = o ，0 1 ，0 1 1 ，c 3 = _ o ，1 1 ，l o l ，则显然看 出c 1 是前缀码，c 2 是后缀码，c 3 是无缀码我们利用c 1 ，岛，c 3 分别对字符x ，yz 进行编码，如果序列1 1 1 0 1 1 0 是由c 1 编码而成的消息，我们可以从左至右逐步解码 序列的左起第一个码字为1 1 ，因为1 1 既不是0 的前缀也不是1 0 的前缀，所以消息 的第一个字符一定是z ，c 1 中的码字1 0 是序列的下一个码字，显然它也不是白中其 它任一码字的前缀，这样我们便得到第二个字符为y ，依次这样下去，我们便得到 解码后的消息z y z x 然而，如果我们试图从右至左解码，那么我们就会遇到问题 了右起第一位是0 ，既可能是x 也可能是y 的后缀，继续后退一位得1 0 ，则遇到 同样的问题，可能是y 。也可能是z x ，这仍要取决于再倒退一位的值是什么再后 退一位得11 0 ，同样仍可能为z x 或z y 因此，序列111 0 11 0 按从右至左解码时是不 能逐码字解的 同样的，一个由c 2 编码而成的序列是能够按照从右至左的顺序逐码字译码的， 但是它通常是不能按照从左至右的顺序逐码字译码的例如，序n 0 11 0 1 0 11 0 是 由已编码而成的，如果按照从右至左的顺序，我们可以逐码字的解码的消息z y z x 但是若按照从左至右的顺序解码，就会遇到与上面相同的问题因为左起第一位0 就意味着消息有可能以任意字符开头然而，因为岛同时满足前缀性和后缀性，所 以由岛编码而成的序列可以从两个不同的方向解码例如，序列1 0 1 1 1 1 0 1 0 无论从 左至右译码还是从右至左译码都可以逐码字的译为z y z x 无缀码的双向解码性质具有许多实际的应用例如，一个文件是由无缀码压 缩得到的。那么若想查找其中的某个字符串就可以从两个方向同时进行查找，这 样便节省了查找时间又例如，一个由无缀码压缩而成的文件可以在头尾两个方 向同时解压缩，这样所花费的解压缩时间就会比单方向解压所花费的时间减少一 半 再举一个应用的例子，假设我们要在某个编码后的文本中查找一个术尸宰的模 式，尸是一个字符串，木代表任意的一个字符串，甚至可以是空串，掌和p 组成一个词 或一个句子为了找到与，i ：p 牢匹配的这种模式，我们必须在所有尸出现的位置向前 向后解码当然，如果所有的码字都是等长的，显然能够满足向前向后解码的要求 但是如果想减少编码文本的长度，就必须采用变长码又因为向前解码和向后解 码都是必须的，所以一定要使用无缀码对原文件进行编码 与前缀码或后缀码相比较，无缀码的另一个优势是其具有更好的健壮性即 在有噪声的信道中传输信息时，无缀码的抗干扰能力更强因此，无缀码常常用在 2 第一章引言 视频与媒体信息编码上目前绝大多数的视频文件都是经过变长前缀码编码的， 目的是减小文件的平均码字长度甚至最小化平均码字长度但是变长的前缀码或 后缀码对于传输错误是高度敏感的，并且有两类比特错误是经常发生的，它们分 别是蔓延性比特错误和非蔓延性比特错误在译码过程中，非蔓延性比特错误是 指译码错误仅仅出现在对出错码字进行译码的时候，而蔓延性比特错误会引起同 步性( s u n c h r o n i z a t i o n ) 的丢失此时，错误比特以后的比特流也将被错误的解码 或者无法解码在某些情况下，同步性在一段时间后将会被自动的重新建立，但是 即便如此。也造成了大量数据的流失因此，为了解决这类问题，我们往往将视频 文件的一帧分成几个片断，然后用一个同步标志来区分每个片断，这样一个片断 的比特错误就不会蔓延到下一个片断如果数据还要通过有噪声的信道进行传输， 则还要采用更加可靠的编码方案，比如我们可以用纠错码对视频数据编码另一 种解决方案就是对视频数据中最重要的部分用更加健壮的码来处理但是一般来 讲。任何更加可靠的编码方案都会造成平均码字长度的增加事实上在很多情形 下。这种平均码字长度的增加是值得的现在，很多视频数据都是利用无缀码来对 其进行压缩特别地，令我们兴奋的是，很多视频数据经无缀码压缩后具有与前缀 码压缩相同的或相似的平均码字长度在这种背景下，无缀码也被称为可逆变长 码( r e v e r s i b l ev a r i a b l el e n g t hc o d e s ) 当一个错误突变发生在用无缀码压缩的子片 断中，解码器能够直接跳至子片断最后的同步标志处并向前解码至错误处停止，这 样就尽可能的减少了数据的损失也就是说，如果视频文件是用无缀码编码的，那 么错误位置后的数据并没有全部丢失 【7 【1 0 】【1 1 】 1 2 】【1 4 】 2 4 和【2 5 】概述了无缀码的错误处理和应用，特别是在视频 标准h 2 6 3 + 和m p e g - 4 中的应用此外，在1 9 9 9 年，以无缀码为基础的数据分割结 构已经作为h 2 6 3 + 视频标准的一部分，并且在该标准的附录5 中被详细叙述 1 2 无缀码的研究现状 对于给定的信源，相对于定长码而言，变长码最大的优势在于它具有较短的 平均码字长度如果想减少编译码和传输时间以及资源存储量，那么选择一个具 有较短的平均码字长度的码是正确的选择因此，对于某个信源，我们称具有最 短平均码字长度的码为最优码1 9 5 6 年，h u f f m a n 在其文献【1 8 】中说明了对每一种 信源，选择一个具有前缀性的最优码是可能的，并且最优的前缀码也是最优码 此外，h u f f m a n 亦给出了构造这种最优前缀码的算法，因此，最优前缀码也被称 3 第一章引言 为h u f f m a n 码1 9 4 9 年，k r a f t 名e 文献 19 】中证明了每一个前缀码c 都满足s ( c ) 1 ， 反之，对于每一个满足k r a f t 和小于等于1 的非负整数序y u ( q t ) l n ，都存在一个前缀 码c 使得( 锄) i e n 是c 的码字长度向量在1 9 9 6 年，a h l s w e d e ，b a l k e w h o l 和k h a c h a t r a i n 在文献【1 】中提出了一个猜想：若一个长度序列的融抓和小于等于；，那么存在一个 无缀码以上述长度序列为码字长度序列这就是关于无缀码的著名的；一猜想在文 献【1 】中，作者还对该猜想进行了一系列说明特别地，他们指出如果用；代替；，则 该猜想成立此外，作者还证明了对任何大于；的数7 ，存在一个l ( i 啦和小于7 的长 度序列，使得没有任何一个无缀码能够与该长度序列相对应但是l ( f 啦和大于；的 无缀码是存在的，举个很简单的例子，设码c 的每一个码字的长度都是相同的，显 然c 为无缀码，但其k r a f t 乘l 为1 目前，无缀码的存在性也是研究的热点之一 在1 9 9 5 年，t a k i s h i m a , w a d a 和m u r a k a m i 在文献 1 0 】中，t s a i 和w h 在文献中 【1 1 】中都给出了无缀码的构造算法，他们都是利用了h u f f m a n 码的码字长度向量 在2 0 0 3 年，l a k o v i 6 和v i l l a s e n o r 在文献【7 】 8 】中对上述算法进行了改进目前还没 有研究者能够证明用他们提出的算法构造出的无缀码是最优的，事实上，容易看 出它们也不是最优的因此，更好的甚至最优的无缀码的构造算法仍是目前研究 的热点之一 1 3 研究方法与研究成果 数据压缩是信息论中重要的一个研究分支。并且具有极其广泛的应用背景特 别地，变长码又是数据压缩中的一项关键技术变长码的技术理论研究一直非常 活跃，本文在前人的基础上，对一种特殊的变长码一无缀码一进行了研究无缀码 具有一些特殊的性能，这些性能具有极大的应用价值，因此是一个值得重视的研 究领域，这也是本文选取这种特殊的变长码作为研究课题的原因 无缀码分为两类，分别是对称的无缀码和非对称的无缀码根据它们的不同 性质，我们分别研究了两类无缀码的存在性此外我们还研究了在实际应用中无 缀码的同步性丢失的问题，并提出了解决方案本论文的主要创新工作如下： 1 提出了关于对称无缀码的存在性的一个判定条件和必要条件。并且由该结论 的第一部分和提出的另一个引理导出了判别对称无缀码的另一个易于使用的 但更强的充分性条件，同时也得到了一个构造满足这个条件的无缀码的算法 2 进一步研究了关于非对称无缀码的著名的i - 猜想，说明在某些特殊的情况下 4 第一章引言 该结论是成立的并且举例说明了本文所给出的结论是前人所未得到过的 3 提出了在无缀码编码过程中仍存在同步性丢失的问题，并且给出了解决方案 4 提出了构造对称同步可逆变长码和非对称同步可逆变长码的算法，该算法构 造出的对称和非对称可逆变长码可以解决同步性丢失问题并最低限度的减少 了数据的丢失 5 给出了两种算法的在英语语言中的模拟结果，充分说明了算法的有效性和实 用性 1 4 论文的结构安排 本文是围绕无缀码展开研究的，具体的结构安排如下： 第一章介绍了无缀码的研究背景，研究意义，研究现状，本文的研究方法和研 究成果以及论文的结构安排 第二章主要是介绍无缀码的基本概念和基本符号首先给出与无缀码相关一 些的定义和概念，其次说明了在无缀码研究中所用到的一些基本符号以及其意义 第三章主要对无缀码存在性进行了研究该章分别对对称的无缀码的存在性 和非对称的无缀码存在性进行了研究 第四章主要是对无缀码的同步性问题进行了研究首先给出同步性问题的出 现背景以及危害，其次给出了解决方案和为此所需的预备知识，再次给出了同步 可逆变长码的构造算法，最后给出了构造算法的模拟结果 第五章是对本文的主要结论的总结 5 第二章无缀码的基本概念和基本符号 第二章无缀码的基本概念和基本符号 前面我们已经对无缀码的定义，研究背景，研究现状和其应用等进行了介绍 下面我们将依次介绍我们的一些研究成果，但在这之前，我们必须先给出在研究 无缀码时常常用到的定义和符号 2 1 无缀码的基本概念 本部分我们先给出无缀码的一些基本概念 定义2 1 满足前缀条件的变长码称为前缀码，即前缀码的码集合中的任何一 个码字都不是其他码字的前缀 定义2 2 满足后缀条件的变长码称为后缀码，即后缀码的码集合中的任何一 个码字都不是其他码字的后缀 定义2 3 既满足前缀条件又满足后缀条件的变长码称为无缀码，即无缀码的 码集合中的任何一个码字既不是其他码字的前缀也不是其他码字的后缀进一步， 如果无缀码的任何一个码字从左至右读取和从右至左读取都是相同的，这样的无 缀码就称为对称无缀码否则，称为非对称的无缀码 例如，无缀码c 1 = ( o o ，1 0 1 ，1 1 1 1 ，岛= 0 1 ，0 0 0 ，1 0 1 1 1 ，显然c 1 的每一个 码字都是对称的，则它是对称无缀码然而c 2 中的码字0 1 ，1 0 1 1 均不是对称的，因 此已是非对称无缀码 定义2 4 同步性是指编码器和译码器之间要保持同步j 挫，即它们的时钟是统 一的，字符与字符间的传输是同步无间隔的具体来说编码器有一个时钟，其输 出脉冲的重复频率等于比特传输的速率，相应的，译码器也有一个时钟，用以确定 接收比特的取样判决时刻为了正确判别，必须使译码器时钟与编码器时钟具有 固定的相位关系如果译码器接受到的信息流中出现了一个比特错误这将会导致 同步性的丢失，因此产生一个错误的解码 6 第二章无缀码的基本概念和基本符号 2 2 无缀码的基本符号 记n 为自然数集合。z 为整数集合 设4 为任意一个集合，本文中4 = o ，1 ) 记表示所有由集合4 中元素组成 的n 长序列的集合，即 4 竹= a l a 2 a n i 。t a ，i = 1 ，2 ，n ) 矿表示所有由集合4 中元素组成的长度大于。的序列的集合，h p a + ：园小 n - - - - 1 表示所有由集合a 中元素组成的有限长度序列的集合，甚至可以为0 长度， 即4 + = u 印 n = o 设形，纱4 + ，我们定义 一1 纱d = e f z a 彤纱一1 磐 z a j x 影，y 纱，使得y = z 名) | x 彤，y 纱，使得x = z u 设集合c 是一码集合，d ：e fcna z ，z n ，即c 中码长为z 的全部码字的集合， 那么记 1 c nd ：e fcnl = ja ：c 1uc 2u uc n 2 记( 口为厶中以a 为首位的码字即 磐 c 厶ic = 。饧c l ，口，q 4 ，2 i z ，1 z 几) 3 记留为厶中以6 为末位的码字即 磐 c 厶ic = c l c f - 1 ，臼弘1 i z - 1 ，1 z 吼 4 ( 口堵为厶中既以。为首位又以6 为末位的码字，即( n 凹) d ：e f ( 。n 留) 5 记( q z ) l n = ( c 9 1 ，q 2 ，) 为码c 的长度向量，其中口l 为码c 中长度为z 的码字 个数，即铆= i cn i ，z n 第二章无缀码的基本概念和基本符号 6 码c 的l l f t 和s ( c ) 与礼阶。m 和瓯( c ) 分别定义为： 7 记锋够) 为以码c 中的码字为前缀的全部礼长序列的集合，即 n 锋( c ) = u ( cn 爿) 一2 1 - - 1 同样地，a 。- ( e ) 为以码c 中的码字为后缀的全部礼长序列的集合，即 n ；够) = u - 1 ( cna z ) 4 几 1 = 1 记售( c ) 为或以码c 中的码字为前缀或以码c 中的码字为后缀的全部礼长序 列的集合。即 售( c ) = ；( c ) u ：( c ) 4 n 8 仇 1 ) 若k 为偶数，令七= 2 1 ， a ) 若佗为偶数，即他= 2 m ， 1 4 一i 一 礼 晰铲 胪2 铴确 邶啪一厂嚣锄 | m 托 绊 = = m ，铆 m 出 胆川 = 0 0 = m m 吖 k q 气乞 户 似舭 = = v 加弋 一一一一 雾器铀m 第三章无缀码的存在性 此时口= d c = d l d 2 如c 1 c 1 ，由c = c l = c 1 c m c 1 的对称性可知，对称的c 的个数是2 m 又由于d 1 d 2 f c l c l 仍是对称的， 那么得如m + 。d 2 f 仍为对称的序列，这样的序列也刑1 1 d 2 l 共有2 卜m 个因此对 称的序列a = d c 的个数为2 m 2 z - m = 2 1 b ) 若佗为奇数，即礼= 2 m + l ， 此时c = c l + 1 e l 的个数为2 m + 1 又由于a = d c = d l d 2 d 2 1 c l c ，l + 1 c ，t l c 1 的对称性，得如m + 2 d 2 z 亦为对称序列，共有2 。一m 种选择因 此对称的d 1 4 2 d 2 l c l + 1 c l 序列个数为：2 m + 1 2 。一m = 2 2 + 1 2 ) 若k 为奇数，令k = 2 1 1 ， a ) 若亿为偶数，即n = 2 m ， 此时a = d c = d l d 2 如l l c l c 1 ，由c = c 1 c n = c 1 c 1 的对称性得：对称的c 的个数是2 m 又由d 1 也l 一1 c 1 c l 的对称性得 如m + l 妇一。仍为对称的序列，这样的序列共有2 2 一m 个因此对称的序列a = d c 的 个数为2 m 2 z m = 2 1 b ) 若n 为奇数，即竹= 2 m + 1 ， 此时c = c l c m c m + 1 c 1 的个数为2 m “由于a = d c = d l d 2 d 2 z 一1 c 1 c ，ic m + l c m c 1 的对称性，得d 2 m + 2 如l 一1 亦为对称序列，共有2 2 一m 一1 种选 择因此对称的d l d 2 d 2 z m c + 1 c r ，l e l 序列个数为：2 m + 1 2 。一m 一1 = 2 。 3 若【詈j k 佗，即墨 k 佗， 1 ) 若n 为偶数，即礼= 2 m ， a ) 若k 为偶数，令k = 2 1 ， 此时a = d c = d t d 2 d k c l c m c 1 ，由a 的对称性得： 画= c ( 1 t m ) ， 且d m + 1 d k c l 仍是对称的，则又有 d m + 12c m ，d , n + 22a m 一1 ，d k2c 2 m k + 1 又因为c 1 c 2 m 一后还具有对称性，所以还可以得到： c 12c 2 m k ，c 22c - 2 m k 一1 ，c m k 22c , n k 2 + l 1 5 第三章无缀码的存在性 整理为： d l2c 12c 2 m 一七2d 2 m 一七 如= c 2 = 饧仇一七一1 = 如m 一七一i 如一k 1 2 = 一k 1 2 = 一k 1 2 + i = d m k 2 + l d 2 m k + l2c 2 m k + l2d k d m 一12c m 一12d 竹t + 2 d m = c m = c + 1 因此，满足条件的序列个数为：2 知2 = 2 1 b ) 若k 为奇数，令k = 2 1 1 ， 由o = d c = d l d 2 d k c l c r r i c 1 为对称序列，得： 也= c i ，( 1 i m ) 并且d m + 1 如+ 2 d k c l 仍满足对称性，那么得： d m + 12c m ，c k + 22c m l ，d 2c 2 m 一知+ 1 又因为c 1 c 2 一七仍是对称的，且k 是奇数，得： c l2c 2 m - kc 25c 2 m 一知一l ，c m 一( k + 1 ) 1 25 c m 一( 知3 ) 1 2 , c m 一( 七一i ) 1 2 三c m 一( 一d 1 2 整理为： d l2c 12c 2 m 一七= d 2 m 一七 d 2 = c 2 = c 2 m 一七一1 = 也m k 一1 d m 一( 七+ 1 ) 22c m 一( k - l - 1 ) 1 2 = 如m k + l2c 2 m 七+ 15d k d m 一12c m 一15d m + 2 d m = c m = d m + 1 c m 一( 七一s ) 1 2 = c f m 一( 七一3 ) 1 2 因此，对称的g = d c 序列个数为2 m 一( 七一1 ) 2 2 m 一( 2 m 一七+ 1 ) + 1 = 2 z 2 ) 若n 为奇数，即钆= 2 m + 1 a ) 若k 为偶数，令k = 2 1 ， 此时n = d c = d 1 如c 1 c m + 1 c 1 ，由。的对称性，得： d i = q ，( 1 t m + 1 ) ， 1 6 第三章无缀码的存在性 且+ 2 d k c l 一1 c m 仍是对称的，b u y 有 d i n + 22c m ，毗= c 2 m 一七+ 2 又因为c 1 c 2 m 一忌+ 1 还具有对称性，所以还可以得到： c 12c 2 m k + lc 22c 2 m 一七，一k 22 一k 2 + 2 , 一七2 + 1 兰c r ，i k 2 + 1 整理为： d l2c 12c 2 m k + l2d 2 m k + l d 2 = c 2 = c 2 m k2d 2 m 一知 d m k 2 = c m k 22c m k 2 + 2 = d m k 2 + 2 一k 2 + 12c m k 2 + 1 如t n 一七+ 2 = 0 2 m 一七+ 2 。d k 6 f m 一1 = c m 一1 = c f m + 3 如= = + 2 d m + 12c m + 1 因此。满足条件的序列个数为：2 m k 2 + 1 2 m + 1 一( 2 m 一七+ 2 ) + 1 = 2 k 2 + 1 = 2 t + 1 b ) 若后为奇数，令k = 2 l 一1 ， 由n = d c = d l d 2 d k c l + l c 1 为对称序列，得： d i = q ，( 1 i m + 1 ) 并且+ 2 d k c l 仍满足对称性，那么得： d m + 22 ( 概，d k2c 2 m k + 2 又因为c 1 0 2 一k + l 仍是对称的，且尼是奇数，得： 整理为： c 12c a m k + lc 220 2 m 一知，c m 一伪一1 ) 22 c m 一( 七一3 ) 2 d l2c 1 = c 2 m 一+ 1 = 如竹l 一七+ 1 d 22c 22c 2 m 一七2d 2 m 一七 c 一( 七一1 ) 22c m 一( 七一1 ) 2 = c m 一( 七一3 ) 2 = d m 一 一3 ) 2 c f 2 m 一七+ 2 = c ；2 m 一七+ 22d k d m + 12 + 1 1 7 第三章无缀码的存在性 因此，满足条件的序列个数为2 仇一( k - z ) 1 2 2 m + 1 一( 2 m - k + 2 ) + 1 = 2 由定理3 1 和引理3 3 ，我们可以得到对称无缀码存在的充分条件 口 定理3 4 对任意s ，s n 如果 m a x l # 2 j 一；：磊s - 1 + 。d , ( s - i ) ) ， 2 ， 则存在以( ) 为长度向量的对称无缀码 事实上，通过定理3 4 和引理3 3 的证明可以看出，对于一个满足不等式( 3 2 ) 的 整数向量( r 1 ，r 2 ，) ，能够得到一个以该整数向量为码字长度向量的对称无缀 码的构造算法下面详细说明该构造算法 设r l ，您，) 为一整数向量，任意( s = 1 ，2 ，m ) 满足不等式( 3 2 ) 实 际上，我们只需考虑其中大于0 的项，这是由于对于n = 0 ，构造出的c n 是一个空集 记这m 个整数中不为0 的项为l ，r 蚴，r 其中l 8 1 8 2 0 ，且 r 钆2 i 舭1 2 1 8 k 2 1 n 2 一一 职( s 七一