Technical Program

Paper Detail

Paper Title Weight Enumerating Function, Number of Full Rank Sub-matrices and Network Coding
Paper IdentifierTU2.R2.3
Authors Mahesh Babu Vaddi, B. Sundar Rajan, Indian Institute of Science, India
Session Network Coding II
Location Saint Germain, Level 3
Session Time Tuesday, 09 July, 11:40 - 13:00
Presentation Time Tuesday, 09 July, 12:20 - 12:40
Manuscript  Click here to download the manuscript
Abstract In most of the network coding problems with $k$ messages, the existence of binary network coding solution over $\mathbb{F}_2$ depends on the existence of adequate sets of k-dimensional binary vectors such that each set comprises of linearly independent vectors. In a given $k \times n$ ($n \geq k$) binary matrix, there exist ${n}\choose{k}$ binary sub-matrices of size $k \times k$. Every possible $k \times k$ sub-matrix may be of full rank or singular depending on the columns present in the matrix. In this work, for full rank binary matrix $\mathbf{G}$ of size $k \times n$ satisfying certain condition on minimum Hamming weight, we establish a relation between the number of full rank sub-matrices of size $k \times k$ and the weight enumerating function of the error correcting code with $\mathbf{G}$ as the generator matrix. We give an algorithm to compute the number of full rank $k \times k$ submatrices.