The Re-Encoding Transformation in Algebraic List-Decoding of Reed–Solomon Codes
The Re-Encoding Transformation in Algebraic List-Decoding of Reed–Solomon Codes
复制标题
DOI：
10.1109/tit.2010.2096034
复制
发表时间：
2010-05
影响因子：
2.5
通讯作者：
R. Koetter;Jun Ma;A. Vardy
中科院分区：
文献类型：
--
作者：
R. Koetter;Jun Ma;A. Vardy
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 formal 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.
