Code Theory - HackMD

> This is note for **Code Theory**-) ## Even Parity Check - can only be detect sigle error - can not fix error ## MLE Decoding - detect errors - correct errors with probability distribution ## Block Codes **Lemma**: $$ d(\mathbf{x}, \mathbf{y}) \le d(\mathbf{x}, \mathbf{z}) + d(\mathbf{z}, \mathbf{y}) $$ Two properties: - the minimum distance of codewords must be greater than tolerance of error correction - a code scheme with $d_{min} = 2 n + 1$, then it can correct at most $n$ errors, and detect at most $2n$ errors ## Linear Code Group code is a set of codewords consisting a group, which including the **zero** or **identity** element. - distance of code is defined to be the minimum distance between any two codewords, $d_{min}$, it determines the capability of detecting and correcting errors - weight of code is defined to be the minimus number of $1$ within all codewords except *zero-codeword*, $w$ - compute the distance of codewords is costly, say $\binom{n}{2} = \frac{n (n - 1)}{2}$, fortunately $d_{min}$ is dependent with weights $$ d(\mathbf{x}, \mathbf{y}) = w(\mathbf{x} + \mathbf{y}) $$ **Theorem**: $$ d_{min} = min\{w(\mathbf{x}): \mathbf{x} \ne \mathbf{0} \} $$ the distance of **group code** is the minimum weight of non-zero codewords, therefore the cost of computing distance becomes $n$, greatly reduced from $\frac{n (n - 1)}{2}$. How to generate a good group code? **Theorem**: **Let $H$ be a matrix $\mathbb{M}_{m \times n}(\mathbb{Z}_2)$, then its null space is a group code**: $$ Null(H) = \{\mathbf{x}: \langle H \cdot \mathbf{x} \rangle = \mathbf{0} \} $$ For example: $$ H = \begin{bmatrix} 0 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 1 & 1 \\ \end{bmatrix} $$ then the group code would be $\mathbf{x} = \{ 00000, 11110, 10101, 01011 \}$, with distance $3$. But how to detect errors? If the received word is $10001$, then we can easily check that it's not a codeword, since $H \cdot \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ 1 \end{bmatrix} = \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix} \ne \mathbf{0}$. Is there a efficient method to generate group code? ## Generator Matrix Original words are represented as column vector $\mathbf{x}_{n - m, 1}$. Split $H_{m \times n}$, $n > m$, into two parts: $$ H_{m \times n} = (A | I_m) $$ where $A$ is $m \times (n - m)$ partial matrix, and $I_m$ is a $m \times m$ identity matrix. Let generator matrix: $$ G_{n \times (n - m)} = (\frac{I_{n - m}}{A}) $$ Then we must have: $$ H \cdot \mathbf{y} = \mathbf{0} $$ where $\mathbf{y} = \langle G, \mathbf{x} \rangle$ is what we want, group code. Why it holds for that? Let's prove it: $$ \begin{aligned} H \cdot \mathbf{y} &= (A | I_m) \cdot (\frac{I_{n - m}}{A}) \cdot \mathbf{x} \\ &= (A | I_m) \cdot (\frac{\mathbf{x}}{A \cdot \mathbf{x}}) \\ &= \langle A, \mathbf{x} \rangle + \langle I_m, A \cdot \mathbf{x} \rangle \\ &= \langle A, \mathbf{x} \rangle + \langle A, \mathbf{x} \rangle \\ &= \mathbf{0} \end{aligned} $$ Besides, we also have $H \cdot G = \mathbf{0}$: $$ H \cdot G = (A | I_m) \cdot (\frac{I_{n - m}}{A}) = \langle A, I_{n - m}\rangle + \langle I_m, A\rangle = A + A = \textbf{0} $$ For example, we have $3$-bits message for transmission, which $n - m = 3$, and assume length of codeword is $n = 2 * 3 = 6$, and partial matrix: $$ A = \begin{bmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \\ \end{bmatrix} $$ then we can obtain the entire group code $\mathbf{y}$ with above method: $$ \def\arraystretch{1.5} \begin{array}{c:c} \mathbf{x} & G \cdot \mathbf{x} \\ \hline 000 & 000\color{red}{000} \\ \hdashline 001 & 001\color{red}{101} \\ \hdashline 010 & 010\color{red}{110} \\ \hdashline 011 & 011\color{red}{100} \\ \hdashline 100 & 100\color{red}{011} \\ \hdashline 101 & 101\color{red}{001} \\ \hdashline 110 & 110\color{red}{010} \\ \hdashline 111 & 111\color{red}{000} \\ \hdashline \end{array} $$ the time complexity of this is $O(2^{n - m})$. Let's take a closer look at: $$ \begin{aligned} \mathbf{y} &= G \cdot \mathbf{x} \\ &= (\frac{I_{n - m}}{A}) \cdot \mathbf{x} \\ &= (\frac{\mathbf{x}}{A \cdot \mathbf{x}}) \\ \end{aligned} $$ the above part of $\mathbf{y}$ is orginal message $\mathbf{x}$ **information bits**, the below (redundant) part of $\mathbf{y}$ is **check bits**. ## General Decode There's an important concept in decoding a receiving word, **syndrome**. For example, there's a binary matrix: $$ H = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ \end{pmatrix} $$ And two receiving words, $\mathbf{x_1} = \begin{pmatrix} 1 \\ 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}$ and $\mathbf{x_2} = \begin{pmatrix} \color{red}{0} \\ 1 \\ 0 \\ 1 \\ 1 \end{pmatrix}$. Then we can prove that $\mathbf{x_1}$ is correct codeword, while the $\mathbf{x_2}$ is not. Since we have: $$ H \cdot \mathbf{x_1} = \mathbf{0} \\ H \cdot \mathbf{x_2} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \ne \mathbf{0} $$ and $H \cdot \mathbf{x_2}$ is just the first column of $H$, we can conclude that the error term is first element of $\mathbf{x_2}$, if we flip the $0$ to $1$, then it will the very $\mathbf{x_1}$. So, we call $H \cdot \mathbf{x}$ is the **syndrome** of receiving word $\mathbf{x}$. In general, $$ \mathbf{x} = \mathbf{c} + \mathbf{e} $$ where $\mathbf{x}$ is receiving word, $\mathbf{c}$ is sending codeword, $\mathbf{e}$ is error term. Since $H \cdot \mathbf{c} = \mathbf{0}$, so $H \cdot \mathbf{x} = H \cdot (\mathbf{c} + \mathbf{e}) = H \cdot \mathbf{e}$. In another words, **syndrome** is independent of sending codeword, it's about the error term. ## Coset Decode Assuming we have the same binary matrix: $$ H = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ \end{pmatrix} $$ we can easily obtain the coresponding codewords $C = G \cdot \mathbf{x}$ with the help of **generator matrix** $G$: $$ \def\arraystretch{1.5} \begin{array}{c:c} \mathbf{x} & G \cdot \mathbf{x} \\ \hline 00 & 00000 \\ \hdashline 01 & 01101 \\ \hdashline 10 & 10011 \\ \hdashline 11 & 11110 \\ \hdashline \end{array} $$ Since $C$ is *group code* with order $2^2$, which is also a subgroup of $\mathbb{Z}_2^5$. So there're $2^{5 - 2} = 2^3$ cosets. How does the coset come from? that's $$ \mathbb{Z}_2^5 / C = \{\mathbf{e} + C: \mathbf{e} \in \mathbb{Z}_2^5\} $$ where $\mathbf{e}$ is elements from $\mathbb{Z}_2^5$ distinct from $C$. According the definition of **coset**, we can also say that $\mathbb{Z}_2^5$ is divided into $2^3$ cosets by group $C$, each coset with order $2^2$. And $\mathbf{e}$ is what we called the **representative** of coset. Coset is not we want to emphasize, the relation between coset representative $\mathbf{e}$ and **syndrome** $\mathbf{s}$ is, so what is the relationship beween them? Assume $\mathbf{x} = \mathbf{c} + \mathbf{e}$, since $\mathbf{c} \in C$, we have the **syndrome** $\mathbf{s} = H \cdot \mathbf{x} = H \cdot \mathbf{e}$, the decode table looks like: $$ \def\arraystretch{1.5} \begin{array}{c:c} \mathbf{e} & \mathbf{s} \\ \hline 00000 & 000 \\ \hdashline 00001 & 001 \\ \hdashline 00010 & 010 \\ \hdashline 10000 & 011 \\ \hdashline 00100 & 100 \\ \hdashline 01000 & 101 \\ \hdashline 00110 & 110 \\ \hdashline 10100 & 111 \\ \hdashline \end{array} $$ We can obtain the error term or representative of coset, $\mathbf{e}$,after looking up the above decode table, treating syndrome $s$ as query. Finally we can get the orginal codeword $\mathbf{c}$: $$ \begin{aligned} \mathbf{c} = \mathbf{x} - \mathbf{e} \\ = \mathbf{x} + \mathbf{e} \end{aligned} $$ #### References [1] [Abstract Algebra: Theory and Applications](http://abstract.ups.edu/)