Power decoding Reed-Solomon codes up to the Johnson radius
From MaRDI portal
Abstract: Power decoding, or "decoding using virtual interleaving" is a technique for decoding Reed--Solomon codes up to the Sudan radius. Since the method's inception, it has been an open question if it is possible to use this approach to decode up to the Johnson radius -- the decoding radius of the Guruswami--Sudan algorithm. In this paper we show that this can be done by incorporating a notion of multiplicities. As the original Power decoding, the proposed algorithm is a one-pass algorithm: decoding follows immediately from solving a shift-register type equation, which we show can be done in quasi-linear time. It is a "partial bounded-distance decoding algorithm" since it will fail to return a codeword for a few error patterns within its decoding radius; we investigate its failure behaviour theoretically as well as give simulation results. This is an extended version where we also show how the method can be made faster using the re-encoding technique or a syndrome formulation.
Recommendations
- Power Decoding of Reed–Solomon Codes Revisited
- Combinatorial list-decoding of Reed-Solomon codes beyond the Johnson radius
- Decoding of Reed Solomon codes beyond the error-correction bound
- Efficient decoding of Reed-Solomon codes beyond half the minimum distance
- scientific article; zbMATH DE number 1461545
- On the complexity of decoding Reed-Solomon codes (Corresp.)
- Improvements on the Johnson bound for Reed-Solomon codes
- The decoding of extended Reed-Solomon codes
- On the covering radius of Reed-Solomon codes
- Bounds on the List-Decoding Radius of Reed--Solomon Codes
Cites work
- scientific article; zbMATH DE number 3167429 (Why is no real title available?)
- scientific article; zbMATH DE number 3711820 (Why is no real title available?)
- scientific article; zbMATH DE number 1461545 (Why is no real title available?)
- scientific article; zbMATH DE number 2151192 (Why is no real title available?)
- scientific article; zbMATH DE number 822685 (Why is no real title available?)
- A New Algorithm for Decoding Reed-Solomon Codes
- A Uniform Approach for the Fast Computation of Matrix-Type Padé Approximants
- A general module theoretic framework for vector M-Padé and matrix rational interpolation
- A linear algebraic approach to multisequence shift-register synthesis
- A method for solving key equation for decoding goppa codes
- Algebraic coding theory
- Algebraic soft-decision decoding of reed-solomon codes
- Algorithms for Simultaneous Padé Approximations
- An Interpolation Procedure for List Decoding Reed–Solomon Codes Based on Generalized Key Equations
- Approximate common divisors via lattices
- Decoding interleaved Reed-Solomon codes beyond their joint error-correcting capability
- Decoding of Reed Solomon codes beyond the error-correction bound
- Efficient Interpolation in the Wu List Decoding Algorithm
- Efficient decoding of Reed-Solomon codes beyond half the minimum distance
- Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations
- Fast skew-feedback shift-register synthesis
- Faster Algorithms for Multivariate Interpolation With Multiplicities and Simultaneous Polynomial Approximations
- High-order lifting and integrality certification
- Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
- Improved decoding of Reed-Solomon and algebraic-geometry codes
- Improved power decoding of interleaved one-point Hermitian codes
- Introduction to Coding Theory
- Key equations for list decoding of Reed-Solomon codes and how to solve them
- Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes
- List decoding of Hermitian codes using Gröbner bases
- List decoding of Reed-Solomon codes from a Gröbner basis perspective
- New List Decoding Algorithms for Reed–Solomon and BCH Codes
- On Rational Interpolation-Based List-Decoding and List-Decoding Binary Goppa Codes
- On lattice reduction for polynomial matrices
- On the key equation
- Power Decoding of Reed–Solomon Codes Revisited
- Solving structured linear systems with large displacement rank
- Sub-Quadratic Decoding of One-Point Hermitian Codes
- Syndrome Decoding of Reed–Solomon Codes Beyond Half the Minimum Distance Based on Shift-Register Synthesis
- Triangular \(x\)-basis decompositions and derandomization of linear algebra algorithms over \(K[x]\)
- VLSI Architectures for Soft-Decision Decoding of Reed–Solomon Codes
Cited in
(4)
This page was built for publication: Power decoding Reed-Solomon codes up to the Johnson radius
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1783708)
