（应用数学专业论文）删位和插位纠错码的组合构造.pdf

摘要 摘要 有关删位和插位纠错码的理论还比较少，已有的结果大多集中在纠正 1 个删位或插位错误本文讨论删位和插位纠错码的组合构造方法，主要研 究了两类完备的删位纠错码：t + k ，”) 一码和t ( t ，k ，”) 一码，这两类码都能 够纠正任意的直至( 一t ) 个删位和插位组合的错误 在第二章中，我们首先引入广义烛台形t 设计( 或t - g c s ) 的概念，然 后给出用t - g c s 构造t + ( ， ，”) 一码的方法，最后证明了当”为奇数时，存在 一个t + ( 3 ，4 ， ) 一码由于l e v e n s h t e i n 已经证明了”为偶数情形的t + ( 3 ，4 ，”) 一 码都是存在的，因而t + ( 3 ，4 ，u ) 一码的存在性问题就被彻底解决了 l e v e n s h t e i n 首先指出有向“设计d b t ( k ，1 ；口) 等价于t ( t ，k ，口) 码在 第三章中，我们基本证明了有向平衡不完全区组设计d b ( 7 ，1 ；”) 存在的必 要条件也是充分的，除了一个例外的”值，以及6 8 个可能例外的”值从 而，我们就得到了相应的t ( 2 ，7 ，”) 一码 在第四章中，我们比较系统地研究了t + ( 2 ，7 ，”) _ 码的存在性当”2 3 5 0 时，t ( 2 ，7 ，。) 一码的存在性已经解决我们同时也构造了大量” 2 3 5 0 的 t ( 2 ，7 ，口) 一码 在第五章中，我们利用有向乒设计得到了一个t ( t ，”) 一码的渐近存在 性结果，并初步讨论了t + ( t ，k ，。) 一码的渐近存在性问题，以及其它与删位和 插位纠错码有关的有向设计，并且提出了若干进一步的研究问题 关键词：删位和插位纠错码；完备的测位纠错码；有向t 一设计；广义烛台 形设计；可分组设计 作者：王健敏 导师：殷剑兴( 教授) a b s t r a c t c o m b i n a t o r i a lc o n s t r u c t i o n sf o rd e l e t i o na n d i n s e r t i o n - c o r r e c t i n gc o d e s a b s t r a c t l i t t l ei sk n o w na b o u tt h et h e o r yo fd e l e t i o na n di n s e r t i o n c o r r e c t i n gc o d e s t h i s d i s s e r t a t i o ni n v e s t i g a t e st h ec o m b i n a t o r i a lc o n s t r u c t i o n sf o rd e l e t i o na n di n s e r t i o n c o r r e c t i n gc o d e s m o s to fo u rw o r ki so nt w ok i n d so fp e r f e c td e l e t i o n 。c o r r e c t i n gc o d e s ： t + ( ，k ， ) 一c o d e sa n dt ( t ，k ，”) 一c o d e s b o t hat ( t ，k ， ) 一c o d ea n dat ( t ，k ， ) - c o d e a r ec a p a b l eo fc o r r e c t i n ga n yc o m b i n a t i o no fu pt o ( k t ) d e l e t i o n sa n di n s e r t i o n so f l e t t e r so c c u r r e di nt r a n s m i s s i o no fc o d e w o r d s i nc h a p t e r2 ，t h en o t i o no fag e n e r a l i z e dc a n d e l a b r at - s y s t e m ( o rt - g c s ) i s i n t r o d u c e da n du s e dt os h o wt h a tat 4 ( 3 ，4 ， ) - c o d ee x i s t sf o ra l lo d d ”c o m b i n i n g t h i sw i t hl e v e n s h t e i n sr e s u l t ，t h ee x i s t e n c ep r o b l e mf o rat 4 f 3 ，4 ，p ) 一c o d ei ss o l v e d c o m p l e t e l y ad i r e c t e dt - d e s i g nd b t ( k ，l ； ) i se q u i v a l e n tt oa t ( t ，k ， ) 一c o d e ，t h i si d e aw a s f i r s tg i v e nb yl e v e n s h t e i n 。i nc h a p t e r3 ，t h en e c e s s a r yc o n d i t i o n sf o rt h ee x i s t e n c eo f ad b ( 7 ，l ；# ) a r es h o w nt ob es u f f i c i e n tw i t ho n ee x c e p t i o na n d6 8p o s s i b l ee x c e p t i o n s ， d b ( 7 ，l ； ) sc a nb eu s e dt oc o n s t r u c tr ( 2 ，7 ， ) 一c o d e s i nc h a p t e r4 ，t h ee x i s t e n c eo fa t + ( 2 ，7 ，口) - c o d ew i t h 2 3 5 0i sp r o v e d a l a r g en u m b e ro fe x p l i c i tc o n s t r u c t i o n s 潍妒2 ，7 ，口) 一c o d e sw i t h # 2 3 5 0a r ea l s o p r e s e n t e d i nc h a p t e r5 ，w eo b t a i na na s y m p t o t i cr e s u l tf o rt ( 2 ，k ，u ) 一c o d e sf o r md i r e c t e d t - d e s i g n s ，a n dd i s c u s si n8n u t s h e l lt h ea s y m p t o t i ce x i s t e n c eo fat 4 ( 2 ，女，) 一c o d ea n d t h eo t h e rd i r e c t e dd e s i g n sw h i c ha r er e l a t e dt od e l e t i o na n di n s e r t i o n ，c o r r e c t i n gc o d e s ， w ea l s op r e s e n ts o m eo p e np r o b l e m sf o rf u r t h e rs t u d y k e y w o r d s ：d e l e t i o na n di n s e r t i o n c o r r e c t i n gc o d e ；p e r f e c td e l e t i o n c o r r e c t i n gc o d e d i r e c t e dt - d e s i g n ；g e n e r a l i z e dc a n d e l a b r as y s t e m ；g r o u pd i v i s i b l ed e s i g n w r i t t e nb yw a n gj i a n m i n s u p e r v i s e db yp r o f y i nj i a n x i n g 第一章绪论 研究背景 1 第一章绪论 王1 骈究背景 在储存或传送数据时经常会发生随机的错误差错控制编码理论的目 懿就是要查塞甚至纠歪这些错误麓位程擒位缨错弱可以爰寒纠纛玛字篱 送过程巾因码元的删除或插入( d e l e t i o n i n s e r t i o n ) 引起的差错我们把这种 错误现象称为码字发生了删位绒插位目前对删位和插位纠错码理论的研 究不是缀多。本文研究嚣l 经霹攒健鲤错码戆缀合构造方法，并显应麓这些方 法具体构作了几类究备的删位纠错码，这几类码可以纠正一个或多个删位 和插位的差错我们首先介绍删位和插位纠镨码的相关理论。 一) 辩j 位和插位纠错码 设a ( v ) 为一个”元集合，称为字母表，并称a ( v ) 巾的元素为字母在 本文中，a ( v ) 透常设取痒磊= o ，1 ，蛰一l 。任意一个分量都取垂直 的商量点一( 钆，魄) 称为a 和) 上鹃一个孝，f 称葱字显的长凌我f | 、j 把a ( v ) 上所有长度为k 的字所组成的集合记作继( ”) ，把a ( v ) 上所有长度 为自并强分量互不棚阕鳆字所组成的集合谜佟氐( 钍) 如果一个长发涛嚣的 字羔可以及一个长度为m 的字筝中测去m 一他个字母聪得到，或者说y 可 以在点中插入m n 个字母得到，则称x 是y 的一个子序列( s u b s e q u e n c e ) ， y 是x 的一个超序戮( s u p e r s e q u e n c e ) 。 逶常码字在传送嚣寸发生插位和( 或) 删德后，码字的长度会不翮于原来 码字的长度这使得常用的汉明( h a m m i n g ) 躐离无法度娥这两个码掌之间的 距离，为她，l e v e n s h t e i n 在f 3 嗣咚奔绥了一种耨的距离潦度量两个长发不程 同的码字闯的距离这种距离通常被稼为l e v e n s h t e i n 躐离 定义1 1 1 设篓和点是a ( v ) 上的两个字置和z 之间的l e v e n s h t e i n 距离 6 乜z ) 窥义为将量变为z 掰嚣徽字母擂往穰戆| 位酶最小数器。 例如对于星= ( 2 ，1 ，0 ，4 ) 和盏= ( 2 ，0 ，1 ，1 ，3 ，4 ) ，6 ( 蜀星) = 4 我们可以按 第一章缱论 研究背景2 如下步骤操作把x 变为y ：首先删除x 中的1 ，然后程0 和4 中间插入f 1 ，3 ) 整个过程中做了1 次删位和3 次插位从上述例子中还可以褥出，通 过5 涵彩次嬲位帮摭蕴把墨变为y 鲍方式不止一静，滋热我懿透露戳这样 操作：首先翻除显巾的0 ，然后在2 和1 之间插入一个0 ，最后在1 和4 之 间插入( 1 ，3 ) 懿象记( 匐势篓懿长度，i 涵鸯为釜秘z 酶公共子澎褒中麴最大长度， z 乜量) 为篓和曼的公共超序列中的最小长度，那么下式成立 6 ( 量，生) 一l ( 显) a - f ( 互) 一2 l ( 墨，主) = 2 f 恒，量) 一f ( 美) 一；( 曼) 从蔼宥d 涵匐= i ( 玉童) 一i ( 羔，羔) 在前面酶例子中，i 涵点) = 3 ，i ( 墨曼) - 7 对任意正整数t ，用幽t 来液示x 的所有长度为z ( x ) 一t 的子序列的集 合，震阐；来表承点的所有长发势+ t 懿超序列酶集合。 定义1 1 2 设小( 口) 。舀雒( w ) 和cc ( ) 若对于c 中任意两个置不相同 k = o 的字x 和星，都有6 ( 显 曲2 t + 1 ，贝4 称c 为一个扣潮饿和播位纠错码著 瑟有酶巢合国t ( 或蠹圈。) ，美c ，两耨不栏交，曩| l 称c 势一个扛潮链 纠错码( 或者扣插俄纠错码) 在上述定义孛，零语“扣糕佼秘播位纠锴”静意恿蔫接我f l 毙够镁正任 何一种t 个删位和j 个插位的错误组合，必瓣满足 4 - j 篓t 通常g 中的字 称为码掣，码字中的字母称为码元c 中的一些码字包含了相同的弼元，但 有时我们也哭磷究嚣器蹙码元互不稷霹的璃字。 l e v e n s h t e i n 【3 6 】和h o l t m a n nf 2 7 指出了如果码g 中所有码字其有一致的 长度，那么定义1 1 2 中的三种粥是等价的因此一个能够纠正f 个删位( 插 位) 镶误酶码gc 震暂) 遣麓够鳞蓬毒- 裂位穰捶僮酶锩谈。壤撂这个枣实， b o u r s 在文 1 1 】中给了码字长度相同的乒删使和插位纠错码的等价定义 定义1 1 。3 设c + a i ( v ) ( 或c a 女( 口) ) ，若噬一。( 口) ( 或a 柚( t j ) ) 的每个 字作势子廖残最多懑瑷在c ( 蛾c ) 酶一个字孛，獬称c ( 或g ) 为一个 一删位j h 插位纠错码， 第一章绪论研究背景 3 在上述定义中，定义了两类t 一删位和插位纠错码，其中一类码中码字 的码元可以相同，另一类码中码字的码元必须互不相同我们引用b o u r s 1 1 给出的术语，称c + 为s + ( 一t ，k ，u ) 一码，c 为s ( k t ， ，”) 一码根据定义 容易看出，s ( 一t ，k ，”) 一码和s ( k t ，k ，”) 一码都能够纠正t 个删位的差 错，这是因为任意两个不同的码字不能共享一个长度大于或等于女一t 的子 序列然而，由于码字长度一致，这意味着这种码可以纠正任何一种i 个删 位和j 个插位的差错组合，其中i + j t 对给定的参数t ，k 和”，构造码字个数l c i 达到最大可能性的s ( k t ，”) 一 码是有意义的研究问题b o u r s 在文 1 1 】中给出了以下结果 定理1 1 4 若c 是一个s ( k t ，k ，u ) _ 码，则c 所含码字的个数 i v | i ”kl c * 一t ，! ( 。二i 二，) ，( 。竺i ! 。) j j 若c + 是一个( 2 ，k ，。) 一码，则c + 所含码字的个数| e 叫i 【等等+ ” 删位和插位纠错码的研究工作主要集中在能够纠错一个删位或插位的 码，相关内容可以参阅文献f 1 2 ，1 3 ，3 7 ，4 7 ，5 3 ，5 4 ，5 5 ，5 6 作为一种特殊的t 删位和插位纠错码，l e n v e n s h t e i n 【3 8 】提出了完备的 删位( 插位) 纠错码的概念 ( 二) 完备的删位( 插位) 纠错码 设b a ( ”) ，记【b j 产u 倒t ，f 曰1 萨u 旧。注意到，若c b ， 贝4l g jc l 曰j t 和v i i f b t 设c 垡m 垡a i ( v ) 若f j 沪【驯t ( c l c - m 1 t ) ，则称c 是m 的一个 从下( 从上) 的t 复盖 定义1 1 5 设c m a * k ( v ) 并且c 是一个t 一删位和插位纠错码若c 是 m 的一个从下( 从上) 的t 一复盖，则称c 是m 中的一个完备的t 删位( 插 位) 纠错码， 第一章绪论研究背景4 在一般情况下，完备的删位纠错码和完备的插位纠错码不是等价的以 下定理就可以说明这个事实l e v e n s h t e i n 在文 3 8 中指出该定理的结果是 在1 9 6 5 年被发现的 定理1 1 6 若n 磊十l ，则晡，n ： 互：( 钆，z ) 雄( 2 ) ：圭i 甄i t = 1 n ( m o dk + 1 ) ) 是雒( 2 ) 中的一个完备的1 删位纠错码此外，w ；，o 也是 雄( 2 ) 中的一个完备的1 插位纠错码，其余的噼。( 1 os ) 都不是完备 的1 一插位纠错码 此外，文 3 8 】中定理2 2 还指出，对任意的2 和”2 ，除了埘，o 外，在a * k ( v ) 中不存在其他的完备的1 插位纠错码因此，在雒( ”) 中我们 主要研究完备的t 删位纠错码 根据定义1 1 5 ，若c 是砧( ”) 中的完备的( k t ) 删位纠错码，则有 【c j = 【a ；( v ) jk 。这说明对于a ( v ) 上的每个长度为t 的字z ，恰好存在唯 一的一个码字x c ，使得z 【x _ j 这对于要求码字的码元互不相同的情 形同样成立由此，b o u r s 在文 1 1 】中给出了饿( ”) ( 或a t ( ”) ) 中完备的删 位纠错码的等价定义 定义1 1 7 设c a k ( v ) ( 或c a ( ”) ) 若鹭( ”) ( 或x t ( v ) ) 中的每个字 作为子序列恰好出现在c 。( 或c ) 的一个码字中，则称c 4 ( 或c ) 为a i ( ”) ( 或a t ( ”) ) 中的一个完备的( k 一一删位纠错码 上述定义中有两类完备的( k 一) 一删位纠错码，其中码中码字的码元 可以相同，码c 中码字的码元必须互不相同根据b o u r s 1 1 1 ，我们称c + 为 t ( t ，k ， ) 一码，c 为t ( t ，k ，u ) 一码术语“ 删位纠错”是指t + ( t ，k ，u ) 码 或者t ( t ，k ，”) 码能够纠正k t 个删位差错。然而，这种码能够纠正任何 直到一t 个删位和插位组合的差错 t ( t ，k ，”) 一码的参数t ，和”必须满足一定的条件 定理1 1 8f 17 假如存在一个t ( t ，k ，”) 码，则对任意0sr t ，有 第一章绪论研究背景5 扣一r ) ( u r 一1 ) ( v t + 1 ) t ! 三0 ( r o o d ( r ) ) 其中o ( r ) = ( k r ) ( 自一r 一1 ) - ( 一t + 1 ) r 事实上，给定参数t ，k 和”，t ( t ，k ，”) 码包含的码字个数是确定的， 而t + ( t ，女， ) 一码则不然 定理1 1 9 ( b o u r s 【1 1 ) 若c 是一个t ( t t ! ( ；) ，( ：) 若口是一个t 电，* 愀眢j j + ” 界 k ，”) 码，则c 所含码字个数i c l = ”) 一码，则c 。所含码字个数l c + ls l e n v e n s h t e i n 在f 3 8 】中对t + ( 一1 ，七， ) 码的码字个数给出了上界和下 定理1 1 1 0 若c 是一个r + ( 女一1 ，口) 码，则有 一1 l c l 0 一1 + ( 一1 ) 一2 + ) 南 l e n v e n s h t e i n 在文【3 8 】中首先对完备的删位纠错码进行了研究此后一 些作者做了进一步的研究( 见文【1 1 ，3 5 ，3 9 ，4 0 ，4 6 ，5 7 ，6 1 】) ，其中有向设计的 理论和方法起着重要的作用 ( 三) 有向t 一设计 有向设计的研究起始于上个世纪七十年代，h u n g 和m e n d e l s o n n s hf 2 8 ，3 3 j 首先将经典的组合设计s t e i n e r 三元系推广为有向三元系和m e n d e l s o n n s h 三 元系。此后，有向三元系得到了非常广泛的研究，并且促使人们去研究其它 类型的有向设计。在很长的一段时期内，人们发现无向设计经过区组重排后 总是能够成为一个有向设计。然而，m a h m o o d i 【3 9 】通过计算机找到了不能 排序成有向设计的具体例子，从而导出了很多无法有序化的无向设计，这就 使得研究有向设计在理论上更为有意义。此外，有向设计在编码理论和计算 机科学等领域中有着许多应用，相关细节可以参考文【4 9 第一章绪论 研究背景 6 有向设计的一个最重要的应用就在于删位和插位纠错码的构造，这主 要归功于有向t 一设计和t ( t ，女，“) 一码之间的等价关系下面我们介绍有向t 一 设计的概念 设 a 。，n 。，a k 为一个k 元集合，其上定义一个二元关系“_ ”： 啦 嘶( 1 i j 茎南) ，则称( n 1 ，0 2 ，a k ) ， ) 为一个可迁有序集， 记作( n 。，。，a 。) 给定两个可迁有序集a = ( a t ，) 和b = ( b l ，5 2 ，b ) ，如果b 产a f ，i = 1 ，2 ，t ，并且当i 2 时，t + ( t ，k ，w ) 码的已知结果非常少在定理1 1 6 中，所有长 度为七的= 元码字被划分成 + 1 个丁+ ( 一1 ，k ，2 ) 一码l e v e n s h t e i n 3 8 给出 了一个由t ( 3 ，4 ，”) 一码构造t + ( 3 ，4 ，”) 一码的方法。利用这个方法并结合定理 1 1 1 4 就得到了下面的结果 定理1 1 2 3 【3 8 】对于任意偶数u ，存在一个t + ( 3 ，4 ， ) 一码 第一章绪论主要结果9 当。为鸯数露，灵鸯几个小鳃倒子露被载黪。l e v e n s h t e i n 在文 删中 构作了t + ( 3 ，4 ，3 ) 一码，并且将t + ( 3 ，4 ，5 ) - 码的存在性作为一个问题提出 m a t h o n 在文f 3 9 】中构作了t + ( 3 ，4 ，5 ) 一码，m a h m o o d i 在文f 3 9 】中构作了 7 ，2 1 ，2 5 鳇t + 祭，4 ，暂) * 鹦。霆就，当v 秀鸯数霹，+ ( 3 ，4 ，* ；一码懿存 程性是一个尚未解决的问题 1 。2 主要结果 利用有向设计构造出的趱! 位和播使纠错码其有较强的纠错能力，但融前 没有太多的有向设计可以用来构造这类纠错码本文主要研究完备的删位 缉爨跨静缓合梅造，具体讨沦了? + ( 3 ，4 ，。) 一码，d b ( 7 ，l ； ) 秘t 8 ( 2 ，7 ，t ，) 一弼 的存在性问题，其中d b ( 7 ，1 ；口) 的结果可以用采襻到相应的t ( 2 ，7 ，”) 一码 在第二鬻中，我们首先引入广义烛台形t 设计( 或t - g c s ) 的概念，然 纛绘窭了曩t - g c s 稳终t 4 纭女，。) 秘酶方法。 蹴理2 1 4 假设存在下述几个设计： ( 1 ) 一个戮为碱9 7 1 夕2 露r ：s ) 的g c s ( t ，k ，”) ； ( 2 ) 一个t + 豫k ，g o + s ) 一码；和 ( 3 ) 一个霉( ，k ，g i + s ) - 码，1 曼i 曼r 那么必存在一个臻+ 。( t ， ) 一码，其中u = 主热+ 鲕+ s 我们将毽为( 贫鲜r ：8 ) 的a c s ( 3 ，4 ，”) 筒记为a c q s ( g ? 鳝s 9 7 r ：s ) 作为定理2 1 4 的特殊情形，我们有以下构作t ( 3 ，4 ，”) 一码的方法 窥淫2 。1 5 假设存在下述咒个设诗： ( 1 ) 一个g g q s ( 懿鲮站2 弗7 ：s ) ； ( 2 ) 一个p ( 3 ，4 ，g o 十s ) * 码；和 3 ) 一个霉强4 ，舅+ 8 ) 一码，t 曼i 曼r ， 那么必存在一个瑶+ 。( 3 ，4 ，。) 一码，其中 = 宣臻m + g o + s 为了应用定理2 1 4 ，我蠢 在第二摩的第二节巾给出了一个g c s ( 3 ，豇， ) 的递推梅作法 第一章绪论 主要结果1 0 霆疆2 2 5 设整数e21 燕暴存在下述豆个设计： ( 1 ) 一个裂为贫1 疗h * 贫t 的e f g ( 3 ，( k t ，2 ，配，k o ) ，v ) ； ( 2 ) 对每个k l k l ，存在一个型为( m - ：r ) 的g c s ( 3 ，m h + r ) ； 3 ) 对每个岛k j ( 2 鬟j 曼e ) ，存在一个型为m + 1 魏d g d d ( 3 ，k ，r n ( k j + 1 ) ) ；以及 ( 4 ) 对每个k o k o ，存在一个型为m 。的d g d d ( 3 ，k ，m k o ) ， 那么必存在一个型为( m 9 1 ) “t ( m a 2 ) 眦- + ( m 鱼：( # 一1 ) r a + r ) 的c o s ( 3 ，k ，撞+ ( e 1 ) m + r ) 在直接构作和递推构作出定理2 1 5 所需的输入设计后，我们确定了” 涛鸯数酶f 4 ( 3 1 ，嚣) 一强鹃存在洼。 寇理2 4 8 对于每个奇数 ，存在一个t + ( 3 ，4 ， ) 码 结台定璎1 1 2 3 释宠灌2 4 8 匏缭粜，f 3 ，4 ，”) + 鹃的存在性闻题就被 彻底解决了 宠遴2 5 。1 对予每拿歪整数茁，存在一个p ( 3 ，4 ，。) 羁。 在第三章中，我们讨论d b ( 7 ，1 ；w ) 的存在性问题首先介绍d b ( k ，1 ；v ) 的递推构作法，主要是特异点积的方法这些方法鼹要d g d d 作为输入设 计，力茈我们给出了几个d g d d 酶遵稚梅箨法。在梅作舞骄镂懿7 - d g d d 作 为输入设计靥，我们得到以下d b ( 7 ，1 ；”) 存在性的结果 宠淫3 3 。1 7 一个d b ( 7 ，l ；秽) 存在黪兖分纛鍪要条件是兰1 ，7 r o o d2 1 显 口7 ，除了例外值”= 2 2 ，以及下列可能的例外值：( 1 ) = 2 1 t + 1 ，t a j ( 2 ) ”= 2 1 t + 7 ，t b 上述定璜中，a = l l ，1 2 ，1 3 ，1 7 ，1 9 ，2 5 ，2 较3 l ，3 3 3 9 ，4 l ，豁，4 7 ，5 1 ，5 3 ，5 4 ， 5 5 ，5 9 ，6 1 ，6 7 ，6 9 ，7 1 ，7 3 ，7 5 ，7 7 ，7 9 ，8 1 ，8 3 ，8 4 ，8 5 ，8 7 ，8 9 ，9 1 ，9 3 ，9 5 ，9 7 ，1 0 9 ，1 1 1 ， b 一 7 ，1 1 ，1 9 ，2 5 ，2 7 ，3 1 ，3 9 ，4 1 ，4 3 ，4 7 ，5 1 ，5 3 ，5 7 ，5 9 ，6 1 ，6 7 ，6 9 ，7 3 ，7 5 ，7 7 ，7 9 ，8 3 ， 8 ，8 7 ，8 ，9 l ，9 3 ，9 5 ，1 0 5 ，1 0 9 第一章绪论 主要结果1 1 结合定理1 1 1 2 和定理3 3 1 7 ，我们就得到了以下t ( 2 ，7 ，”) 一码存在性 的结果 定理3 4 1 一个t ( 2 ，7 ，”) 码存在的充分和必要条件是”7 和u 兰1 ，7 ( m o d2 1 ) ， 并且 2 2 ，以及下列可能的例外值：( 1 ) = 2 1 t + 1 ，t a ；( 2 ) = 2 1 t + 7 ， t b 在第四章中，我们首先介绍一些t + ( 2 ，k ，”) 一码的组合构造法，并且提 出了一个新的构造方法 定理4 1 1 1 假设 ，女，w ，f 和e 都为非负整数，k 3 ，f 叫并且f e 【譬j 若存在一个i d b ( k ，1 ； ，w ) 和一个t ( 2 ，k ，伽一，) 一码，则存在一个 t + ( 2 ，k ，u e ) 一码 接着，我们研究了t ( 2 ，7 ，”) 码的存在性，得到了以下几个无穷类 t + ( 2 ，7 ， ) ，码 引理4 3 1 对于任意正整数 兰0 ，1 ，2 ，4 ，5 ，6 ，7 ，8 ，1 9 ，2 0 ( r o o d2 1 ) 且 ( 1 ) u 2 1 t + 1 一e ，其中t a 或者t = 1 ，e 一1 ，0 ，1 ，2 ，3 ；以及 ( 2 ) 2 1 t + 7 一e ，其中t b ，e - 1 ，0 ，1 ，2 ，3 ， 存在一个t + ( 2 ，7 ，f ) 码 引理4 3 2 对于任意整数t 0 且t 簪 3 ，5 ，6 ，1 2 ，1 4 ，1 9 ，2 2 ，2 7 ，3 4 ，3 7 ，3 9 ，4 2 ， 4 7 ，5 9 ，6 2 ，存在一个露( 2 ，7 ，4 2 t 十3 ) 一码 我们还构作了大量”值较小的t + ( 2 ，7 ，”) 一码基于上面这些结果，我 们得到了一个t + ( 2 ，7 ，u ) 一码的渐近存在性结果 定理4 5 4 若 22 3 5 0 ，则存在一个t 4 ( 2 ，7 ， ) - 码 在第五章，我们利用有向t 一设计的结果得到了一个t ( t ，k ，”) 一码的渐近 存在性结果，并对t ( t ，k ，”) 一码的渐近存在性问题作了一些初步性的讨论 我们还介绍了其它两类与删位和插位纠错码有关的有向设计：有向填充和 有向p b d ，并且提出了若干进一步的研究问题 第二章t 。( 3 ，4 ，口) 一码 利用t g c s 的绚雒t 2 第二章z 。( 3 ，4 ，刀) 一码 本章研究p 浅4 ，* ) 一码静存在性出予l e v e n s h t e i n 已经惩决了”为偶 数时t ( 3 ，4 ，”) 一码的存在性，因此我们只须讨论”为奇数的情形首先，我 们分绥t - g c s 的概念，并且利用t - g c s 给出一个f + 3 ，4 ，) - 码的构造法；然 后，给漱t - g c s 的递推梅造法，弗构作了一麓t - g c s ；最后，确定v 为奇数 的r + ( 3 ，4 ，”) 一码的存在性 2 。1 雾l 焉t - g c s 静构侔 我们先叙述t 。e s 的定义，然后将这个概念推广为t - g c s ，并给出利用 t - g c s 构依t 纸竞， ) * 码的方法。 定义2 1 1 设v ，s 是非负整数，t 是一个藏楚数，并是某些正整数的集 合一个阶数为”的烛台形( c a n d e l a b r a ) t 设计( 或t - c s ) 是一个四元组 ( x ，墨蛋，国，它游趣下魏五个象律： ( 1 ) x 是一个u 髭( 点) 集； ( 2 ) s 是x 的一个s 元子集，称作千( s t e m ) ； 3 ) g = g ，g z ， 是盍x 的一些菲空子集梅戒懿集合，盈赵分x s ， 蛋的元素称作组或分支( b r a n c h ) ； ( 4 ) 嚣是由x 的一蠖子集构成的集合，称其元素为区缀，且对每个b 器， | b | 影； ( 5 ) 对于x 的每个t 元子集t ，如果对每个i ，l r n ( s u g 。) 1 t ，那么 f 恰包含予8 中一个区组丽对予l 壬意，s u g t 的任意t 元子集都不包含 于嚣中疆俺一个嚣缀中。 通常把这样的设计记作c s ( t ，k ，吐当k = 七 时，就简记k 为七，蓿母包 含臻拿大小鸯繇酶缝i 茎isr ) ，并豆子酶大小秀s ，剡称魏t - c s 懿鳖为 ( 贫1 醪2 簖r ：s ) 若所有组的大小相同，则称此t - c s 是一致的一个型为 第二章t 4 ( 3 ，4 ， ) 一码 利用t - g c s 的构作 1 3 ( 1 ”：0 ) 的c s ( t ，k ，t 州x ，o ，毋，1 3 ) 通常被称为一个f 平衡设计( t b d ) ，记作 s ( t ，k ，”) 在文献【2 6 中，一个型为( 卯1 9 卵t ：s ) 的c s ( 3 ，4 ，”) 被称为 烛台形四元系( c a n d e l a b r aq u a d r u p l es y s t e m ) ，并简记为e q s ( 贫1 篮2 妒：s ) 以上介绍的一c s 是一种无向设计下面我们修改t - c s 的定义，使设计 中的区组是可迁有向子集，并且允许区组包含重复的元素 定义2 1 2 设v ，s 是非负整数，t 是一个正整数，是某些正整数的集合一 个阶数为”的广义烛台形t 设计( 或t - g c s ) 是一个四元组( x ，s ，9 ，日) ， 它满足下列五个条件： ( 1 ) x 是一个”元点集； ( 2 ) s 是x 的一个8 元子集，称作干( s t e m ) ； ( 3 ) 9 = g 。，g 。，) 是由x 的一些非空子集构成的集合，且划分x s 9 的元素称作组或分支( b r a n c h ) ； ( 4 ) 8 是由x 上的一些字构成的集合，其中字称为区组，且对每个b 8 ， 长度l ( b ) k ； ( 5 ) 对于x 上的每个长度为t 的字篓，如果对每个i ，五g ( sug ，) ；， 那么签恰作为子序列出现在舀的一个区组中而对于任意i ，sug ；上的任 意长度为t 的字都不出现在8 的任何区组中 我们把这种t - g c s 记作c c s ( t ，k ， ) ，并且将一个型为( 计1 9 9 7 r ：s ) 的g c s ( 3 ，4 ，u ) 筒记为g c q s ( g ? 1 9 ；2 簖r ：s ) 在给出利用t - g c s 构作t + ( t ，k ，”) 一码的构造方法前，我们还需要子码 的概念 定义2 1 3 设c 1 是字母表u 上的t + ( t ，k ，札) 码，g 是字母表矿上的 t ( t ，k ，口) 一码若c 。c 2 且u v ，则称c l 是岛的一个子码( s u b c o d e ) ， 为方便起见，用记号咒( t ，k ，。) 一码来表示一个t + ( t ，k ，”卜码包含了一 个t ( t ，k ，让) 码我们允许u = 0 ，那么这种空集上的退化子码可以被视 第二章t + ( 3 ，4 ，”) 一码 利用t g c s 的构作1 4 为任意一个码的子码容易看出，若存在一个咒( ，k ，u ) 一码，则存在一个 t ( t ，k ，”) 一码；反之则不一定成立，除非让= 0 利用t - g c s ，我们给出下面一个t + ( ，k ，口) 码的构造方法 定理2 1 4 假设存在下述几个设计： ( 1 ) 一个型为( 蛳1 l n l 醇2 9 7 r ：5 ) 的g c s ( t ，k ，u ) ； ( 2 ) 一个t + ( t ，k ，g o + s ) 一码；和 ( 3 ) 一个巧( t ，k ，g i + s ) 一码， 1sisr 那么存在一个丐+ 。( t ，k ，”) 一码，其中”= 壹 + o + s 4 证明：假设僻，s ，9 o ) ，) 是给定- - 的 g i n igu gb g c s ( t ，k ，u ) ，其中l g o l = 鼬 现在我们构作一个t + ( t ，k ，”) 如下 1 在g ous 上构作一个t ( t ，k ，g o + s ) 一码； 2 对于每个g 9 ，在g u s 上构作一个p ( t ，k ，g + s ) 一码，其包含一个s 上的子码t + ( t ，女，s ) 一码，然后将这个子码t + ( t ，k ，s ) 一码中所有的码字 删除掉； 3 取8 中所有的区组作为码字 容易看出，按上述的步骤可以得到一个t 4 ( t ，”) 码，并且它包含一个g o u s 上的子码t + ( t ，k ，g o + s ) 一码 口 作为上述定理的特殊情形，我们有以下构作t + ( 3 ，4 ，”) 码的方法 定理2 1 5 假设存在下述几个设计： ( 1 ) 一个g c q s ( g t 9 7 1 9 ；2 9 7 ：s ) ； ( 2 ) 一个t + ( 3 ，4 ，g o 十s ) 码；和 ( 3 ) 一个霉( 3 ，4 ，g l + s ) 一码， 1 i 茎r 那么必存在一个瑶+ 。( 3 ，4 ，”) 一码，其中w = 耋9 i n i + 跏+ s 第二章丁+ ( 3 ，4 ，u ) 一码 g c s ( 3 ， ) 的递推构作 1 5 我们在这里也提一下另外两个t + ( 3 ，4 ，”) 一码的构造法给定一个点集 x 上的t ( 3 ，4 ， ) 一码，对任意的z ，y x 且$ y ，把形为( 。，y ，y ，z ) 和 ( z ，z ，z ，z ) 的有向四元组添加到码字集合中，这样就得到了一个t + ( 3 ，4 ，u ) 一 码这个方法是l e v e n s h t e i n 给出的 定理2 1 6 3 8 若存在一个t ( 3 ，4 ，”) 码，则存在一个t 4 ( 3 ，4 ，”) 一码 m a h m o o d i 给出了一个用s ( 3 ，k ，”) 构作t + ( 3 ，4 ， ) 一码的方法，但这个 方法依赖于必须存在一类特殊的t ( 3 ，4 ，w ) 码 定义2 1 7 如果字母表x 上t + ( t ，k ，u ) 一码对每个z x 都包含了码字 ( z ，z ，z ) ，则称此t + ( t ，k ，”) 码为z 型的 定理2 1 8 【3 9 假设存在下述几个设计 一个s ( 3 ，k ，”) ，其中对某个f k ，存在一些大小为z 的区组，它们 构成一个b i b d ( 1 ，1 ； ) ； 2 一个妒型的t + ( 3 ，k ，f ) 一码；和 3 一个t ( 3 ，k ， ) 一码，其中h k 且h f 那么存在一个t + ( 3 ，u ) ，码 2 2 c o s ( 3 ，k ，v ) 的递推构作 为了应用定理2 1 4 ，我们有必要构作一些g c s ( ，七，”) 在这一节中， 我们给出了g c s ( 3 ，k ，”) 的递推构作法下面先介绍一些组合设计的基本概 念与记号 定义2 2 1 设”，a 和t 为正整数，为某些正整数的集合若一个二元组 ( x ，8 ) 满足以下三