# 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 42nd ACM symposium on Theory of computing - STOC ’10 (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