From the Euclidean Algorithm for Solving a Key Equation for Dual Reed–Solomon Codes to the Berlekamp–Massey Algorithm | SpringerLink
Skip to main content
Springer Nature Link
Log in

From the Euclidean Algorithm for Solving a Key Equation for Dual Reed–Solomon Codes to the Berlekamp–Massey Algorithm

  • Conference paper
Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (AAECC 2009)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 5527))

Abstract

The two primary decoding algorithms for Reed-Solomon codes are the Berlekamp-Massey algorithm and the Sugiyama et al. adaptation of the Euclidean algorithm, both designed to solve a key equation. This article presents a new version of the key equation and a way to use the Euclidean algorithm to solve it. A straightforward reorganization of the algorithm yields the Berlekamp-Massey algorithm.

An extended version is in preparation for being submitted for publication.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Berlekamp, E.R.: Algebraic coding theory. McGraw-Hill Book Co., New York (1968)

    MATH  Google Scholar 

  2. Cox, D.A., Little, J., O’Shea, D. (eds.): Using algebraic geometry, 2nd edn. Graduate Texts in Mathematics, vol. 185. Springer, New York (2005)

    MATH  Google Scholar 

  3. Dornstetter, J.-L.: On the equivalence between Berlekamp’s and Euclid’s algorithms. IEEE Trans. Inform. Theory 33(3), 428–431 (1987)

    Article  MathSciNet  MATH  Google Scholar 

  4. David Forney Jr., G.: On decoding BCH codes. IEEE Trans. Information Theory IT-11, 549–557 (1965)

    Article  MathSciNet  MATH  Google Scholar 

  5. Heydtmann, A.E., Jensen, J.M.: On the equivalence of the Berlekamp-Massey and the Euclidean algorithms for decoding. IEEE Trans. Inform. Theory 46(7), 2614–2624 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  6. Massey, J.L.: Shift-register synthesis and BCH decoding. IEEE Trans. Information Theory IT-15, 122–127 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  7. O’Sullivan, M.E., Bras-Amorós, M.: The Key Equation for One-Point Codes, ch. 3, pp. 99–152 (2008)

    Google Scholar 

  8. Roth, R.: Introduction to coding theory. Cambridge University Press, Cambridge (2006)

    Book  MATH  Google Scholar 

  9. Sugiyama, Y., Kasahara, M., Hirasawa, S., Namekawa, T.: A method for solving key equation for decoding Goppa codes. Information and Control 27, 87–99 (1975)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Spain

    Maria Bras-Amorós

  2. Department of Mathematics and Statistics, San Diego State University, USA

    Michael E. O’Sullivan

Authors
  1. Maria Bras-Amorós
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Michael E. O’Sullivan
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. Departament d’Enginyeria Informàtica i Matemàtiques, Universitat Rovira i Virgili, Avinguda Països Catalans, 26, 43007, Tarragona, Spain

    Maria Bras-Amorós

  2. Department of Mathematics, The Technical University of Denmark, Building 303, 2800, Lyngby, Denmark

    Tom Høholdt

Rights and permissions

Reprints and permissions

Copyright information

© 2009 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Bras-Amorós, M., O’Sullivan, M.E. (2009). From the Euclidean Algorithm for Solving a Key Equation for Dual Reed–Solomon Codes to the Berlekamp–Massey Algorithm. In: Bras-Amorós, M., Høholdt, T. (eds) Applied Algebra, Algebraic Algorithms and Error-Correcting Codes. AAECC 2009. Lecture Notes in Computer Science, vol 5527. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02181-7_4

Download citation

  • DOI: https://doi.org/10.1007/978-3-642-02181-7_4

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-642-02180-0

  • Online ISBN: 978-3-642-02181-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics