HaCkEd By KaSpEr511

Encoding Matrices and Linear Codes

July 4th, 2009

In the previous post here, the message 1101 is encoded into 11011101. By writing 1101 as the row vector $\begin{pmatrix}1&1&0&1\end{pmatrix}$ , we can write the encoded message as

$\begin{pmatrix}1&1&0&1\end{pmatrix}[I\mid I]=\begin{pmatrix}1&1&0&1&1&1&0&1\end{pmatrix}.$

So the idea here is that we can use a matrix to encode messages efficiently. From now on we will refer the messages as words and the encoded messages as codewords. Suppose we have a word of length $k$ and a matrix G, turn this word into a codeword of lengh $n$ . Then it is clear that $G$ is of the size $k\times n$ . We also want that each codeword correspond to a unique word. In order to do so we need $G$ to have a full rank, i.e., we need the rank of $G$ equals $k$ .

We can view the codewords as the set of all vectors of the form $uG$ where $u\in \mathbb{Z}_2^k$ . Note that if $r_1,\cdots,r_k$ are the rows of $G$ , then

$uG=\begin{pmatrix}u_1&u_2&\cdots&u_k\end{pmatrix}\begin{pmatrix}r_1\\r_2\\\vdots\\r_k\end{pmatrix}=\sum_{i=1}^k u_ir_i$ .

So the codewords are the set of all linear combination of the vector rows $r_1,\cdots,r_k$ . Hence the set of codewords is a $\mathbb{Z}_2$ -sub vector space of $\mathbb{Z_2}^n$ . Since $\text{rank } G=k$ , then $r_1,\cdots ,r_k$ is a basis of this vector space. From this observation one can see that to study the encoding mechanism it is enough to study subspaces of $\mathbb{Z}_2^n$ .

We are ready for the definition of liner codes.

Definition

An $[n,k]$ linear codes $\mathcal{C}$ is a $\mathbb{Z}_2$ -subspace of $\mathbb{Z}_2^n$ of dimension $k$ .

It is natural to ask the other way around, given an $[n,k]$ linear code $\mathcal{C}$ , is there a $k\times n$ matrix $G$ such that $\mathcal{C}=\{uG\mid u\in \mathbb{Z}_2^k\}$ ?

Since $\mathcal{C}$ is of dimension $k$ , $\mathcal{C}$ has a basis $\{s_1,\cdots,s_k\}$ . Let define a matrix $G$ where it’s rows are $s_1,\cdots,s_k$ . Previously we seen that $uG$ is the set of linear combination of rows of $G$ , i.e., linear combination of $s_1,\cdots,s_k$ . But $\{s_1,\cdots,s_k\}$ is a basis of $\mathcal{C}$ . Therefore $\mathcal{C}=\{uG\mid u\in\mathbb{Z}_2^k\}$ .