Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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)).

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$.

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?

So far, I have identified the following examples:

distance 2: $\cal{C}$ = [8,1,8] repetition code, $\cal{C}^\perp$ = [8,7,2]

distance 3: $\cal{C}$ = [15,4,8] Reed-Muller code, $\cal{C}^\perp$ = [15,11,3] Hamming code

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.

Here is a link to the MacWilliams identity (which I am having problems putting into a comment).

share|improve this question
Do you look at the MacWilliams transform of $\mathcal{C}$? It does provide a lot of conditions on $\mathcal{C}^\perp$. –  Dima Pasechnik Jul 5 '12 at 4:12
Thanks. It's been a long while since I've played around with the MacWilliams identity, and that does look very informative for finding the minimum distance of $\cal{C}^\perp$, namely by finding the first nonzero term for $x$ in the expansion of the weight enumerator $W(\cal{C};y−x,y+x)$. I suppose the better question then may be how to first identify/construct a candidate code $\cal{C}$. –  Jim Harrington Jul 5 '12 at 5:08
Some trace codes will surely have this property. A theorem of Ax has been used in the past to give precise information about divisibility of weights by a power of two. IIRC Oscar Moreno & P.V. Kumar have published something about this. I would begin by searching for applications of Ax's theorem to this. Trace codes have typically a relatively low rate. Therefore the dual are correspondingly very large and have relatively small minimum Hamming weights. –  Jyrki Lahtonen Jul 5 '12 at 13:25

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.