Also known as Walsh code, Walsh-Hadamard code.
Description
An \([2^m,m,2^{m-1}]\) balanced binary 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)\)).
Notes
Review of Hadamard matrices [1].
Parents
- Binary linear LTC — The Hadamard code is the first code to be identified as a (three-query) LTC [2,3].
- 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 [4,5].
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.
- 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)\)). The \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is the simplex code (a.k.a. RM\(^*(1,m)\)).
- \([2^m-1,m,2^{m-1}]\) simplex code — The \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is the simplex code (a.k.a. RM\(^*(1,m)\)).
- \([2^m,m+1,2^{m-1}]\) First-order 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)\)).
- \(q\)-ary sharp configuration — Hadamard codes for \(q=4r\) are sharp configurations [6; Table 12.1].
- Universally optimal \(q\)-ary code — Several punctured Hadamard codes are LP universally optimal codes [7].
- Combinatorial design — Hadamard designs form a set of combinatorial designs that are equivalent to Hadamard matrices [8]; see Ref. [9].
- Error-correcting output code (ECOC) — Hadamard codes and subcodes can be used as ECOCs [10–12].
- 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]
- A. Hedayat and W. D. Wallis, “Hadamard Matrices and Their Applications”, The Annals of Statistics 6, (1978) DOI
- [2]
- 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
- [3]
- 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
- [4]
- S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2012) DOI
- [5]
- Gopi, Sivakanth. Locality in coding theory. Diss. Princeton University, 2018.
- [6]
- P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [7]
- H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
- [8]
- J. A. Todd, “A Combinatorial Problem”, Journal of Mathematics and Physics 12, 321 (1933) DOI
- [9]
- C. J. Colbourn and J. H. Dinitz, editors , Handbook of Combinatorial Designs (Chapman and Hall/CRC, 2006) DOI
- [10]
- T. G. Dietterich and G. Bakiri, “Solving Multiclass Learning Problems via Error-Correcting Output Codes”, (1995) arXiv:cs/9501101
- [11]
- V. Guruswami and A. Sahai, “Multiclass learning, boosting, and error-correcting codes”, Proceedings of the twelfth annual conference on Computational learning theory (1999) DOI
- [12]
- 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