Hadamard Code

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 bits to a codeword of bits; it is able to detect errors and to correct errors. In standard coding theory notation for block codes, the Hadamard code is a -code, that is, it is a linear code over a binary alphabet, has block length, message length (or dimension), and minimum distance . For large, 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, 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.