Bounds on collaborative decoding of interleaved Hermitian codes and virtual extension (Q2436580): Difference between revisions

The purpose of the paper is the study of some problems related to the decoding of interleaved Hermitian codes. The author points out that the decoding of interleaved algebraic-geometric codes ``had been neglected by the community'' and he mentions as only antecedent a paper of \textit{A. Brown} et al. [Lecture Notes in Computer Science 3796, 37--46 (2005; Zbl 1122.94058)]. In the author's words ``we present here a conceptually simple approach to collaborative decoding of interleaved Hermitian (IH) codes that achieves a larger decoding radius than the algorithm by Brown et al. and a smaller failure probability for the same error weight.'' Section 2 reminds codes defined over Hermitian curves and a division decoding algorithm due to the author et al. [``Solving the key equation for Hermitian codes with a division algorithm'', in: IEEE International Symposium on Information Theory 2011, 1008--1012 (2011)] and Section 3 describes a modification of that algorithm allowing to find a basis for all solutions of the key equation of a given weight. The core Section 4 deals with the idea of collaborative decoding of interleaved codes and, with the help of the division algorithm, finds the maximum decoding radius for IH codes. It also finds the failure probability (theorem 3) and the computational complexity of the proposed decoding. Finally, generalizing to (non-interleaved) Hermitian codes the idea of virtual extension for Reed-Solomon codes, Section 5 gives an upper bound on the code rate below which virtual extension can increase the decoding radius.