understanding code

The formal definition of a code is this: a code of length n is a subset of all possible strings, or vectors, of n symbols (chosen from some alphabet, which will often be {0,1}), which has the property that every two members of the subset (i.e., codewords) differ in at least some fixed number of places d (the minimum distance of the code). If the number of codewords (which equals the number of possible messages) is M, then we shall say that it is an (n,M,d) code. Also, a code on {0,1} is called a binary code. So in our original example, {00,11} is a binary code of length 2, with 2 codewords and minimum distance 2. Similarly, {000,111} is a code of length 3 with minimum distance 3. We would like to have n small (for speed), M large (for efficiency), and d large (for reliability). These goals of course conflict, and a large part of coding theory is constructing codes that strike a balance between these three, and that are also practical to use. For notation, the number of places in which two vectors differ is usually referred to as the Hamming distance between the two vectors. The weight of a vector is the number of non0 entries in it (that is, its Hamming distance from the all 0’s vector). Using mod 2 arithmetic (that is, 1+1=0) to add two vectors coordinate by coordinate (no carrying), we see that the Hamming distance between two vectors is equal to the weight of their difference. For example, 100110101 has weight 5, and

010010010-110100111 = 100110101, so 010010010 and 110100111 have Hamming distance 5. So if a codeword gets garbled, then the number of errors is exactly the Hamming distance of the received vector from the original codeword. In order that we detect the errors, the received vector must not land on another codeword. This is why a large minimum distance is so important; if there are fewer than d errors then we can at least detect the error. Also, if there are there are strictly fewer than d/2 errors, then the received vector is still closer to the original codeword than to any other.

Related posts

• What is decoding (0)
• Waterfall Reinforces its Status as the First Choice for Protection of SCADA Systems (0)
• Use of debuggers analysis (0)
• Check enterprise applications for static passwords (0)
• Why do I get Ctrl-M characters in my CVS files (0)