On linear balancing sets

DOI10.3934/AMC.2010.4.345MaRDI QIDQ540382zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(7)

• Balancing sets of vectors
• The maximum number of balancing sets
• Lower bound for balanced sets
• scientific article; zbMATH DE number 3190563 (Why is no real title available?)
• Balanced and absorbing subsets with empty interior
• BALANCED SETS AND THE VECTOR GAME
• scientific article; zbMATH DE number 524124 (Why is no real title available?)

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)