Applications of Grobner Bases to Linear Codes.
Jeanne Fitzgerald · 1996
Put $A={\bf F}\sb{q}\lbrack x\sb1,\...,x\sb{s}\rbrack,$ and let I be an ideal of A. Let $P\sb1,\...,P\sb{n}$ be all the ${\bf F}\sb{q}$-rational points of $V(I)$. Define a map $\varphi:A/I\to{\bf F}\sbsp{q}{n}$ by $\varphi(\tilde f)=(f(P\sb1),\...,f(P\sb{n})),$ where f is any preimage of $\tilde f$ under the canonical map from A to $A/I.$ Let $\{\tilde f\sb{i}\vert i\in {\bf N}\}$ be a basis of $A/I$ as an ${\bf F}\sb{q}$-vector space. Define the affine variety code C and its dual $C\sp\perp$ by$$C=\varphi(\langle\tilde f\sb1,\...,\tilde f\sb{m}\rangle);$$C$\sp\perp$ is the orthogonal complement of C with respect to the usual inner product in ${\bf F}\sbsp{q}{n}$. We show that any linear code can be expressed as an affine variety code. When a code C is represented as an affine variety code, problems of decoding and finding the minimum distance of C may be expressed as questions about polynomial ideals. Using the theory of Grobner bases, along with computer programs that calculate Grobner bases, we show how to decode and find the minimum distance of any linear code.