Low-Complexity Koetter-Vardy Decoding of Reed-Solomon Codes using Module Minimization
Jiongyue Xing, Li Chen, Martin Bossert · 2019
The Koetter-Vardy (KV) algorithm achieves advanced decoding performance for Reed-Solomon (RS) codes but with a high computational cost. This paper studies the lowcomplexity KV decoding that utilizes the module minimization (MM) interpolation technique, namely the KV-MM algorithm. A module contains bivariate polynomials that interpolate all the prescribed points with their multiplicity. Presenting the module basis as a matrix over univariate polynomials, row operation further reduces it into the Gröbner basis, delivering the interpolated polynomial. We will also introduce the re-encoding transformed KV-MM algorithm by giving an explicit construction for the module basis. This research shows MM interpolation yields a remarkably lower complexity for KV decoding than the conventional Koetter's interpolation, especially for high rate codes. This is also true when the re-encoding transform is applied. This finding is a rectification of some earlier results.