Hadamard code 

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)\)). Rows of a Hadamard matrix forming a Prometheus orthonormal set (PONS) are codewords of a coset of RM\((1,m)\) in RM\((2,m)\) [6].
  • \([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)\) [6].
  • \(q\)-ary sharp configuration — Hadamard codes for \(q=4r\) are sharp configurations [7; Table 12.1].
  • Universally optimal \(q\)-ary code — Several punctured Hadamard codes are LP universally optimal codes [8].
  • Combinatorial design — Hadamard designs are combinatorial designs constructed from Hadamard matrices [9]; see Ref. [10].
  • Difference-set cyclic (DSC) code — Hadamard difference sets are difference sets constructed from Hadamard matrices [11; Ch. 6].
  • Error-correcting output code (ECOC) — Hadamard codes and subcodes can be used as ECOCs [12–14].
  • 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]
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
[7]
P. Boyvalenkov, D. Danev, "Linear programming bounds." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[8]
H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
[9]
J. A. Todd, “A Combinatorial Problem”, Journal of Mathematics and Physics 12, 321 (1933) DOI
[10]
C. J. Colbourn and J. H. Dinitz, editors , Handbook of Combinatorial Designs (Chapman and Hall/CRC, 2006) DOI
[11]
C. Ding, Codes from Difference Sets (WORLD SCIENTIFIC, 2014) DOI
[12]
T. G. Dietterich and G. Bakiri, “Solving Multiclass Learning Problems via Error-Correcting Output Codes”, (1995) arXiv:cs/9501101
[13]
V. Guruswami and A. Sahai, “Multiclass learning, boosting, and error-correcting codes”, Proceedings of the twelfth annual conference on Computational learning theory (1999) DOI
[14]
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
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.