Hadamard code: Difference between revisions

Revision as of 16:17, 15 September 2019

Revision as of 01:31, 16 September 2019

Line 25:

The '''Hadamard code''' is an [[error-correcting code]] named after [[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]].<ref>http://www.mcs.csueastbay.edu/~malek/TeX/Hadamard.pdf</ref> 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]].

ItThe Hadamard code is also known under the names '''Walsh code''', '''Walsh family''',<ref>See, e.g., {{Harvtxt|Amadei|Manzoli|Merani|2002}}</ref> and '''Walsh–Hadamard code'''<ref>See, e.g., {{Harvtxt|Arora|Barak|2009|loc=Section 19.2.2}}.</ref> in recognition of the American mathematician [[Joseph Leonard Walsh]].

The Hadamard code is named after the French mathematician [[Jacques Hadamard]].

It is also known under the names '''Walsh code''', '''Walsh family''',<ref>See, e.g., {{Harvtxt|Amadei|Manzoli|Merani|2002}}</ref> and '''Walsh–Hadamard code'''<ref>See, e.g., {{Harvtxt|Arora|Barak|2009|loc=Section 19.2.2}}.</ref> in recognition of the American mathematician [[Joseph Leonard Walsh]].

The Hadamard code is an example of a [[linear code]] of length <math>2^m</math> over a [[binary set|binary alphabet]].

Unfortunately, this term is somewhat ambiguous as some references assume a message length <math>k = m</math> while others assume a message length of <math>k = m+1</math>.

In this article, the first case is called the '''Hadamard code''' while the second is called the '''augmented Hadamard code'''.

The Hadamard code is unique in that each non-zero codeword has a [[Hamming weight]] of exactly <math>2^{k-1}</math>, which implies that the [[Block code#The distance d|distance]] of the code is also <math>2^{k-1}</math>.

In standard [[Block code#Popular notation|coding theory notation]] for [[block code]]s, the Hadamard code is a <math>[2^k,k,2^{k-1}]_2</math>-code, that is, it is a [[linear code]] over a [[binary set|binary alphabet]], has [[Block code#The block length n|block length]] <math>2^k</math>, [[Block code#The message length k|message length]] (or dimension) <math>k</math>, and [[Block code#The distance d|minimum distance]] <math>2^k/2</math>.

The block length is very large compared to the message length, but on the other hand, errors can be corrected even in extremely noisy conditions.

In

The '''augmented Hadamard code''' is a slightly improved version of the Hadamard code; it is a <math>[2^k,k+1,2^{k-1}]_2</math>-code and thus has a slightly better [[Block code#The rate R|rate]] while maintaining the relative distance of <math>1/2</math>, and is thus preferred in practical applications.

In communication theory, this code is typicallysimply called the Hadamard code and it is the same as the first order [[Reed–Muller code]] over the binary alphabet.<ref>See, e.g., {{harvtxt|Guruswami|2009|p=3}}.</ref>

Normally, Hadamard codes are based on [[Hadamard matrix#Sylvester's construction|Sylvester's construction of Hadamard matrices]], but the term “Hadamard code” is also used to refer to codes constructed from arbitrary [[Hadamard matrix|Hadamard matrices]], which are not necessarily of Sylvester type.