字典序下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]	侯阳张琼赵紫煊朱正宇张晓博. 基于YOLOv5s的复杂场景下高效烟火检测算法——YOLOv5s-MRD[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[2]	张奇业, 曾心蕊. 带高斯核的支持向量数据描述问题的高效积极集法[J]. 《计算机应用》唯一官方网站, 2024, 44(12): 3808-3814.
[3]	曹晓意罗煦琼李景贺恩锋. 改进人工势场法下的多无人机编队路径规划方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[4]	袁志超杨磊田井林魏晓威李康顺. 面向复杂约束多目标优化问题的双种群双阶段进化算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[5]	冷琴, 毛政元. 考虑设施规模决策的两级选址-路径优化[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3513-3520.
[6]	彭庆媛, 王晓峰, 王军霞, 华盈盈, 唐傲, 何飞. 可满足性问题相变研究综述[J]. 《计算机应用》唯一官方网站, 2024, 44(11): 3503-3512.
[7]	孙仁科, 皇甫志宇, 陈虎, 李仲年, 许新征. 神经架构搜索综述[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 2983-2994.
[8]	孙安泰, 刘烨, 徐冬梅. 多智能体系统的动态面渐近补偿算法[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3151-3157.
[9]	颜超英, 张紫仪, 曲映楠, 李秋禹, 郑地翔, 孙丽珺. 基于联盟链的双向拍卖碳交易[J]. 《计算机应用》唯一官方网站, 2024, 44(10): 3240-3245.
[10]	杨志龙邹德旋李灿邵莹莹马乐杰. 融入限制反向学习与柯西-高斯变异的蜣螂优化算法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[11]	姚光磊, 熊菊霞, 杨国武. 基于神经网络优化的花朵授粉算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2829-2837.
[12]	力尚龙, 刘建华, 贾鹤鸣. 融合多狩猎协调策略的爬行动物搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(9): 2818-2828.
[13]	李焱, 潘大志, 郑思情. 多车场带时间窗车辆路径问题的改良自适应大邻域搜索算法[J]. 《计算机应用》唯一官方网站, 2024, 44(6): 1897-1904.
[14]	张倩婷胡丽莹陈黎飞. 时间序列的鲁棒形态表征方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.
[15]	胡林波倪志伟程家乐刘文涛朱旭辉. 基于融合社区检测的复杂协作众包任务分配方法[J]. 《计算机应用》唯一官方网站, 0, (): 0-0.

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

Design of termination criterion of BMS algorithm for lexicographical ordering

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics