模的Grbner基理论及在纠错码译码中的应用

针对如何提高纠错码译码过程中的效率问题,讨论了利用模的Grbner基理论计算纠错码中错误位置和错误值。计算过程中,首先将译码过程中关键方程的求解问题化为不同偏序下模的Grbner基的计算,然后利用一种偏序关系下已知的Grbner基计算另一种序下的Grbner基以得到错位及错误图样。该方法可以将错位多项式和错误值多项式同时求出。基于模的Grbner基理论的译码方法适用于二进制及多进制循环码的译码问题,并有助于提高译码的性能。     

Grbner基与联立方程式的解法

固定一个项序,利用Buchberger算法求多项式环S=C[x1,x2,…,xn]上的理想I的Grbner基。根据S上任意多项式f(x1,x2,…,xn)用Grbner基表示时其余项唯一的特点,将其应用到求解联立方程和求满足特定条件的多项式值等问题,从而得出Grbner基在求解多元非线性方程组方面的一个行之有效的方法,该方法为解决诸如此类数学建模问题开辟了一个新途径。     

微分算子环的强既约Grbner基

为解决计算微分算子环中Grbner基的Buchberger算法与Insa-Pauer算法在某些情况下不能将Grbner基进一步简化的问题,K.Nabeshima给出了微分算子环的弱既约Grbner基的定义和算法,但弱既约Grbner基并不唯一.为此,给出了微分算子环的强既约Grbner基的定义及算法,并证明微分算子环的强既约Grbner基的存在性和唯一性.     

线性变换下Grbner基的转换问题

Grbner基是符号计算中的基本工具之一,在许多实际问题中需要进行Grbner基的转换。讨论了经变元的线性变换φ:k[x_1,…,x_n]→k[x_1,…,x_n]后Grbner基的转换问题。证明了Grbner基在这种变换下保持基的性质。并证明了当变换矩阵为可经过行交换化为非退化上三角阵且变换后k[x_1,…,x_n]的序与原有序相容时,Grbner基经变换后仍保持Grbner基性质。     

四元数除环上多项式环的Gr(o)bner基的应用

利用四元数除环上多项式环的Gr(o)bner基理论得到了消元定理,利用消元定理给出求理想生成元的肖元算法,且该生成元是相对消元序的Gr(o)bner基;研究了多项式映射ψ的核Kerψ的Gr(o)bner基和给出算法来判定ψ是否是映上的.     

Gr(o)bner基与联立方程式的解法

固定一个项序,利用Buchberger算法求多项式环s=C[3x1,x2,…,xn]上的理想Ⅰ的Gr(o)bner基.根据S上任意多项式f(x1,x2,…,xn)用Gr(o)bner基表示时其余项唯一的特点,将其应用到求解联立方程和求满足特定条件的多项式值等问题,从而得出Gr(o)bner基在求解多元非线性方程组方面的一个行之有效的方法,该方法为解决诸如此类数学建模问题开辟了一个新途径.     

模的Gr(o)bner基理论及在纠错码译码中的应用

针对如何提高纠错码译码过程中的效率问题,讨论了利用模的Gr(o)bner基理论计算纠错码中错误位置和错误值.计算过程中,首先将译码过程中关键方程的求解问题化为不同偏序下模的Gr(o)bner基的计算,然后利用一种偏序关系下已知的Gr(o)bner基计算另一种序下的Gr(o)bner基以得到错位及错误图样.该方法可以将错位多项式和错误值多项式同时求出.基于模的Gr(o)bner基理论的译码方法适用于二进制及多进制循环码的译码问题,并有助于提高译码的性能.     

基于多项式符号代数的数据通路模型

当前所研究的集成电路已经越来越趋于复杂化,伴随着这个变化,需要在设计流程的早期进行良好的功能正确性验证。将多项式代数符号方法应用于高层次数据通路的研究中,通过字级多项式实现寄存器和传输级之间的等价性验证,从多项式集合公共零点的角度定义高层次数据通路的功能等价,通过验证数据证明形式验证与等价验证的正确性。     

基于多项式符号运算的时钟周期确定新方法

采用多项式符号代数理论建立了包含时序元件的整个同步时序电路的统一多项式符号描述形式,并采用WGL(weighted general lists)模型进行多项式的符号运算.在时序电路统一多项式描述和及其WGL运算的基础上,通过对有限状态机的简化比较,提出一种完全考虑周期的时序特性的时钟周期确定算法.该方法打破了传统上认为时钟周期要不小于实际传输延迟的认识;通过对多种现有方法的实验比较,该方法可以在不增加计算复杂度的情况下比现有方法找到更精确的时钟周期;实验还表明电路正常工作的时钟周期可以在不使用流水的情况下比实际传输延迟小很多.     

基于模拟的定点算术数据通路等价性验证

