# Linear Algebra - Linear binary code

In a linear binary code, the set C of codewords is a vector space over GF(2).

In such a code, there is a matrix H, called the check matrix, such that C is the null space of H. When the Receiver receives the vector $\tilde{c}$, she can check whether the received vector is a codeword by multiplying it by H and checking whether the resulting vector (called the error syndrome) is the zero vector.

The vector space C can be specified:

• as the null space of the check matrix H.
• of in terms of generators.

The generator matrix for a linear code is a matrix G whose columns are generators for the set C of codewords. (It is traditional to defi ne the generator matrix so that its rows are generators for C).

By the linear-combinations de finition of matrix-vector multiplication, every matrix-vector product G p is a linear combination of the columns of G, and is therefore a codeword.

## 2 - Error-correcting codes

• Originally inspired by errors in reading programs on punched cards
• Now used in WiFi, cell phones, communication with satellites and spacecraft, digital television, RAM, disk

drives, flash memory, CDs, and DVDs

Hamming code is a linear binary block code:

• linear because it is based on linear algebra,
• binary because the input and output are assumed to be in binary, and
• block because the code involves a fixed-length sequence of bits.

## 3 - Block Code

To protect an 4-bit block:

• Sender encodes 4-bit block as a 7-bit block c (a codeword)
• Sender transmits c
• c passes through noisy channel—errors might be introduced.
• Receiver receives 7-bit block ${\bf \tilde{c}}$
• Receiver tries to figure out original 4-bit block

C = set of permitted codewords

## 4 - Codeword

The 7-bit encodings are called codewords in the block code

## 5 - Encoding

Hamming discovered a code in which a four-bit message is represented by a seven-bit codeword. The generator matrix is: $$G = \begin{bmatrix} 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix}$$ A four-bit message is represented by a 4-vector p over GF(2). The encoding of p is the 7-vector resulting from the matrix-vector product G*p.

Let $f_G$ be the encoding function, the function de ned by $f_G(x) = G*p$ The image of $f_G$, the set of all codewords, is the row space of $G$ .

## 6 - Decoding

Four of the rows of G are the standard basis vectors e1, e2, e3, e4 of GF(2). It implies that the words are in the codewords.

$$R = \begin{bmatrix} 0 & 0 & 0 & 0 & 0 & 0 & 1\\ 0 & 0 & 0 & 0 & 0 & 1& 0 \\ 0 & 0 & 0 & 0 & 1& 0 & 0 \\ 0 & 0 & 1& 0 & 0 & 0 & 0 \end{bmatrix}$$

The matrix-matrix product RG should be the identity matrix

## 7 - Error Syndrome

The codeword $c$ is send across a noisy channel and the vector received is $\tilde{c}$. The following formula reflect the fact that $\tilde{c}$ might di ffer from $c$: $$c = \tilde{c} + e$$ where:

• c is the original codeword
• $\tilde{c}$ is the non-codeword (received code word with may be one fault)
• e is the error vector, the vector with ones in the corrupted positions.

If we can figure out the error vector $e$ , we can recover the codeword $c$ and therefore the original message.

## 8 - Finding the error

### 8.1 - Check Matrix

To figure out the error vector $e$, a check matrix is used, which for the Hamming code is:

$$H = \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1& 1 \\ 1 & 0 & 1 & 0 & 1& 0 & 1 \end{bmatrix}$$

The orders of the columns are specials. It's in gf2, the sequence from 001 to 111: $001, 010, 011, 100, 101, 110, 111$

Definition of the function $HG$:

1. Consider the function $f_H$ by $f_H(y) = H*y$ where the image under $f_H$ of any codeword is the zero vector.
2. Consider the function $f_H \circ f_G$ that is the composition of $f_H$ with $f_G$. For any vector $p$, $f_G(p)$ is a codeword $c$, and for any codeword $c$, $f_H(c) = 0$. This implies that, for any vector $p$, $(f_H \circ f_G)(p) = 0$.
3. The matrix $HG$ corresponds to the function $f_H \circ f_G$. The entries of the matrix HG are then

$$HG = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix}$$

### 8.2 - Error syndrome

As a fi rst step towards figuring out the error vector, we computes the error syndrome: $$H*\tilde{c}$$ which equals: $$H*e$$ as $e$ en $c$ are codewords

### 8.3 - Which bit is corrupted

We assumes that at most one bit of the codeword is corrupted, so at most one bit of $e$ is nonzero in position $i \in \{1, 2, \dots, 7\}$.

The error syndrom (the value of $H*e$) is the 3-vector where the error occurs.

It use the dot product property of Gf2

• $1 * [0,1,0] = [0,1,0]$
• $1 * [0,0,1] = [0,0,1]$

For instance, if $e$ has a 1 in its third position, $e = [0, 0, 1, 0, 0, 0, 0]$ , then the result of $H*e$ gives the column where the bit error is. In this case, the third column of $H$, which is $[0, 1, 1]$.

### 8.4 - Decoding

non_codeword = Vec({0,1,2,3,4,5,6}, {0: one, 1:0, 2:one, 3:one, 4:0, 5:one, 6:one})
error_syndrome = H*non_codeword
error_vector = find_error(error_syndrome) # See the previous sectie
code_word = non_codeword + error_vector
original = R*code_word