Linear Algebra - Linear binary code

> Linear Algebra

1 - 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.

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.
Advertising

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 <math>{\bf \tilde{c}}</math>
  • 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: <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> .

Advertising

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.

<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

7 - 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.

8 - Finding the error

8.1 - 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>:

  1. Consider the function <math>f_H</math> by <math>f_H(y) = H*y</math> where the image under <math>f_H</math> of any codeword is the zero vector.
  2. 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>.
  3. 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>

Advertising

8.2 - 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

8.3 - 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>.

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

9 - Documentation / Reference

linear_algebra/binary_code.txt · Last modified: 2017/09/13 16:04 by gerardnico