为证明定点数据通路的定点算术规范与转换后的寄存器传输级实现是等价的,结合算术转换和多项式函数对实现序列加法、乘法、移位运算的定点数据通路进行建模,根据多项式函数的结论得到对定点数据通路进行等价验证所需要的模拟向量数的上界,避免穷举所有的模拟向量。实验结果证明本文提出的方法是有效的。     

类F5算法设计准则模型研究

本文通过引入L-对、准则序等概念,给出了类F5算法设计准则的一个模型,并证明了现有类F5算法的设计准则都是该模型中采用了某个特定准则序的特例。与孙等人的准则模型相比,我们的模型包括了F5、F5C等算法使用L-对准则的情况,并证明了类F5算法设计准则不仅是Gr?bner基的计算依据,也是强Gr?bner基的计算依据。     

LBRSS算法和GBSS算法的关系

文章研究了域上的单序列综合问题的LBRSS(格基约化单序列综合)算法和GBSS(Gr bner基单序列综合)算法之间的联系,证明了LBRSS算法可以推出GBSS算法,从而使得LBRSS算法成为解决单序列综合问题的统一方法。     

量子群Uq（C3）及其不可约模的Gr?bner-Shirshov基

为了研究量子群Uq ( C3)及其有限维不可约模的Gr?bner-Shirshov基,基于赋值图C3的Auslander-Reiten理论和表示的Gr?bner-Shirshov基理论,运用Ringel-Hall代数方法,构造了量子群Uq ( C3)的Gr?bner-Shirshov基,进而用双自由模及钻石-合成引理,给出量子群Uq ( C3)的有限维不可约模的Gr?bner-Shirshov基。     

同态哈希函数在多变量公钥密码体制中的应用

提出一个具有双重验证条件的多变量二次签名方案.通过在其中心方程设入秘密私钥将同态哈希函数应用到中等扩域体制中.该方法在签名验证时,不仅只验证通常的公钥方程,还涉及体制内部结构,因此在一定程度上提高了对Grbner基攻击的安全性.分析结果表明,该双重验证可更有效地防止伪造,提高算法的安全性.     

多项式数据通路的高层次综合方法

为了实现多项式数据通路的高层次综合,采用有序、简化和正则的带权值广义表模型表达该多项式.首先对该带权值广义表进行线性化处理;然后提出了基于带权值广义表的多项式数据通路的高层次优化方法.该方法以自底向上的方式遍历带权值广义表中的节点,并迭代地析取该带权值广义表中的乘法和加法项,进而将该带权值广义表转换为不可简化的有层次的带权值广义表集合,最终将该集合转换为更适于高层次综合的可调度数据流图.实验结果表明,与传统的方法相比,采用该方法得到的数据流图转化为寄存器传输级结构具有更小的延迟和面积.     

广义Grtzsch环函数的变换性质(英文)

该文将Grtzsch环函数μa(r)的一种离散的变换性质推广为广义Grtzsch环函数μa(r)的一种连续的变换性质,得到了μa(r)所满足的几个不等式,并改进了原有的关于μa(r)的相应结果.     

采用近似方法的实代数数准确表示及其应用

针对如何保证实代数数的二进制展开不形成伪随机序列的问题,提出了通过实代数数的近似值重构它的准确极小多项式的算法,以此为基础提供了一种新的计算机实代数数表示方法.采用1个三元组序列:适当误差控制的实代数数近似值,极小多项式的次数和高度的上界.与目前的3种实代数数的计算机表示方法相比,在稀疏极小多项式情况下,新表示方法占有的二进制比特位与区间方法一致,低于符号方法,而略高于序方法;在稠密极小多项式情况下,比目前的3种表示方法都低.同时利用近似值重构极小多项式的方法,可获得多项式的准确因式分解.通过理论的分析和试验的验证,显示新的实代数数准确表示方法和应用是高效合理的.     

广义Grtzsch环函数的一些性质(英文)

本文将Grtzsch环函数μ(r)的几个结果推广到了广义Grtzsch环函数μa(r),得到了关于μa(r)的几个不等式,并改进了原有的关于μ(r)的结果。     

一类循环条件非线性的程序终止性

针对Tiwari提出的线性循环程序的终止性判定问题,提出了循环条件为齐次多项式的非线性程序的不可中止性判定的理论证明,然后将程序终止性判定问题转化为参数半代数系统的求解。在求解中,借助强有力的代数符号工具DISCOVERER,解决了计算机浮点计算所造成的近似误差,精确地判定这类程序的不可终止性。最后,通过计算代数理论,把循环条件推广到了非齐次多项式,并且进行了验证。通过理论的证明和实验的验证,解决循环条件是非线性的一类循环程序的方法是高效合理的。     

可解多项式代数与它在阶滤子下两种分次代数的关系

针对可解多项式代数A，证明了它在阶滤子下两种分次代数grC(A)与A^～均为可解多项式代数．应用Groebner基理论，给出了其左理想L和gr^C(L)与L^～的Groebner基的转换．