字典序下BMS算法终止条件的设计

doi:10.3724/SP.J.1087.2012.02977

计算机应用 ›› 2012, Vol. 32 ›› Issue (11): 2977-2980.DOI: 10.3724/SP.J.1087.2012.02977

• 先进计算 • 下一篇

字典序下BMS算法终止条件的设计

牟晨琪

北京航空航天大学数学与系统科学学院，北京 100191

收稿日期:2012-05-07 修回日期:2012-06-25 发布日期:2012-11-12 出版日期:2012-11-01
通讯作者: 牟晨琪
作者简介:牟晨琪(1984-)，男，山东潍坊人，博士研究生，主要研究方向: 计算机代数。
基金资助:
国家自然科学基金资助项目(60911130369)

Design of termination criterion of BMS algorithm for lexicographical ordering

School of Mathematics and Systems Science，Beihang University，Beijing 100191，China

Received:2012-05-07 Revised:2012-06-25 Online:2012-11-12 Published:2012-11-01
Supported by:
Exact/Certified Computation with Algebraic Systems

摘要/Abstract

摘要： 编码理论中的BMS算法具有良好的解码效率与纠错能力，目前的研究通常集中于分次项序下的情形。通过分析字典序与分次项序的本质特征，利用与BMS算法密切相关的Gr?bner基的消去性质，设计出字典序下BMS算法的终止条件，并给出了基于该条件的易于实现的具体算法描述。实验结果表明，该终止条件切实有效，与算法中的原始理论终止条件完全吻合。

关键词: BMS算法, Grbner基, 字典序, 终止条件

Abstract: The BMS algorithm from Coding Theory has good decoding efficiency and error-correcting capability, and current work usually focuses on the case of graded orderings. With the analysis on the essential characteristics of lexicographical and graded orderings, a termination criterion of BMS algorithm for the lexicographical ordering is designed by using the elimination property of Gr?bner bases, which are closely related to the BMS algorithm, and an implementation-oriented description for the algorithm based on this criterion is also provided. Experimental results verify the effectiveness of the proposed termination criterion, and the new criterion matches the original theoretical one in the algorithm.

Key words: BMS algorithm, Grbner basis, lexicographical ordering, termination criterion

中图分类号:

TP301.6

牟晨琪. 字典序下BMS算法终止条件的设计[J]. 计算机应用, 2012, 32(11): 2977-2980.

参考文献

[1]SAKATA S. Finding a minimal set of linear recurring relations capable of generating a given finite twodimensional array ［J］. Journal of Symbolic Computation, 1988, 5(3): 321-337. ［2］SAKATA S. Extension of the BerlekampMassey algorithm to N dimensions ［J］. Information and Computation, 1990, 84(2): 207-239. ［3］FENG G L, RAO T R N. Decoding algebraicgeometric codes up to the designed minimum distance ［J］. IEEE Transactions on Information Theory, 1993, 39(1): 37-45. ［4］BRASAMORóS M, O’SULLIVAN M E. The correction capability of the BerlekampMasseySakata algorithm with majority voting ［J］. Applicable Algebra in Engineering, Communication and Computing, 2006, 17(5): 315-335. ［5］SAINTS K, HEEGARD C. Algebraicgeometric codes and multidimensional cyclic codes: a unified theory and algorithms for decoding using Grbner bases ［J］. IEEE Transactions on Information Theory, 2002, 41(6): 1733-1751. ［6］BUCHBERGER B. Grbner bases: an algorithmic method in polynomial ideal theory ［C］ // Multidimensional Systems Theory. Berlin: Springer, 1985: 184-232. ［7］王东明, 牟晨琪, 李晓亮, 等. 多项式代数［M］. 北京: 高等教育出版社, 2011. ［8］FAUGERE JC. A new efficient algorithm for computing Grbner bases (F4) ［J］. Journal of Pure and Applied Algebra, 1999, 139(1-3): 61-88. ［9］FAUGERE JC. A new efficient algorithm for computing Grbner bases without reduction to zero (F5) ［C］ // Proceedings of the 2002 International Symposium on Symbolic and Algebraic Computation. New York: ACM, 2002: 75-83. ［10］FAUGERE JC, SAFEY EL DIN M, SPAENLEHAUER PJ.Computing loci of rank defects of linear matrices using Grbner bases and applications to cryptology ［C］ // Proceedings of the 2010 International Symposium on Symbolic and Algebraic Computation. New York: ACM, 2010: 257-264. ［11］LEE K M，O’SULLIVAN M E. List decoding of ReedSolomon codes from a Grbner basis perspective ［J］. Journal of Symbolic Computation, 2008, 43(9): 645-658. ［12］LIN Z, XU L, BOSE N K. A tutorial on Grbner bases with applications in signals and systems ［J］. IEEE Transactions on Circuits and Systems I: Regular Papers, 2008, 15(1): 445-461. ［13］LAUBENBACHER R, STURMFELS B. Computer algebra in systems biology ［J］. The American Mathematical Monthly, 2009, 116(10): 882-891. ［14］COX D, LITTLE J, O’SHEA D. Using algebraic geometry［M］.2nd ed. Berlin: Springer, 2005. ［15］FAUGERE JC, MOU CHENQI. Fast algorithm for change of ordering of zerodimensional Grbner bases with sparse multiplication matrices ［C］ // Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation. New York: ACM, 2011: 115-122. ［16］FAUGERE JC, GIANNI P, LAZARD D, et al. Efficient computation of zerodimensional Grbner bases by change of ordering ［J］. Journal of Symbolic Computation, 1993, 16(4): 329-344. ［17］BJORCK G, FROBERG R. A faster way to count the solutions of inhomogeneous systems of algebraic equations, with applications to cyclic nroots ［J］. Journal of Symbolic Computation, 1991, 12(3): 329-336. ［18］BASIRI A, FAUGERE JC. Changing the ordering of Grbner bases with LLL: case of two variables ［C］ // SENDRA J. R.Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation. New York: ACM, 2003: 23-29.

