Hadamard code
From Wikipedia, the free encyclopedia
The Hadamard code, named after Jacques Hadamard, is a system used for signal error detection and correction. It is one of the family of [2n, n + 1, 2n − 1] codes. Especially for large n it has a poor rate but it is capable of correcting many errors.
Contents |
[edit] Construction
The code is based on Hadamard matrices. If H is an Hadamard matrix of order 2n the codewords are constructed by taking the rows of H and −H as codewords, where each −1 is replaced by 0. In this way 2n + 1 code words are constructed that each have a length of 2n. Since the rows of a Hadamard matrix are orthogonal the minimum distance is 2n - 1. In this way a [2n, n + 1, 2n − 1] code is constructed.
The code can also be constructed by creating the parity-check matrix which consists of all 2n − 1 vectors containing an odd number of 1s, or by using a recursive encoding process.
[edit] Decoding
The code has minimum distance 2n − 1 and hence can correct at most t = 2n − 2 − 1 errors. The algorithm below achieves this.
When a code word is received it is first transformed to a 1/−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 code word. If it is positive the code word came from H, if it is negative the code word came from −H.
Proof: If there were no errors the product (v HT) would consist of only zero's and one entry of +/−2n. If there are errors in v then, in absolute value, some of the zeros become larger and the maximum becomes smaller. Each error that occurs can change a zero with 2. So the zeros can become at most 0 + 2t = 2n − 1 − 2. The maximum can decrease at most to 2n − 2t = 2n − 2n − 1 + 2 = 2n − 1 + 2. So the maximum that points to the correct row will always be larger in absolute value than the other values in the row.
[edit] History
A Hadamard code was used during the 1971 Mariner 9 mission to correct for picture transmission error. [1] The data words used during this mission were 6 bits long, which represented 64 grayscale values. Because of limitations of the quality of the alignment of the transmitter the maximum useful data length was about 30 bits. Instead of using a repetition code, a [32, 6, 16] Hadamard code was used. Errors of up to 7 bits per word could be corrected using this scheme. Compared to a 5-repetition code, the error correcting properties of this Hadamard code are much better, yet its rate is comparable. The efficient decoding algorithm was an important factor in the decision to use this code. The circuitry used was called the "Green Machine". [2]. It employed the Fast Fourier Transform which can increase the decryption speed with a factor of 3.
[edit] Optimality
For value of n <= 6 the Hadamard codes have been proven optimal. [3]
