## Abstract

Let n be an even positive integer and F be the field GF(2). A word in F^{n} is called balanced if its Hamming weight is n/2. A subset C ⊆ F^{n} is called a balancing set if for every word y ε 2 F^{n} there is a word x ε C such that y + x is balanced. It is shown that most linear subspaces of Fn of dimension slightly larger than 3/2 log_{2} n are balancing sets. A generalization of this result to linear subspaces that are "almost balancing" is also presented. On the other hand, it is shown that the problem of deciding whether a given set of vectors in F^{n} spans a balancing set, is NP-hard. An application of linear balancing sets is presented for designing efficient error-correcting coding schemes in which the codewords are balanced.

Original language | English (US) |
---|---|

Pages (from-to) | 345-361 |

Number of pages | 17 |

Journal | Advances in Mathematics of Communications |

Volume | 4 |

Issue number | 3 |

DOIs | |

State | Published - Aug 2010 |

Externally published | Yes |

## Keywords

- Balanced codewords
- Balancing sets
- Covering of hamming space
- Linear codes