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

DOI10.1109/TIT.2014.2311042MaRDI QIDQ2986386zbMATH OpenOpenAlexWikidataFDO

Authors Hajime Matsui

Publication date 16 May 2017

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

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)

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.

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)