论文部分内容阅读
伴随着以计算机科学为代表的第三次工业革命的爆发,古老的组合数学重新焕发青春,而编码理论更是现代计算机科学和数字通信技术的核心。组合数学、计算机理论和数字通信技术的研究对象都具有离散性质,三门学科之间存在着天然的联系。在本篇论文中,我们将从组合数学的视角出发考察编码理论中的几类问题,包括常用的最优线性纠错码,电力线通信中的非线性纠错码,以及用于多媒体防伪和信号压缩感知的信息编码等。 在论文的第一部分,我们将研究两类优良线性分组纠错码的组合构造方法。由于线性码具有高效的编码算法,是在实际生活中最为常用的编码。在第2章中,我们将展示利用差集的轨道矩阵来构造线性码码链的想法。这一方法是受到Ding等人从差集构造循环码以及Lander使用关联结构得到子模码等相关工作的启发而获得的。在这一章中,我们将从具有素数阶半正则自同构群的循环差集出发,研究其关联矩阵在同构作用下的轨道形成的分块阵列。利用阵列的Smith标准型中的不变因子序列分布情况,我们从轨道矩阵中选取适当的行空间序列构造线性码码链。很多例子都显示,这一构造方法得到的码链中包含了许多达到各种理论上界的最优线性码。 但遗憾的一点是,上述方法构造的线性码不一定保持循环性,因此其解码复杂度可能较高。为了克服这一缺点,我们将在第3章中研究一类可以通过信息传递等迭代算法快速译码的分组线性纠错码,即低密度奇偶校验码(LDPC码)。这是一类性能非常接近Shannon极限的好码,已经在当前各种最新的通信标准中占据主导地位。通过对基于循环群上的差矩阵内的元素进行二元矩阵散布,我们可以获得正则的拟循环低密度校验矩阵。与文献中从其它组合结构得到的码进行比较后发现,我们的方案在性能上与前人结果非常接近,但具有更大的灵活性,可以选择的参数更广。 第4章和第5章一起构成了论文的第二部分。我们将在其中讨论在电力线通信技术中具有重要应用的两类非线性分组纠错码,它们分别是置换码和常重复合码,其中后者可以看作是前者的推广形式。当然,这两类编码在其它领域也都具有广泛的应用。目前关于置换码的研究进展非常缓慢,事实上,我们只能构造出最小距离不超过3的最优置换码。而对于一般的距离条件,关于其码字个数的上下界估计都是极其困难的。在第4章里,我们通过将置换码对应到Cayley图上的顶点独立集,从而利用图论中的方法对码字数目的下界进行估计。在渐近意义下,即当码长n趋于无穷时,我们的结果将传统的Gilbert-Varshamov型下界提高了Ω(In(n))倍。 第5章中将探讨的常重复合码,可以看作置换码放松了每个字母只能在码字中出现一次这一条件后得到的推广形式;另一方面,它也可以被看作是传统的二元常重码的一类扩展。从二十世纪九十年代后期以来,人们才逐渐展开关于最优常重复合码的系统性研究。其中Chee等人于2008年确定出了重量为3时,所有长度和距离的最优三元常重复合码所含的码字个数。在这一章中,我们将延续前人的工作,利用可分组码以及各种组合设计中的递归方法,完全构造出重量为4且最小距离为5时,所有长度的最优三元常重复合码。 以上两个部分中研究的几类编码,都属于信道编码中的分组纠错码。而在论文的最后一部分,即第6章和第7章中,我们将把关注点转移到两类信息编码问题上。为了应对数字多媒体内容的盗版和篡改等问题,一种通行的方法是向这些内容中嵌入数字指纹。但普通的指纹只能追踪单个非法用户,而对于合谋犯罪无能为力。第6章所考虑的可分码就是在这一背景下由Cheng等人提出的,它可以用来抵抗合谋犯罪中最为常见的平均攻击模型。本章中研究了强度t=2时,可分码的上下界问题。我们利用坐标分组的想法,大幅改进了前人提出的上界。特别的,当可分码是一个线性码时,其上界可以被进一步降低,并且我们将利用正交表构造出了达到这一上界的线性可分码。另一方面,我们分别使用概率方法和Stein-Lovász定理,得到了可分码的一些下界结果。其中,在码长固定而字母表大小趋向无穷的这一渐近意义下,由前一方法得到的可分码的大小和我们改进后的上界具有相同的阶。 在第7章中,我们展示了使用代数曲线构造压缩感知矩阵的方法。压缩感知理论研究如何从极少次数的测量结果中恢复出原始的稀疏信号,这一过程也可以被理解成实数域上的信源编码问题。受到DeVore想法的启发,我们从有限域上的代数曲线出发,利用除子的Riemann-Roch空间内所有函数在曲线的一些有理点处的取值,构造出合适的二元感知矩阵。通过选取适当的参数,DeVore构造的矩阵也可以由我们的方法给出。数值模拟也显示,当矩阵规模较小时,我们的矩阵和已知最优的随机Gauss矩阵在信号恢复性能上相差不大。