Paper Info
Title
Lemma for Linear Feedback Shift Registers and DFTs Applied to Affine Variety Codes
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.
Year
DOI
Venue
2014
10.1109/TIT.2014.2311042
IEEE Transactions on Information Theory
Keywords
DocType
Volume
Gaussian processes,Reed-Solomon codes,algebraic codes,computational complexity,decoding,discrete Fourier transforms,feedback,geometric codes,shift registers,DFT,Gaussian elimination,Gröbner basis,Reed-Solomon codes,affine variety codes,algebraic coding theory,algebraic geometry codes,computational complexity,erasure-and-error decoding,erasure-only decoding,generalized inverse discrete Fourier transform,linear feedback shift registers,nonsystematic encoding,Berlekamp??Massey??Sakata algorithm,Gr??bner bases,evaluation codes from order domains,fast decoding,systematic encoding
Journal
abs/1211.4728
Issue
ISSN
Citations 
5
0018-9448
0
PageRank 
References 
Authors
0.34
20
1
Name
Order
Citations
PageRank
Hajime Matsui1188.14