面向信息的组合学理论和方法

This project is devoted to investigating several forefront combinatorial topics which have deep interactions with information science. Aiming at data processing, we will investigate into compressed sensing for sampling signals, sequence designs in OCDMA, traffic grooming in networks, LDPC codes and code synchronization problems. For information security, we will study optimal frequency hopping sequences, digital fingerprinting, authentication codes with arbitration, and balanced nonlinear mappings in cryptography. We will describe meticulously the mathematical models used in these information applications and analyze thoroughly their combinatorial properties. Combining with the theory and methods in Algebra, Number theory, Finite geometries, Probability and Statistics, we plan to make great improvements in the specific problems as follows: construction and design of recovery algorithms for deterministic sensing matrices and structured random sensing matrices; embedding, construction and detection of digital fingerprinting; determination of maximal volume and effective constructions for optimal 3-dimensional optical orthogonal codes and optical orthogonal signature pattern codes; traffic C-grooming in unidirectional WDM rings with C≥7; existence of optimal A-codes with arbitration and strong partially balanced designs with strength t≥3; combinatorial and algebraic approaches for optimal frequency hopping sequences, LDPC codes and balanced nonlinear mappings.

本项目拟研究信息处理和信息安全中几类与组合学密切相关的前沿课题。在信息处理方面，拟研究信号采样中的压缩感知、基于光码分多址的序列编码、网络业务疏导、LDPC码以及信息传输的同步问题；在信息安全方面，拟研究跳频通信中的最优跳频序列、信息隐藏之数字指纹、带仲裁的认证码以及密码学中的平衡非线性映射。本项目拟更精确地刻画这些源于信息科学问题的数学模型，深入剖析其组合特性，结合代数、数论、有限几何和概率统计的理论方法，在以下具体问题上取得重要进展：确定性测量矩阵和结构化的随机测量矩阵的构造和恢复算法的设计；数字指纹的嵌入、构造与检测；最优三维光正交码、最优光正交签名码的容量确定与构造方法；单向波分复用网中比率C≥7的业务疏导问题；带仲裁的最优认证码及强度t≥3的强部分平衡设计的构造；最优跳频序列、LDPC码和平衡非线性映射的代数与组合学方法。

本项目的研究内容为信息处理和信息安全中几类与组合学密切相关的课题。在信息处理和信息安全的几个前沿问题上，本项目取得重要的研究成果，主要成果包括：1）构造两类具有循环性质的压缩感知矩阵；2）针对闪存编码，构造新的准完美码，证明奇数阶置换群上的蛇形码构造方案的可行性；3）确定权重为3并具有AM-OPP性质的最优三维光正交码所含码字个数的精确值，解决渐近最优光正交签名码的构造问题，在多长度光正交码的最优性判别和组合编制上取得重要进展；4）改进防诬陷码、父代识别码、追踪码和分离哈希族等数字指纹码的上界和下界；5）完全确定权重为4、码距为4的最优常重码的存在性，基本完全确定权重不超过4的最优多层常重码的存在谱；6）给出若干新码长的自对偶量子纠错码的无穷类，刻画t=2,3时量子跳跃码维数的上界及下界；7）编制一批新的最优的跳频序列和跳频序列集。另外，项目组在若干其它组合与编码问题上也取得重要的研究成果，包括：单向波分复用网业务疏导、带仲裁的最优认证码、多元循环常重码、完美分解集、集中式缓存方案、字符结对码与b-字符结对码、置换码、隐私保护信息检索相关编码、子空间码等。