A polynomial-time soft-decision decoding algorithm for Reed-Solomon codes is developed. This list-decoding algorithm is algebraic in nature and builds upon the interpolation procedure proposed by Guruswami and Sudan f...
详细信息
A polynomial-time soft-decision decoding algorithm for Reed-Solomon codes is developed. This list-decoding algorithm is algebraic in nature and builds upon the interpolation procedure proposed by Guruswami and Sudan for hard-decision decoding. Algebraic soft-decision decoding is achieved by means of converting the probabilistic reliability information into a set of interpolation points, along with their multiplicities. The proposed conversion procedure is shown to be asymptotically optimal for a certain probabilistic model. The resulting soft-decoding algorithm significantly outperforms both the Guruswami-Sudan decoding and the generalized minimum distance (GMD) decoding of Reed-Solomon codes, while maintaining a complexity that is polynomial in the length of the code. Asymptotic analysis for a large number of interpolation points is presented, leading to A geometric characterization of the decoding regions of,the proposed algorithm. It is then shown that the asymptotic performance can be approached as closely as desired with a list size that does not depend on the length of the code.
In the last couple of decades, error correction techniques play a prominent role in various scientific and engineering fields such as information theory, communication, networking, to name a few. These techniques are ...
详细信息
ISBN:
(纸本)9781538646496
In the last couple of decades, error correction techniques play a prominent role in various scientific and engineering fields such as information theory, communication, networking, to name a few. These techniques are mainly utilized to locate and fix corrupted data over noisy channels. The data might be corrupted due to various reasons, for instance, communication failures, noise, or adversarial activities. On the other hand, data-privacy has been in the center of attention by many researchers in recent years. As such, it's important to be able to use error correction techniques over private data. This paper therefore proposes a secure error correction method by using secure multiparty computation (MPC). To the best of our knowledge, our proposed approach is the first solution in the literature. In secure MPC protocols, parties first share their private inputs by cryptographic primitives in order to jointly compute a function without revealing those private inputs. At the end of the protocol, only the function value will be revealed to all parties. Our secure MPC protocol efficiently implements the error-locator function of berlekamp-welch algorithm. After locating errors, we utilize another cryptographic technique, named enrollment protocol, to fix the errors.
暂无评论