检索结果-内蒙古大学图书馆

Efficient Interpolation in the guruswami-sudan algorithm

IEEE TRANSACTIONS ON INFORMATION THEORY 2010年第9期56卷 4341-4349页

作者： Trifonov, Peter V. St Petersburg State Polytech Univ Distributed Comp & Networking Dept St Petersburg 195251 Russia

A novel algorithm is proposed for the interpolation step of the guruswami-sudan list decoding algorithm. The proposed method is based on the binary exponentiation algorithm, and can be considered as an extension of the Lee-O'Sullivan method. The algorithm is shown to achieve both asymptotical and practical performance gain compared to the case of iterative interpolation algorithm. Further complexity reduction is achieved by employing the reencoding transformation. The key contribution of the paper, which enables the complexity reduction, is a novel randomized ideal multiplication algorithm.

关键词： Grobner basis guruswami-sudan algorithm ideal multiplication interpolation list decoding reencoding Reed-Solomon codes

来源：评论

学校读者我要写书评

暂无评论

A Progressive Interpolation Approach for guruswami-sudan algorithm

A Progressive Interpolation Approach for Guruswami-Sudan Alg...

引用

14th IEEE International Conference on Communication Technology (ICCT)

作者： Zhang, Jingwei Zhao, Chang-An Chen, Li Ma, Xiao Yangzhou Univ Sch Math Sci Yangzhou Peoples R China Guangzhou Univ Sch Educ Software Guangzhou Peoples R China Sun Yat Sen Univ Sch Informat Sci & Technol Guangzhou Peoples R China

ISBN: (纸本)9781467321013;9781467321006

In this paper, we present a progressive interpolation approach in guruswami-sudan (GS) decoding of Reed-Solomon (RS) codes. The objective of the interpolation is to construct the minimal polynomial Q(x, y) by the progressive approach with increasing multiplicities until the roots of Q(x, y) give the correct message. Then the error-correction capability can be adaptively obtained by assigning a suitable multiplicity according to the number of errors occurred in the channel. We present an efficient way to update the polynomial set utilizing the previous computational results in the interpolation step. It enables the decoder to adjust its decoding complexity to the needed level. Simulation results suggest that the average decoding complexity of GS algorithm can be significantly reduced by the progressive approach for RS codes.

关键词： guruswami-sudan algorithm progressive interpolation Reed-Solomon codes

来源：评论

学校读者我要写书评

暂无评论

On the Roth and Ruckenstein Equations for the guruswami-sudan algorithm

On the Roth and Ruckenstein Equations for the Guruswami-Suda...

引用

IEEE International Symposium on Information Theory

作者： Augot, Daniel Zeh, Alexander INRIA Team SECRET Paris France

ISBN: (纸本)9781424422562

In 2000 Roth and Ruckenstein proposed an Extended Key Equation for solving the interpolation step in the sudan decoding algorithm. Generalizing their idea, a sequence of key equations for the guruswami-sudan (GS) algorithm, which is able to fist decode a Reed-Solomon code with arbitrary rate, is derived. This extension allows a reduction of the number of equations and therefore a reduction of the algorithm's complexity. Furthermore, we indicate how to adapt the Fundamental Iterative algorithm for block Hankel matrices and thus solving the GS-interpolation step efficiently.

关键词： guruswami-sudan algorithm list decoding (Extended) Key Equation Reed-Solomon codes polynomial interpolation

来源：评论

学校读者我要写书评

暂无评论

Optimal Threshold-Based Multi-Trial Error/Erasure Decoding with the guruswami-sudan algorithm

Optimal Threshold-Based Multi-Trial Error/Erasure Decoding w...

引用

IEEE International Symposium on Information Theory (ISIT)

作者： Senger, Christian Sidorenko, Vladimir R. Bossert, Martin Zyablov, Victor V. Univ Ulm Inst Telecommun & Appl Informat Theory Ulm Germany Russian Acad Sci Inst Informat Transmiss Problems Moscow Russia

ISBN: (纸本)9781457705953

