4.7 Encoding with a Linear Code

Let C be an [ n, k, d]-linear code over the finite field F _q. Each codeword of C can represent one piece of information, so C can represent q ^k distinct pieces of information. Once a basis { r ₁ , , r _k} is fixed for C, each codeword v, or, equivalently, each of the q ^k pieces of information, can be uniquely written as a linear combination,

where u ₁ , ,u _k ? F _q.

Equivalently, we may set G to be the generator matrix of C whose ith row is the vector r _i in the chosen basis. Given a vector u = ( u ₁ , ,u _k) ? , it is clear that

is a codeword in C. Conversely, any v ? C can be written uniquely as v = u G, where u = ( u ₁ , ,u _k) ? . Hence, every word u ? can be encoded as v = u G.

The process of representing the elements u of as codewords v = u G in C is called encoding.

Example 4.7.1

Let C be the binary [5 , 3]-linear code with the generator matrix

then the message u = 101 is encoded as

Note that the information rate...