A problem about a MacWilliams' identity

250 Views Asked by At

Problem. Let $C$ be a binary $[n, k]$ code with a generator matrix that has no column being the all zero vector. Show that the sum of all the weights of the codewords in $C$ is $n 2^{k-1}$ (Do this problem in two different ways, the first not using MacWilliams' identities; the second using MacWilliams' identities.)

I succeeded in not using the MacWilliams identites, but it took me a long time to think about how to use these identites for calculating the sum of all the weights of the codewords.

Here is some concept about coding and the MacWilliams' identites from the textbook A Course in Combinatorics by J.H. van Lint & R.M. Wilson:

If $C$ is a $q$ -ary $[n, k]$ (linear) code, and if $A_{i}$ denotes the number of codewords of weight $i$ in $C$, then $A(z)=\sum\limits_{i=0}^n A_i z^i$ is called the weight enumerator of C.

Theorem. Let $C$ be an $[n, k]_q$ code with weight enumerator $A(z)$ and let $B(z)$ be the weight enumerator of $C^\perp$. Then $$ B(z)=q^{-k}(1+(q-1) z)^n A\left(\frac{1-z}{1+(q-1) z}\right) $$ In particular, for binary code: $$B(z)=2^{-k}(1+z)^n A\left(\frac{1-z}{1+z}\right)$$

Any help is appreciated.

1

There are 1 best solutions below

0
On BEST ANSWER

If the code has weight enumerator $B(z)=\sum_{i=0}^n B_iz^i$, then $B_i$ is the number of codewords of weight $i$ and thus the total weight of all the codewords is just $\sum_i iB_i = B^\prime(1)$, where $B^\prime(z) = \sum_{i=1}^n iB_iz^{i-1}$ is the formal derivative of $B(z)$.

You are told that the code has the property that no column of its generator matrix $G$ has a column of zeroes. But $G$ is the parity check matrix of the dual code (whose weight enumerator is $A(z)$). Now, if a parity-check matrix has a column that is identically zero, then the minimum weight of that code is $1$ since $00\cdots 00100\cdots 00$ is a codeword of the code. But we are told that $G$ has no zero column and so the dual code has no codewords of weight $1$. Thus, in the MacWilliams identity which I have rewritten to make the dual code of dimension $n-k$, we get \begin{align}B(z) &= 2^{k-n}\sum_{i=1}^n A_i(1+z)^{n-i}(1-z)^I\\& = 2^{k-n}\big((1+z)^n + A_1(1+z)^{n-1}(1-z) + A_2 (1+z)^{n-2}(1-z)^2 + \cdots \big)\tag{1} \end{align} we have that $A_1=0$. So, the formal derivative of $B(z)$ is the same as the formal derivative of the right side of $(1)$. I won't write this down in detail because we don't really need all the details; all we need is the value of $B^\prime(1)$ and after taking the formal derivative of the sum on the right, all the terms in the derivative except the first will have a $(1-z)$ factor in them so that $$B^\prime(1) = 2^{k-n} n(1+z)^{n-1}\big\vert_{z=1} = n2^{k-1}.$$