Traditionally, multi-trial error/erasure decoding of Reed-Solomon (RS) codes is based on Bounded Minimum Distance (BMD) decoders with an erasure option. Such decoders have error/erasure tradeoff factor lambda = 2, which means that an error is twice as expensive as an erasure in terms of the code's minimum distance. The guruswami-sudan (GS) list decoder can be considered as state of the art in algebraic decoding of RS codes. Besides an erasure option, it allows to adjust lambda to values in the range 1 < lambda <= 2. Based on previous work [1], we provide formulae which allow to optimally (in terms of residual codeword error probability) exploit the erasure option of decoders with arbitrary lambda, if the decoder can be used z >= 1 times. We show that BMD decoders with z(BMD) decoding trials can result in lower residual codeword error probability than GS decoders with z(GS) trials, if z(BMD) is only slightly larger than z(GS). This is of practical interest since BMD decoders generally have lower computational complexity than GS decoders.

关键词： Approximation methods Concatenated codes Error probability guruswami-sudan algorithm Maximum likelihood decoding Reed-Solomon codes Reed-Solomon codes Reliability algebraic codes algebraic decoding computational complexity computational complexity decoding error statistics optimal threshold-based multitrial error/erasure decoding residual codeword error probability

来源：评论

学校读者我要写书评

暂无评论

VLSI Architectures for Soft-Decision Decoding of Reed-Solomon Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2011年第2期57卷 648-667页

作者： Ahmed, Arshad Koetter, Ralf Shanbhag, Naresh R. Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA Tech Univ Munich Inst Commun Engn D-80290 Munich Germany

Soft-decision decoding of Reed-Solomon codes delivers significant coding gains over classical minimum distance decoding. In this paper, we present architectures for polynomial interpolation and factorization, the two main steps of the soft-decoding algorithm. We introduce an algorithmic transformation for reducing the iterations required in generating the interpolation polynomial and present efficient architectures by sharing computations. We also describe algorithmic transformations for further reducing the interpolation and factorization latency. An area efficient, folded-pipelined version of the interpolation architecture is also described. Finally, we present an example of a Reed-Solomon soft decoder utilizing the presented architectures, having a 250 Mbps throughput.

关键词： Berlekamp-Massey algorithm guruswami-sudan algorithm Koetter-Vardy algorithm Reed-Solomon decoders soft-decision decoding VLSI architectures

来源：评论

学校读者我要写书评

暂无评论

Polynomial root finding over local rings and application to error correcting codes

引用

APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING 2013年第6期24卷 413-443页

作者： Berthomieu, Jeremy Lecerf, Gregoire Quintin, Guillaume Univ Paris 06 INRIA Paris Rocquencourt LIP6 POLSYS CNRS UMR 7606 LIP6 F-75252 Paris 5 France LIX CNRS UMR 7161 Lab Informat F-91128 Palaiseau France

This article is devoted to algorithms for computing all the roots of a univariate polynomial with coefficients in a complete commutative Noetherian unramified regular local domain, which are given to a fixed common finite precision. We study the cost of our algorithms, discuss their practical performances, and apply our results to the guruswami and sudan list decoding algorithm over Galois rings.

关键词： Polynomial root finding Galois ring List decoding guruswami-sudan algorithm

来源：评论

学校读者我要写书评

暂无评论

Prefactor Reduction of the guruswami-sudan Interpolation Step

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2014年第12期60卷 7451-7463页

作者： Senger, Christian Univ Toronto Edward S Rogers Sr Dept Elect & Comp Engn Toronto ON M5S 2J7 Canada

The most computationally intensive step of the guruswami-sudan list decoder for generalized Reed-Solomon codes is the formation of a bivariate interpolation polynomial. Complexity can be reduced if this polynomial has prefactors, i. e., factors of its univariate constituent polynomials that are independent of the received vector, and hence known a priori. For example, the well-known re-encoding projection due to Koetter et al. leads to one class of prefactors. This paper introduces so-called Sierpinski prefactors that result from the property that many binomial coefficients, which arise in the multiplicity constraints defined in terms of the Hasse derivative, are zero modulo the underlying field characteristic. It is shown that re-encoding prefactors and Sierpinski prefactors can be combined to achieve a significantly reduced guruswami-sudan interpolation step. In certain practically relevant cases, the introduction of Sierpinski prefactors reduces the number of unknown polynomial coefficients by an additional 10% or more (beyond the reduction due to re-encoding prefactors alone), without incurring additional computational effort at the decoder.

