Hadamard code
Description
Also known as a Walsh code or Walsh-Hadamard code. 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 can be constructed by adding the all-zero bit. Its codewords are the rows of the \(2^m\)-dimensional Hadamard matrix \(H\) and its negation \(-H\) with the mapping \(+1\to 0\) and \(-1\to 1\). Its codewords form a \(2^m\)-dimensional biorthogonal spherical code under the antipodal mapping.
The \([2^m-1,m,2^{m-1}]\) shortened Hadamard code is a binary simplex code. Its codewords form a \(2^m\)-simplex spherical code under the antipodal mapping.
Parents
- 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.
- Balanced code — Each Hadamard codeword has length \(2^m\) and Hamming weight of \(2^{m-1}\), making this code balanced.
Cousins
- Dual linear code — The Hadamard code is the dual of the extended Hamming Code.
- 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 augmented Hadamard code is the RM\((1,m)\) code.
- Simplex spherical code — The shortened Hadamard code maps to a \((2^m,2^m+1)\) simplex spherical code under the antipodal mapping [1; Sec. 6.5.2][2; pg. 18].
- Biorthogonal spherical code — The augmented Hadamard code maps to a \((2^m,2^{m+1})\) biorthogonal spherical code under the antipodal mapping [3][1; Sec. 6.4][2; pg. 19].
- \(q\)-ary sharp configuration — Hadamard codes for \(q=4r\) are sharp configurations [4; Table 12.1].
- Universally optimal \(q\)-ary code — Several punctured versions of Hadamard codes are LP universally optimal codes [5].
- Binary linear LTC — The Hadamard code is the first code to be identified as locally testable [6].
- Levenshtein code — The augmented Hadamard and Levenshtein codes are both constructed using Hadamard matrices.
- Simplex code — Binary simplex codes are \([2^m-1,m,2^{m-1}]\) shortened Hadamard codes.
References
- [1]
- Forney, G. D. (2003). 6.451 Principles of Digital Communication II, Spring 2003.
- [2]
- T. Ericson, and V. Zinoviev, eds. Codes on Euclidean spheres. Elsevier, 2001.
- [3]
- G. D. Forney and G. Ungerboeck, “Modulation and coding for linear Gaussian channels”, IEEE Transactions on Information Theory 44, 2384 (1998) DOI
- [4]
- W. C. Huffman, J.-L. Kim, and P. Solé, Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
- [5]
- H. Cohn and Y. Zhao, “Energy-Minimizing Error-Correcting Codes”, IEEE Transactions on Information Theory 60, 7442 (2014) arXiv:1212.1913 DOI
- [6]
- 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
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
Github: https://github.com/errorcorrectionzoo/eczoo_data/tree/main/codes/classical/bits/easy/hadamard.yml.