基于Grbner基的对称正交多带多维滤波器组设计

通过引入计算代数中Gr bner基技术和合冲模算法,提出了一种多带多维滤波器组的多相元矩阵的对称正交化设计方法,给出了一个4带二维对称正交滤波器组的设计算例;另外,给出了由多维滤波器组构造多维小波的多维尺度方程表示形式,并将设计得到的4带二维滤波器组构造出一种4带二维小波。

图的k-独立集与Grbner基求解

本文给出一种求解任一具有n个顶点的有限图G的极大独立集和独立数的代数计算方法.该方法是通过将求解G的极大独立集问题加强为对每个1≤k≤n求解G的k-独立集问题来给出的.首先证明了G中k-独立集的存在性等价于一个多元多项式方程组的解的存在性,使得可以通过使用多项式理想的Grbner来判断所得方程组解的存在性并进一步求解方程组.由于k-独立集存在时只有有限多个,得到的Grbner基构成的方程组是很容易求解的三角形方程组,G的极大独立集和独立数在求解最多n个方程组即可得到.最后,通过实例验证了代数计算方法的有效性.

NGP并联机构运动学正解的高效通用解析方法

研究了NGP(nearly general stewart-gough platform)并联机构动平台位置与姿态变量之间的耦合关系,将9个变量中的6个用其余的3个表达出来,从而实现了位置变量和姿态变量的解耦.运用Gr bner基算法,得到了15个只含有其余3个变量的4次相容方程.在此基础上,采用变量代换的方法消去其中的高次项,最终将NGP并联机构的运动学正解问题简化为求解一个一元20次的代数方程;这个方程是通过计算一个10阶行列式得出的,并且通过一个具体的算例验证了该方法的正确性.该方法适用于所有的NGP并联机构.

对Bivium流密码的变元猜测代数攻击

非线性方程组的求解是代数攻击的关键一环.对于一个具体的密码系统,在转化为方程组后,由于其计算上的复杂性,一般采用先猜测部分变元,再进行求解分析的方法.本文首先给出了对于猜测部分变元后子系统平均求解时间的估计模型,提出了基于动态权值以及静态权值的猜测变元选则方法和面向寄存器的猜测方法.在计算Gr bner基的过程中,对变元序的定义采用了AB,S,S-rev,SM,DM等十种新的序.同时,提出了矛盾等式的概念,这对正确分析求解结果以及缩小猜测空间有重要作用.最后,我们对Bivium流密码算法的攻击时间进行了估计.结果表明,在最坏情况下,使用DM-rev序及Evy3的猜测位置,猜测60个变元有最优的攻击结果,约2 exp(39.16)秒.

定点算术数据通路的等价性检验方法

以vanishing多项式理想的极小强Grbner基为理论基础,提出一种针对定点算术数据通路的等价性检验方法.通过使用多项式函数建模定点数据通路的设计规范和寄存器传输级实现,将等价性检验问题转化为判断一个多项式函数是否为vanishing多项式、vanishing多项式理想的极小强Grbner基被用来有效地解决该问题.理论分析和实验结果表明,与现有的算法相比,该方法在时间消耗上具有一定的优势.