基于Hash算法的DNA序列k-mer index问题的数学建模

针对查找DNA序列的相似序列问题,给出了建立索引和查找索引的数学模型,基于Hash算法,建立了依赖于k值大小的顺序索引模型和散列索引模型,特别对较大k值选用了DJBHash函数,有效的避免了Hash冲突问题。最后在硬件平台CPU为2.6GHz、内存为8G、操作系统为64位Windows 7的条件下,对100万条长度为100的DNA序列进行了测试,给出了不同k值下建立和查询索引的用时和占用内存情况,有效的解决了DNA序列的k-mer index问题。     

2n周期优秀二元序列生成及其特性分析简

The 2ⁿ-periodic binary sequence with high linear complexity and high k-error linear complexity is defined as an excellent sequence. We design a genetic algorithm for generating excellent sequences and studying their features. Choosing the N-periodic binary sequences, where N=8, 16, 32, k=N/4, we search the resulted sequences by the genetic algorithm with various parameters, and compute the linear complexity profiles of results sequences by using the Lauder-Paterson algorithm, to confirm that the obtained sequences are the real excellent sequences. By numerous experiments, we speculate that the k-error linear complexity of the N-periodic binary excellent sequence meets the formula LC_k(S)≤N-2k+1, when k=N/4、N/8 (we also do experiments on sequences with periods 64, 128 and 256). By the brute-force method we obtain that the proportion of the excellent sequence in all binary sequences of the same period is 1/4.     

单机带库存约束的排序问题

研究了一类单台机上带有库存约束的排序问题,目标函数是极小化加权完工时间总和。针对问题,首先证明了问题是NP-困难的,接着给出贪婪算法,证明了该算法的最坏情况界是无穷大,但随机试验表明算法的平均性能是令人满意的。     

面向交互应用的HEVC编码性能分析

结合现行的视频编码标准H.264/AVC,分析HEVC的具体编码技术,并对HEVC编码算法的编码效率和编码复杂度进行了对比研究。以交互应用视频序列为样本,对HEVC的具体性能进行测试,结果表明,在交互领域,和H.264/AVC相比,HEVC编码效率获得有大约50%的提升,编码复杂度也增加到了170%左右。     

FCSR序列非线性复杂度的研究

从Galois型非线性反馈移位寄存器（NFSR）的角度对带进位反馈移位寄存器（FCSR）进行了重新认识,证明了能够生成FCSR全体输出序列集合的Galois NFSR等价于同级的Fibonacci型NFSR,给出了FCSR全体输出序列集合的非线性复杂度,最后对其与同一FCSR生成的全体周期序列集合的非线性复杂度之间的差异进行了分析。     

大规模MIMO系统下的低复杂度迫零预编码技术

针对大规模天线技术导致传统迫零(zero-forcing, ZF)预编码复杂度上升的问题,提出了一种低复杂度预编码技术。首先利用对称超松弛迭代(semi-iteration symmetric successive overrelaxation method, SSOR)技术优化信道矩阵求逆复杂度的问题;然后利用切比雪夫半迭代法(semi-iteration, SI)加速SSOR迭代(semi-iteration symmetric successive overrelaxation method, SI-SSOR)的收敛速度,使得ZF预编码可以快速的收敛。实验结果表明,SI-SSOR预编码在误码率和传输速率上都有非常好的性能。切比雪夫半迭代法加速的SSOR预编码技术通过2次迭代就可以近似达到传统ZF预编码性能的95%以上,同时利用相对于迫零预编码更少的计算资源,因此,SI-SSOR预编码技术可以作为无线通信抑制干扰的重要手段。     

Continuous-time orbit problems are decidable in polynomial-time

We place the continuous-time orbit problem in P$\mathsf{P}$, sharpening the decidability result shown by Hainry [7].     

针对LBlock算法的踪迹驱动Cache攻击

LBlock是一种轻量级分组密码算法,其由于优秀的软硬件实现性能而备受关注。目前针对LBlock的安全性研究多侧重于抵御传统的数学攻击。缓存( Cache)攻击作为一种旁路攻击技术,已经被证实对密码算法的工程实现具有实际威胁,其中踪迹驱动Cache攻击分析所需样本少、分析效率高。为此,根据LBlock的算法结构及密钥输入特点,利用访问Cache过程中密码泄露的旁路信息,给出针对LBlock算法的踪迹驱动Cache攻击。分析结果表明,该攻击选择106个明文,经过约27.71次离线加密时间即可成功恢复LBlock的全部密钥。与LBlock侧信道立方攻击和具有Feistel结构的DES算法踪迹驱动Cache攻击相比,其攻击效果更明显。     

高效动态存储再分配方案与实现

为提高大小和数量都不确定的数据动态存储的空间利用率和处理速度,针对常规系统动态存储分配存在的问题,提出一种高效的动态存储再分配方案。通过减少系统动态存储分配的执行次数,在有效提高存储空间利用率的同时,提高存储空间动态分配的速度,给出动态存储再分配方案的具体实现算法,用实际数据对其性能进行测试。测试结果表明,该方案能节省36％至75％的系统存储空间,分配速度提高了20至50倍。