Hadamard code: Difference between revisions

Revision as of 13:59, 13 April 2021

Revision as of 20:07, 18 June 2021

Line 1:

{{Lead too long|date=May 2020}}

{{use dmy dates|date=June 2021|cs1-dates=y}}

{{infobox code

| name = Hadamard code

Line 25 ⟶ 26:

[[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]]

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: name="Malek_2006"//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]].

The Hadamard code is also known under the names '''Walsh code''', '''Walsh family''',<ref>See, e.g., {{Harvtxt|name="Amadei|-Manzoli|Merani|2002}}<-Merani_2002"/ref> and '''Walsh–Hadamard code'''<ref>See, e.g., {{Harvtxt|name="Arora|Barak|2009|loc=Section 19.2.2}}.<-Barak_2009"/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]].

Line 37 ⟶ 38:

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 is simply 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|pname=3}}.<"Guruswami_2009"/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.

In general, such a code is not linear.

Such codes were first constructed by [[R. C. Bose]] and [[Sharadchandra Shankar Shrikhande|S. S. Shrikhande]] in 1959.<ref>{{cite journalname="Bose_1959"/>

| last1 = Bose | first1 = R.C.

| last2 = Shrikhande | first2 = S.S.

| title =A note on a result in the theory of code construction

| journal = Information and Control

| volume = 2

| issue = 2

| year = 1959

| pages = 183–194

| doi = 10.1016/S0019-9958(59)90376-6

| citeseerx = 10.1.1.154.2879

}}</ref>

If ''n'' is the size of the Hadamard matrix, the code has parameters <math>(n,2n,n/2)_2</math>, meaning it is a not-necessarily-linear binary code with 2''n'' 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.

Line 58 ⟶ 48:

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. Using [[list decoding]], however, it is possible to compute a short list of possible candidate messages as long as fewer than <math>\frac{1}{2}-\epsilon</math> of the bits in the received word have been corrupted.

In [[code division multiple access]] (CDMA) communication, the Hadamard code is referred to as Walsh Code, and is used to define individual [[communication channel]]s. 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 (telecommunication)|terminal]], unless that terminal uses the same codeword as the one used to encode the incoming [[signal (information theory)|signal]].<ref>{{cite web|urlname=http:"Langton_2002"//complextoreal.com/wp-content/uploads/2013/01/CDMA.pdf|title=CDMA Tutorial: Intuitive Guide to Principles of Communications|publisher=Complex to Real|access-date=10 November 2017|url-status=live|archive-url=https://web.archive.org/web/20110720084646/http://www.complextoreal.com/CDMA.pdf|archive-date=20 July 2011|df=}}</ref>

==History==

Line 199 ⟶ 189:

==Optimality==

For ''k''&nbsp;≤&nbsp;7 the linear Hadamard codes have been proven optimal in the sense of minimum distance.<ref>{{citation |first=David B. |lastname="Jaffe |first2=Iliya |last2=Bouyukliev |title=Optimal binary linear codes of dimension at most seven |url=http://www.math.unl.edu/~djaffe2/papers/sevens.html |access-date=2007-08-21 |archive-url=https://web.archive.org/web/20070808235329/http://www.math.unl.edu/~djaffe2/papers/sevens.html |archive-date=2007-08-08 |url-status=dead }}<Bouyukliev_2007"/ref>

==See also==

* [[Zadoff–Chu sequence]] — improve over the Walsh–Hadamard codes

==Notes==

{{Reflist}}

==References==

{{Reflist}}|refs=

* {{Citation

<ref name="Malek_2006">{{cite book |title=Coding Theory |chapter=Hadarmark Codes |author-first=Massoud |author-last=Malek |date=2006 |url=http://www.mcs.csueastbay.edu/~malek/TeX/Hadamard.pdf |url-status=dead |archive-url=https://web.archive.org/web/20200109044013/http://www.mcs.csueastbay.edu/~malek/TeX/Hadamard.pdf |archive-date=2020-01-09</ref>

| last1=Amadei | first1=M.

<ref name="Amadei-Manzoli-Merani_2002">{{Cite book |title=Global Telecommunications Conference, 2002. GLOBECOM'02. IEEE |volume=1 |author-last1=Amadei |author-first1=M. |author-last2=Manzoli |author-first2=U. |author-last3=Merani |author-first3=M. L. |chapter=On the assignment of Walsh and quasi-orthogonal codes in a multicarrier DS-CDMA system with multiple classes of users |publisher=[[IEEE]] |isbn=0-7803-7632-3 |doi=10.1109/GLOCOM.2002.1188196 |date=2002 |pages=841–845}}</ref>

| last2=Manzoli | first2=U.

<ref name="Arora-Barak_2009">{{Cite book |title=Computational Complexity: A Modern Approach |chapter=Section 19.2.2 |author-last1=Arora |author-first1=Sanjeev |author-link1=Sanjeev Arora |author-last2=Barak |author-first2=Boaz |publisher=[[Cambridge University Press]] |date=2009 |isbn=978-0-521-42426-4 |url=http://www.cs.princeton.edu/theory/complexity/}}</ref>

| last3=Merani | first3=M.L.

<ref name="Guruswami_2009">{{Cite book |title=List decoding of binary codes |author-last1=Guruswami |author-first1=Venkatesan |date=2009 |page=3 |url=https://www.cs.cmu.edu/~venkatg/pubs/papers/ld-binary-ms.pdf}}</ref>

| chapter=On the assignment of Walsh and quasi-orthogonal codes in a multicarrier DS-CDMA system with multiple classes of users

<ref name="Bose_1959">{{cite journal |title=A note on a result in the theory of code construction |author-last1=Bose |author-first1=R. C. |author-last2=Shrikhande |author-first2=S. S. |journal=[[Information and Control]] |volume=2 |issue=2 |date=1959 |doi=10.1016/S0019-9958(59)90376-6 |citeseerx=10.1.1.154.2879 |pages=183–194}}</ref>

| publisher=IEEE |isbn=0-7803-7632-3 |doi=10.1109/GLOCOM.2002.1188196

<ref name="Langton_2002">{{cite web |title=CDMA Tutorial: Intuitive Guide to Principles of Communications |author-first=Charan |author-last=Langton |date=2002 |url=http://complextoreal.com/wp-content/uploads/2013/01/CDMA.pdf |publisher=Complex to Real |access-date=2017-11-10 |url-status=live |archive-url=https://web.archive.org/web/20110720084646/http://www.complextoreal.com/CDMA.pdf |archive-date=2011-07-20}}</ref>

| year=2002

<ref name="Jaffe-Bouyukliev_2007">{{cite web |title=Optimal binary linear codes of dimension at most seven |author-first=David B. |author-last=Jaffe |author-first2=Iliya |author-last2=Bouyukliev |url=http://www.math.unl.edu/~djaffe2/papers/sevens.html |access-date=2007-08-21 |url-status=dead |archive-url=https://web.archive.org/web/20070808235329/http://www.math.unl.edu/~djaffe2/papers/sevens.html |archive-date=2007-08-08}}</ref>

| pages=841–5

| title=Global Telecommunications Conference, 2002. GLOBECOM'02. IEEE

| volume=1

}}

* {{Citation

==Further reading==

| last1=Arora | first1=Sanjeev |author-link1=Sanjeev Arora

* {{citationcite |first=Atri |last=Rudraweb |title=Hamming code and Hamming bound |formatauthor-first=PDFAtri |author-last=Rudra |url=http://www.cse.buffalo.edu/faculty/atri/courses/coding-theory/lectures/lect4.pdf |work=Lecture notes }}

| last2=Barak | first2=Boaz

* {{cite book |title=Modulationsverfahren |chapter=46.4. Hadamard– oder Walsh–Codes |language=de |author-first1=Dietmar |author-last1=Rudolph |author-first2=Matthias |author-last2=Rudolph |date=2011-04-12 |publisher=[[Brandenburg University of Technology]] (BTU) |publication-place=Cottbus, Germany |page=214 |url=http://www.diru-beze.de/modulationen/skripte/Modulationsverfahren.pdf |access-date=2021-06-14 |url-status=live |archive-url=https://web.archive.org/web/20210616042506/http://www.diru-beze.de/modulationen/skripte/Modulationsverfahren.pdf |archive-date=2021-06-16}} (xiv+225 pages)

| title=Computational Complexity: A Modern Approach

| url = http://www.cs.princeton.edu/theory/complexity/

| publisher=Cambridge University Press

| year=2009

| isbn=978-0-521-42426-4

}}

* {{Citation

| last1=Guruswami | first1=Venkatesan

| title=List decoding of binary codes

| year=2009 |format=PDF

| url=https://www.cs.cmu.edu/~venkatg/pubs/papers/ld-binary-ms.pdf

}}

*{{citation |first=Atri |last=Rudra |title=Hamming code and Hamming bound |format=PDF |url=http://www.cse.buffalo.edu/faculty/atri/courses/coding-theory/lectures/lect4.pdf |work=Lecture notes }}

{{CCSDS}}