On linear balancing sets

Previous Article
Linear programming bounds for unitary codes
AMC Home
This Issue
Next Article
New linear codes from matrix-product codes with polynomial units

August 2010, 4(3): 345-361. doi: 10.3934/amc.2010.4.345

On linear balancing sets

Arya Mazumdar ^1, , Ron M. Roth ^2, and Pascal O. Vontobel ^3,

1.	Department of Electrical and Computer Engineering, University of Maryland, College Park, MD 20742
2.	Computer Science Department, Technion, Haifa 32000, Israel
3.	Hewlett–Packard Laboratories, Palo Alto, CA 94304, United States

Received November 2009 Revised March 2010 Published August 2010

Abstract
Related Papers

Let $n$ be an even positive integer and $\mathbb F$ be the field GF$(2)$. A word in $\mathbb F$ⁿ is called balanced if its Hamming weight is $n$/$2$. A subset $\mathcal C\subseteq\mathbb F$ⁿ is called a balancing set if for every word $\mathbf y\in\mathbb F$ⁿ there is a word $\mathbf x\in \mathcal C$ such that $\mathbf y + \mathbf x$ is balanced. It is shown that most linear subspaces of $\mathbb F$ⁿ of dimension slightly larger than $\frac{3}{2} \log$₂$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 $\mathbb F$ⁿ 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.

Keywords: covering of Hamming space., balanced codewords, linear codes, Balancing sets.

Mathematics Subject Classification: Primary: 94B05, 94B25; Secondary: 68R0.

Citation: Arya Mazumdar, Ron M. Roth, Pascal O. Vontobel. On linear balancing sets. Advances in Mathematics of Communications, 2010, 4 (3) : 345-361. doi: 10.3934/amc.2010.4.345

[1]	Alexander A. Davydov, Massimo Giulietti, Stefano Marcugini, Fernanda Pambianco. Linear nonbinary covering codes and saturating sets in projective spaces. Advances in Mathematics of Communications, 2011, 5 (1) : 119-147. doi: 10.3934/amc.2011.5.119
[2]	Irene Márquez-Corbella, Edgar Martínez-Moro. Algebraic structure of the minimal support codewords set of some linear codes. Advances in Mathematics of Communications, 2011, 5 (2) : 233-244. doi: 10.3934/amc.2011.5.233
[3]	Tsonka Baicheva, Iliya Bouyukliev. On the least covering radius of binary linear codes of dimension 6. Advances in Mathematics of Communications, 2010, 4 (3) : 399-404. doi: 10.3934/amc.2010.4.399
[4]	Manish K. Gupta, Chinnappillai Durairajan. On the covering radius of some modular codes. Advances in Mathematics of Communications, 2014, 8 (2) : 129-137. doi: 10.3934/amc.2014.8.129
[5]	Vianney Perchet, Marc Quincampoix. A differential game on Wasserstein space. Application to weak approachability with partial monitoring. Journal of Dynamics & Games, 2019, 6 (1) : 65-85. doi: 10.3934/jdg.2019005
[6]	Laurent Gosse. Well-balanced schemes using elementary solutions for linear models of the Boltzmann equation in one space dimension. Kinetic & Related Models, 2012, 5 (2) : 283-323. doi: 10.3934/krm.2012.5.283
[7]	Joaquim Borges, Josep Rifà, Victor Zinoviev. Completely regular codes by concatenating Hamming codes. Advances in Mathematics of Communications, 2018, 12 (2) : 337-349. doi: 10.3934/amc.2018021
[8]	Rafael Arce-Nazario, Francis N. Castro, Jose Ortiz-Ubarri. On the covering radius of some binary cyclic codes. Advances in Mathematics of Communications, 2017, 11 (2) : 329-338. doi: 10.3934/amc.2017025
[9]	Otávio J. N. T. N. dos Santos, Emerson L. Monte Carmelo. A connection between sumsets and covering codes of a module. Advances in Mathematics of Communications, 2018, 12 (3) : 595-605. doi: 10.3934/amc.2018035
[10]	Anuradha Sharma, Saroj Rani. Trace description and Hamming weights of irreducible constacyclic codes. Advances in Mathematics of Communications, 2018, 12 (1) : 123-141. doi: 10.3934/amc.2018008
[11]	Qi Wang, Yue Zhou. Sets of zero-difference balanced functions and their applications. Advances in Mathematics of Communications, 2014, 8 (1) : 83-101. doi: 10.3934/amc.2014.8.83
[12]	Gérard Cohen, Alexander Vardy. Duality between packings and coverings of the Hamming space. Advances in Mathematics of Communications, 2007, 1 (1) : 93-97. doi: 10.3934/amc.2007.1.93
[13]	B. K. Dass, Namita Sharma, Rashmi Verma. Characterization of extended Hamming and Golay codes as perfect codes in poset block spaces. Advances in Mathematics of Communications, 2018, 12 (4) : 629-639. doi: 10.3934/amc.2018037
[14]	Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333
[15]	Maciej J. Capiński. Covering relations and the existence of topologically normally hyperbolic invariant sets. Discrete & Continuous Dynamical Systems - A, 2009, 23 (3) : 705-725. doi: 10.3934/dcds.2009.23.705
[16]	Masaaki Harada, Akihiro Munemasa. On the covering radii of extremal doubly even self-dual codes. Advances in Mathematics of Communications, 2007, 1 (2) : 251-256. doi: 10.3934/amc.2007.1.251
[17]	Aixian Zhang, Zhengchun Zhou, Keqin Feng. A lower bound on the average Hamming correlation of frequency-hopping sequence sets. Advances in Mathematics of Communications, 2015, 9 (1) : 55-62. doi: 10.3934/amc.2015.9.55
[18]	Sergio R. López-Permouth, Steve Szabo. On the Hamming weight of repeated root cyclic and negacyclic codes over Galois rings. Advances in Mathematics of Communications, 2009, 3 (4) : 409-420. doi: 10.3934/amc.2009.3.409
[19]	Olof Heden, Faina I. Solov’eva. Partitions of $\mathbb F$ⁿ into non-parallel Hamming codes. Advances in Mathematics of Communications, 2009, 3 (4) : 385-397. doi: 10.3934/amc.2009.3.385
[20]	Alonso sepúlveda Castellanos. Generalized Hamming weights of codes over the $\mathcal{GH}$ curve. Advances in Mathematics of Communications, 2017, 11 (1) : 115-122. doi: 10.3934/amc.2017006

2018 Impact Factor: 0.879

American Institute of Mathematical Sciences