Reverse Berlekamp-Massey Decoding

2013/01/30 by Jiun-Hung Yu, Hans-Andrea Loeliger, Hans‐Andrea Loeliger +2
Computer Science · Mathematics · #Cellular Automata and Applications #Coding theory and cryptography #Cryptography and Residue Arithmetic #FOS: Computer and information sciences #Information Theory (cs.IT) #cs.IT #math.IT

paper · pdf · doi:10.48550/arxiv.1301.7236

Updated version

openalex publication_date 2013/01/30 · arxiv created 2013/05/17 · arxiv updated 2013/05/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We propose a new algorithm for decoding Reed-Solomon codes (up to half the minimum distance) and for computing inverses in F[x]/m(x). The proposed algorithm is similar in spirit and structure to the Berlekamp-Massey algorithm, but it works naturally for general m(x).

Related

• The Berlekamp-Massey Algorithm and the Euclidean Algorithm: a Closer Link
• Simultaneous Partial Inverses and Decoding Interleaved Reed-Solomon Codes
• Syndrome Decoding of Reed-Solomon Codes Beyond Half the Minimum Distance based on Shift-Register Synthesis
• An Optimal Sequence Reconstruction Algorithm for Reed-Solomon Codes
• A Decoding Approach to Reed-Solomon Codes from Their Definition