Hadamard Code - Decoding

Decoding

The code has minimum distance n/2 and hence can correct at most t = n/4 − 1 errors. The algorithm below achieves this.

When a codeword is received it is first transformed to a ±1 vector v by changing all 0s to −1. Compute (v HT). The entry with the maximum absolute value corresponds to the row taken as a codeword. If it is positive the codeword came from H; if it is negative the codeword came from −H.

Proof: If there were no errors the product (v HT) would be a vector consisting of zeros except for one entry of magnitude n. For each error in v, the dot product of v with a row of H changes by ±2. If there are no more than t errors, the zero entries become entries of magnitude no larger than 2t = n/2 − 2, and the entry of magnitude n becomes an entry of magnitude no smaller than n−2t = n/2+2. Consequently the entry with maximum absolute value remains maximal, and therefore points to the intended codeword. This argument also implies that the code can detect up to t+1 errors.