Fast generalized minimum-distance decoding of algebraic-geometry and Reed-Solomon codes

1996/05/01 by R. Kotter, Ralf Kötter · 4 citations
Computer Science · Engineering · #Coding theory and cryptography #Error Correcting Code Techniques #graph theory and CDMA systems

paper · doi:10.1109/18.490540

Abstract

Generalized minimum-distance (GMD) decoding is a standard soft-decoding method for block codes. We derive an efficient general GMD decoding scheme for linear block codes in the framework of error-correcting pairs. Special attention is paid to Reed-Solomon (RS) codes and one-point algebraic-geometry (AG) codes. For RS codes of length n and minimum Hamming distance d the GMD decoding complexity turns out to be in the order O(nd), where the complexity is counted as the number of multiplications in the field of concern. For AG codes the GMD decoding complexity is highly dependent on the curve in consideration. It is shown that we can find all relevant error-erasure-locating functions with complexity O(o/sub 1/nd), where o/sub 1/ is the size of the first nongap in the function space associated with the code. A full GMD decoding procedure for a one-point AG code can be performed with complexity O(dn/sup 2/).

Cited by

• Improved Constructions of Linear Codes for Insertions and Deletions
• Decoding Generalized Reed-Solomon Codes and Its Application to RLCE\n Encryption Schemes
• Faster Algorithms for Multivariate Interpolation with Multiplicities and Simultaneous Polynomial Approximations
• Adaptive Single-Trial Error/Erasure Decoding of Reed-Solomon Codes

Related

• On error distance of received words with fixed degrees to Reed-Solomon code
• Algebraic Soft-Decision Decoding of Reed-Solomon Codes Using Bit-level Soft Information
• Power Error Locating Pairs
• Quasi-linear time decoding of RS and AG codes for burst errors up to the Singleton bound
• Reed-Solomon Subcodes with Nontrivial Traces: Distance Properties and Soft-Decision Decoding