Hadamard-Code

An Hadamard code is a binary block code, which is used for error detection and error correction. It is a linear code. It was named after the French mathematician Jacques Hadamard. For large block lengths, the Hadamard codes have poor information rate, but can correct many errors.

Construction

The code is based on the Hadamard matrices. Is a Hadamard matrix of rank, the codewords are constructed by the lines and are used by the code words. The entries are replaced by. In this kind of code words of length can be constructed. Since the rows of orthogonal, two different rows of a Hadamard matrix in locations differ. So is the Hamming distance. There is a code was thus constructed.

Decoding

The code has a minimum Hamming distance and can thus correct only faults. If a word is received, it is first converted into a vector by all noughties be replaced by -1. Now, the vector -matrix product is computed. The entry with the highest absolute value corresponds to the line that was used as a code word. If this value is positive, then the word comes from, it is negative, then the word comes from.

Reason: Were there no errors, then the product consists only of zeros and a single entry. Were there any errors in, then - in absolute values ​​- some of the larger zeros and the maximum is smaller. Any error that occurs can replace a zero with a 2. Thus most zeros can be changed. The maximum is reduced to at most. So is the maximum that points to the correct row, getting absolutely greater than all other values ​​in the row.

History

A Hadamard code 1971 used in the Mariner 9 mission to correct image transmissions from Mars. The data words in this mission were 6 bits long, they represented 64 gray levels. Due to the limitations of the transmitter, the largest usable data length was 30 bits. Instead of a repeating code of the Hadamard code is used. It was 7 bits per word to be corrected, 8-bit errors were not detected. This Hadamard code has been compared with a 5- repetition code similar information rate, but he has a better correction rate. An important reason for the use of this code was its efficient decoding algorithm. The decryption engine was called the " Green Machine". This led through a fast Fourier transformation, accelerated the decryption by a factor 3.

Optimality

For the Hadamard codes are optimal.