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

• 先进计算 •    下一篇

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

牟晨琪   

  1. 北京航空航天大学 数学与系统科学学院,北京 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

  1. 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

摘要: 编码理论中的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

中图分类号: