4
$\begingroup$

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

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ Do you look at the MacWilliams transform of $\mathcal{C}$? It does provide a lot of conditions on $\mathcal{C}^\perp$. $\endgroup$
    – Dima Pasechnik
    Commented Jul 5, 2012 at 4:12
  • $\begingroup$ 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}$. $\endgroup$
    – Jim Harrington
    Commented Jul 5, 2012 at 5:08
  • 1
    $\begingroup$ 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. $\endgroup$
    – Jyrki Lahtonen
    Commented Jul 5, 2012 at 13:25

1 Answer 1

Reset to default
2
$\begingroup$

In Weight Divisibility of Cyclic Codes, Highly nonlinear functions on $F_{2^m}$, and crosscorrelation of maximum length sequences, Canteaut, Charpin, and Dobbertin (Siam J. Discrete Math. 13(1):105-138) this problem was considered for Cyclic codes.

The classical McEliece's theorem states that a binary cyclic code $C$ is exactly $2^{\ell}$ divisible if and only if $\ell$ is the minimum integer such that $\ell+1$ nonzeros of $C$, i.e., roots of the parity check polynomial, have product 1 with repetition allowed.

There are indeed links between this problem and traces and m-sequence crosscorrelations, as suggested in the comments.

This work has been cited widely, and may help you pin down what's the current state of knowledge on divisibility.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.