Week 4 Exercises — solutions

Version 2023-11-04. These exercises in PDF

Exercise 4.1. Write down the weight enumerator of $Rep (n, F_{2}),$ more generally of $Rep (n, F_{q}) .$

Answer to E4.1. [These exercises without answers]

$Rep (n, F_{2})$ has one codevector of weight $0$ and one codevector of weight $n .$ Hence $W_{Rep (n, F_{2})} (x, y) = x^{n} + y^{n} .$

Exercise: show that $W_{Rep (n, F_{q})} (x, y) = x^{n} + (q - 1) y^{n} .$

Notation: below, $C \subseteq F_{q}^{n}$ is a linear code, $d (C) = d,$ and $t = [\frac{d - 1}{2}] .$

Exercise 4.2. Prove that each vector $\underset{―}{a}$ of weight $\leq t$ in the space $F_{q}^{n}$ is a unique coset leader (that is, $w (\underset{―}{a})$ is strictly less than weights of all other vectors in its coset $\underset{―}{a} + C) .$

Hint. If $\underset{―}{a} \neq \underset{―}{b}$ are in the same coset, show that $d \leq w (\underset{―}{a}) + w (\underset{―}{b}) .$ Then use $d - t > t .$

Answer to E4.2. [These exercises without answers]

If $\underset{―}{a}, \underset{―}{b}$ are in the same coset, then by properties of cosets, $\underset{―}{c} := \underset{―}{a} - \underset{―}{b}$ is a codevector. If $\underset{―}{a} \neq \underset{―}{b}$ then $\underset{―}{c} \neq 0$ and so $d \leq w (\underset{―}{c}) = w (\underset{―}{a} - \underset{―}{b}) = d (\underset{―}{a}, \underset{―}{b}) .$ By the triangle inequality, $d (\underset{―}{a}, \underset{―}{b}) \leq d (\underset{―}{a}, \underset{―}{0}) + d (\underset{―}{0}, \underset{―}{b}) = w (\underset{―}{a}) + w (\underset{―}{b}) .$ Thus, $d \leq w (\underset{―}{a}) + w (\underset{―}{b})$ as claimed.

Now assume $w (\underset{―}{a}) \leq t .$ Then $w (\underset{―}{b}) \geq d - w (\underset{―}{a}) \geq d - t .$ But $t < \frac{d}{2}$ so $d - t > t .$ We have $w (\underset{―}{b}) \geq d - t > t \geq w (\underset{―}{a}) .$ This shows that $\underset{―}{a}$ has strictly minimal weight among the vectors in its coset, and so is the unique coset leader.

Exercise 4.3 (important fact about perfect linear codes — needed for exam).

Assume $C$ is perfect. Use the Hamming bound to show that the number of cosets equals $# S_{t} (\underset{―}{0}),$ i.e., there as many cosets as vectors of weight $\leq t$ in the space $F_{q}^{n} .$ Deduce that every coset has a unique coset leader, and that the coset leaders are exactly the vectors of weight $\leq t .$

Answer to E4.3. [These exercises without answers]

By the previous exercise, the vectors $\underset{―}{a} \in S_{t} (\underset{―}{0})$ are unique coset leaders of $# S_{t} (\underset{―}{0})$ distinct cosets. The total number of cosets is $\frac{q^{n}}{# C} .$

Now if $C$ is perfect, then $# C = \frac{q^{n}}{# S_{t} (\underset{―}{0})}$ (the right-hand side is the Hamming bound), and so $\frac{q^{n}}{# C} = # S_{t} (\underset{―}{0}) .$ Thus if $C$ is perfect, cosets with a unique coset leader of weight $\leq t$ exhaust all cosets, as claimed.

Exercise 4.4 (not done in tutorial). Find standard arrays for binary codes with each of the following generator matrices. For each code, determine whether every coset has a unique coset leader (i.e., if there is exactly one coset leader in each coset). Find the probability of an undetected / uncorrected error for $BSC (p)$ and argue whether the code is worth using for this channel, compared to transmitting unencoded information.

$G_{1} = [\begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}], G_{2} = [\begin{matrix} 1 & 0 & 1 \\ 0 & 1 & 1 \end{matrix}], G_{3} = [\begin{matrix} 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 0 & 1 & 1 \end{matrix}] .$

Answer to E4.4. [These exercises without answers]

$G_{1}$ generates the trivial binary code of length $2.$ Because the code is the whole space $F_{2}^{2},$ its standard array consists of one row:

$00 01 10 11$

(the order of the codevectors after $00$ is arbitrary). The only coset is the trivial coset which has only one coset leader, $00.$

$G_{2}$ generates $E_{3},$ the even weight code of length $3.$ It has $4$ codevectors and $2$ cosets:

$\begin{matrix} 000 & 101 & 011 & 110 \\ 001 & 100 & 010 & 111 \end{matrix}$

Note that the non-trivial coset has three coset leaders; any of them could be put in column 1.

$G_{3} :$ list all the $4$ codevectors and then use the algorithm for constructing the standard array. One possible answer is given below:

$\begin{matrix} 00000 & 10110 & 01011 & 11101 \\ 10000 & 00110 & 11011 & 01101 \\ 01000 & 11110 & 00011 & 10101 \\ 00100 & 10010 & 01111 & 11001 \\ 00010 & 10100 & 01001 & 11111 \\ 00001 & 10111 & 01010 & 11100 \\ 11000 & 01110 & 10011 & 00101 \\ 01100 & 11010 & 00111 & 10001 \end{matrix}$

