（基础数学专业论文）可纠错ddisjunct矩阵的一些构作.pdf

河北师范大学硕士学位论文 中文摘要 本文首先研究了6 ( n ，d ，k ) 的补阵6 。( n ，d ，) 的d i 印u n c t 性质，证明了当k = n 一1 时它是伽一d ) 一d i s j u n c t 矩阵，然后研究了在单纯复形和子空问上由包含关系所构作 的矩阵的补阵的d f 耵u n c t 性质及检纠错能力定义了一个新矩阵扩+ ( m d ，) ，它是由在 6 ( ，l ，吐k ) 的行的基础上再增加扩( ，o ，k ) 得到的，其中1s o ts m + 1 似z ) ，证明了 当k d 2 m ( m 3 ) 时日( 玩( 6 “( n ，d ，) ) ) 4 且护( ，l ，d ，k ) 可检错和纠错；特别地， 当k = n 一1 时，6 “( n ，d ，k ) 的检错和纠错能力最大 主要结果是： 定理3 1 设扩( n ，d ，n - 1 ) 是6 ( ，d ，n - 1 ) 的补阵，则扩( n ，d , n - 1 ) 是( 竹一d ) 一西巧u n c t 矩阵 定理3 2 设扩( n ，d ，k ) 是6 ( n ，d ，k ) 的补阵，如果k n - 1 ，则扩( n ，d ，k ) 是l 一出s j u n c t 矩阵 定理3 4 设1 dsn 一1 ，且表示集合m 上的一个单纯复形二元矩阵 m ( a ，d ，n 一1 ) 的行和列分别用中所有d 一面a l ，a 2 ，a i 和所有一1 ) - 面 b 1 ，岛，晶。标定，且( a ，马) 处元素为1 当且仅当ac 马设m 。( ，d ，t 一1 ) 是m ( a ，d ，n 一1 ) 的补阵，则m 。( ，d ，l 一1 ) 是m d ) 一d i s j u n c t 矩阵 定理3 5 设1sdsk ”，令表示集合m 上的一个单纯复形二元矩阵 m ( a ，d ，k ) 的行和列分别用中所有d 一面4 l ，a 2 ，a 和所有k 一面历，岛，b f 标 定，且( a ，马) 处元素为1 当且仅当ac 马设m e ( a ，d ，k ) 是m ( a ，d ，k ) s j * l , 阵，如 果k n 一1 ，受f m e ( z a ，正k ) 是i d i s j u n c t 矩阵 定理3 6 设1 dsks n 且q 是个素数幂，令【譬 口表示毋中所有k 一维 河北师范大学硕士学位论文 子空问做成的集合二元矩阵7 ( n ，d ，女) 的行和列分别用【学】。和【掣】。中的元素标定 对d 嘲。和k6 譬】q ，矩阵7 ( 吼d ，女) 在( d ，k ) 处为1 当且仅当d 是k 的个子 集设甲( n ，d ，k ) 是7 ( n ，d ，k ) 的补阵，如果k n 一1 ，则r ( n ，d ，) 是1 一出町n d 矩 阵 定理3 7 令1 d s 七s n rq 2 1 ，令( 掣) m 表示长为n 重为七的全体q 一元向 量作成的集合二元矩阵丌( 口，竹，d ，) 的行和列分别用( 学) k 】d 和( n 】) m 中的元素标 定对。( n 】) 【q 】4 和r ( n 】) 【水，矩阵”( g ，n ，d ，女) 在( q ，r ) 处为1 当且仅当a r 设矿( q ，n ，d ，k ) 是 ( q ，n ，d ，k ) 的补阵，如果后 n 一1 ，则矿( 吼n ，d ，k ) 是1 一d f 彰“耐 矩阵 定理4 2 设扩( n ，d 詹) 是在矩阵j 加，d ，k ) 的行的基础上再增加伊m ，2 ，砷得到的， 如果k d 23 ，则日( 玩( 6 “( n ，d ，) ) ) 4 定理4 3 设j ”( 鸭d ，k ) 是在矩阵5 ( n ，d ，k ) 的行的基础上再增加6 。( n ，口，k ) 得到的， 其中1 n m + l ( a z ) ，且k d 芝m ( m 3 ) ，则日( 玩( 6 ”( n ，d ，) ) ) 4 定理4 4 对2 d n 一2 ， 日( 矿+ ( n ，d ，n 一1 ) ) 22 n 一她 日( b d ( 矿( ，d ，n 一1 ) ) ) 2 ，l d 关键词，p o o l i n 9 设计，d d i 鲥t n d 矩阵。b a m m 咖距离，矩阵的补阵 河北师范大学硼士学位论文 i i i a b s t r a c t f i r s t l yw ed i s c u s st h ed i 鲥u n c tp r o p e r t i e so f 伊m ，d ，女) ，t h ec o m p l e m e n tm a t r i xo f 6 ( n ，d ，) ，a n dp r o v et h a ti ti s ( n d ) 一d i s j u n c ti f 七= 社一1 n e x tw ef f l s e u $ t h e d f 可u n e tp r o p e r t i e sa n dd e t e c t i n ga n dc o r r e c t i n ga b i l i t i e so fm a t r i c e sw h i c ha c t 船t h e c o m p l e m e n tm a t r i c e so ft h o s eo b t a i n e db yt h ei n c l u s i o n r e l a t i o n si ns i m p l ec o m p l e x e s a n ds u b s p a c d e f i n ean e wm a t r i x 扩( 凡，d ，t ) 鹅t h a tw h i c hr e s u l t sb yr o wa u g m e n t - i n gt h em a t r i x6 ( n ，d ，k ) w i t h6 c ( n ，o ，后) ( 1 口m + 1 ( a z ) ) w ep r o v et h a ti f k d m ( m 3 ) ，t h e n 丑( b d ( 巧( n ，d ，七) ) ) 4a n d6 杆( 乱，d ，k ) c a nd e t e c ta n dc o r r e c t t l r r o r f l i np a r t i c l i l ”，i f 七= f i 一1 ，t h e ni t sa b i l i t yf o rd e t e c t i n ga n dc o r r e c t i n ge r r o r 8i s t h el a r g e s t t h ef o u 0 w i n gi so l l rn l a i i lr e s u l t s ： t h e o r e m3 1l e t 扩( n ，正n 一1 ) b et h ec o m p l e m e n tm a t r i xo f6 ( n ，d ，n 一1 ) t h e n 6 。( 啦d ，n 一1 ) i s ( n d ) 一d t s j u n e t m a t r i x t h e o r e m3 3l e 俨( 拈，d ，七) b et h ec o m p l e m e n tm a t r i xo f 占( n ，d ，蠡) i fk 竹一1 t h e n 俨( n ，d ，k ) i sa 1 一面耵“耐m a t r i x t h e o r e m3 4f o r1 ds 竹一1 ，l e t d e n o t es i m p l i c i a lc o m p l e xi na 鞋，t 【嘲d e - f i n et h eb i n a r ym a t r i xm ( ，d ，t l 一1 ) bl e t t i n gi t sr a 嘲a n dc o h m mb er e s p e c t i v e l y i n d e x e db ya l lt h em e m b e r so fd - p l a n e ，s a ya 1 ，a 2 ，aa n da l lt h e 加一1 ) - p l a n e ， s a yb 1 ，岛，骨k t h em a t r i xm ( ，d ，n 一1 ) h a sa1i ni t s ( a ，马) 地e n t r yi fa n do n l y i fa c 马l e t | ! l = p ( ，d ，n 一1 ) b et h ec o m p l e m e n tm a t r i xo f f ( ，d ，住一1 ) t h e n m c ( ，吐n 1 ) i s a n ( n 一田一疵耵“n d m a t r i x 打北师范大学硕士学位论文i v t h e o r e m3 5f o r1 d k n ，l e t d e n o t es i m p h c i a lc o m p l e xi nas e tm d e f i n e t h eb i n a r ym a t r i xm ( a ，d ，k ) b yl e t t i n gi t sr o w 8a n dc o l u m n sb er e s p e c t i v e l yi n d e x e db y a l l t h e m e m b e r s o f d p l a n e ，s a y a i ，a 2 ，a ta n d a l l t h e k - p l a n e ，s a y b x ，b z ，b t t h e m a t r i x m ( a ，d ，k ) h a sa l i n i t s ( a i ，马) 埔e n t r y i fa n do n l y i f a c 岛l e t m 。( ，d ，k ) b e t h ec o m p l e m e n t m a t r i xo f m ( a ，吐七) 。i f 摩 珏一1 ，t h e n m c ( a ，d ，詹) i s a l 一d i s j u n c t m a t r i x t h e o r e m3 - 6f o r1sd k na n dl e tm 8p r i m ep o w e ra n dl e t 旧。d e n o t e t h ef a m i l yo fkd i m e n s i o n a ls u b s p a c e so f 曩d e f i n et h eb i n a r ym a t r i x7 ( m d ，) b y 慨堍1 t sr a n dc o l u m n sb er e s p e c t i v e l yi n d e x e db yt h em e m b e r s o f qa n d 吼， f o rd e 吼a n dk 巩t h e m a t r i x7 ( m d ) h a s81i ni t s ( d ，k ) me n t r yi f a n d o n l yi fd i s8s u b s e to fk l e t7 。( n ，d ，k ) b et h ec o m p l e m e n tm a t r i xo f7 ( n ，d ，) t h e n r ( n ，匾七) i sa1 一d i s j u n c tm a t r i x t h e o r e m3 7f o r l d 詹s f l a n d q 1 ，l e t ( 掣) m d e n o t e t h e s e to f a l l 口一a r y v e c t o r so fl e n g t hna n dw e i g h tj d e f i n et h eb i n a r ym a t r i x 霄( q ，几，d ，k ) b y l e t t i n gi t s r o w sa n dc o l u m n sb er e s p e c t i v e l yi n d e x e db yt h em e m b e r s o f ( 学) a n d ( 粤) q l f o r 口( 学) m 4a n dr ( 掣) 【g 】，t h em a t r i x ，r ( q ，n ，d ，功h a sa1i n i t s 陋，r ) 砺e n t r yi f a n d o n l yi fo r l e t 霄。“，t l ，西k ) b et h ec o m p l e m e n tm a t r i xo f r ( 口，t l ，d ，奄) k n 一1 ， t h e n 矿( g ，竹，d ，功i sa1 一d i s j u n c tm a t r i x t h e o r e m 4 2 6 ”( 站，吐日i s t h e m a t r i x w h i c hr e s u l t sb y r o w a u g m e n t i n g t h e m a t r i x 6 ( n ，d ，k ) w i t h 俨( n ，2 ，k ) a n d 一d 3 ，t h e n h ( b d o “( n ，d ，) ) ) 24 t h e o r e m4 3i f 扩( t l ，d ，) i st h em a t r i xw h i c hr e s u l t sb yr o wa u g m e n t i n gt h e 嘶 t r i x5 ( n ，d ，k ) w i t h 扩n ，o t ，七) ( 1 口仃l + l ( a z ) ) a n d 七一d m ( m 3 ) ，t h e n 日( b d ( 扩( n ，d ，功) ) 4 河北师范大学明士学位论文 v t h e o r e m4 4f o r2 sd n 一2 ，w eh a v e 日( 矿( n ，d ，n 1 ) ) 2 n 一2 d 日( b d ( d “，d ，n 一1 ) ) ) 2 n d k e y w o r d s ：p o o l i n g d e s i g n ，d - d i 巧u n c t m a t r i x ，h a m m i n g d d s t a n c e ，c o m p l e m e n to f m a - 学位论文原创性声明 本人所提交的学位论文删箱z 咖瘫嘲，是在导师的指 导下，独立进行研究工作所取得的原创性成果。除文中已经注明引用 的内容外，本论文不包含任何其他个人或集体已经发表或撰写过的研 究成果。对本文的研究做出重要贡献的个人和集体，均已在文中标明。 本声明的法律后果由本人承担。 论文作者( 签名) ：瑶碓各 舻1 年f 月f 寥日 学位论文原创性确认书 学泽所提交的学位论文四嗽不如岫删，是在 本人的指导下，由其独立进行研究工作所取得的原创性成果。除文中 已经注明引用的内容外，该论文不包含任何其他个人或集体已经发表 或撰写过的研究成果。 指导教师( 签名) ： 硼年j 月1 9 日 i 驭刚 河北师范大学硕士学位论文 第一章绪论 1 1 课题背景与发展概况 分组测试理论自1 9 4 3 年以来发展很快，它的组合分支被称为组合分组测试理论( 。d m b i n a t o r i a lg r o u pt e s t i n g ) j i l l 2 ，由于在血试验，化学渗透试验，电子检验，码，多路存取 信道传递和艾滋病筛选等方面的应用 a l i 4 1 1 5 1 而得以盛行 首先介绍组合分组测试的基本模型；假设有n 个对象，它们中的每一个或是阳性的 ( 通常称有缺陷的) 或是阴性的( 通常称为正常的) ，且阳性对象的个数不超过d 组合分 组测试的根本问题就是把所有的阳性对象找出来在此过程中我们所用的方法就是所谓 的分组实验( g r o u pt e s t s ) 个分组实验可以通过对检测对象集的任何一个子集进行测 试，只产生两个可能的结果；阳性或阴性结果是阴性的说明这个对象集的子集中的所有 对象都是阴性的。结果是阳性的说明这个对象集的子集中至少有一个对象是阳性的它 的主要原理也可以用圣诞树灯泡问题很好地说明一批灯泡按照电学原理串联在一起， 测试时给这整批灯泡或者其中一部分加上电压。如果所有灯泡都亮，说明它们都是合格 的；如果所有灯泡都不亮，说明其中至少有个不合格组合分组的目的是使用最少个数 的试验找出所有的阳性对象分组测试算法通常有两种，时序的和非适应的一个算法 称为时序的，如果试验一个接个地进行，而且允许后面的实验使用前爵试验的试验结 果个算法称为非适应的，如果所有的试验都是同时进行的，不允许使用前面试验的 结果这两种算法各具有优缺点，时序算法所需的试验个数少但用的时间较长，而非适 应算法所需的试验个数多但用的时间较短介于两个算法之间的还有一个s - - 部算法， 这种算法中的每步中所作的试验同时进行，但每两步之间是时序的 分组测试理论在分子生物学上也有广泛的应用【6 】在分子生物学的应用上，个分组 测试算法称为个p o o l i n g 设计，每个实验构成个p d 耐虽然分子生物试验的目的是使 河北师范大学硕士学位论文 2 用尽量少的试验，但由于分子生物试验具备以下两个特点；1 需要测试的对象是大量 的；2 分子生物试验极易出错因此分组测试算法用在分子生物试验上，时序性算法是 不切实际的，而且必须建立能容错的算法，即能容错的p o o l i n g 设计【8 】而非适应性分 组测试算法的数学模型就是d 一出s j u n c t 矩阵，能容错的数学模型就是矿矩阵，同时， h a m m i n g 距离大于等于4 的d d i s j u , m t 矩阵也具有容错功能 1 9 7 7 年，f j m a c w i u i a m s 和n j a s l o a n e 【9 1 证明了在个( 0 ，1 ) d d i 可u n c t 矩阵 p 中，若日( p ) ( 矩阵p 的h a m m i n g 距离) = 4 ，则矩阵p 具有检测两个错误纠正个错误 的能力1 9 9 7 年，m a c u l a 1 0 得出结论，若h ( i t ) k ，则芦具有检测( k 一1 ) 个错误纠正 ( 晴2 1 1 ) 个错误的能力紧接着，他又给出了用包含关系所定义的( 0 ，1 ) d 一出s j u n c t 矩阵烈n ，d 女) ， 通过在j 伽，d ，k ) 的行的基础上再增加伊1 ，k ) 就得到个新矩阵 扩( 札，d ，) ，并证明了a ( b d o + ( t l ，d ，) ) ) 4 ( b d ( i t ) 的概念见定义2 1 1 1 ) ，从而可以进行 检错和纠错在【1 2 】中t a y u a nh u a n g 和c h i h - w e nw e n g 给出了铲一d i s j u n c t 矩阵的 概念并证明了个萨一d 纫u n c t 矩阵能够检测出实验结果中的e 个错误并能纠正 e 2 j 个错误 本文首先研究了j ( n ，d ，k ) 的补阵俨( n ，d ，k ) 的d i s j u n c t 性质，证明了当k = 一1 时它是似一回一d i s j u n e t 矩阵。然后研究了在单纯复形和子空闻上由包含关系所构 作的矩阵的补阵的如巧u n c t 性质及检纠错能力并通过在j ( 啊d ，k ) 的行的基础上再 增加扩( n ，口，) ( 1 曼a m + l ( a 刃) 从而得到一个新矩阵j ”( n ，d ，) ，证明了当 k d m ( m 3 ) 时日( 玩( 扩( 仉d ，) ) ) 芝4 ，达到了检错和纠错的目的；特别地，当 k = n 一1 时，风( 扩( n ，d ，) ) 的h a m m i n g 距离更大，从而增强了检错和纠错能力 河北师范大学硕士学位论文 3 1 2 本文综述 本文共分四章第一章阐述了课题背景及发展概况；第二章为预备知识，着重介绍了 后面几章中要用到的一些符号，概念和基本结论；第三章研究了d d i s j u n c t 矩阵的补 阵的一些性质；第四章研究了矿( n ，d ，k ) 的性质 主要结果有； 定理3 1 设j 。( n ，吐n - - 1 ) 是j ( 佗，d ，n - 1 ) 的补阵，则扩( n ，西n - 1 ) 是( ”一回一d i s j u n e t 矩阵 定理3 2 设酽( ，l ，d ，k ) 是6 ( n ，d ，k ) 的补阵，如果k n - 1 ，则扩( t l ，d ，k ) 是1 一d 泖u n c t 矩阵 定理3 4 设1sdsn 一1 ，且表示集合m 上的一个单纯复形= 元矩阵 m ( a ，d ，r t 一1 ) 的行和列分别用中所有d 一面a 1 ，如，a 和所有m 1 ) 一面 b l ，疡，b k 标定，且( a ，毋) 处元素为1 当且仅当ac 易设m e ( a ，d ，n 一1 ) 是膨( ，d n 一1 ) 的补阵，划膨。( ，吐一1 ) 是一田一d i s j u n c t 矩阵 定理3 5 设1sdsk n ，令表示集合m 上的一个单纯复形二元矩阵 m ( a ，d , k ) 的行和列分别用a 中所有d - 面a 1 ，也，a 和所有k 一面岛，岛，岛标 定，且( a ，马) 处元素为1 当且仅当ac 岛设m e ( a ，d ，k ) 是m ( a ，d ，k ) 的补阵。如 果k n 一1 ，则胪( ，d ，k ) 是1 一巍巧u n c t 矩阵 定理3 6 设1 d k 墨竹且g 是一个素数幂，令【掣】。表示才中所有k 一维 子空间做成的集合二元矩阵7 ( m d ，七) 的行和列分别用 学】。和 留】。中的元素标定 对d 【嘲。和眉 i 忭】。，矩阵7 如，d 七) 在( d ，彤) 处为1 当且仅当d 是的个子 集设r ( n ，d , k ) 是7 ( 竹，d ，) 的补阵，如果知 n i ，则r ( n ，d ，后) 是1 一d i s j u n c t 矩 阵 河北师范大学硕士学位论文 4 定理3 7 令1 sd s i n 且q 1 ，令( 掣) m 表示长为n 重为k 的全体q 一元向 量作成的集合二元矩阵”( 口，d ，女) 的行和列分别用( 拿) 【q p 和( 紫) ( q r 中的元素标 定x c a ( 学) ( 叮j 4 和r ( f n j ) m ，矩阵- ( q ，行，正p 在( a ，r ) 处为1 当且仅当a r 设矿( 玑n ，d ，k ) 是- ( q ，n ，d ，k ) 的补阵，如果k 竹一1 ，则矿( 吼n ，d ，砷是1 一d f 巧u n c t 矩阵 定理4 2 设扩( n ，d ，) 是在矩阵6 ( n ，d ，k ) 的行的基础上再增加6 。( n ，2 ，k ) 得到的， 如果k d 3 ，则日( 玩( 护( n ，d ，) ) ) 4 定理4 3 设( n ，吐k ) 是在矩阵d ( d ，k ) 的行的基础上再增加扩( n ，口，k ) 得到的， 其中1 s n s m + 1 ( 0 z ) ，且一d 2 m ( m 3 ) ，则日( b d ( 6 “印，d ，女) ) ) 4 定理4 4 对2 d n 一2 ， 日( 矿( n ，d ，n 一1 ) ) 2 n 一2 d ， 目( b d ( 矿( n ，d ，n 一1 ) ) ) 竹一d 河北师范大学硕士学位论文 5 2 1 符号与基本概念 第二章预备知识 y 的布尔和记为x v y ，即x v y = ( 二i 二) ， 其中毛v 弘：f o ， 若1 2 弘2 o ，t 2 ， 河北师范大擘硕士学位论文6 p 为d d i s j u n c t 矩阵 例如t 是2 一d i s j u n c t 矩阵 “= l1 10 01 lo 0l 0o 00 lo 10 01 01 ll 定义2 1 1 0 c n i 给定m 上的矩阵弘，任取p 的d + 1 列c o ，a ，o ，任意指定其中 一列，不妨设为岛，若至少有e + 1 个1 在c b 而不在u dg 中，则称肛为扩一击巧n c t i = l 矩阵( 或者记为( d ，e ) 一d i 彰“n 矗矩阵) 例如： “= 是d = 2 ，e = 1 的( 2 ，1 ) 一也s j u n e t 矩阵 10 lo ol o1 o0 00 定义2 1 1 1 1 日设弘是个( o ，1 ) 一矩p 韩1sdsn ，由p 的所有布尔和也s 白( p ) 作列，其中s 【盥】1 ，并且列标按字典序排列的矩阵称为b d ( u ) 矩阵 河北师范大学硕士学位论文 7 例如 则 p = 恳( p ) = lo 1o 01 ol 0 0 oo 10 011 10 o1l 0lo1o 0lo10 o0lo1 oolo1 定义2 1 1 2 1 1 】给定两个二元向量x ，y ， x = ( z l ，- ，z ，z 。) y = ( 1 ，挑，) ， 用m i 鼽l 表示x 与y 的h a m m i n g 距离且记为h ( x ，l ，) 定义2 1 1 3 1 “】对m 上的矩阵鳓把矩阵p 的任何列向量对的最小h a m m i n g 距离 称为日( p ) ，即z ( u ) = m i n h ( x ，y ) l x ，y e ) ，其中c 为p 的所有列的集合 定义2 1 1 4 “】记1 兰d k ”，定义一个( ：) x ( 2 ) 的( 0 。1 ) 一阵6 ( n ，d ，) ，满足； ( 1 ) 行与歹分别由( ( 2 ) ) 与( 瞠) ) 的子集标定； ( 2 ) 矩阵6 ( d ，k ) 中( d ，k ) 处元素为1 当且仅当d c k ，其中d ( ( 2 ) ) ，k ( ( 2 ) ) 定义2 1 1 5 1 1 1 16 ( n ，d ，k ) 的定义如前，在6 ( n ，d ，) 的行上加上酽( n ，l ，) 所得到的 ( ( 2 ) + n ) x ( ( 2 ) ) 的( 0 ，1 ) - 阵，记为扩，d ，) 河北师范大学硕士学位论文 8 一2 ) 列 t ( ：) 行6 ( n ，d ，k ) 土 t n 行 扩( ，i ，1 ，) l 定义2 1 1 6 在6 ( n ，d ，自) 的行上加上扩( n ，o t ，) 所得到的矩阵记为护( md ，) 其中 1 d s m + 1 ，且o t z 定义2 1 1 7 n 设p 是m 上的矩阵，任意指定一行，此行中元索1 的个数称为行重； 任意指定一列，此列中元素i 的个数称为列重 定义2 1 1 8 1 3 1 一个单纯复形a 是指集合f n 】的一个子集族，使得该子集族当中的每 个元素的子集也在该子集族中 m 中所有元素叫做点，a 中的每个元素叫做面特别 地，包含个点的面也叫做七一面例如，o 一面就是空集，而1 一面就是一个点 定义2 1 1 9 1 目假定1sd 膏，定义一个( o 1 ) 一矩阵肘( ，面| i ) ，它以一个单纯复 形中所有的d 一面a l ，a 2 ，a 为行，以中所有的七一面且，上k 局为列，且 ( a ，马) 处元素为1 当且仅当a c 岛 定义2 1 2 0 1 5 t 令q 是个素数幂且日帕表示有限域日上的几一维向量空间对 1 七s 付，高斯二项式系数【：】。表示蹬中一维子空间的个数令 管】。表示瑶砷 中所有k - 维子空间做成的集合 定义2 1 2 1 1 1 5 1 令1 d s t l 且口是个素数幂，定义二元矩阵7 ( f l ，d ，) ，其行 和列分别用【学 。和【留】。中的元素标定对d 【学】。和k e 【掣】。，矩阵1 ( 作，d ，) 在 ( d ，k ) 处为1 当且仅当d 是耳的个子集( 因此是个子空间) 定义2 1 2 2 1 1 5 1 对奄s m 令( 掣) q l 表示长为f l , 重为的全体q - 元向量作成的集 河北师范大学硕士学位论文 9 合其中g 一元向量的重指的是向量中不为。的元素个数令n ( 学) q l 。和r ( 留) q l ， 其中d 七，n ( f ) 和r “) 分别表示n 和r 的第i 个分量称a r 如果对n ( i ) 0 ， 1 f s f l ，n ( ) = r ( o 例如，0 3 0 1 0 0 3 1 1 2 这里0 3 0 1 0 ( 粤) 1 3 1 2 1 ；1 0 3 1 1 2 ( e y ) 1 3 1 4 定义2 1 2 3 1 目令1sd s n 且q 1 ，定义( ：) 一( 2 ) 矿二元矩阵7 r ( 口，n ，d ，) 其行和列分别用( 学) k 】d 和( 留) i q l 中的元素标定对n ( 【n 】) 口】。和r ( 留) q l ， 矩阵池n ，正纠在陋，r ) 处为1 当且仅当o 河北师范大学硕士学位论文 1 0 2 2 基本性质和已知结论 命题2 2 1 u 1 日( f k ( p ) ) 詹当且仅当对j l 的任何不同的列子集e 和有p 的不 同行r l r 2 ，“使得对每个i 旧有n n c = 1 和n n = 0 成立或n n e = 0 和 n n = 1 成立，其中l c i ，i i d 命题2 2 2 1 1 qj ( 吼d ，七) 是列重为( ：) 且行重为( 2 二：) 的d d i s j u n c t 矩阵 命题2 2 3 1 1 q 个矩阵p 是d - d i s j u n c t 矩阵当且仅当它是( d ，0 ) - d i s j u n e t 矩阵 命题2 2 4 【1 目6 ( n ，d ，) ( d d 2 ，则矩阵m ( a ，d ，膏) 是( ( d 一1 ) ，( 一d + 1 ) ) 一d i s j u n c t 矩 阵 命题2 2 9 f 1 4 1 设p 是i n 上的矩阵，若p 是个萨一d i s j u n c t 矩阵，则任意两个基 坷北师范大学硕士学位论文 1 1 数为d 的列子集之间的h a m m i n g 距离至少是2 e + 2 命题2 2 1 0 i s l 令1 d m ，且p 是个n t 的扩一d i s j u n e t 矩阵，令s 和t 是 基数至多为d 的m 的不同列子集，则 ( 1 ) 如果s c t ，则日( y s ，v t ) e + 1 ( 2 ) 如果s 茌t 且t 篮s ，则h ( v s , v t ) 2 e + 2 河北师范大学硕士学位论文 1 2 第三章d d i s j u n c t 矩阵的补阵的一些性质 本苹得到rf 面主要定理： 定理3 1 俨( n ，d ，n 1 ) 是胁一d ) 一d i s j 删矩阵一 证明因为5 ( n ，d ，) 的任意m 列的交有n m 个元素，因此这些列中有( ”i m ) 行 的元素都是1 ，所以在相应的补阵俨( 扎，d ，n 一1 ) 中对应于上面这些列存在( “i m ) 行的元 素都是0 ，因此有( ”乞一田) = 1 且( ”：“1 ) = 0 ，所以结论成立 例如； 酽( 5 ，2 ，4 ) = o ool l 0 0l0l o1o o1 1o oo1 oollo 01010 1o 010 o110 o l010o 110 oo 是个3 一d t 巧u n d 矩阵 推论3 2 对d z n 一1 ，酽( 仉d ，n 1 ) 是( n - f ，( 1 l 一- d 1 ) 一1 ) - - d i s j u n e t 矩阵 证明由命题5 直接可得 定理3 3 膏 n 一1 ，则萨( n ，d ，k ) 是1 一d i s j u n e t 矩阵 证明为得此结论我们只需证明存在一列可被其余两列的并所覆盖令c 又= i i ，如，i k 为选定的一列，因为k n - - 1 ，剥至少存在两个元素z ，f m 且以”薯c k ，所以我们有 坷北师范大学硕士学位论文 1 3 两列 g ，= i i ，i 2 ，故吨z ) c ，血= a l i 7 ， k 一1 ，g 显然在列c i 和c 五中元素都为0 的行在列c k 中元素也为0 ，因此0 。和c 幺覆盖列 g 。所以结论成立 例如； 酽( 5 ，2 ，3 ) = 是个1 一击可t i n c t 矩阵 oo ol 1lllll ol1001 1111 10i01011i1 ll010 01 111 ol11l10 011 1o1 l110101 11011110 01 1110110110 1l11o1l001 11111o110 0 定理3 4m c ( a ，d ，竹一1 ) 是( 住一d ) 一d i s j u n e t 矩阵 证明过程与定理3 1 类似，略 定理3 5 如果岛 n 一1 ，则m c ( a ，d ，k ) 是1 一d i s j u n c t 矩阵 证明类似于定理3 3 ，我们只需证明存在一列可被其余两列的并所覆盖令c k 为选 定的一列，由于m c ( z x ，盔k ) 的列是由k 一面标定的，所以不妨设c = i l ，如，i t ) ， 因为k n 一1 ，则至少存在两个元素z ，i n 且z ，簪c ，所以我们有另外两个七一面 所标定的列岛。，c 五，其中 g 1 = l ，2 ，i t , “z ， 河北师范大学硕士学位论文 1 4 = 0 l ， 2 ，i k 一1 ， ， 使得在列g ，和c k 中元素都为0 的行在列c k 中元素也为0 ，因此g ，和c 岛覆盖列 c k 所以结论成立 定理3 6 如果k ，| 一1 ，则r ( n ，d ，) 是1 一d i s j u n e t 矩阵 证明在r ( 凡，d ，女) 中，令c 名是个基为o t i ，d 2 ，o t k 的k 维子空间，即 = l ( a l ，嘞，o ) ， 注意到七 n 一1 ，于是至少存在曩“) 中的两个向量a ，卢，使得l ( n ，卢) + c 为个曩“ 中的七+ 2 维子空间，于是我们有两个子空间g ，c k ， 它们为 g l = l ( a l ，o t 2 ，o 一1 ，n ) c 幺= l ( a l ，q 2 ，n 一1 ，p ) 注意到q 。c 幺，于是在列q ，和g ，中元素为0 的行在列c 矗中元素也为o ，因此0 ， 和c k 覆盖列c k 所以结论成立 定理3 7 如果k n 一1 ，则俨( 口 n ，d ，k ) 是1 一d i a j u n c t 矩阵 证明在矿( 口，d ，砷中，令c k 是个长为t l 重为k 的g 一元向量，不妨设c 知= ( z i , 现，瓢，0 ，o ) ，因为k n 一1 则c k 中至少存在两个分量为0 ，因此我们有另 外两个长为n 重为k 的g 一元向量c 量，c k ，其中 g l 一( l ，沈，一l ，0 ，z ，0 ，o ) ， c 幺= ( z 1 ，x 2 ，100 ，0 ，) ， 河北师范大学明士学位论文 1 5 使得在列0 。和c 幺中元素都为0 的行在列g o 中元素也为0 ，因此0 ，和c 幺覆盖列 g o 所以结论成立 河北师范大学硕士学位论文 参考文献 【1 】d - z d u ，f k h w a n g ，c o m b i n a t o r i a lg r o u pt e s t m ga n di t sa p p l i c a t i o n s , w o r l ds c i e n t i f i c ，s i n g a p o r e ，1 9 9 3 【2 1d - z d u ，f k h w a n g ，c o m b i n a t o r a g r o u pt e s t i n ga n di t sa p p l i c a t i o n s , ( 2 a de d i t i o n ) ，w o r l ds c i e n t i f i c ：s i n g a p o r e ，2 0 0 0 【3 1w h k a u t z ，r r s i n g l e t o n ，n o n r a n d o mb i n a r ys u p e r i m p o s e dc o d e s ，i e e t r a n si n f o r m ，1 9 6 4 ，1 0 ：3 6 3 - 3 7 7 f 4 】d j b a l d i g ，w j b r u n o ，e k n i l l ，d c t o r n e y , ac o m p a r a t i v es t t r 唧 o fn o n - a d a p t i v ep o o l i n gd e s i g n s ，i ng e n e t i cm a p p i n ga n dd n a s e q u e n c i n g , ( m i n n e a p o l i s ，m n ，1 9 9 4 ) ，s p r i n g e r ，n e wy o r k ，1 9 9 6 ，p p ：1 3 3 - 1 5 4 嘲 w e i l iw u ，y a o c h n nh u n n g ，y i n g s h ul i ，d o r f m n n ，o ne r r o r - t o l e r a n td n a “g l i 蝎d i s c r e t ea p p l i e dm a t h e m a t i c s ，2 0 0 6 ，1 5 4 ：1 7 5 3 - 1 7 5 8 【6 】d 撕dc t o m e y , s e t sp o o l n gd e s i g n s , a n n a l so fc o m b i n a t o d c s ，s p r i n g e r - v e r l a g1 9 9 9 【7 】h u n gq n g o ，d i n g - z h ud u ，n e wc o n s t r u c t i o n so fn o n - a d a p t i v ea n de r r o r - t o l e r a n c ep o o l i n gd e s i g n s , d i s c r e t em a t h e m a t i c s ，2 0 0 2 ，2 4 3 ：1 6 1 1 7 0 i s h u n g - l i nf u ，f k h w a n g ，an o v e _ l u s eo lt - p a c k i n g st oc o n s t r u c td - d i s j n n c m a t r i c e s , d i s c r e t ea p p l i e dm a c h - e m a t i 2 0 0 6 1 5 4 ：1 7 5 9 - 1 7 6 2 【9 】f j m a c w i l l i a m s ，n j a s l o a n e , t h et h e o r yo fe r r o r - c o r r e c t i n gc o d e s , n o r t h - h 0 a n d ，a m s t e r d a m ，1 9 7 7 河北师范大学硕士学位论文 2 2 【1 0 1a j m 8 c 1 1 l a ，e r r o r - c o r r e c t i n gn o n a d a p t i v eg r o u pt e s t i n gw i t h 扩一d i s j u n c t m a t r i