[1]	平凡, 汤小春, 潘彦宇, 李战怀. 不规则任务在图形处理器集群上的调度策略[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3295-3301.
[2]	雷鹰, 郑万波, 魏嵬, 夏云霓, 李晓波, 刘诚武, 谢洪. 基于概率性能感知演化博弈策略的“云+边”混合环境中任务卸载方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3302-3308.
[3]	乔钢柱, 王瑞, 孙超利. 基于分解的高维多目标改进进化算法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3097-3103.
[4]	邹复民, 罗思杰, 陈志辉, 廖律超. 基于轨迹数据的出租车交接班时空分布识别方法[J]. 《计算机应用》唯一官方网站, 2021, 41(11): 3376-3384.
[5]	肖智豪胡志华朱琳. 求解冷链物流时间依赖型车辆路径问题的混合自适应大邻域搜索算法[J]. 计算机应用, 0, (): 0-0.
[6]	沙林秀，聂凡，高倩，孟号. 基于布朗运动与梯度信息的交替优化算法[J]. 计算机应用, 0, (): 0-0.
[7]	董永峰孙跃华高立超韩鹏季海鹏. 基于改进一维卷积和双向长短期记忆神经网络的故障诊断方法[J]. 计算机应用, 0, (): 0-0.
[8]	李大海刘庆腾艾志刚王振东. 基于动态D向分割和混沌扰动的阴阳对算法[J]. 计算机应用, 0, (): 0-0.
[9]	朱诚潘旭华张勇. 基于趋化校正的哈里斯鹰优化算法[J]. 计算机应用, 0, (): 0-0.
[10]	杨杰张名扬芮晓彬王志晓. 融合节点覆盖范围和结构洞的影响力最大化算法[J]. 计算机应用, 0, (): 0-0.
[11]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[12]	李蒙蒙, 秦伟, 刘艺, 刁兴春. 结合头脑风暴优化的混合蚁群优化算法[J]. 计算机应用, 2021, 41(8): 2412-2417.
[13]	张闻强, 邢征, 杨卫东. 基于多区域采样策略的混合粒子群优化求解多目标柔性作业车间调度问题[J]. 计算机应用, 2021, 41(8): 2249-2257.
[14]	张祥飞, 鲁宇明, 张平生. 基于协同进化的约束多目标优化算法[J]. 计算机应用, 2021, 41(7): 2012-2018.
[15]	张萌, 李维华. 用户互动表示下的影响力最大化算法[J]. 计算机应用, 2021, 41(7): 1964-1969.

字典序下BMS算法终止条件的设计

Design of termination criterion of BMS algorithm for lexicographical ordering

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics