20-12-2012, 06:26 PM
Linear Block Codes
1Linear Block.PPT (Size: 767.5 KB / Downloads: 473)
linear Encoder.
By linear transformation
c =m ⋅G =m0g0 + m1g0 +……+ mk-1gk-1
The code C is called a k-dimensional subspace.
G is called a generator matrix of the code.
Here G is a k ×n matrix of rank k of elements from GF(2), gi is the i-th row vector of G.
The rows of G are linearly independent since G is assumed to have rank k.
Linear Block Codes
the number of codeworde is 2k since there are 2k distinct messages.
The set of vectors {gi} are linearly independent since we must have a set of unique codewords.
linearly independent vectors mean that no vector gi can be expressed as a linear combination of the other vectors.
These vectors are called baises vectors of the vector space C.
The dimension of this vector space is the number of the basis vector which are k.
Gi є C the rows of G are all legal codewords.
Hamming Weight
the minimum hamming distance of a linear block code is equal to the minimum hamming weight of the nonzero code vectors.
Since each gi єC ,we must have Wh(gi) ≥ dmin this a necessary condition but not sufficient.
Therefore, if the hamming weight of one of the rows of G is less than dmin, dmin is not correct or G not correct.
Generator Matrix
All 2k codewords can be generated from a set of k linearly independent codewords.
The simplest choice of this set is the k codewords corresponding to the information sequences that have a single nonzero element.
The Encoding Problem (Revisited)
Linearity makes the encoding problem a lot easier, yet:
How to construct the G (or H) matrix of a code of minimum distance dmin?
The general answer to this question will be attempted later. For the time being we will state the answer to a class of codes: the Hamming codes.
Standard Array Decoding
For an (n,k) linear code, standard array decoding is able to correct exactly 2n-k error patterns, including the all-zero error pattern.
Illustration 1: The (7,4) Hamming code
# of correctable error patterns = 23 = 8
# of single-error patterns = 7
Therefore, all single-error patterns, and only single-error patterns can be corrected. (Recall the Hamming Bound, and the fact that Hamming codes are perfect.
The Syndrome
Huge storage memory (and searching time) is required by standard array decoding.
Define the syndrome
s = vHT = (c + e) HT = eHT
The syndrome depends only on the error pattern and not on the transmitted codeword.
Therefore, each coset in the array is associated with a unique syndrome.