Abstract
The main computational steps in algebraic soft-decoding, as well as Sudan-type list-decoding, of Reed-Solomon codes are bivariate polynomial interpolation and factorization. We introduce a computational technique, based upon re-encoding and coordinate transformation, that significantly reduces the complexity of the bivariate interpolation procedure. This re-encoding and coordinate transformation converts the original interpolation problem into another reduced interpolation problem, which is orders of magnitude smaller than the original one. A rigorous proof is presented to show that the two interpolation problems are indeed equivalent. An efficient factorization procedure that applies directly to the reduced interpolation problem is also given.
Introduction
Reed-Solomon (RS) codes are the workhorses of digital communications and data storage, used in everything from QR codes to satellite links. While standard decoding algorithms are efficient, they are limited by a specific decoding radius. Advanced techniques, such as Guruswami-Sudan list-decoding and Koetter-Vardy soft-decision decoding, offer superior error correction capabilities but at a high computational cost.
The primary bottleneck in these advanced methods is bivariate polynomial interpolation. Decoders must find a polynomial $Q(X, Y)$ that satisfies a set of constraints defined by points and their associated multiplicities. For high-rate codes used in industrial applications, this involves solving thousands of simultaneous linear equations, requiring millions of finite-field multiplications—a process often too slow and memory-intensive for practical hardware.
The Re-Encoding Transformation
To address this "interpolation nightmare," we propose a two-step transformation that simplifies the problem by orders of magnitude:
- Re-Encoding and Shift: We select $k$ points (where $k$ is the code dimension) from the received data and determine a "re-encoding polynomial" $e(X)$ that interpolates them. By shifting the $Y$-coordinates of all points by $e(X)$, the interpolation constraints for these $k$ points are effectively "zeroed out."
- Coordinate Transformation: Using a birational isomorphism, the remaining points are mapped into a new coordinate system. This converts the original interpolation problem into a "reduced" problem.
Instead of solving for the large original polynomial $Q(X, Y)$, the decoder solves for a much smaller polynomial $H(X, Y)$. We also provide a modified Roth-Ruckenstein factorization algorithm to extract the final message directly from $H(X, Y)$, bypassing the need to reconstruct the complex original polynomial.
Key Results and Complexity Reduction
The re-encoding transformation provides dramatic performance gains, particularly for high-rate codes. The savings are roughly proportional to $(n/(n-k))^2$, where $n$ is the code length and $k$ is the dimension.
In a practical example of a $(255, 239)$ RS code over $\mathbb{F}_{256}$, the original interpolation problem involves a massive number of constraints. The table below illustrates the distribution of these constraints across points with varying multiplicities before the transformation is applied.
By applying the re-encoding transformation to this scenario, the number of linear equations to solve drops from 6,912 to just 290. This results in a 456x speedup in finite-field multiplications. Furthermore, the memory footprint is significantly reduced, as the maximum degree of the polynomials to be stored drops from approximately 1,598 to 40, facilitating more efficient hardware (VLSI) implementations.
Conclusion
The re-encoding transformation makes powerful list-decoding and soft-decision decoding practical for real-world, high-rate communication systems. While the current work focuses on Reed-Solomon codes, the underlying birational transformations suggest potential applicability to more complex algebraic-geometric (AG) codes. Future work may explore optimal point selection strategies to further leverage these algorithmic gains.
Summary updated