Lemma for Linear Feedback Shift Registers and DFTs Applied to Affine Variety Codes

DOI10.1109/TIT.2014.2311042zbMATH Open1360.94427arXiv1211.4728OpenAlexW2074377659WikidataQ124810876 ScholiaQ124810876MaRDI QIDQ2986386FDOQ2986386

Authors: Hajime Matsui 

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: In this paper, we establish a lemma in algebraic coding theory that frequently appears in the encoding and decoding of, e.g., Reed-Solomon codes, algebraic geometry codes, and affine variety codes. Our lemma corresponds to the non-systematic encoding of affine variety codes, and can be stated by giving a canonical linear map as the composition of an extension through linear feedback shift registers from a Grobner basis and a generalized inverse discrete Fourier transform. We clarify that our lemma yields the error-value estimation in the fast erasure-and-error decoding of a class of dual affine variety codes. Moreover, we show that systematic encoding corresponds to a special case of erasure-only decoding. The lemma enables us to reduce the computational complexity of error-evaluation from O(n^3) using Gaussian elimination to O(qn^2) with some mild conditions on n and q, where n is the code length and q is the finite-field size.

Full work available at URL: https://arxiv.org/abs/1211.4728

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Applications to coding theory and cryptography of arithmetic geometry (14G50) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

This page was built for publication: Lemma for Linear Feedback Shift Registers and DFTs Applied to Affine Variety Codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2986386)