关键词： Generalized Reed-Solomon code guruswami-sudan algorithm list decoding polynomial interpolation Pascal triangle Sierpinski gasket binomial coefficient

来源：评论

学校读者我要写书评

暂无评论

Subspace Polynomials and Limits to List Decoding of Reed-Solomon Codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2010年第1期56卷 113-120页

作者： Ben-Sasson, Eli Kopparty, Swastik Radhakrishnan, Jaikumar Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel MIT Comp Sci & Artificial Intelligence Lab Cambridge MA 02139 USA Tata Inst Fundamental Res Mumbai 400005 Maharashtra India

We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson-guruswami-sudan bounds. In particular, we showthat for arbitrarily large fields F-N, vertical bar F-N vertical bar = N, for any delta is an element of (0, 1), and K = N-delta: Existence: there exists a received word omega(N) : F-N -> F-N that agrees with a super-polynomial number of distinct degree K polynomials on approximate to N-root 8 points each;Explicit: there exists a polynomial time constructible received word omega(N)' : vertical bar N -> vertical bar N that agrees with a super-polynomial number of distinct degree K polynomials, on approximate to 2(root log N) K points each. In both cases, our results improve upon the previous state of the art, which was approximate to N-delta/delta points of agreement for the existence case (proved by Justesen and Hoholdt), and approximate to 2N(delta) points of agreement for the explicit case (proved by guruswami and Rudra). Furthermore, for delta close to 1 our bound approaches the guruswami-sudan bound (which is root NK) and implies limitations on extending their efficient Reed-Solomon list decoding algorithm to larger decoding radius. Our proof is based on some remarkable properties of subspace polynomials. Using similar ideas, we then present a family of low rate codes that are efficiently list-decodable beyond the Johnson bound. This leads to an optimal list-decoding algorithm for the family of matrix-codes.

关键词： guruswami-sudan algorithm Johnson bound list decoding subspace polynomials Reed-Solomon codes

来源：评论

学校读者我要写书评

暂无评论

Fast factorization architecture in soft-decision Reed-Solomon decoding

引用

IEEE TRANSACTIONS ON VERY LARGE SCALE INTEGRATION (VLSI) SYSTEMS 2005年第4期13卷 413-426页

作者： Zhang, XM Parhi, KK Univ Minnesota Dept Elect & Comp Engn Minneapolis MN 55455 USA

Reed-Solomon (RS) codes are among the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to its hard-decision counterpart, soft-decision decoding offers considerably higher error-correcting capability. The recent development of soft-decision RS decoding algorithms makes their hardware implementations feasible. Among these algorithms, the Koetter-Vardy (KV) algorithm can achieve substantial coding gain for high-rate RS codes, while maintaining a polynomial complexity with respect to the code length. In the KV algorithm, the factorization step can consume a major part of the decoding latency. A novel architecture based on root-order prediction is proposed in this paper to speed up the factorization step. As a result, the time-consuming exhaustive-search-based root computation in each iteration level, except the first one, of the factorization step is circumvented with more than 99% probability. Using the proposed architecture, a speedup of 141% can be achieved over prior efforts for a (255, 239) RS code, while the area consumption is reduced to 31.4%.

关键词： Chien search factorization guruswami-sudan algorithm Koetter-Vardy (KV) algorithm Reed-Solomon (RS) code root-order prediction soft-decision decoding VLSI architecture

来源：评论

学校读者我要写书评

暂无评论

Algebraic soft-decision decoding of Reed-Solomon codes

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2003年第11期49卷 2809-2825页

作者： Koetter, R Vardy, A Univ Illinois Coordinated Sci Lab Urbana IL 61801 USA Univ Calif San Diego Dept Elect & Comp Engn La Jolla CA 92093 USA Univ Calif San Diego Dept Comp Sci La Jolla CA 92093 USA Univ Calif San Diego Ctr Wireless Commun La Jolla CA 92093 USA

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.

关键词： Berlekamp-Welch algorithm guruswami-sudan algorithm list decoding polynomial interpolation Reed-Solomon codes soft-decision decoding

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：