Linear Codes

ICMS

Page:

Related Projects :

Error Correcting Codes & Reed Solomon Codes

LINEAR CODES

Now, having decided on the number of errors (k) we would like to correct, we need to construct a code f for which the minimum distance d is at least 2k+1. This construction is relatively straightforward for linear codes. A code f: B^m à Bⁿ is called a linear code if for any two words v and w in B^m ,

f(v + w) = f(v) + f(w).

The + sign here represents binary pointwise addition.

0 + 0 = 0 = 1 + 1 For example: 101

1 + 0 = 1 = 0 + 1 + 011

110

Mathematically, the function f is a linear transformation and thus, it can be represented as a matrix multiplication:

f(w) = w.G_{m x n}

Here, G_{m x n} is a matrix with m rows and n columns. Treat the word w (of length m) as a 1 x m matrix (i.e. a matrix with one row and m columns). The codeword f(w) is then a 1 ´ n matrix, which represents a word of length n.

Since we have decided on the number of errors (k) that we would like to correct, we need to construct a linear code with minimum distance d that is at least 2k+1. This determines the number of check digits that we have to attach to each word. Thus, we have answered the first of the questions we posed.

To answer the second question, we describe the general method for constructing a linear code f: B^m à Bⁿ with minimum distance d. We illustrate the method with the example discussed earlier, f: B² à B⁵.