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)\)).Decoding
Local decoder making one quantum query to the received word [1].Notes
Review of Hadamard matrices [2].Cousins
- Locally recoverable code (LRC)— The Hadamard code is an LRC with \(r=3\) [3].
- 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.
- Binary quadratic-residue (QR) code— For Hadamard matrices obtained from the Paley construction, the linear span of the resulting Hadamard codes yields quadratic-residue codes [4; pg. 49].
- 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)\) [5].
- \([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)\) [5].
- \(q\)-ary sharp configuration— The augmented binary Hadamard code family is listed among the sharp configurations in [6; Table 12.1].
- Universally optimal \(q\)-ary code— Several punctured Hadamard codes are LP universally optimal codes [7].
- Combinatorial design— Hadamard designs are combinatorial designs constructed from Hadamard matrices [8,9]; see Ref. [10].
- Polar code— The generator matrices of RM and polar codes are different submatrices of Kronecker products of Hadamard matrices [11,12]. There are families interpolating between the two codes [13].
- Difference-set cyclic (DSC) code— Hadamard difference sets are difference sets constructed from Hadamard matrices [14; Ch. 6].
- Error-correcting output code (ECOC)— Hadamard codes and subcodes can be used as ECOCs [15–17].
- Linear \(q\)-ary code— Random linear codes are random puncturings of the \(q\)-ary Hadamard code, whose generator matrix has every vector of \(\mathbb{F}_q^k\) as a column [18; Sec. 4.3].
- Hadamard BPSK c-q modulation format— 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.
Primary Hierarchy
References
- [1]
I. Kerenidis and R. de Wolf, “Exponential Lower Bound for 2-Query Locally Decodable Codes via a Quantum Argument”, (2002) arXiv:quant-ph/0208062
- [2]
A. Hedayat and W. D. Wallis, “Hadamard Matrices and Their Applications”, The Annals of Statistics 6, (1978) DOI
- [3]
L. Golowich and V. Guruswami, “Quantum Locally Recoverable Codes”, (2023) arXiv:2311.08653
- [4]
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (Elsevier, 1977)
- [5]
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
- [6]
P. Boyvalenkov, D. Danev, “Linear programming bounds”, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021), pp. 251-266 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. Seberry and M. Yamada, “Hadamard matrices, Sequences, and Block Designs”, University of Wollongong (1992) URL
- [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]
E. Arikan, “Channel Polarization: A Method for Constructing Capacity-Achieving Codes for Symmetric Binary-Input Memoryless Channels”, IEEE Transactions on Information Theory 55, 3051 (2009) arXiv:0807.3917 DOI
- [12]
E. Arikan, “A survey of reed-muller codes from polar coding perspective”, IEEE Information Theory Workshop 2010 (ITW 2010) 1 (2010) DOI
- [13]
M. Mondelli, S. H. Hassani, and R. Urbanke, “From Polar to Reed-Muller Codes: a Technique to Improve the Finite-Length Performance”, (2014) arXiv:1401.3127
- [14]
C. Ding, Codes from Difference Sets (WORLD SCIENTIFIC, 2014) DOI
- [15]
T. G. Dietterich and G. Bakiri, “Solving Multiclass Learning Problems via Error-Correcting Output Codes”, (1995) arXiv:cs/9501101
- [16]
V. Guruswami and A. Sahai, “Multiclass learning, boosting, and error-correcting codes”, Proceedings of the twelfth annual conference on Computational learning theory 145 (1999) DOI
- [17]
A. Zhang, Z.-L. Wu, C.-H. Li, and K.-T. Fang, “On Hadamard-Type Output Coding in Multiclass Learning”, Lecture Notes in Computer Science 397 (2003) DOI
- [18]
A. Rudra and M. Wootters, “Every list-decodable code for high noise has abundant near-optimal rate puncturings”, (2013) arXiv:1310.1891
- [19]
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 73 (1990) DOI
- [20]
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
- [21]
S. Yekhanin, “Locally Decodable Codes”, Foundations and Trends® in Theoretical Computer Science 6, 139 (2012) DOI
- [22]
S. Gopi, “Locality in coding theory”, PhD thesis, Princeton University, 2018.
Page edit log
- Victor V. Albert (2026-10-26) — most recent
- Victor V. Albert (2026-06-08)
- Victor V. Albert (2023-03-05)
- Alexander Barg (2023-03-05)
- Victor V. Albert (2021-12-18)
- Dhruv Devulapalli (2021-12-17)
Cite as:
“\([2^m,m,2^{m-1}]\) Hadamard code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2026. https://errorcorrectionzoo.org/c/hadamard, arXiv:2606.11484