On linear balancing sets

DOI10.3934/AMC.2010.4.345zbMATH Open1213.94179arXiv0901.3170OpenAlexW3105293487MaRDI QIDQ540382FDOQ540382

Authors: Arya Mazumdar, Ron M. Roth, Pascal O. Vontobel 

Publication date: 3 June 2011

Published in: Advances in Mathematics of Communications (Search for Journal in Brave)

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 subseteq F^n$ is called a balancing set if for every word y in F^n there is a word x in C such that y + x is balanced. It is shown that most linear subspaces of F^n of dimension slightly larger than 3/2log_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.

Full work available at URL: https://arxiv.org/abs/0901.3170

Recommendations

• scientific article; zbMATH DE number 5901714
• Balancing sets of vectors
• On error-correcting balanced codes
• Design of some new efficient balanced codes
• Combinatorial properties of balanced codes over the complexm-th roots of unity and efficient coding algorithms

zbMATH Keywords

linear codesbalanced codewordsbalancing setscovering of Hamming space

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Linear codes (general theory) (94B05) Combinatorial codes (94B25)

Cited In (7)

• Lower bound for balanced sets
• Balancing sets of vectors
• Title not available (Why is that?)
• The maximum number of balancing sets
• Title not available (Why is that?)
• BALANCED SETS AND THE VECTOR GAME
• Balanced and absorbing subsets with empty interior

This page was built for publication: On linear balancing sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q540382)