Hadamard code

Hadamard code
Named after	Jacques Hadamard
Classification
Type	Linear block code
Parameters
Block length	n = 2k − 1
Message length	k
Rate	k / 2k − 1
Distance	d = 2k − 2
Alphabet size	2
Notation	[2k − 1,k,2k − 2]2-code

Matrix of the Hadamard code (32, 6, 16) for the Reed-Muller Code (1, 5) of the NASA space probe Mariner 9

XOR operations
Here the white fields stand for 0
and the red fields for 1

The Hadamard code is an error-correcting code that is used for error detection and correction when transmitting messages over very noisy or unreliable channels. A famous application of the Hadamard code was the NASA space probe Mariner 9 in 1971, where the code was used to transmit photos of Mars back to Earth. Because of its unique mathematical properties, the Hadamard code is not only used by engineers, but also intensely studied in coding theory, mathematics, and theoretical computer science. The Hadamard code is named after Jacques Hadamard and also known under the names Walsh code and Walsh–Hadamard code.

The Hadamard code maps a message consisting of k bits to a codeword of 2^{k − 1} bits; it is able to detect 2^{k − 2} − 1 errors and to correct 2^{k − 3} − 1 errors. In standard coding theory notation for block codes, the Hadamard code is a [2^{k − 1},k,2^{k − 2}]₂-code, that is, it is a linear code over a binary alphabet, has block length 2^{k − 1}, message length (or dimension) k, and minimum distance 2^{k − 2}. For large k, the block length is very large, but many errors can be corrected. The Hadamard code of message length k is the same as the first order Reed–Muller code RM(1,k−1).

Normally, Hadamard codes are based on Sylvester's construction of Hadamard matrices, but the term “Hadamard code” is also used to refer to codes constructed from arbitrary Hadamard matrices, which are not necessarily of Sylvester type. In general, such a code is not linear. Such codes were first constructed by R. C. Bose and S. S. Shrikhande in 1959. If n is the size of the Hadamard matrix, the code has parameters (n,2n,n / 2)₂, meaning it is a not-necessarily-linear binary code with 2n codewords of block length n and minimal distance n/2. The construction and decoding scheme described below apply for general n, but the property of linearity and the identification with Reed–Muller codes require that n be a power of 2 and that the Hadamard matrix be equivalent to the matrix constructed by Sylvester's method.

History

Hadamard code is the name that is most commonly used for this code in the literature. Jacques Hadamard did not invent the code himself, but he defined Hadamard matrices around 1893, long before the first error-correcting code, the Hamming code, was developed in the 1940s. The Hadamard code is based on Hadamard matrices, and while there are many different Hadamard matrices that could be used here, normally only Sylvester's construction of Hadamard matrices is used to obtain the codewords of the Hadamard code. James Joseph Sylvester developed his construction of Hadamard matrices in 1867, which actually predates Hadamard's work on Hadamard matrices. Hence the name Hadamard code is not undisputed and sometimes the code is called Walsh code, honoring the American mathematician Joseph Leonard Walsh.

A Hadamard code was used during the 1971 Mariner 9 mission to correct for picture transmission errors. 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". It employed the fast Fourier transform which can increase the decoding speed by a factor of 3. Since the 1990s use of this code by space programs has more or less ceased, and the Deep Space Network does not support this error correction scheme for its dishes that are greater than 26m.

Construction

While all Hadamard codes are based on Hadamard matrices, the constructions differ in subtle ways for different scientific fields, authors, and uses. Engineers, who use the codes for data transmission, and coding theorists, who analyze extremal properties of codes, typically want the rate of the code to be as high as possible, even if this means that the construction becomes mathematically slightly less elegant. On the other hand, for many applications of Hadamard codes in theoretical computer science it is not so important to achieve the optimal rate, and hence simpler constructions of Hadamard codes are preferred since they can be analyzed more elegantly.

Construction with higher rate

