Can the BMS Algorithm Decode Up to Errors? Yes, but with Some Additional Remarks

Shojiro SAKATA

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E93-A    No.4    pp.857-862
Publication Date: 2010/04/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E93.A.857
Print ISSN: 0916-8508
Type of Manuscript: LETTER
Category: Coding Theory
algebraic geometric codes,  one-point codes,  BMS algorithm,  unknown syndrome,  without majority voting,  

Full Text: PDF(148KB)>>
Buy this Article

It is a well-known fact that the BMS algorithm with majority voting can decode up to half the Feng-Rao designed distance dFR. Since dFR is not smaller than the Goppa designed distance dG, that algorithm can correct up to errors. On the other hand, it has been considered to be evident that the original BMS algorithm (without voting) can correct up to errors similarly to the basic algorithm by Skorobogatov-Vladut. But, is it true? In this short paper, we show that it is true, although we need a few remarks and some additional procedures for determining the Groebner basis of the error locator ideal exactly. In fact, as the basic algorithm gives a set of polynomials whose zero set contains the error locators as a subset, it cannot always give the exact error locators, unless the syndrome equation is solved to find the error values in addition.