Hadamard code 

Description

Also known as a Walsh code or Walsh-Hadamard code. An \([2^m,m,2^{m-1}]\) balanced binary code dual to an extended Hamming Code.

The \([2^m,m+1,2^{m-1}]\) augmented Hadamard code can be constructed by adding the all-zero bit. Its codewords are the rows of the \(2^m\)-dimensional Hadamard matrix \(H\) and its negation \(-H\) with the mapping \(+1\to 0\) and \(-1\to 1\). Its codewords form a \(2^m\)-dimensional biorthogonal spherical code under the antipodal mapping.

The \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is a binary simplex code. Its codewords form a \(2^m\)-simplex spherical code under the antipodal mapping.

Parents

  • Long code — The Hadamard code is a subcode of the long code and can be obtained by restricting the long-code construction to only linear functions.
  • Balanced code — Each Hadamard codeword has length \(2^m\) and Hamming weight of \(2^{m-1}\), making this code balanced.
  • Locally decodable code (LDC) — Hadamard codes are locally decodable [1].

Cousins

References

[1]
S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2011) DOI
[2]
Forney, G. D. (2003). 6.451 Principles of Digital Communication II, Spring 2003.
[3]
T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
[4]
G. D. Forney and G. Ungerboeck, “Modulation and coding for linear Gaussian channels”, IEEE Transactions on Information Theory 44, 2384 (1998) DOI
[5]
P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[6]
H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
[7]
M. Blum, M. Luby, and R. Rubinfeld, “Self-testing/correcting with applications to numerical problems”, Journal of Computer and System Sciences 47, 549 (1993) DOI
[8]
T. G. Dietterich and G. Bakiri, “Solving Multiclass Learning Problems via Error-Correcting Output Codes”, (1995) arXiv:cs/9501101
[9]
V. Guruswami and A. Sahai, “Multiclass learning, boosting, and error-correcting codes”, Proceedings of the twelfth annual conference on Computational learning theory (1999) DOI
[10]
A. Zhang et al., “On Hadamard-Type Output Coding in Multiclass Learning”, Intelligent Data Engineering and Automated Learning 397 (2003) DOI
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: hadamard

Cite as:
“Hadamard code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/hadamard
BibTeX:
@incollection{eczoo_hadamard, title={Hadamard code}, booktitle={The Error Correction Zoo}, year={2023}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/hadamard} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/hadamard

Cite as:

“Hadamard code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2023. https://errorcorrectionzoo.org/c/hadamard

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/bits/easy/hadamard.yml.