The Hadamard code is obtained from an n-by-n Hadamard matrix H. In particular, the 2n codewords of the Hadamard code are the rows of H and the rows of −H. To obtain a code over the alphabet {0,1}, the mapping −1 ↦ 1, 1 ↦ 0, or, equivalently, x ↦ log₋₁ x, is applied to the matrix elements. That the minimum distance of the code is n/2 follows from the defining property of Hadamard matrices, namely that their rows are mutually orthogonal. This implies that two distinct rows of a Hadamard matrix differ in exactly n/2 positions, and, since negation of a row does not affect orthogonality, that any row of H differs from any row of −H in n/2 positions as well, except when the rows correspond, in which case they differ in n positions.

For the linear code, where n = 2^k-1 and H is of Sylvester type, the message length is log₂(2n) = k. A generator matrix for this code can be constructed by forming the (k−1)×2^k−1 matrix

$\begin{bmatrix} \uparrow & \uparrow & & \uparrow\\ g_0 & g_1 & \dots & g_{2^{k-1}-1} \\ \downarrow & \downarrow & & \downarrow \end{bmatrix}\,.$

where $g_i \in \{0,1\}^{k-1}$ is the vector corresponding to the binary representation of i, and then inserting and additional all-one vector as row 1. In other words, $g_0,g_1,\dots,g_{2^{k=1}-1}$ is the list of all vectors of {0,1}^{k − 1} in lexicographic order. For example, when k = 4, a generator matrix is

$G=\begin{bmatrix}1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\0 & 1 & 0 & 1 & 0 & 1 & 0 & 1\end{bmatrix}.$

For general k, this generator matrix is a parity-check matrix for the extended Hamming code of length 2^k−1 and dimension 2^k−1−k, which makes the Hadamard code the dual code of the extended Hamming code. Alternative constructions for the Hadamard code use its parity-check matrix or a recursive encoding process.

Elegant construction

In many theoretical applications of the Hadamard code, the rate does not matter so much. Here, a simpler construction than the above is used that roughly keeps the properties of the code the same. Most authors call this code also Hadamard code, but some texts refer to this simpler code as the Walsh–Hadamard code. The codewords of the Walsh–Hadamard code consist of all rows of an n-by-n Hadamard matrix H that is of Sylvester type, where again the mapping −1 ↦ 1, 1 ↦ 0 has been applied to the matrix elements. This code has n = 2^k codewords, but the block length is twice as large as above, that is, the rate is half of the rate of the above code. The Walsh–Hadamard code of dimension k−1 and the Hadamard code of dimension k both have block length k−1. The former is a subcode of the latter in which the complements of codewords are not codewords. In particular, in the Walsh–Hadamard code, the first letter of every codeword is 0 and therefore the all-one word is not a codeword.

The $k \times 2^k$ generator matrix for the Walsh–Hadamard code of dimension k is obtained from the generator matrix for the Hadamard matrix of dimension k+1, described above, by removing its first row. For example, the generator matrix for the Walsh–Hadamard code of dimension 3 is

$G = \begin{bmatrix} 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1\\ 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1\\ 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{bmatrix}.$

As is usual for linear codes generated by a generator matrix, we encode a message $x\in\{0,1\}^k$, viewed as a row vector, by computing its codeword $z\in\{0,1\}^{2^k}$ using the vector-matrix product in the vector space over the finite field $\mathbb F_2$:

$z=x\cdot G\,.$

This way, the matrix G defines a linear operator $\text{WH}:\{0,1\}^k\to\{0,1\}^{2^k}$ and we can write z = WH(x).

Equivalently, WH can be defined using the scalar product $\langle x , y \rangle$ over $\mathbb F_2^k$:

For any two strings $x,y\in\{0,1\}^k$, we have $\langle x , y \rangle = \sum_{i=1}^{k} x_i y_i\ \bmod\ 2.$

Then $\text{WH}(x)= \big(\langle x , y \rangle\big)_{y\in\{0,1\}^k}$, that is, the Walsh–Hadamard encoding of x is the string consisting of all inner products with x.

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 H^T). 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 H^T) 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.

Optimality

For k ≤ 7 the linear Hadamard codes have been proven optimal in the sense of minimum distance.

References

• Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4, http://www.cs.princeton.edu/theory/complexity/ 
• Lecture notes of Atri Rudra: Hamming code and Hamming bound