The Hadamard code is an error-correcting code named after the French mathematician Jacques Hadamard that is used for error detection and correction when transmitting messages over very noisy or unreliable channels.

In 1971, the code was used to transmit photos of Mars back to Earth from the NASA space probe Mariner 9.

Unfortunately, this term is somewhat ambiguous as some references assume a message length

The Hadamard code is unique in that each non-zero codeword has a Hamming weight of exactly

-code, that is, it is a linear code over a binary alphabet, has block length

Such codes were first constructed by Raj Chandra Bose and Sharadchandra Shankar Shrikhande in 1959.

, 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.

The Hadamard code is a locally decodable code, which provides a way to recover parts of the original message with high probability, while only looking at a small fraction of the received word.

This gives rise to applications in computational complexity theory and particularly in the design of probabilistically checkable proofs.

Since the relative distance of the Hadamard code is 1/2, normally one can only hope to recover from at most a 1/4 fraction of error.

It is usual in the CDMA literature to refer to codewords as “codes”.

Each user will use a different codeword, or “code”, to modulate their signal.

Because Walsh codewords are mathematically orthogonal, a Walsh-encoded signal appears as random noise to a CDMA capable mobile terminal, unless that terminal uses the same codeword as the one used to encode the incoming signal.

An augmented Hadamard code was used during the 1971 Mariner 9 mission to correct for picture transmission errors.

Because of limitations of the quality of the alignment of the transmitter at the time (due to Doppler Tracking Loop issues) the maximum useful data length was about 30 bits.

The efficient decoding algorithm was an important factor in the decision to use this code.

It employed the fast Fourier transform which can increase the decoding speed by a factor of three.

Since the 1990s use of this code by space programs has more or less ceased, and the NASA Deep Space Network does not support this error correction scheme for its dishes that are greater than 26 m. While all Hadamard codes are based on Hadamard matrices, the constructions differ in subtle ways for different scientific fields, authors, and uses.

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.

In particular, an equivalent way to write the inner product definition for the Hadamard code arises by using the generator matrix whose columns consist of all strings

For example, the generator matrix for the augmented Hadamard code of dimension

To obtain a code over the alphabet {0,1}, the mapping −1 ↦ 1, 1 ↦ 0, or, equivalently, x ↦ (1 − x)/2, 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.

, the chosen Hadamard matrix H has to be of Sylvester type, which gives rise to a message length of

The distance of a code is the minimum Hamming distance between any two distinct codewords, i.e., the minimum number of positions at which two distinct codewords differ.

Thus, in fact, all non-zero codewords of the Hadamard code have relative Hamming weight

, the random subsum principle applies again, and the relative weight of

A locally decodable code is a code that allows a single bit of the original message to be recovered with high probability by only looking at a small portion of the received word.

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