11-12-2012, 02:40 PM
ERROR CONTROL CODING
ERROR CONTROL.PPT (Size: 639 KB / Downloads: 144)
Hamming Distance
Def.: The Hamming distance between two codewords ci and cj, denoted by d(ci,cj), is the number of components at which they differ.
dH(011,000) = 2 dH [C1,C2]=WH(C1+C2)
dH (011,111) = 1
Therefore 011 is closer to 111.
Maximum Likelihood Decoding reduces to Minimum Distance Decoding, if the priory probabilities are equal (P(0)=P(1))
Error Correction and Detection
Consider a code consisting of two codewords with Hamming distance dmin. How many errors can be detected? Corrected?
# of errors that can be detected = td= dmin -1
# of errors that can be corrected = tc =
In other words, for t-error correction, we must have
dmin = 2tc + 1
Minimum Distance of a Code
Def.: The minimum distance of a code C is the minimum Hamming distance between any two different codewords.
A code with minimum distance dmin can correct all error patterns up to and including t-error patterns, where
dmin = 2tc + 1
It may be able to correct some higher error patterns, but not all.
Coding: Gain and Cost (Revisited)
Given an (n,k) code.
Gain is proportional to the error correction capability, tc.
Cost is proportional to the number of check digits, n-k = r.
Given a sequence of k information digits, it is desired to add as few check digits r as possible to correct as many errors (t) as possible.
What is the relation between these code parameters?
Hamming Bound
For an (n,k) code, there are 2k codewords and 2n possible received words.
Think of the 2k codewords as centers of spheres in an n-dimensional space.
All received words that differ from codeword ci in tc or less positions lie within the sphere Si of center ci and radius tc.
For the code to be tc-error correcting (i.e. any tc-error pattern for any codeword transmitted can be corrected), all spheres Si , i =1,.., 2k , must be non-overlapping.
In other words, When a codeword is selected, none of the n-bit sequences that differ from that codeword by tc or less locations can be selected as a codeword.
Consider the all-zero codeword. The number of words that differ from this codeword by j locations is
The total number of words in any sphere (including the codeword at the center)
Gilbert Bound
While Hamming bound sets a lower limit on the number of redundant bits (n-k) required to correct tc errors in an (n,k) linear block code.
Another lower limit is the Singleton bound
Gilbert bound places an upper bound on the number of redundant bits required to correct tc errors.
It only says there exist a code but it does not tell you how to find it.
The Encoding Problem
How to select 2k codewords of the code C from the 2n sequences such that some specified (or possibly the maximum possible) minimum distance of the code is guaranteed?
Example: How were the 16 codewords of the (7,4) code constructed? Exhaustive search is impossible, except for very short codes (small k and n)
Are we going to store the whole table of 2k(n+k) entries?!
A constructive procedure for encoding is necessary.