Can the BMS Algorithm Decode Up to <eq201003.gif> Errors? Yes, but with Some Additional Remarks

Shojiro SAKATA; Masaya FUJISAWA

doi:10.1587/transfun.E93.A.857

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

Shojiro SAKATA, Masaya FUJISAWA

Full Text Views

0

Cite this

Summary :

It is a well-known fact that the BMS algorithm with majority voting can decode up to half the Feng-Rao designed distance d_FR. Since d_FR is not smaller than the Goppa designed distance d_G, 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.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E93-A No.4 pp.857-862

Publication Date: 2010/04/01

Publicized

Online ISSN: 1745-1337

DOI: 10.1587/transfun.E93.A.857

Type of Manuscript: LETTER

Category: Coding Theory

Cite this

Copy

Shojiro SAKATA, Masaya FUJISAWA, "Can the BMS Algorithm Decode Up to Errors? Yes, but with Some Additional Remarks" in IEICE TRANSACTIONS on Fundamentals, vol. E93-A, no. 4, pp. 857-862, April 2010, doi: 10.1587/transfun.E93.A.857.
Abstract: It is a well-known fact that the BMS algorithm with majority voting can decode up to half the Feng-Rao designed distance d_FR. Since d_FR is not smaller than the Goppa designed distance d_G, 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.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.857/_p

Copy

@ARTICLE{e93-a_4_857,
author={Shojiro SAKATA, Masaya FUJISAWA, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Can the BMS Algorithm Decode Up to Errors? Yes, but with Some Additional Remarks},
year={2010},
volume={E93-A},
number={4},
pages={857-862},
abstract={It is a well-known fact that the BMS algorithm with majority voting can decode up to half the Feng-Rao designed distance d_FR. Since d_FR is not smaller than the Goppa designed distance d_G, 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.},
keywords={},
doi={10.1587/transfun.E93.A.857},
ISSN={1745-1337},
month={April},}

Copy

TY - JOUR
TI - Can the BMS Algorithm Decode Up to Errors? Yes, but with Some Additional Remarks
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 857
EP - 862
AU - Shojiro SAKATA
AU - Masaya FUJISAWA
PY - 2010
DO - 10.1587/transfun.E93.A.857
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E93-A
IS - 4
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - April 2010
AB - It is a well-known fact that the BMS algorithm with majority voting can decode up to half the Feng-Rao designed distance d_FR. Since d_FR is not smaller than the Goppa designed distance d_G, 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.
ER -