An h-interleaved one-point Hermitian code is a direct sum of h many one-point Hermitian codes, where errors are assumed to occur at the same positions in the constituent codewords. We propose a new partial decoding al...
详细信息
An h-interleaved one-point Hermitian code is a direct sum of h many one-point Hermitian codes, where errors are assumed to occur at the same positions in the constituent codewords. We propose a new partial decoding algorithm for these codes that can decodeunder certain assumptionsan error of relative weight up to 1-(, where k is the dimension, n the length, and g the genus of the code. Simulation results for various parameters indicate that the new decoder achieves this maximal decoding radius with high probability. The algorithm is based on a recent generalization of improved power decoding to interleaved Reed-Solomon codes, does not require an expensive root-finding step, and improves upon the previous best decoding radius at all rates. In the special case h=1, we obtain an adaption of the improved power decoding algorithm to one-point Hermitian codes, which for all simulated parameters achieves a similar observed failure probability as the Guruswami-Sudan decoder above the latter's guaranteed decoding radius.
power decoding is a partial decoding paradigm for arbitrary algebraic geometry codes for decoding beyond half the minimum distance, which usually returns the unique closest codeword, but in rare cases fails to return ...
详细信息
ISBN:
(纸本)9781538682098
power decoding is a partial decoding paradigm for arbitrary algebraic geometry codes for decoding beyond half the minimum distance, which usually returns the unique closest codeword, but in rare cases fails to return anything. The original version decodes roughly up to the Sudan radius, while an improved version decodes up to the Johnson radius, but has so far been described only for Reed-Solomon and one-point Hermitian codes. In this paper we show how the improved version can be applied to any algebraic geometry code.
Known properties of cyclic codes are used to give a unified description of many classical decoding algorithms for Reed-Solomon codes up to half the minimum distance. This description allows also simplified proofs for ...
详细信息
Known properties of cyclic codes are used to give a unified description of many classical decoding algorithms for Reed-Solomon codes up to half the minimum distance. This description allows also simplified proofs for these decoders. Further, a novel decoding algorithm is derived using these properties directly and variants of a new error/erasure decoding algorithm are given. For decoding beyond half the minimum distance, a basis of all solutions for decoding is derived. This basis allows to use side information in order to decode beyond half the minimum distance. Other methods where this basis can be used are power decoding, also known as virtual syndrome extension, where additional equations are generated by taking powers of the received symbols, and interleaved Reed-Solomon codes. The extended Euclidean algorithm, which calculates the greatest common divisor, plays an essential role in many presented methods.
We present a new decoding algorithm based on error locating pairs and correcting an amount of errors exceeding half the minimum distance. When applied to Reed-Solomon or algebraic geometry codes, the algorithm is a re...
详细信息
We present a new decoding algorithm based on error locating pairs and correcting an amount of errors exceeding half the minimum distance. When applied to Reed-Solomon or algebraic geometry codes, the algorithm is a reformulation of the so-calledpower decodingalgorithm. Asymptotically, it corrects errors up to Sudan's radius. In addition, this new framework applies to any code benefiting from an error locating pair. Similarly to Pellikaan's and Kotter's approach for unique algebraic decoding, our algorithm provides a unified point of view for decoding codes with an algebraic structure beyond the half minimum distance. It permits to get an abstract description of decoding using only codes and linear algebra and without involving the arithmetic of polynomial and rational function algebras used for the definition of the codes themselves. Such algorithms can be valuable for instance for cryptanalysis to construct a decoding algorithm of a code without having access to the hidden algebraic structure of the code.
We present the first two sub-quadratic complexity decoding algorithms for one-point Hermitian codes. The first is based on a fast realization of the Guruswami-Sudan algorithm using state-of-the-art algorithms from com...
详细信息
We present the first two sub-quadratic complexity decoding algorithms for one-point Hermitian codes. The first is based on a fast realization of the Guruswami-Sudan algorithm using state-of-the-art algorithms from computer algebra for polynomial-ring matrix minimization. The second is a power decoding algorithm: an extension of classical key equation decoding which gives a probabilistic decoding algorithm up to the Sudan radius. We show how the resulting key equations can be solved by the matrix minimization algorithms from computer algebra, yielding similar asymptotic complexities.
We model the decoding of Interleaved Chinese Remainder codes as that of finding a short vector in a Z-lattice. Using the LLL algorithm, we obtain an efficient decoding algorithm, correcting errors beyond the unique de...
详细信息
ISBN:
(纸本)9781479904464
We model the decoding of Interleaved Chinese Remainder codes as that of finding a short vector in a Z-lattice. Using the LLL algorithm, we obtain an efficient decoding algorithm, correcting errors beyond the unique decoding bound and having nearly linear complexity. The algorithm can fail with a probability dependent on the number of errors, and we give an upper bound for this. Simulation results indicate that the bound is close to the truth. We apply the proposed decoding algorithm for decoding a single CR code using the idea of "power" decoding, suggested for Reed-Solomon codes. A combination of these two methods can be used to decode low-rate Interleaved Chinese Remainder codes.
暂无评论