Spectral Distribution of Random Matrices From Binary Linear Block Codes

摘要

Let ${cal C}$ be a binary linear block code of length $n$, dimension $k$ and minimum Hamming distance $d$ over $mathop{rm GF}(2)^{n}$. Let $d^{perp}$ denote the minimum Hamming distance of the dual code of ${cal C}$ over $mathop{rm GF}(2)^{n}$. Let $varepsilon:mathop{rm GF}(2)^{n}mapsto{-1,1}^{n}$ be the component-wise mapping $varepsilon (v_{i}){:=}(-1)^{v_{i}}$, for ${bf v}=(v_{1},v_{2},ldots,v_{n})inmathop{rm GF}(2)^{n}$. Finally, for $p$nrightarrowinfty$ the empirical spectral distribution of the Gram matrix of ${{1}over{sqrt{n}}}{mmb{Phi}}_{cal C}$ resembles that of a random i.i.d. Rademacher matrix (i.e., the Marchenko–Pastur distribution). Moreover, an explicit asymptotic uniform bound on the distance of the empirical spectral distribution of the Gram matrix of ${{1}over{sqrt{n}}}{mmb{Phi}}_{cal C}$ to the Marchenko–Pastur distribution as a function of $y$ and $d^{perp}$ is presented.