Hadamard code: Difference between revisions

Revision as of 20:01, 29 August 2019

Revision as of 16:17, 15 September 2019

Line 11:

}}

{{infobox code

| name = PuncturedAugmented Hadamard code

| namesake = [[Jacques Hadamard]]

| type = [[Linear code|Linear]] [[block code]]

Line 21:

| notation = <math>[2^k,k+1,2^{k-1}]_2</math>-code

}}

[[File:Hadamard-Code.svg|thumb|250 px|Matrix of the PuncturedAugmented Hadamard code [32, 6, 16] for the [[Reed–Muller code]] (1, 5) of the NASA space probe [[Mariner 9]]]]

[[File:Multigrade operator XOR.svg|thumb|250px|[[Exclusive or|XOR]] operations<br>Here the white fields stand for 0<br>and the red fields for 1]]

Line 28:

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]] over a [[binary set|binary alphabet]] that maps messages of length <math>k2^m</math> toover codewordsa of[[binary lengthset|binary <math>2^k</math>alphabet]].

ItUnfortunately, this term is uniquesomewhat inambiguous thatas eachsome non-zeroreferences codeword hasassume a [[Hammingmessage weight]] of exactlylength <math>2^{k-1} = m</math>, whichwhile impliesothers thatassume thea [[Blockmessage code#The distance d|distance]]length of the code is also <math>2^{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 '''puncturedaugmented 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.

TheIn puncturedcommunication theory, this code is typically 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.

Line 67 ⟶ 70:

[[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 disputed and sometimes the code is called ''Walsh code'', honoring the American mathematician [[Joseph Leonard Walsh]].

AAn augmented 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 at the time (due to Doppler Tracking Loop issues) the maximum useful data length was about 30 bits. Instead of using a [[repetition code]], a [32, 6, 16] Hadamard code was used.

Line 87 ⟶ 90:

:<math>\text{Had}(x) = \Big(\langle x , y \rangle\Big)_{y\in\{0,1\}^k}</math>

As mentioned above, the ''puncturedaugmented'' Hadamard code is used in practice since the Hadamard code itself is somewhat wasteful.

This is because, if the first bit of <math>y</math> is zero, <math>y_1=0</math>, then the inner product contains no information whatsoever about <math>x_1</math>, and hence, it is impossible to fully decode <math>x</math> from those positions of the codeword alone.

On the other hand, when the codeword is restricted to the positions where <math>y_1=1</math>, it is still possible to fully decode <math>x</math>.

Hence it makes sense to restrict the Hadamard code to these positions, which gives rise to the ''puncturedaugmented'' Hadamard encoding of <math>x</math>; that is, <math>\text{pHad}(x) = \Big(\langle x , y \rangle\Big)_{y\in\{1\}\times\{0,1\}^{k-1}}</math>.

===Construction using a generator matrix===

Line 116 ⟶ 119:

The matrix <math>G</math> is a <math>(k\times 2^k)</math>-matrix and gives rise to the [[linear operator]] <math>\text{Had}:\{0,1\}^k\to\{0,1\}^{2^k}</math>.

The generator matrix of the ''puncturedaugmented'' Hadamard code is obtained by restricting the matrix <math>G</math> to the columns whose first entry is one.

For example, the generator matrix for the puncturedaugmented Hadamard code of dimension <math>k=3</math> is:

:<math>

Line 129 ⟶ 132:

Then <math>\text{pHad}:\{0,1\}^k\to\{0,1\}^{2^{k-1}}</math> is a linear mapping with <math>\text{pHad}(x)= x \cdot G'</math>.

For general <math>k</math>, the generator matrix of the puncturedaugmented Hadamard code is a [[parity-check matrix]] for the [[Hamming code#Hamming codes with additional parity (SECDED)|extended Hamming code]] of length <math>2^{k-1}</math> and dimension <math>2^{k-1}-k</math>, which makes the puncturedaugmented Hadamard code the [[dual code]] of the extended Hamming code.

Hence an alternative way to define the Hadamard code is in terms of its parity-check matrix: the parity-check matrix of the Hadamard code is equal to the generator matrix of the Hamming code.

Line 135 ⟶ 138:

Generalized Hadamard codes are obtained from an ''n''-by-''n'' [[Hadamard matrix]] ''H''. In particular, the 2''n'' codewords of the code are the rows of ''H'' and the rows of −''H''. To obtain a code over the alphabet {0,1}, the mapping −1&nbsp;↦&nbsp;1, 1&nbsp;↦&nbsp;0, or, equivalently, ''x''&nbsp;↦&nbsp;(1&nbsp;&minus;&nbsp;''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. 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.

To get the puncturedaugmented Hadamard code above with <math>n=2^{k-1}</math>, the chosen Hadamard matrix ''H'' has to be of Sylvester type, which gives rise to a message length of <math>\log_2(2n)=k</math>.

==Distance==

Line 147 ⟶ 150:

Then, when conditioned on the values of <math>y_2,\dots,y_k</math>, the event is equivalent to <math>y_1 \cdot x_1 = b</math> for some <math>b\in\{0,1\}</math> depending on <math>x_2,\dots,x_k</math> and <math>y_2,\dots,y_k</math>. The probability that <math>y_1=b</math> happens is exactly <math>1/2</math>. Thus, in fact, ''all'' non-zero codewords of the Hadamard code have relative Hamming weight <math>1/2</math>, and thus, its relative distance is <math>1/2</math>.

The relative distance of the ''puncturedaugmented'' Hadamard code is <math>1/2</math> as well, but it no longer has the property that every non-zero codeword has weight exactly <math>1/2</math> since the all <math>1</math>s vector <math>1^{2^{k-1}}</math> is a codeword of the puncturedaugmented Hadamard code. This is because the vector <math>x=10^{k-1}</math> encodes to <math>\text{pHad}(10^{k-1}) = 1^{2^{k-1}}</math>. Furthermore, whenever <math>x</math> is non-zero and not the vector <math>10^{k-1}</math>, the random subsum principle applies again, and the relative weight of <math>\text{Had}(x)</math> is exactly <math>1/2</math>.

==Local decodability ==