Coset leaders of weight $0$ and $1$ are the only coset leaders in their cosets. Coset leaders of weight $2$ are not unique: e.g., $11000$ and $00101$ are coset leaders of the same coset.

Error probabilities. The code generated by $G_{1}$ is the trivial code, so using it is the same as sending unencoded information.

The code generated by $G_{2}$ has weight enumerator $W_{E_{3}} (x, y) = x^{3} + 3 x y^{2} .$ Hence an undetected error occurs with probability

$P_{undetect} (E_{3}) = W_{E_{3}} (1 - p, p) - (1 - p)^{3} = 3 (1 - p) p^{2} \sim 3 p^{2} .$

Note that this is of the same order as $p^{2}$ but at a rate of $2 / 3$ (recall the code considered in the chapter with worse rate $1 / 2) .$

The probability of an uncorrected error here is $1 - P_{corr} (E_{3}) = 1 - (α_{0} (1 - p)^{3} + α_{1} p (1 - p)^{2})$ where $α_{0} = 1$ (one coset leader of weight $0)$ and $α_{1} = 1$ (one coset leader of weight $1)$ . We have $1 - P_{corr} (E_{3}) = 1 - ((1 - p)^{3} + p (1 - p)^{2}) = 1 - (1 - p + p) (1 - p)^{2} = 1 - (1 - p)^{2} \sim 2 p .$

The code $E_{3}$ does not improve the probability of incorrect decoding. Indeed, Hamming’s theory says that $E_{3}$ has no error-correcting capability and can only be used for error detection.

The code generated by $G_{3}$ has weight enumerator $x^{5} + 2 x^{2} y^{3} + x y^{4} .$ Hence

$P_{undetect} = 2 (1 - p)^{2} p^{3} + (1 - p) p^{4} \sim 2 p^{3} .$

If $p = 0.01,$ this is $\approx 2 \times 10^{- 6},$ which is 5,000 times better than without encoding.

Furthermore, looking at the coset leaders, we find one coset leader of weight 0, $α_{0} = 1;$ five coset leaders of weight 1, $α_{1} = 5;$ two coset leaders of weight 2, $α_{2} = 2.$ This gives

$\begin{aligned} 1 - P_{corr} & = 1 - (α_{0} (1 - p)^{5} + α_{1} p (1 - p)^{4} + α_{2} p^{2} (1 - p)^{3}) \\ = 1 - ((1 - p)^{2} + 5 p (1 - p) + 2 p^{2}) (1 - p)^{3} \\ = 8 p^{2} - 14 p^{3} + 9 p^{4} - 2 p^{5} \sim 8 p^{2} . \end{aligned}$ If $p = 0.01,$ incorrect decoding occurs with probability $\approx 8 \times 10^{- 4},$ which is 12.5 times better than without encoding.

Of course, this improvement in reliability comes at a price: the rate of the code is only $0.4,$ meaning that we have to transmit $2.5$ times as much information.

Exercise 4.5 (more weight enumerators — not done in tutorial). (a) As usual, let $W_{C} (x, y)$ denote the weight enumerator of a $q$ -ary linear code $C .$ Show that $W_{C} (1, 0) = 1$ and that $W_{C} (1, 1) = q^{k}$ where $k = \dim C .$

(b) Show that the weight enumerator of the trivial binary code $F_{2}^{n}$ is $W_{F_{2}^{n}} (x, y) = (x + y)^{n} .$ Can you write $W_{F_{q}^{n}} (x, y)$ in a similar form?

(c) Write down $W_{E_{3}} (x, y) .$ Can you suggest a compact way to write $W_{E_{n}} (x, y)$ ?

Answer to E4.5. [These exercises without answers]

(a) Recall $W_{C} (x, y) = \sum_{\underset{―}{c} \in C} x^{n - w (\underset{―}{c})} y^{w (\underset{―}{c})} .$ If $y = 0,$ the only non-zero term in this sum is the term without $y$ which corresponds to the (unique) zero codevector of the linear code $C;$ thus, $W_{C} (x, 0) = x^{n}$ and $W_{C} (1, 0) = 1.$ Also, $W_{C} (1, 1) = \sum_{\underset{―}{c} \in C} 1 = # C = q^{k} .$

(b) To work out $W_{F_{q}^{n}} (x, y),$ write it in the form $W_{F_{q}^{n}} (x, y) = \sum_{i = 0}^{n} A_{i} x^{n - i} y^{i}$ where $A_{i} = # {\underset{―}{v} \in F_{q}^{n} : w (\underset{―}{v}) = i} .$ Note that $w (\underset{―}{v}) = d (\underset{―}{v}, \underset{―}{0}),$ and in the proof of the Hamming bound we calculated the number of words at distance $i$ from $\underset{―}{0}$ (or from any other fixed vector) to be $(\binom{n}{i}) (q - 1)^{i} .$ Hence

$W_{F_{q}^{n}} (x, y) = \sum_{i = 0}^{n} (\binom{n}{i}) (q - 1)^{i} x^{n - i} y^{i} = (x + (q - 1) y)^{n} .$

(c) The even weight code $E_{3}$ is ${000, 011, 101, 110},$ so that $W_{E_{3}} (x, y) = x^{3} + 3 x y^{2} .$ The weight enumerator of $E_{n}$ will be obtained in the lectures as an application of the MacWilliams identity.