Lemma for Linear Feedback Shift Registers and DFTs Applied to Affine Variety Codes
Lemma for Linear Feedback Shift Registers and DFTs Applied to Affine Variety Codes
复制标题
DOI：
10.1109/tit.2014.2311042
复制
发表时间：
2012-11
影响因子：
2.5
通讯作者：
H. Matsui
中科院分区：
文献类型：
--
作者：
H. Matsui
在本文中，我们在代数编码理论中建立了一个引理，该理论经常出现在Reed-Solomon代码，代数几何代码和仿射品种代码的编码和解码中。可以通过从Gröbner的线性反馈移位寄存器和广义的逆离散傅立叶变换来表示，可以通过给出的典型反馈偏移寄存器来说明。 - 对双仿射品种的解码，我们表明系统的编码对应于一种仅擦除的特殊情况。在N和Q上具有一些轻度条件的O（QN2），其中N是代码长度，而Q是有限的场尺寸。
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 nonsystematic 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 Gröbner 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(n3) using Gaussian elimination to O(qn2) with some mild conditions on n and q, where n is the code length and q is the finite-field size.