Error Correcting Codes

Error-control codes:

• Forward error correction (FEC)
  Block codes Convolutional codes
• Automatic repeat request (ARQ)

Channel coding in a digital communication system:

 
Figure 1: Simplified model of a digital communication system.

Block codes

 
Figure 2: A channel encoder that generates an (n,k) block code.

Code rate:
Channel data rate:
where denotes the bit rate of the information source.

Convolutional codes

 
Figure 3: A convolutional encoder with memory M that encodes the incoming bits serially.

Modulo-2 arithmetic
- Taking the remainder when dividing by 2:

Block codes
A binary block code C of block length n is a subset of the set of all binary n-tuples where for . An n-tuple belonging to the code is called a codeword or code vector of the code.

If the subset is a vector space over {0,1}, the binary block code is then a linear block code.

Minimum Hamming distance
The Hamming weight of an n-tuple , , is the number of nonzero components of the n-tuple.

The Hamming distance between any two n-tuples and , denoted , is the number of positions in which their components differ. It is clear that where is defined as (a component-by-component subtraction).

The minimum Hamming distance, , of the block code C is the smallest Hamming distance between pairs of distinct codewords.

Example .

Correction and detection ability of a block code
When is the actual codeword and its possible corrupted received version, then the error pattern is the n-tuple defined by

The number of errors is just .

Error detection We say that a code can detect all patterns of t or fewer errors if the decoder chosen never incorrectly decodes whenever the number of errors is less than or equal to t.

Error correction We say that a code can correct all patterns of t or fewer errors if the decoder chosen correctly decodes whenever the number of errors is less than or equal to t.

The implicit decoding rule: decode to the nearest codeword in terms of Hamming distance.

Linear codes
A binary block code C is linear if, for and in C, is also in C.

The minimum Hamming distance of a linear block code is equal to the smallest weight of the nonzero codewords in the code.

Example is a linear code because etc.

If we take k n-tuples , , that are linearly independent and form a matrix

An (n,k) block code may then be conveniently represented as

where is the codeword corresponding to the message block .

G is called the generator matrix of the code.

A code is systematic if the generator matrix G is of the form

i.e., where is a identity matrix and P is an matrix. The generator matrix is also said to be systematic.

In a systematic code, the first k bits of the codeword is the same as the corresponding message bits.

For the generator matrix G of a linear code, there exists an matrix, H, whose n-k rows are linearly independent such that

The matrix H is called the parity check matrix of the code.

For any codeword in the code,

If the code is systematic,

where is an identity matrix.

Clearly, the n-k rows are linearly independent and

Syndrome decoding
Given a received vector , the receiver has the task of decoding from .

Syndrome:

• The syndrome depends only on the error pattern, and not on the transmitted codeword.
• All error patterns that differ by a codeword have the same syndrome.

Standard array for an (n,k) linear code:

1. The codewords are placed in a row with all-zero codeword as the left-most one.
2. An error pattern is picked and placed under , and a second row is formed by adding to each of the remaining codewords in the first row. ( has not appeared previously and has the least minimum Hamming weight.)
3. Step 2 is repeated until all the possible error patterns have been account for.

Each row in the standard array is called a coset. The left-most element of a row is called the coset leader of the coset. Note that each coset has a unique syndrome.

Syndrome decoding for an (n,k) linear block code:

1. For the received vector , compute the syndrome .
2. Within the coset characterized by the syndrome , identify the coset leader; call it .
3. Compute the codeword
   
   as the decoded version of the received vector .

Example Consider the (6,3) linear code generated by the following matrix

We then have the parity check matrix

Standard array for the (6,3) linear code:

Example (cont.) If the code is used for error correction on a BSC with transition probability p, the probability that the decoder decodes correctly is

The probability that the decoder commits an erroneous decoding is then

To minimize , the error patterns that are mostly likely to occur for a given channel should be chosen as the coset leaders.

Example The generator matrix for the the repetition code of length 3 ({ 000, 111 } ) is

Therefore, the parity check matrix of the code is

Hamming codes
For any positive , there exists a Hamming code (a linear code) with the following parameters:

The parity check matrix H of this code consists of all the nonzero m-tuple as its columns. In systematic form, the columns of H are arranged in the following form:

where is an identity matrix and the submatrix Q consists of columns which are the m-tuples of weight 2 or more.

Dual codes
An (n,k) linear code with generator matrix G and parity check matrix H has a dual code that is a (n,n-k) linear code with generator matrix H and parity matrix G.

Example The even parity check code of length is generated by

The parity check matrix is [1 1 1] which is the generator matrix of the repetition code of length 3. This code is a dual code of the repetition code of length 3.