[Jump to code hierarchy]

Hadamard code

Alternative names: 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].

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)\)). Rows of a Hadamard matrix forming a Prometheus orthonormal set (PONS) are codewords of a coset of RM\((1,m)\) in RM\((2,m)\) [2].
  • \([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)\)). Rows of a Hadamard matrix forming a Prometheus orthonormal set (PONS) are codewords of a coset of RM\((1,m)\) in RM\((2,m)\) [2].
  • \(q\)-ary sharp configuration— Hadamard codes for \(q=4r\) are sharp configurations [3; Table 12.1].
  • Universally optimal \(q\)-ary code— Several punctured Hadamard codes are LP universally optimal codes [4].
  • Combinatorial design— Hadamard designs are combinatorial designs constructed from Hadamard matrices [5]; see Ref. [6].
  • Difference-set cyclic (DSC) code— Hadamard difference sets are difference sets constructed from Hadamard matrices [7; Ch. 6].
  • Error-correcting output code (ECOC)— Hadamard codes and subcodes can be used as ECOCs [8–10].
  • 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.

Member of code lists

Primary Hierarchy

Classical Domain
Binary Kingdom
Binary codeECC
Binary group-orbit codeECC
Linear binary codeLinear \(q\)-ary ECC
Binary linear LTCLinear \(q\)-ary LTC ECC
Parents
Binary linear LTC
The Hadamard code is the first code to be identified as a (three-query) LTC [11,12].
Balanced codeConstant-weight ECC
Each Hadamard codeword has length \(2^m\) and Hamming weight of \(2^{m-1}\), making this code balanced.
\(q\)-ary linear LCCLinear \(q\)-ary LCC LRC Distributed-storage LDC ECC
Hadamard codes are two-query LDCs and LCCs [13,14].
Hadamard code

References

[1]
A. Hedayat and W. D. Wallis, “Hadamard Matrices and Their Applications”, The Annals of Statistics 6, (1978) DOI
[2]
M. An, J. Byrnes, W. Moran, B. Saffari, H. S. Shapiro, and R. Tolimieri, “Pons, Reed-Muller Codes, and Group Algebras”, NATO Science Series II: Mathematics, Physics and Chemistry 155 DOI
[3]
P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[4]
H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
[5]
J. A. Todd, “A Combinatorial Problem”, Journal of Mathematics and Physics 12, 321 (1933) DOI
[6]
C. J. Colbourn and J. H. Dinitz, editors , Handbook of Combinatorial Designs (Chapman and Hall/CRC, 2006) DOI
[7]
C. Ding, Codes from Difference Sets (WORLD SCIENTIFIC, 2014) 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, Z.-L. Wu, C.-H. Li, and K.-T. Fang, “On Hadamard-Type Output Coding in Multiclass Learning”, Intelligent Data Engineering and Automated Learning 397 (2003) DOI
[11]
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
[12]
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
[13]
S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2012) DOI
[14]
Gopi, Sivakanth. Locality in coding theory. Diss. Princeton University, 2018.
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/dual_hamming/hadamard.yml.