Also known as Walsh code, Walsh-Hadamard code.

## Description

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 is the first-order RM code (a.k.a. RM\((1,m)\)), while the \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is the simplex code (a.k.a. RM\(^*(1,m)\)).

## Parents

- Binary linear LTC — The Hadamard code is the first code to be identified as a (three-query) LTC [1,2].
- Balanced code — Each Hadamard codeword has length \(2^m\) and Hamming weight of \(2^{m-1}\), making this code balanced.
- \(q\)-ary linear LCC — Hadamard codes are two-query LDCs and LCCs [3,4].

## Cousins

- 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.
- 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.
- \([2^r-1,2^r-r-1,3]\) Hamming code — The Hadamard code is the dual of the extended Hamming Code. Conversely, 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. Conversely, the shortened Hadamard code is the dual of the Hamming Code.
- Reed-Muller (RM) code — The \([2^m,m+1,2^{m-1}]\) augmented Hadamard code is the first-order RM code (a.k.a. RM\((1,m)\)), while the \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is the simplex code (a.k.a. RM\(^*(1,m)\)).
- \(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].
- \([2^m-1,m,2^{m-1}]\) simplex code — Binary simplex codes are shortened Hadamard codes.
- \([2^m,m+1,2^{m-1}]\) First-order RM code — First-order RM codes are augmented Hadamard codes.
- Error-correcting output code (ECOC) — Hadamard codes and subcodes can be used as ECOCs [7–9].
- 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]
- M. Blum, M. Luby, and R. Rubinfeld, “Self-testing/correcting with applications to numerical problems”, Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC ’90 (1990) DOI
- [2]
- 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
- [3]
- S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2012) DOI
- [4]
- Gopi, Sivakanth. Locality in coding theory. Diss. Princeton University, 2018.
- [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]
- T. G. Dietterich and G. Bakiri, “Solving Multiclass Learning Problems via Error-Correcting Output Codes”, (1995) arXiv:cs/9501101
- [8]
- V. Guruswami and A. Sahai, “Multiclass learning, boosting, and error-correcting codes”, Proceedings of the twelfth annual conference on Computational learning theory (1999) DOI
- [9]
- 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