What odd-length binary codes have Hamming weights restricted to be multiples of eight? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T04:00:10Z http://mathoverflow.net/feeds/question/101362 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/101362/what-odd-length-binary-codes-have-hamming-weights-restricted-to-be-multiples-of-e What odd-length binary codes have Hamming weights restricted to be multiples of eight? Jim Harrington 2012-07-05T03:08:00Z 2012-07-05T06:07:37Z <p>Let $G$ be a $k$ by $n$ binary matrix with row vectors $\lbrace \vec{x}_j {\rbrace} _{j=1}^k$. We can interpret $G$ as a generator matrix of a linear $[n,k]$ code $\cal{C}$ whose codewords consist of all linear combinations of these vectors (with arithmetic defined for GF(2)).</p> <p>Let $H$ be a $(n-k)$ by $n$ binary matrix with row vectors $\lbrace \vec{y}_j {\rbrace} _{j=1}^{n-k}$ where $\vec{x}_a \cdot \vec{y}_b = 0~\forall a, b$. We can interpret $H$ as a parity check matrix for code $\cal{C}$. Alternatively, we can treat $H$ as the generator for the dual $[n,n-k]$ code $\cal{C}^\perp$.</p> <p>If we require both that $n$ be odd and that all codewords of $\cal{C}$ (not just the rows of $G$) have a Hamming weight $w_j \equiv 0$ (mod 8), what minimum distances are possible for $\cal{C}^\perp$? What families of codes satisfy these properties?</p> <p>So far, I have identified the following examples:</p> <p>distance 2: $\cal{C}$ = [8,1,8] repetition code, $\cal{C}^\perp$ = [8,7,2]</p> <p>distance 3: $\cal{C}$ = [15,4,8] Reed-Muller code, $\cal{C}^\perp$ = [15,11,3] Hamming code</p> <p>My previous example (based on the Golay code) for distance 4 was incorrect. It was only distance 3, and in fact I have repeatedly failed to find a good candidate with distance larger than 3.</p> <p>Here is a link to the <a href="http://en.wikipedia.org/wiki/Enumerator_polynomial" rel="nofollow">MacWilliams identity</a> (which I am having problems putting into a comment).</p>