On Finding Low Weight Vectors in Quadratic Residue Codes for $p = 8m - 1$
M. Karlin, F. J. Macwilliams · SIAM Journal on Applied Mathematics · 1973
p is a prime of the form $8m \pm 1$, and F is the field $GF( 2 )$. The quadratic residue code $\mathcal{A}( p )$ over F is a subspace of $F^p $ of dimension $( p + 1 )/ 2$, expressed in terms of a basis $\varepsilon _0 ,\varepsilon _1 , \cdots ,\varepsilon _{p - 1} $ of $F^p $. This code is invariant under the permutations $\pi $, $\mu _q $, where q is a generator of the quadratic residues of p, and \[ \begin{gathered} \varepsilon _i \pi = \varepsilon _{i + 1} , \hfill \\ \varepsilon _i \mu _q = \varepsilon _{iq} . \hfill \\ \end{gathered} \] The group $\langle \pi \rangle $ generated by $\pi $ is of order p and has no subgroups; however the group generated by $\mu _q $ is of order $( p - 1 )/2$ and may have nontrivial subgroups H. If it does,$\mathcal{A}( p )$ contains a subcode $\mathcal{A}_H $ which is (pointwise) fixed by H. It is much easier to compute the weight structure of $\mathcal{A}_H $ than that of $\mathcal{A}( p )$. Thus we obtain an upper bound for the minimum weight in .$\mathcal{A}( p )$. If $p = 8m - 1$, it is very easy to write down a set of generators for $\mathcal{A}_H $. This paper describes how to do it. We also give a number of examples, and some new upper bounds for the minimum weight in $\mathcal{A}( p )$ for various values ofp.