\(\newcommand{\footnotename}{footnote}\)
\(\def \LWRfootnote {1}\)
\(\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}\)
\(\let \LWRorighspace \hspace \)
\(\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }\)
\(\newcommand {\mathnormal }[1]{{#1}}\)
\(\newcommand \ensuremath [1]{#1}\)
\(\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } \)
\(\newcommand {\setlength }[2]{}\)
\(\newcommand {\addtolength }[2]{}\)
\(\newcommand {\setcounter }[2]{}\)
\(\newcommand {\addtocounter }[2]{}\)
\(\newcommand {\arabic }[1]{}\)
\(\newcommand {\number }[1]{}\)
\(\newcommand {\noalign }[1]{\text {#1}\notag \\}\)
\(\newcommand {\cline }[1]{}\)
\(\newcommand {\directlua }[1]{\text {(directlua)}}\)
\(\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}\)
\(\newcommand {\protect }{}\)
\(\def \LWRabsorbnumber #1 {}\)
\(\def \LWRabsorbquotenumber "#1 {}\)
\(\newcommand {\LWRabsorboption }[1][]{}\)
\(\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }\)
\(\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }\)
\(\def \mathcode #1={\mathchar }\)
\(\let \delcode \mathcode \)
\(\let \delimiter \mathchar \)
\(\def \oe {\unicode {x0153}}\)
\(\def \OE {\unicode {x0152}}\)
\(\def \ae {\unicode {x00E6}}\)
\(\def \AE {\unicode {x00C6}}\)
\(\def \aa {\unicode {x00E5}}\)
\(\def \AA {\unicode {x00C5}}\)
\(\def \o {\unicode {x00F8}}\)
\(\def \O {\unicode {x00D8}}\)
\(\def \l {\unicode {x0142}}\)
\(\def \L {\unicode {x0141}}\)
\(\def \ss {\unicode {x00DF}}\)
\(\def \SS {\unicode {x1E9E}}\)
\(\def \dag {\unicode {x2020}}\)
\(\def \ddag {\unicode {x2021}}\)
\(\def \P {\unicode {x00B6}}\)
\(\def \copyright {\unicode {x00A9}}\)
\(\def \pounds {\unicode {x00A3}}\)
\(\let \LWRref \ref \)
\(\renewcommand {\ref }{\ifstar \LWRref \LWRref }\)
\( \newcommand {\multicolumn }[3]{#3}\)
\(\require {textcomp}\)
\(\newcommand {\tcbset }[1]{}\)
\(\newcommand {\tcbsetforeverylayer }[1]{}\)
\(\newcommand {\tcbox }[2][]{\boxed {\text {#2}}}\)
\(\newcommand {\tcboxfit }[2][]{\boxed {#2}}\)
\(\newcommand {\tcblower }{}\)
\(\newcommand {\tcbline }{}\)
\(\newcommand {\tcbtitle }{}\)
\(\newcommand {\tcbsubtitle [2][]{\mathrm {#2}}}\)
\(\newcommand {\tcboxmath }[2][]{\boxed {#2}}\)
\(\newcommand {\tcbhighmath }[2][]{\boxed {#2}}\)
\(\newcommand {\intertext }[1]{\text {#1}\notag \\}\)
\(\let \Hat \hat \)
\(\let \Check \check \)
\(\let \Tilde \tilde \)
\(\let \Acute \acute \)
\(\let \Grave \grave \)
\(\let \Dot \dot \)
\(\let \Ddot \ddot \)
\(\let \Breve \breve \)
\(\let \Bar \bar \)
\(\let \Vec \vec \)
\(\newcommand {\real }{\mathbb {R}} \)
\(\newcommand {\RR }{\mathbb {R}} \)
\(\newcommand {\ZZ }{\mathbb Z} \)
\(\newcommand {\F }{\mathbb F} \)
\(\newcommand {\Ham }{\mathrm {Ham}}\)
\(\newcommand {\PP }{\mathbb P}\)
\(\newcommand {\co }[1]{\overline {#1}} \)
\(\newcommand {\ul }[1]{\underline {#1}} \)
\(\newcommand {\bo }[1]{\mathbf {#1}} \)
\(\newcommand {\concat }[2]{[\, #1 \,|\, #2 \,]} \)
\(\newcommand {\Encode }{\texttt {ENCODE}} \)
\(\newcommand {\Decode }{\texttt {DECODE}} \)
\(\newcommand {\RM }{R} \)
\(\newcommand {\Rep }{\mathit {Rep}} \)
\(\renewcommand {\qedhere }{} \)
\(\newcommand {\tmm }[2]{\textbf {\color {#1}#2}}\)
\(\newcommand {\tcm }[3]{\left [\begin {smallmatrix}#1\\ #2\\ #3\end {smallmatrix}\right ]}\)
Week 4 Exercises (answers at end)
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).\)
[Answers to these exercises]
Notation: below, \(C\subseteq \F _q^n\) is a linear code, \(d(C)=d,\) and \(t=\left [\frac {d-1}{2}\right ].\)
-
Exercise 4.2. Prove that each vector \(\ul a\) of weight \(\le t\) in the space \(\F _q^n\) is a unique coset
leader (that is, \(w(\ul a)\) is strictly less than weights of all other vectors in its coset \(\ul a+C).\)
Hint. If \(\ul a\ne \ul b\) are in the same coset, show that \(d \le w(\ul a)+w(\ul b).\) Then use \(d-t>t.\)
[Answers to these exercises]
-
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(\ul 0),\) i.e., there as many cosets as vectors of weight \(\le 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 \(\le t.\)
[Answers to these exercises]
-
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
\(\mathit {BSC}(p)\) and argue whether the code is worth using for this channel, compared to transmitting unencoded information.
\[ G_1=\begin {bmatrix} 1&0 \\ 0&1 \end {bmatrix}, \qquad G_2=\begin {bmatrix} 1&0&1 \\ 0&1&1 \end {bmatrix}, \qquad G_3 = \begin {bmatrix} 1&0&1 &1&0\\
0&1&0&1&1 \end {bmatrix}. \]
[Answers to these exercises]
-
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)\)?
[Answers to these exercises]