（基础数学专业论文）小维数和小权数的mds码.pdf

摘要 如果码c 满足极小距离d = n k + 1 ，则称它为极大距离可分( m d s ) 码m d s 码是给定参数n ，k 之后纠错能力最强的码此外，它的重量分布 是完全确定了的假设c 为口元集合a = o ，1 ，2 ，口一1 ) 上码长为n ，维 数为k ，极小距离为d 的m d s 码，则它的任意k 个位置都可以作为信息位 m d s 码分为线性m d s 码和非线性m d s 码线性m d s 码的研究可以借助 于线性代数、有限域，有限几何和射影平面、线性码的相关知识等作为工 具，所以研究成果比较丰富非线性m d s 码只是一些码字的集合，没有系 统的研究方法，与线性m d s 码比较起来，其研究更为困难 我们用m 口( 七) 表示有限域f 口上g 元线性h ，k ，n k + 1 m d s 码的码长 n ，m j k ) 表示q 元集合a 上g 元非线性( n ，q 詹，扎一k + 1 ) m d s 码的码长n 显 然，m 口( 七) 鸩( 七) 研究( 七) 和仇。( 七) 所能达到的精确值以及它们所能 达到的上下界是m d s 码理论研究的重要问题之一 本文主要研究具有参数q ，k 的极大距离可分码的最大码长坂( 七) 通过 运用组合学的方法，结合码的h a m m i n g 距离，码的等价性，码的权重公式， 正交拉丁矩阵知识以及码的重量分布等概念，给出m j k ) 的一个新上界公 式m j k ) l ( q 一1 ，k ) + k + 1 ，特别的，我们得到蝎( 6 ) = 8 ，鸩( g ) = q + 1 ， 和m q ( 3 ) q + 1 ( q 为奇数) ，m j q 一1 ) q + 1 ( q 为奇数) ，坞( q 一1 ) q + 2 ( g 为偶数且口兰4 ( r o o d6 ) ) 关键词纠错码；m d s 码；h a m m i n g 距离；码的等价性；重量分 布；正交拉丁方阵；线性码；非线性码；码的界；鸽笼原理 a b s t r a c t c o d e sw i t hd = n k + 1a r ec a l l e dm 戚m u md i s t a n c es e p a r a b l ec o d e s ， o rm d sc o d e sf o rs h o r t f i x e dp a r a m e t e r sn ，k ，m d sc o d e sh a v et h em a 硒m 以 c o r r e c t i n ga b i l i t y , a n di t sw e i g h td i s t r i b u t i o ni sc o m p l e t e l yf i x e d i fac o d ec o v e rt h eq - a r ya l p h a b e ta 一 o ，1 ，2 ，口一1 ) i sa nm d sc o d eo fl e n g t hn ， d i m s i o n 七，a n dm i n i m u md i s t a n c ed ，t h e na n yks y m b o l so fc o d e w o r d sm a yb e t a k e na sm e s s a g es y m b o l s m d sc o d e sc a nb es e p a r a t e di n t ol i n e a rm d sc o d e s a n dn o n l i n e a rm d sc o d e s t h ei n v e s t i g a t i o no fl i n e a rm d sc o d e sc a nr e c u rt o t h ek n o w l e d g eo fl i n e a ra l g e b r a ，f i n i t ef i e l d s ，f i n i t eg e o m e t r i e s ，a n dp r o j e c t i v e p l a n e ，l i n e a rc o d e s ，a n ds oo n s oi t si n v e s t i g a t i o nn l a d em o r ea c h i e v e m e n t st h a n n o n l i n e a rm d sc o d e s t h en o n l i n e a rm d sc o d e sa r eo n l yas e to fs o m ec o d e s w i t hp a r a m e t e r sn ，q ，k ，a n dd = n 一七+ 1 ，a n dw i t h o u ts y s t e m i ci n v e s t i g a t i o n m e t h o d s s o ，i t si n v e s t i g a t i o ni sm o r ed i f f i c u l t yt h a nl i n e a rm d sc o d e s g e n e r a l l y , t h em a x i m a ln u m b e rn s u c ht h a tt h e r ee x i s t sal i n e a r 【n ，k ，n - k + 1 】m d sc o d eo v e rf 口w i l lb ed e n o t e db ym 口( i ) ，a n dm q ( k ) d e n o t et h em a x i m a l n u m b e rns u c ht h a tt h e r ee x i s t sa nn o n l i n e a r ( n ，矿，n k + 1 ) m d sc o d eo v e r q - a r ya l p h a b e ta c l e a r l y , m g ( 七) 毛( 七) o n eo ft h ep r o b l e m so nm d s c o d e s i st od e t e r m i n et h ee x a c tv a l u eo f 坞( 后) a n dm q ( k ) o rt oo b t a i nb o u n d sf o rt h e m i nt h i sp a p e r ，w es t u d yt h em a x i m a ll e n g t h 坞( 后) o fm d sc o d e sw i t ht h e p a r a m e t e rg ，k b yu s i n gt h ek n o w l e d g eo ft h ec o m b i n a t o r i c sm e t h o d s ，t h e h a m m i n gd i s t a n c eo fc o d e s ，t h ee q u i v a l e n c eo fc o d e s ，t h ew e i g h tf o m u a lo fm d s c o d e s ，m u t u a l l yo r t h o g o n a ll a t i ns q u a r e s ，a n dt h ew e i g h td i s t r i b u t i o no fm d s c o d e s ，a n ds oo n ，w eo b t a i na nn e wu p p e rb o u n df o r m u l ao f 坞( 七) i s 鸩( 七) l ( q 一1 ，七) + k + 1 ，e s p e c i a l l y , w eo b t a i nt h a t 鸩( 6 ) = 8 ，鸩( 口) = g + 1 ，a n d m d 3 ) g + 1 ( q i so d d ) ，m q ( q 一1 ) q + 1 ( gi so d d ) ，坞( 口一1 ) q + 2 ( qi s e v e na n dq 三4 ( r o o d6 ) ) k e yw o r d se r r o r - c o r r e c t i n gc o d e s ；m d sc o d e s ；h a m m i n gd i s - t a n c e ；c o d e se q u i v a l e n c e ；w e i g h td i s t r i b u t i o n ；m u t u a l l yo r t h o g o n a ll a t i ns q u a r e s ； l i n e a rc o d e s ；n o n l i n e a rc o d e s ；c o d e sb o u n d ；t h ep i g e o n h o l ep r i n c i p l e u 原创性声明 本人声明：所呈交的论文是本人在导师指导下进行的研究工作除了 文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过 的研究成果参与同一工作的其他同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示了谢意 签名：五德秀日期：。g i , 本论文使用授权说明 本人完全了解上海大学有关保留，使用学位论文的规定，即t 学校有权 保留论文及送交论文复印件，允许论文被查阅和借阅；学校可以公布论文 的全部或部分内容 ( 保密的论文在解密后应遵守此规定) 签名：王德、秀导师签名：槿逞羔日期：略- t 7 第一章引言 编码理论是一门年轻的学科，但是在军事、国防，通讯、经济等诸多领域 已有了广泛的应用美国数学家c e s h a n n o n 的论文。m a t h e m a t i c a lt h e o r yo f c o m m u n i c a t i o n 。( 1 9 4 8 ) 开创了一门在现代科学技术中具有重大意义的崭新 学科，即信息论编码理论是信息论的一个专门分支汉明( r w h a m m i n g ) 在1 9 5 0 年发表的论文。检错码和纠错码”是开拓编码理论研究的第一篇论 文目前我们研究的主要是纠错编码理论，纠错码是提高信息传输可靠性 的一种重要手段在纠错码理论中码的纠错能力和检错能力与h a m m i n g 距离的概念密切相关，码的h a m m i n g 距离越大，则码的纠错能力越强由 码的s i n g l e t o n 界知，如果存在g 元码( n ，m ，d ) ，1 d ，l l ，则m q n - d + 1 特别的，如果m = q 七，则有d n 一七+ 1 如果有d = n k + 1 ，则这个码的纠 错能力最大我们把达到这个界的码称为m d s ( m a x i m u md i s t a n c es e p a r a b l e ) 码( 极大距离可分码) m d s 码之所以重要，在于它是在给定n ，k 之后纠错能 力最强的码此外，它的优点是，重量分布是完全确立了的，若( n ，m ，d ) 码 为m d s 码，则它的任意k 个位置都可以作为信息位m d s 码的码字可以 分为信息位和校验位，这就是可分码的由来由于码的生成空间的不同， m d s 码分为线性m d s 码和非线性m d s 码，关于线性m d s 码的研究成果 目前已经有很多，我们重点研究小维数和小权数上的非线性m d s 码的性 质本文运用较为简单的组合学的方法，结合码的h a m m i n g 距离，码的等 价性，码的权重公式，正交拉丁矩阵以及码的重量分布等概念，给出非线性 m d s 码在参数g ，k 确定的情况下，它能取到的最大码长 1 1 m d s 码问题的简介与研究现状 1 1 1m d s 码问题的来源 1 9 4 8 年s h a n n o n 发表i 通信的数学理论 一文，奠定了通信的数学 基础一信息论和通信的可靠性理论具体的通信方式可以是多种多样的 1 2 0 0 8 上海大学硕士学位论文 2 ( 打电话传送电子邮件，宇宙飞船将金星图片传回地球邮差传送信件 和公文，) ，它们的抽象的数学模型可以表示成以下最基本的形式t 弘曼l 二圈 i 发矧一一i 收瑚 要发送的原始信息可以有不同形式( 声音。文字、图像、数据、) 利用 各种物理技术手段，把原始信息统一编成离散的脉冲电信号发出，脉冲信号 只有有限多个状态，假设有m 个状态( m 2 ) ，可以表示成0 ，1 ，2 ，m 一1 ， 并且将集合 o ，1 ，m l 按模m 做加减乘运算，即状态集合是模m 同 余类环也可把状态集合取成有限域b ，其中口= p l ( p 为素数，j 1 ) ， 这时还可做除法运算事实上，数字通信中最常用的脉冲信号只有两个状 态，即最常用的是二元域f 2 = o ，1 ) ( 1 + 1 = o ) 关于有限域的内容见【1 】 以叼表示f 口上的n 维向量空间，其中q n 个不同向量( c o ，c l ，一1 ) 瓴 f ) 可以表示矿个不同的信息，比如f ；中有8 个向量，可表示0 ，1 ，7 这 8 个信息s 0 = ( o o o ) ，1 = ( 1 0 0 ) ，2 = ( 0 1 0 ) ，3 = ( 1 1 0 ) ， 4 = ( 0 0 1 ) ，5 = ( 1 0 1 ) ，6 = ( 0 1 1 ) ，7 = ( 1 1 1 ) 假设发方把数字3 传给对方，即把码字( 1 1 0 ) 传出去事实上，在传送信息 的过程中，如果信道( 电话线，大气层，) 受到干扰( 或发生设备故障) ， 则会使发送的信息( 1 1 0 ) 的某位出错，比如第3 位由0 变成1 ，则收方得到 ( 1 1 1 ) 由于( 1 1 1 ) 也代表信息( 数字7 ) ，收方无法发现传送的错误，即无法判 定发来得就是7 ( 无错) ，还是发来其他数字错成了7 这表明，通信系统完全 没有检查错误和纠正错误的能力如何使通信系统具有纠错能力，这需要 将信息进行一次纠错编码目前最简单的两个检错和纠错方式为奇偶校验 码和重复码，这也是通信系统最早采用的检错和纠错方式将通信系统加 上纠错功能之后，数学模型便成为如下形式， 匝f 吨多笪薹型硇二匝fi 发方卜一一纠错编硎一一l 纠错译码| 一l 收方卜一 发方将信息z 嗡编成有纠错能力的码字c 叼，传给收方的过程中信 道出现错误e 睇( e 叫错误向量) ，从而收方得到t ，= c + e 收方进行纠错， 恢复成正确的码字c ，然后得到信息氖 2 0 0 8 上海大学硕士学位论文 3 目前，利用纠错码降低各类数字通信系统以及计算机存贮和运算系统 中的误码率，提高通信质量，延长计算机无故障运行时间等，在美国等西方 国家中已作为一门标准技术而广泛采用丽且纠错码技术还应用于超大规 模集成电路设计中，以提高集成电路芯片的成品率，降低芯片的成本不仅 如此，自7 0 年代末以来，纠错码技术已开始渗透到很多领域因此，可以 预料，随着科学的进步和实际的需要，纠错码理论必将进一步发展，它的应 用范围必将进一步扩大 我们以口个符号的集a 作为字母表假设q 已取定，则一个( n ，d ) 码 是指一个长为几，极小距离为d 的码我们对码字的最大数目( 即能放在 处的最大m ) 感兴趣 对于码的研究，主要是对码的参数进行讨论码的参数主要包括；码长 n ，码所能达到的码的数目上下界m ，码的极小距离d 和极小重量u 等码 的数目制约这一个码所能传递的信息的容量，而码的极小距离与码的纠错 和检错能力有很大的关系因此对于码字数目的上下界的估计以及码的极 小重量和极小距离的讨论，引起许多学者的兴趣，也取得了较多的成果 一个好的口元( n ，m ，d ) 码应具有如下性质； ( 1 ) 为了更快的发送信息，码长n 应该小； ( 2 ) 为了更多的发送信息，码字个数m 应该大； ( 3 ) 为了能纠正更多的错误，最小距离d 应该大 事实上，这些条件是互相矛盾的对于n ，m ，d 这三个参数，固定其中的两 个。而使另外一个达到最优的问题称之为编码理论的基本问题( n ，m ，d ) 的 参数之间应当满足一些不等式，叫做纠错码的各种界，达到这些界的码就是 性能最好的纠错码其中，能够达到s i n g l e t o n 界( 1 2 2 ) 的码满足d n - k + l ， 当d = n 一良+ 1 时，我们就说q 元码( n ，m ，d ) 为m d s 码 m a c w i l l i a r n sf j a n ds l o a n en j a 曾经说m d s 码理论是纠错码理 论中最有魅力的一节内容【2 】在纠错码理论中，码的纠错能力和检错能力 与h a m m i n g 距离的概念密切相关，码的h a m m i n g 距离越大，则码的纠错能 力越强由码的s i n g l e t o n 界知，如果存在q 元码( n ，m ，d ) ，l d n 一1 ，则 m q n d + 1 ，特别的，如果m = 矿，则有d ，l 一七+ 1 如果有d = t t 一七十1 ，则 这个码的纠错能力最大我们把达到这个界的码称为m d s ( m a x i m a ld i s t a n c e s e p a r a b l e ) 码( 极大距离可分码) 2 0 0 8 上海大学硕士学位论文 4 m d s 码之所以重要，在于它是在给定竹，k 之后纠错能力最强的码此 外，它的优点是，重量分布是完全确立了的，若( n ，m ，d ) 码为m d s 码，则 它的任意k 个位置都可以作为信息位m d s 码的码字可以分为信息位和校 验位，这就是可分码的由来由于码的生成空间的不同，m d s 码分为线性 m d s 码和非线性m d s 码，关于线性m d s 码的研究成果目前已经有很多， 我们重点研究小维数和小权数的非线性m d s 码的性质本文运用较为简单 的组合学的方法，结合码的h a m m i n g 距离，码的等价性，码的权重公式， 正交拉丁矩阵以及码的重量分布等概念，给出非线性的m d s 码在参数q ，k 确定的情况下，它能取到的最大码长 1 1 2 研究现状与研究方法 m d s 理论是一门涉及代数编码理论、纠错码理论、组合设计、密码学、 仿射几何、有限群，代数几何的交叉热点学科 由于码的生成空间的不同，m d s 码分为线性m d s 码和非线性m d s 码，线性m d s 码的研究可以借助于线性代数、有限域、有限几何和射影平 面，线性码的相关知识等作为工具，所以研究成果比较丰富非线性m d s 码只是一些码字的集合，没有系统的研究方法，与线性m d s 码比较起来， 其研究更为困难 目前关于非线性m d s 码的研究成果很少下面我们对国际国内已有研 究成果给出综述 对于任意一个具有参数( n ，q 七，n k + 1 ) 的非线性m d s 码，( k 2 ) 在1 9 4 9 年，b r u c kr h 和r y s e rh j 【3 】共同发现，当q 三l ( m o d4 ) 或2 ( m o d4 ) 且口的无平方因子可以被形如4 t + 3 的素数整除时，具有参数 ( g + k 一1 ，矿，q ) 的m d s 码是不存在的( 1 1 1 ) 之后，s i l v e r m a nr 【4 】于1 9 6 0 年应用组合分析的方法给出了下列结果 的证明。 当q 为奇数时，具有参数( q + k 一1 ，矿，q ) 的m d s 码是不存在的( 1 1 2 ) 当存在一个素数p 使p 2 时，如果具有参数( 口+ k 一1 ，矿，q ) 的m d s 码存在，则 4 1 q ( 1 1 4 ) 当k 3 ，q 2 时，如果具有参数( g + k 一1 ，矿，q ) 的m d s 码存在，则 3 6 1 q ( 1 1 5 ) 上述结果的给出。大多是运用了有限射影平面和组合学的知识进行理 论推导而得出的在运用上述知识证明的过程中，推导相对复杂我们思 考，能不能用相对简单的组合学的方法来证明新的m d s 码的上界呢? m d s 码的性质与码字之间的h a m m i n g 距离有着密切的联系1 9 9 4 年， 由万哲先等数学家【6 】，运用组合学的知识结合码字的h a m m i n g 距离，对任 意字母表a 上的m d s 码给出了如下一系列的性质定理： ( 1 ) 在任意的字母表a 上，都不存在“a | + k ，k ，i a l + 1 ) m d s 码 ( 2 ) 当口为素数的幂时，有 特别的，当k = 2 时，有 m ( k ，q ) q + k 一1 m ( 2 ，g ) = m ( 2 ，q ) = q + 1 ( 3 ) 假设q 为一个素数的幂；当口为偶数时，有 当q 为奇数时，有 m ( 3 ，q ) = m ( 3 ，q ) = q + 2 m ( 3 ，q ) = q + 1 ，口+ 1 u ( 3 ，口) q + 2 在上述结论之后，作者继续运用m d s 码的极小h a m m i n g 距离和简单的组 合学知识，证明出在任意基数为3 的字母表a 上都不存在( 5 ，3 s ，3 ) m d s 码 由文章 6 】中定理5 的证明过程，我们可以看到一种新的证明m d s 码 码长上界的方法，但这种方法也有它的局限性，我们经过推导可以得出这 种方法只适用于q 4 时( 口十2 ，9 3 ，口) ( q 为奇数) m d s 码的存在情况就需要考虑使用新 的方法来给予证明 2 0 0 8 上海大学硕士学位论文 6 另外，对于小权数的非线性m d s 码的研究成果，目前给出的很少本 文我们在这一领域也做了一定的工作 1 2 本文主要工作 本文主要做了三方面的工作 一第3 2 中主要通过建立码的等价性，两两正交的拉丁矩阵与m d s 码之间的联系，给出了m d s 码的一个新上界公式和相关推论 ( 1 ) 假设c 为具有参数( n ，矿，n 一七+ 1 ) 的m d s 码( 七sq 一1 ) ，则 佗l ( q 一1 ，七) + k + 1( 1 2 1 ) 这里l ( q 一1 ，七) 为( g 一1 ) k 阶两两正交的拉丁矩阵的最大个数 ( 2 ) 假设c 为具有参数( 9 ，7 6 ，4 ) 的m d s 码，则由( 1 1 2 ) 的结论知， 尬( 6 ) 8 即( 9 ，7 6 ，4 ) m d s 码不存在又因为7 是素数，所以有( 6 ) = 8 ( 3 ) 假设c 为具有参数( g + 2 ，n3 ) 的m d s 码，则通过和( 1 1 2 ) 的证 明过程类似的方法，我们可以得出不存在( 口+ 2 ，口口，3 ) 的m d s 码因此有 坞( g ) q + 1 又因为对任意g ，( g 2 ) ，存在参数为( 口+ 1 ，口口，2 ) 的m d s 码， 即可得到鸩( g ) = q + 1 二在3 3 中，作者通过一种较为简单的方法，通过对小维数上m d s 码 的权重公式的应用，结合码的h a m m i n g 距离，给出了( 1 1 2 ) 中当七= 3 时 ( 口+ 2 ，q 3 ，q ) m d s 码不存在的简单证明即( 3 ) q + 1 ( q 为奇数) 三第3 4 和3 5 中通过对m d s 码的重量分割，鸽笼原理，码的等价 性，码字的h a m m i n g 距离以及m d s 码的权重公式和重量分布原理的应用， 给出了如下小权数上m d s 码的新上界公式 ( 1 ) 坞( 口一1 ) q + 1 ( 口为奇数) ( 2 ) 鸩( 口一1 ) 5q + 2 ( q 为偶数且q 三4 ( r o o d6 ) ) 2 0 0 8 上海大学硕士学位论文 7 第二章m d s 码理论的预备知识 这一章我们首先给出关于经典纠错码理论的基本知识和简介然后对 线性m d s 码以及非线性m d s 码的性质和研究情况给出介绍，并列举例子 最后对目前m d s 码方向主要的研究问题给出陈述并对本文的符号进行说 明 2 1 经典的纠错码理论简介 编码理论仍然是一门年轻的学科它导源于现代通信技术与电子计算 机技术中差错控制研究的实际需要美国数学家仙农( c e s h a n n o n ) 在 1 9 4 8 年发表的著名论文。通信的数学理论。开刨了一门在现代科学技术中 具有重大意义的崭新学科，即信息论编码理论是信息论的一个专门分支 汉明( r w h a m m i n g ) 在1 9 5 0 年发表的论文。检错码与纠错码是开 拓编码理论研究的第一篇论文以后，纠错码受到了越来越多的通信和教学 工作者，特别是代数学家的重视，使纠错码无论在理论还是在实际中都得 到飞速发展 5 0 年代至8 0 年代，是纠错码理论飞速发展的重要时期，并在实用中也 取得了巨大成功如美国在7 0 年代初发射的。旅行者。号飞船中，成功的 应用了纠错码技术，使宇宙飞船在极其遥远的距离( 3 0 亿公里) 。向地面传 回了天王星，海王星等星体的天文图片发现了天王星的9 个卫星和光环 以及海王星的6 个卫星和光环等许多极其宝贵的资料若不应用纠错码， 这些成就的取得是不可想象的 自8 0 年代初以来，戈帕等从几何观点讨论分析码，利用代数曲线构造 了一类代数几何码在这些码中，某些码的性能达到了香农码所能达到的性 能由于代数几何码是一类范围非常广的码，在理论上已证明它具有优越 的性能，因而一开始就受到了编码理论工作者，特别是代数几何学家的重 视，使代数几何码的研究得到了非常迅速的发展，取得了许多成果现在， 代数几何码的研究方兴未艾 2 0 0 8 上海大学硕士学位论文 8 目前，利用纠错码降低各类数字通信系统以及计算机存贮和运算系统 中的误码率，提高通信质量，延长计算机无故障运行时间等，在美国等西方 国家中已作为一门标准技术而广泛采用而且纠错码技术还应用于超大规 模集成电路设计中，以提高集成电路芯片的成品率，降低芯片的成本不仅 如此，自7 0 年代末以来，纠错码技术已开始渗透到很多领域因此，可以 预料，随着科学的进步和实际的需要，纠错码理论必将进一步发展，它的应 用范围必将进一步扩大 下面我们给出编码理论中的一些基本概念设a 为g 元集合，信息流 m = r o o m l 仇2 a ，将信息流m 依次分成若干组，每组k 个比特，然后采 用某个编码规则，对每组进行编码编码的目的是使传送的信息能够抵抗 信道的干扰，收到者能正确译码 定义2 1 1 【7 】记a n = 【( 勋，z i ，z n ) l 龟a ，i = 1 ，2 ，仡) ，对任意 z ，y a n ，称 d ，y ) = i i l l i n ，戤鼽) i 为z 与可之间的h a m m i n g 距离，称 u ( z ) = i i l l i n ，戤o ) i 为z 的h a m m i n g 重量( 权) h a m m i n g 距离满足通常距离的基本性质：非负性，对称性和三角不等 式性 定义2 1 2 【7 】a n 的每个非空子集c 叫做a 上一个码，小中元素叫 做字，c 中元素叫做码字，n 称为码字的长度，简称码长 如果i c i = 1 ，则称c 为平凡码，否则称c 为非平凡码假定c 为非平 凡码，记 r ：l o g 口i c l ：，l 一1l 。岛f c i d = m i n d ( x ，y ) l x ，秒c ，z 3 ，) t o = m i n w ( x ) l x a z o p 2 够 d ( z ，c ) l x 个，c c ) zc 则称r ，d ，伽和p 分别为码c 的码率，极小距离，极小权重和覆盖半径 2 0 0 8 上海大学硕士学位论文 9 定理2 1 3 1 7 如果码c 的极小距离为d ，则c 可以检测sd 1 个随机 错误。可以纠正【掣】个随机错误 每个数学分支都有主要的研究对象，研究这些对象的基本性质，并且研 究基本对象的分类的问题，要求同一类的对象具有相同的基本性质在纠错 码理论中，对于固定的口元集合a ，我们也把所有g 元纠错码加以分类，使 得同一类中的纠错码有相同参数n ，m ，d 最容易想出的是以下三类变换【7 】 ( 1 ) 分量置换设c 是口元码( f , ，m ，d ) ，对于集合 0 ，1 ，2 ，n 一1 ) 的每 个置换盯，我们把c 中每个码字c = ( c 1 ，c 2 ，) 变成 仃( c ) = ( c a ( 1 ) ，白( 2 ) ，( n ) ) a n 即把码字c 的各分量作置换口，新的集合 仃( c ) = 盯( c ) i c c ) 给出具有相同参数( n ，m ，d ) 的口元码 ( 2 ) 元素置换设，是集合a 到a 的一一映射中口个元素的一个 置换) ，f ( 0 ) = 0 于是每个码c 小，将码字c = ( c 1 ，c 2 ，c n ) c 变成 f ( c ) = ( ，( c 1 ) ，( ) ) a n ，易知新的码 f ( c ) = f ( c ) l c c ) 与c 具有相同的参数n ，m ，d ( 3 ) 码的平移设c 小，对每个勘a “，新的码 = c + t ，= c + v l c c 与c 具有相同的参数n ，m ，d 定义2 1 4 1 7 设c 和是两个g 元码，如果通过有限次上述三种变换 把c 变成，称c 和是等价的码 一个g 元( n ，m ) 码可以排成一个mxn 阶矩阵，其每一行是一个码 字以后我们经常会用这种矩阵的形式来表示一个g 元( n ，m ) 码第( 1 ) 种 变换对应于将矩阵中的列进行重新排列；第( 2 ) 种变换对应于将矩阵中某 一固定列中的字符进行置换不难看出，在上述三种置换运算下，码字之 间的h a m m i n g 距离保持不变因此，两个等价的码c 和有相同的参数 ( n ，m ，d ) ，它们可以检查和纠正相同数目的错误 2 0 0 8 上海大学硕士学位论文 1 0 定理2 1 5 任意一个口元( n ，m ，d ) 码等价于一个包含零码字掣的 q 元( 几，m ，d ) 码 对于码的研究，主要是对码的参数进行讨论码的参数主要包括：码长 n ，码所能达到的码的数目上下界m ，码的极小距离d 和极小重量u 等事 实上，( n ，m ，d ) 的参数之间应当满足一些不等式，叫做纠错码的各种界， 达到这些界的码就是性能最好的纠错码 定理2 1 6 ( h a m m i n g ) 界【2 】如果存在纠错码( n ，m ，回，则 q n m 萎i - - - - - 0c q 一，( ：) 矿 ( q 一1 ) 叫! l l 这里( ：) 是组合数 个物体中取t 个的方法数卜其中 = 攀掣= 鼎 注1 ：由于定理的证明和线性没有关系，所以h a m m i n g 界同样适用于非 线性码 定义2 1 7 【2 】设c 为q 元码( n ，m ，2 1 + 1 ) 如果 卜m 扣玎 矿= m ( 口一1 ) i l7 1l = 0、 i 则称c 为完全码 完全码是一类好的纠错码几何上，如果c 是上述参数的g 元完全码， 则m 个球岛( c ，z ) ( c c ) 恰好填满整个空间叼 例1 考虑由以下1 6 个码字构成的二元码( 码长n = 7 ，m = 1 6 ) 2 0 0 8 上海大学硕士学位论文 l l 0 0101ll 1o ol0l1 110o101 1110 0l0 0l1l00l l01110 o 010111o 0 0 0 0 0 0 0 llo10 00 011010 0 0011010 0001 10l 10o01 l0 0l00 0l1 101o 0 0l 11111 11 这是( 0 0 1 0 1 1 1 ) 循环移位给出的7 个码字，与( 1 1 0 1 0 0 0 ) 循环移位给出的7 个 码字，再加上( 0 0 0 0 0 0 0 ) 和( 1 1 1 1 1 1 1 ) 可直接验证此码的极小距离为3 ，即为二元码( 7 ，1 6 ，3 ) 因为 口n = 2 7 = 2 8 ，m ：= 。c 口一，( ：) = 6 ：。( ：) = 6 c l + 7 ，= 2 8 ， 所以二元码( 7 ，1 6 ，3 ) 是完全码 定理2 1 8 ( s i n g l e t o n 界) 2 】如果存在q 元( n ，m ，d ) 码，1 d n 一1 ， 则 m q n - d + 1 定义2 1 9 【2 】设c 是g 元( n ，m ，d ) 码，如果m = q n - d + l ( 即n = k + d - 1 ) 当d = n 一七+ 1 时，则c l l 做极大距离可分码，简称为m d s ( m a x i m a ld i s t a n c e s e p a r a b l e ) 码 关于m d s 码的概念和性质，我们将在2 5 和2 6 节给出详细介绍 下面由p l o t k i n 给出的界只对二元码有效 定理2 1 1 0 ( 二元码的p l o t k i n 界) 2 j 如果存在参数为( n ，m ，回的二元 码，并且2 d n ，则 m ( n ：1 ) 国一l ，+ ( n 一21 ) 。一1 ，2 + + n - - 1 ) c 口一1 ，d 一2 的最小整数，则一定可以构造出一个长为n ，极小距离为d 的h ，k ，d 】的线性 码 p l o t k i n 限和h a m m i n g 限都是构成码的必要条件，任何码都必须满足此 必要条件，越接近它就越有效，等于它时就达到最佳而v - g 限是充分条 件，并限定于线性码，满足这一条件必存在一个极小距离为d 的融，七，司的 线性码但是。当n _ o o 时，满足v - g 限的线性码目前仅找到两类：某些 代数几何码和j u s t e s e n 码有些码类，如【2 m ，仇】二进制准循环码，码字重 量为4 m 的线性二进制自对偶码，已证明接近v - g 限，但遗憾的是直到目前 还未找到具体的构造方法 2 2 线性码的基本概念和性质 为了应用上的实现，一个好的纠错码还必须易于编码及解码通常我 们会要求码具有一定的代数结构，例如要求码c 是赡的线性子空间，即所 谓的线性码此时码的势就由它的维数k 决定，我们通常用h ，k ，司表示一 个长度为n 维数为k ，极小h a m m i n g 距离为d 的线性码线性码一直是经典 纠错码理论研究的重点对于线性码的研究，我们可以借助线性代数作为工 具，为构造好码和好的译码算法带来很多益处 经典的纠错码理论通常研究的是有限域上的编码，特别是在二元域上， 令峨是含有g 个元素的有限域，叼是n 元向量空间叼中的任一子集 c 就是一个编码，其中c 的元素称为码元，而蝣中的向量称为字 定义2 2 1 1 8 设f 口为g 元有限域，叼的线性子空间叫做口元线性分 组码，简称口元线性码如果d i mc = 七，则称c 为f 口上h ，k 】线性码 2 0 0 8 上海大学硕士学位论文 1 3 如果c 为r 上融，叫线性码，则r = 垦磐= n - il o 岛l 矿i = ；k ，c e i l d = m i n d ( x ，秒) l z ，可c ，z ) = m i n d ( ：r , 一夥，o ) l x ，矽g z y o = m i n w ( z ) l x c ，z o = t t ， 这表明线性码的码率等于码长除以信息位的数目，线性码的极小距离等于 最小重量一般而言，如果c 为线性码，则记为h ，k ，d 】码，这里n 为码长， k 为维数，d 为极小距离；如果c 为非线性码，则记为( n ，m ，d ) ，这里n 为码 长，m 为码字数日，d 为极小距离 注2 ：本文中，我们用h ，七，d 】表示极小距离为d ，长为n 的k 维线性码 ( 亿，m ，d ) 表示任何极小距离为d ，长为n 且含m 个码字的码 注3 ：若i c i = 1 ，我们就说这个码是平凡的若g = 2 ，码称为二元码， g = 3 ，则称为三元码，等等 注4 ：无特殊说明，下面我们讨论的都是非平凡码 对于线性码而言，码c 就是叼的线性子空间一般情况下，任何一个 k ，七，明码的一致校验矩阵日可表示为 日：悔, n - - 1 葛一, n - - 2 2 l n i 。n 一1 ，l n 一七，n 一2 h i ，0 h 2 ，0 k 吨0 它是一个加一k ) xn 阶矩阵由此日矩阵可以很快的建立码的线性方程组： 简写为 或 h i n 一2 k 。一2 l n 一七n 一2 ，l h l , o = 酽 h 伊：0 t 。 c h t ；0 ( 2 2 1 ) ( 2 2 2 ) l t _ 矿 扩 一 协 h k 铲 允 ，-lii-一 2 0 0 8 上海大学硕士学位论文 1 4 可知日矩阵的每一行代表一个线性方程组的系数，它表示求一个校验元线 性方程因此任何一个h ，七，d 】码的日矩阵必须有n 一七行，且每行必须线 性独立若把日的每一行看成一个矢量，则这n 一七个矢量必然张成了，l 维 线性空间中的一个n 一七维子空间k m 由于p l ，七，d 】码的每一个码字必须满足( 2 2 1 ) 式，即它的每一个码字必 然在由日的行所张成的k 。n 一七空间中的零空问中显然k n 一七的零空间必 然是一个七维子空间k ，七，而这正是h ，七，明码的码字集合全体所以，k 加七 与k ，七，司码的每一个码字均正交，也就是日矩阵的每一行与它的每一个 码字的内积均为零 【礼，k ，d 】码的码字组成一个k 维子空间，因此这个码字完全可以由七个 独立矢量所组成的基底而张成设基底为 睦兰曩 f 9 1 扩 g ：i 一 l i l9 k ? 刀一 9 1 ，l 一2 9 2 n 一2 鲰7 1 一2引 k ，七，d 】码中的任何码字，都可由这些基底的线性组合生成，即 c=m。g=【竹hq，吨，一七，c三三三 9 1 n 一2 9 2 ，n 一2 鲰n 一2 g l 。o 9 2 。0 g k ，0 式中，1 7 1 , = 【弛一1 ，m 矗一2 ，m 住一d 是七个信息元组成的信息组因此，若已 知信息组1 7 t ，通过上式可求得相应的码字，称上式的g 为【n ，七，d 】码的生成 矩阵 2 0 0 8 上海大学硕士学位论文 1 5 例如，h a m m i n g 7 ，3 ，4 】码，可以从它的8 个码字中任意挑出七= 3 个线 性无关的码字t ( 1 0 0 1 1 1 0 ) ，( 0 1 0 0 1 1 1 ) ，( 0 0 1 1 1 0 1 ) 作为码的生成矩阵的行，则 1 0 0 i g = 1010 l 0 01 、 111 o 、 0111 l i 11017 ( 。11 ) 1 00 1110 = ( 。111 。1 。) 2 0 0 8 上海大学硕士学位论文 1 6 例如，h a m m i n g 码【7 ，4 ，3 】码，它的对偶码必是【7 ，3 ，4 】码，其生成矩阵 g 7 ，4 1 就是【7 ，3 ，4 】码的校验矩阵q 7 3 】 g r ，4 1 = h t 7 ，3 】= 011000j l 11010 0l i 10 0 010l i 110 00 1 肚卜一 2 3 几类常见的线性码 线性码是纠错码理论中重要的组成部分下面我们介绍几种重要的线 性码 h a m m i n g 码：设礼= 告m 为k 维射影空间p g ( 七一1 ，g ) 中不同点数) ， 如果矩阵h 由n 个f 口上两两线性无关的k 维列向量( p c ( k - 1 ，q ) 中n 个不 2 0 0 8 上海大学硕士学位论文 1 7 同点作为列向量) 组成，则以日为校验矩阵的线性码称为h ，n k h a i n m i n g 码 循环码；一个i n ，k ，硼线性码c ，若它的任一码字的循环移位仍然是c 的码字。则称该码为循环码 b c h 码：f 口上码长为n 的循环码叫做设计距离为d 的b c h 码是指 该码的生成多项式是，+ 1 ，+ d - 2 ( 对某个z ) 的极小多项式的最小公倍 式，这里卢是f 口的某个扩域中的n 次本原单位根 如果l = 1 ，则称相应的b c h 码为狭义b c h 码，如果p 为f 口m 的本原 元，即n = q m 一1 ，则称b c h 码为本原b c h 码设计距离为d 的b c h 码可 描述为； c = c ( z ) i c ( z ) f 口i x ( 矿一1 ) ，c ( 岛) = 0 ，f j 2 + d 一2 ) 由 8 】可知，设计距离为d 的b c h 码的极小距离至少为d r e e d - s o l o m o n 码；f 口上码长为竹= g 一1 ，设计距离为d 的本原b c h 码叫做r e e d - s o l o m