Hadamard code 

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 [79].
  • 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

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.