## 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

- Dual linear code — The Hadamard code is the dual of the extended Hamming Code. Conversely, the shortened Hadamard code is the dual of the Hamming Code.
- Hamming code — The shortened Hadamard code is the dual of the Hamming Code.
- Extended Hamming code — The Hadamard code is the dual of the extended Hamming Code.
- Reed-Muller (RM) code — The augmented Hadamard code is the RM\((1,m)\) code.
- Simplex spherical code — The shortened Hadamard code maps to a \((2^m,2^m+1)\) simplex spherical code under the antipodal mapping [2; Sec. 6.5.2][3; pg. 18].
- Biorthogonal spherical code — The augmented Hadamard code maps to a \((2^m,2^{m+1})\) biorthogonal spherical code under the antipodal mapping [4][2; Sec. 6.4][3; pg. 19].
- \(q\)-ary sharp configuration — Hadamard codes for \(q=4r\) are sharp configurations [5; Table 12.1].
- Universally optimal \(q\)-ary code — Several punctured versions of Hadamard codes are LP universally optimal codes [6].
- Binary linear LTC — The Hadamard code is the first code to be identified as locally testable [7].
- Levenshtein code — The augmented Hadamard and Levenshtein codes are both constructed using Hadamard matrices.
- Error-correcting output code (ECOC) — Hadamard codes and subcodes can be used as ECOCs [8–10].
- Simplex code — Binary simplex codes are \([2^m-1,m,2^{m-1}]\) shortened Hadamard codes.
- Hadamard BPSK c-q code — The Hadamard BPSK c-q code can be thought of as a concatenation of the Hadamard binary linear code with BPSK for the purposes of transmission of classical information over quantum channels.

## 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

- Victor V. Albert (2023-03-05) — most recent
- Alexander Barg (2023-03-05)
- Victor V. Albert (2021-12-18)
- Dhruv Devulapalli (2021-12-17)

## 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.