Hadamard Code

Matrix of the [32,6,16] Hadamard code of NASA space probe Mariner 9 (1971/1972). The color black encodes the binary digit 1, and the color white encodes the binary digit 0.

Truth table with XOR links
Here the white fields stand for false (0)
and the red for true (1)

A Hadamard code is a binary block code that is used for error detection and error correction. It's a linear code . It was named after the French mathematician Jacques Hadamard . For large block lengths , the Hadamard codes have a poor information rate , but can correct many errors. ${\ displaystyle [2 ^ {n}, n + 1,2 ^ {n-1}]}$ ${\ displaystyle n}$

construction

The code is based on the Hadamard matrices . If a Hadamard matrix is of rank , the code words are constructed using the lines of and as code words. The entries are replaced by. In this way, code words of length are constructed. Since the rows of are orthogonal, two different rows of a Hadamard matrix differ in places. So is the Hamming distance . A code was thus constructed. ${\ displaystyle H}$ ${\ displaystyle 2 ^ {n}}$ ${\ displaystyle H}$ ${\ displaystyle -H}$ ${\ displaystyle -1}$ ${\ displaystyle 0}$ ${\ displaystyle 2 ^ {n + 1}}$ ${\ displaystyle 2 ^ {n}}$ ${\ displaystyle H}$ ${\ displaystyle 2 ^ {n-1}}$ ${\ displaystyle 2 ^ {n-1}}$ ${\ displaystyle [2 ^ {n}, n + 1,2 ^ {n-1}]}$

Decoding

The code has a minimum Hamming distance of and can therefore correct errors at most . When a word is received, it is first converted into a vector by replacing all zeros with −1. The vector-matrix product is now calculated. The entry with the highest absolute value corresponds to the line that was used as the code word. If this value is positive, then the word comes from , if it is negative, then the word comes from . ${\ displaystyle 2 ^ {n-1}}$ ${\ displaystyle t = 2 ^ {n-2} -1}$ ${\ displaystyle v}$ ${\ displaystyle 1 / -1}$ ${\ displaystyle vH ^ {T}}$ ${\ displaystyle H}$ ${\ displaystyle -H}$

Reason: If no errors occurred, the product consists of only zeros and an entry . If there were errors in , then - in absolute values - some of the zeros become larger and the maximum becomes smaller. Every error that occurs can replace a zero with a 2. So at most zeros can be changed. The maximum is reduced to at most . So the maximum that points to the correct line is always absolutely greater than all other values in the line. ${\ displaystyle vH ^ {T}}$ ${\ displaystyle \ pm 2 ^ {n}}$ ${\ displaystyle v}$ ${\ displaystyle 0 + 2t = 2 ^ {n-1} -2}$ ${\ displaystyle 2 ^ {n} -2t = 2 ^ {n} -2 ^ {n-1} + 2 = 2 ^ {n-1} +2}$

history

A Hadamard code was used in the Mariner 9 mission in 1971 to correct image transmissions from Mars. The data words in this mission were 6 bits long, they represented 64 gray values . Due to the limitations of the transmitters, the largest usable data length was 30 bits. The Hadamard code was used instead of a repeat code. So 7 bits per word could be corrected, 8 bit errors were still recognized. This Hadamard code has a similar information rate compared to a 5-repeat code, but it has a better correction rate. An important reason for using this code was its efficient decoding algorithm. The decryption machine was called the "Green Machine". This carried out a fast Fourier transformation , which accelerated the decryption by a factor of 3. ${\ displaystyle [32,6,16]}$

Optimality

The Hadamard codes are ideal for . ${\ displaystyle n \ leq 6}$

literature

KJ Horadam: Hadamard Matrices and Their Applications . Princeton University Press, 2006, ISBN 978-0-691-11921-2 .