\documentclass{article}
\usepackage{a4wide}
\usepackage[utf8x]{inputenc}
\usepackage[english]{babel}
%\usepackage{graphicx}
%\usepackage{clrscode}
\usepackage{fancyhdr}
\pagestyle{fancy}
\newcounter{priklad}
\newcommand{\pr}{\newpage\noindent\stepcounter{priklad}}
\headheight 23.2pt
\fancyfoot{}
\lhead{Jiří Slabý, 98734}
\chead{\textbf{Error-correcting codes, cryptography and \\ cryptographical
protocols (IV054)}}
\rhead{Exercise 2.\arabic{priklad}}
\renewcommand{\baselinestretch}{1.17}
\renewcommand{\labelenumi}{(\alph{enumi})}
\begin{document}
\pr \indent % 1. priklad
No it isn't a linear code. The code has 36 codewords, it is $q^k=6^2$, $GF(6)$
code. But $q$
has to be power of a prime and it isn't. The code could be $GF(7)$ with some
more words (49). But as is, it isn't a linear code, as I wrote.
\pr % 2. priklad
When the code $C$ is self-dual, the proof is straightforward.
Otherwise, we define $C^\perp$ as
\[C^\perp = \{ \textbf v\in F^n|\textbf v\cdot \textbf c=0,\forall\textbf
c\in C\}\]
where $C,\ C^\perp\subseteq F^n$. $C$ is linear, hence
satisfies these 2 conditions:
\begin{enumerate}
\item $\textbf u + \textbf v\in C\ \forall \textbf u,\,\textbf v \in C$
\item $a\textbf u\in C\ \forall \textbf u\in C,\,a\in GF(q)$
\end{enumerate}
We have to prove, if these conditions are satisfied in $C^\perp$. So:
\begin{enumerate}
\item Suppose, that exists some $\textbf x\in C^\perp$ so that for any
$\textbf u\in C^\perp$, $\textbf x+\textbf u\notin C^\perp$. We
know, that each element from $C$ multiplied by this vector is 0. Ditto
for $\textbf u$, i. e. $\textbf x\textbf c=0$ and $\textbf u\textbf c=0$
for some $c$. Choose some $c\in C$ and fix it for further consideration.
Now, $\textbf u\textbf c+\textbf v\textbf c=0$ and $\textbf u\textbf
c+\textbf v\textbf c=u_1c_1+x_1c_1+u_2c_2+x_2c_2+\ldots+u_qc_q+x_qc_q=
(u_1+x_1)c_1+(u_2+x_2)c_2+\ldots+(u_q+x_q)c_q=(\textbf u+\textbf
x)\textbf c$, where $\textbf u=(u_1,u_2,\ldots,u_q)$, ditto for
$\textbf x$ and $\textbf c$. But it is, that is against our presumtion.
This condition is satisfied.
\item We can write $a\textbf u=\textbf u+\textbf u+\ldots+\textbf u$,
where count of $\textbf u$ is $a$. Because (a) is true, its addition is
in the $C^\perp$ too and this condition is satisfied too.
\end{enumerate}
Hence $C^\perp$ is linear.
\pr \indent % 3. priklad
Say, $S$ is the Singleton bound and $H$ the Hamming's bound, then: \\
$18 \leq A_2(20,7) \leq 776H \leq 16384S$ \\
$1138 \leq A_3(20,7) \leq 351454H \leq 4782969S$ \\
$145100 \leq A_5(20,7) \leq 647 212 653H \leq 6 103 515 625S$ \\ \indent
We can see, that Singleton bound is worse than Hamming's in these cases, so
the Hamming's bound points to more exact result. Gilbert-Varshal's is then
lower bound.
\pr % 4. priklad
Because the word has length $15=2^4-1$, the code is $[2^4-1,
2^4-1-4]=[15,11]$, its generator matrix is:
\[ G=\left( \begin{array}{ccccccccccccccc}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 1 \\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1
\end{array} \right) \]
and its parity check matrix:
\[ H=\left( \begin{array}{ccccccccccccccc}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\
1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 0 & 1
\end{array} \right) \]
I used the latter to compute syndrome, which is $S("111111111100000")=1011$.
So the error is on the 11th position. The codeword, that belongs to the code
is 1111\textbf01111100000. So I tried to decode it and the result is
11110111110. If I try to encode this word back, I get 111101111100000 as
expected. The error was caused by the transfer.
\pr \indent % 5. priklad
We can assume, that all codes are generated by adding one line to each
other. Because the addition is modulo $q$, we can divide the problem in some
cases. When we write the 2 codes vertically, there could be only a few cases
of addition of 2 couples, that preserves even parity:
\begin{enumerate}
\item
\[ \begin{array}{c}
\ldots0\ldots0\ldots \\
+ \\
\ldots0\ldots0\ldots \\
= \\
\ldots0\ldots0\ldots
\end{array}
\]
I call this 00+00 addition. Source codes are even and the result too.
Ditto for 11+11.
\item 01+01 gives the result 00 and it doesn't change the result. To
preserve the even parity, there should be in each code from the 2
next couple 01 or
10, which will pass through some of these cases.
\item 01+10 is the same, because not to be odd parity in the code, there
should be some other 01 or 10 couple. And in the result it is 11, that
is even. Ditto for 10+10.
\item 10+01 -- as I wrote, there may be this combination resulting in 11,
it's similar to the previous case.
\end{enumerate}
We iterate through this cases until we have 0 or 1 symbol. If the code
has even length, the count of symbols left are 0 and we are done. Otherwise,
in odd codes, there have
to be one (moveable) bit, that is 0 in each case and we may not count it,
because of even-weight rows in generator matrix $G$.
\pr % 6. priklad
\begin{enumerate}
\item If $\textbf a\in V$, then $\textbf a=\textbf a+\textbf 0$, so
$\textbf a$ is in some coset $\textbf a+A$. We can do it
for all $\textbf a\in V$, so that each element is in some coset.
\item We must notice, that linear code $C$ has $q^k$ codewords. When we
get some coset $\textbf a+C$, the number of words doesn't change, only
codewords may change depending on $\textbf a$. So the number of words is
in each coset is exactly $q^k$.
\item Let's suppose, that some 2 cosets $\textbf a+A$ and $\textbf b+A$
overlap. In that case, we can find some
$\textbf c\in(\textbf a+A)\cap(\textbf b+A)$. We can easily prove (below),
if $\textbf a+A$ is a coset of $A$ and $\textbf b\in\textbf a+A$,
$\textbf a+A=\textbf b+A$. And hence, our $\textbf c+A=\textbf a+A$. But
it means, that we proved, what we want to.
\end{enumerate}
The proof mentioned above (cut \& paste): \\
Since $b\in \textbf a + W$, we have $b=\textbf a+\textbf x$ for some
$\textbf x\in W$. Now if $\textbf b+\textbf y\in\textbf b+W$, then
\[\textbf b+\textbf y=(\textbf a+\textbf x)+\textbf y=\textbf a+(\textbf x+
\textbf y)\in\textbf a+W\]
Hence $\textbf b+W\subseteq\textbf a+W$. On the other hand, if $\textbf a+
\textbf z\in\textbf a+W$, then
\[\textbf a+\textbf z=(\textbf b-\textbf x)+\textbf z=\textbf b+(\textbf z-
\textbf x)\in\textbf b + W\]
Hence $\textbf a+W\subseteq\textbf b+W$, and so $\textbf a+W=\textbf b+W$.
\end{document}