Hadamard code

The Hadamard code, named after Jacques Hadamard, is a system used for signal error detection and correction. It is one of the family of [2^"n", "n" + 1, 2^{"n" − 1}] codes. Especially for large "n" it has a poor rate but it is capable of correcting many errors.

Construction

The code is based on Hadamard matrices. If "H" is an Hadamard matrix of order 2^"n" the codewords are constructed by taking the rows of "H" and −"H" as codewords, where each −1 is replaced by 0. In this way 2^{"n" + 1} code words are constructed that each have a length of 2^"n". Since the rows of a Hadamard matrix are orthogonal the minimum distance is 2^{"n" - 1}. In this way a [2^"n", "n" + 1, 2^{"n" − 1}] code is constructed.

The code can also be constructed by creating the parity-check matrix which consists of all 2^{"n" − 1} vectors containing an odd number of 1s, or by using a recursive encoding process.

Decoding

The code has minimum distance 2^{"n" − 1} and hence can correct at most "t" = 2^{"n" − 2} − 1 errors. The algorithm below achieves this.

When a code word is received it is first transformed to a 1/−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 code word. If it is positive the code word came from "H", if it is negative the code word came from −"H".

"Proof:" If there wereno errors the product ("v" "H"^T) would consist of only zero's and one entry of +/−2^"n". If there are errors in "v" then, in absolute value, some of the zeros become larger and the maximum becomes smaller. Each error that occurs can change a zero with 2. So the zeros can become at most 0 + 2"t" = "2"^{"n" − 1} − 2. The maximumcan decrease at most to 2^"n" − 2"t" = 2^"n" − 2^{"n" − 1} + 2 = 2^{"n" − 1} + 2. So the maximum that points to the correct row will always be larger in absolute value than the other values in the row.

History

A Hadamard code was used during the 1971 Mariner 9 mission to correct for picture transmission error. [ [http://www-math.cudenver.edu/~wcherowi/courses/m4410/m5410cd1.html] . Part of "Math 4410 - Mathematics of Coding Theory"] 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". [ [http://www-math.cudenver.edu/~wcherowi/courses/m6409/mariner9talk.pdf] Combinatorics in SpaceThe Mariner 9 Telemetry System] . It employed the Fast Fourier Transform which can increase the decryption speed with a factor of 3.

Optimality

For value of n <= 6 the Hadamard codes have been proven optimal. ["Optimal binary linear codes of dimension at most seven", David B. Jaffe, Iliya Bouyukliev. [http://www.math.unl.edu/~djaffe2/papers/sevens.html] ]

Notes