6.26 Error-correcting codes: hamming distance

So-called linear codes create error-correction bits by combining the data bits linearly. The phrase "linearcombination" means here single-bit binary arithmetic.

The length- $K$ (in this simple example $K=1$ ) block of data bits is represented by the vector $b$ , and the length- $N$ output block of the channel coder, known as a codeword , by $c$ . The generator matrix $G$ defines all block-oriented linear channel coders.

As we consider other block codes, the simple idea of the decoder taking a majority vote of the received bitswon't generalize easily. We need a broader view that takes intoaccount the distance between codewords. A length- $N$ codeword means that the receiver must decide among the $2^N$ possible datawords to select which of the $2^K$ codewords was actually transmitted. As shown in [link] , we can think of the datawords geometrically. We define the Hamming distance between binary datawords $c_1$ and $c_2$ , denoted by $d(c_1, c_2)$ to be the minimum number of bits that must be "flipped" to gofrom one word to the other. For example, the distance between codewords is 3 bits. In our table of binary arithmetic, wesee that adding a 1 corresponds to flipping a bit. Furthermore, subtraction and addition are equivalent. We can express theHamming distance as

The probability of one bit being flipped anywhere in a codeword is $N{p}_e(1-p_e)^{(N-1)}$ . The number of errors the channel introduces equals the number of ones in $e$ ; the probability of any particular error vector decreases with the number of errors.