Linear Algebra - Linear binary code
About
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 <math>\tilde{c}</math> , 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.
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.
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 <math>{\bf \tilde{c}}</math>
- Receiver tries to figure out original 4-bit block
C = set of permitted codewords
Codeword
The 7-bit encodings are called codewords in the block code
Encoding
Hamming discovered a code in which a four-bit message is represented by a seven-bit codeword. The generator matrix is: <MATH> 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} </MATH> 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 <math>f_G</math> be the encoding function, the function de ned by <math>f_G(x) = G*p</math> The image of <math>f_G</math> , the set of all codewords, is the row space of <math>G</math> .
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.
<MATH> 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} </MATH>
The matrix-matrix product RG should be the identity matrix
Error Syndrome
The codeword <math>c</math> is send across a noisy channel and the vector received is <math>\tilde{c}</math> . The following formula reflect the fact that <math>\tilde{c}</math> might di ffer from <math>c</math> : <MATH>c = \tilde{c} + e</MATH> where:
- c is the original codeword
- <math>\tilde{c}</math> 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 <math>e</math> , we can recover the codeword <math>c</math> and therefore the original message.
Finding the error
Check Matrix
To figure out the error vector <math>e</math> , a check matrix is used, which for the Hamming code is:
<MATH> 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} </MATH>
The orders of the columns are specials. It's in gf2, the sequence from 001 to 111: <math>001, 010, 011, 100, 101, 110, 111</math>
Definition of the function <math>HG</math> :
- Consider the function <math>f_H</math> by <math>f_H(y) = H*y</math> where the Linear Algebra - Function (Set) under <math>f_H</math> of any codeword is the zero vector.
- Consider the function <math>f_H \circ f_G</math> that is the composition of <math>f_H </math> with <math>f_G</math> . For any vector <math>p</math> , <math>f_G(p)</math> is a codeword <math>c</math> , and for any codeword <math>c</math> , <math>f_H(c) = 0</math> . This implies that, for any vector <math>p</math> , <math>(f_H \circ f_G)(p) = 0</math> .
- The matrix <math>HG</math> corresponds to the function <math>f_H \circ f_G</math> . The entries of the matrix HG are then
<MATH> HG = \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{bmatrix} </MATH>
Error syndrome
As a fi rst step towards figuring out the error vector, we computes the error syndrome: <MATH> H*\tilde{c} </MATH> which equals: <MATH> H*e </MATH> as <math>e</math> en <math>c</math> are codewords
Which bit is corrupted
We assumes that at most one bit of the codeword is corrupted, so at most one bit of <math>e</math> is nonzero in position <math>i \in \{1, 2, \dots, 7\}</math> .
The error syndrom (the value of <math>H*e</math> ) is the 3-vector where the error occurs.
It use the dot product property of Gf2
- <math>1 * [0,1,0] = [0,1,0]</math>
- <math>1 * [0,0,1] = [0,0,1]</math>
- …
For instance, if <math>e</math> has a 1 in its third position, <math>e = [0, 0, 1, 0, 0, 0, 0]</math> , then the result of <math>H*e</math> gives the column where the bit error is. In this case, the third column of <math>H</math> , which is <math>[0, 1, 1]</math> .
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