A Gröbner-Bases Approach to Syndrome-Based Fast Chase Decoding of Reed–Solomon Codes

DOI10.1109/TIT.2022.3140678zbMATH Open1497.94184arXiv2008.01796OpenAlexW4205701723MaRDI QIDQ5088387

Amit Berman, Yaron Shany

Publication date: 13 July 2022

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: We present a simple syndrome-based fast Chase decoding algorithm for Reed--Solomon (RS) codes. Such an algorithm was initially presented by Wu (IEEE Trans. IT, Jan. 2012), building on properties of the Berlekamp--Massey (BM) algorithm. Wu devised a fast polynomial-update algorithm to construct the error-locator polynomial (ELP) as the solution of a certain linear-feedback shift register (LFSR) synthesis problem. This results in a conceptually complicated algorithm, divided into $8$ subtly different cases. Moreover, Wu's polynomial-update algorithm is not immediately suitable for working with vectors of evaluations. Therefore, complicated modifications were required in order to achieve a true "one-pass" Chase decoding algorithm, that is, a Chase decoding algorithm requiring $O(n)$ operations per modified coordinate, where $n$ is the RS code length. The main result of the current paper is a conceptually simple syndrome-based fast Chase decoding of RS codes. Instead of developing a theory from scratch, we use the well-established theory of Groebner bases for modules over $mathbb{F}_q[X]$ (where $mathbb{F}_q$ is the finite field of $q$ elements, for $q$ a prime power). The basic observation is that instead of Wu's LFSR synthesis problem, it is much simpler to consider "the right" minimization problem over a module. The solution to this minimization problem is a simple polynomial-update algorithm that avoids syndrome updates and works seamlessly with vectors of evaluations. As a result, we obtain a conceptually simple algorithm for one-pass Chase decoding of RS codes. Our algorithm is general enough to work with any algorithm that finds a Groebner basis for the solution module of the key equation as the initial algorithm (including the Euclidean algorithm), and it is not tied only to the BM algorithm.

Full work available at URL: https://arxiv.org/abs/2008.01796

zbMATH Keywords

Gröbner basesReed-Solomon (RS) codessyndrome-based fast Chase decoding algorithm

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Decoding (94B35)

Recommendations

• Bounded distance decoding of linear error-correcting codes with Gröbner bases 👍 👎
• List decoding of Reed-Solomon codes from a Gröbner basis perspective 👍 👎
• On the decoding of cyclic codes using Gröbner bases 👍 👎
• Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases 👍 👎
• On syndrome decoding of punctured Reed-Solomon and Gabidulin codes 👍 👎
• Decoding Linear Error-Correcting Codes up to Half the Minimum Distance with Gröbner Bases 👍 👎
• Syndrome decoding of Reed-Muller codes and tensor decomposition over finite fields 👍 👎
• Fast Chase Decoding Algorithms and Architectures for Reed–Solomon Codes 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: A Gröbner-Bases Approach to Syndrome-Based Fast Chase Decoding of Reed–Solomon Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5088387)