Balanced code[1]
Description
An even-length-\(n\) \(q\)-ary code whose nonzero codewords all have a Hamming weight of \(n/2\). A code is \(\epsilon\)-balanced if the relative weight (i.e., weight divided by \(n\)) of all nonzero codewords lies in the interval \([\frac{1-\epsilon}{2},\frac{1+\epsilon}{2}]\). A code is \(\gamma\)-unbiased if the relative weight lies in the interval \((\frac{1}{2}-\frac{1}{n^{\gamma}},\frac{1}{2}+\frac{1}{n^{\gamma}})\).
Protection
Can detect unidirectional errors, such as a zero going to a one.
Encoding
Efficient encoder [1].
Decoding
Realizations
Balanced length-eight code, known as a 6b/8b encoding, used for balancing direct current in a communications system [4]
Parents
Child
- Hadamard code — Each Hadamard codeword has length \(2^m\) and Hamming weight of \(2^{m-1}\), making this code balanced.
Cousins
- Locally testable code (LTC) — Random low-rate unbiased linear codes are LTCs [5].
- Ta-Shma zigzag code — Ta-Shma codes are \(\epsilon\)-balanced.
References
- [1]
- D. Knuth, “Efficient balanced codes”, IEEE Transactions on Information Theory 32, 51 (1986) DOI
- [2]
- S. Al-Bassam and B. Bose, “On balanced codes”, IEEE Transactions on Information Theory 36, 406 (1990) DOI
- [3]
- K. A. Schouhamer Immink and J. H. Weber, “Very Efficient Balanced Codes”, IEEE Journal on Selected Areas in Communications 28, 188 (2010) DOI
- [4]
- K. A. S. Immink. Codes for mass data storage systems. Shannon Foundation Publisher, 2004.
- [5]
- S. Kopparty and S. Saraf, “Local list-decoding and testing of random linear codes from high error”, Proceedings of the forty-second ACM symposium on Theory of computing (2010) DOI
Page edit log
- Victor V. Albert (2022-07-14) — most recent
Cite as:
“Balanced code”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2022. https://errorcorrectionzoo.org/c/balanced