论文标题
基于综合征的Groebner-Bases方法，基于综合征的快速追逐解码 - 固体代码
A Groebner-bases approach to syndrome-based fast Chase decoding of Reed--Solomon codes
论文作者
论文摘要
我们提出了一种简单的基于综合征的快速追逐解码算法，用于芦苇 - 固体（RS）代码。这种算法最初由Wu（IEEE Trans。，2012年1月）提出，建立在Berlekamp-Massey（BM）算法的属性上。 WU设计了一种快速多项式UPDATE算法，以构建错误位置多项式（ELP）作为特定线性馈回移位寄存器（LFSR）合成问题的解决方案。这导致了一种概念上复杂的算法，分为$ 8 $微妙的情况。此外，WU的多项式上升算法并不适合使用评估载体。因此，需要进行复杂的修改，以实现真正的“一通”追逐解码算法，即，需要每次修改的坐标$ o（n）$操作的追逐解码算法，其中$ n $是RS代码长度。 当前论文的主要结果是基于概念上的简单综合症的RS代码快速追逐解码。我们没有从头开始开发理论，而是使用$ \ Mathbb {f} _Q [x] $的模块的良好的groebner基础理论（其中$ \ m athbb {f} _q $是$ q $元素的有限字段，用于$ q $ ements $ q $ a prime a Prime a Priende a Prime a Priend a prime a prone a prime a prime a prime a prime a a Prime）。基本的观察结果是，而不是WU的LFSR合成问题，而是考虑模块上的“正确”最小化问题要简单得多。解决这个最小化问题的解决方案是一种简单的多项式上限算法，避免了综合征更新并与评估的矢量无缝搭配。结果，我们获得了一种概念上简单的算法，用于对RS代码的一通追逐解码。我们的算法足够通用，可以处理任何算法，该算法找到了关键方程的解决方案模块作为初始算法（包括欧几里得算法）的溶液模块，并且不仅绑定到BM算法。
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.
