Varshamov bound for linear codes

For a prime-power alphabet size $q$, a linear $[n,k,\ge d]$ code exists if $V_q(n-1,d-2)<q^{n-k}$. Choose parity-check columns successively, avoiding combinations of at most $d-2$ earlier columns. Fewer than $q^{n-k}$ vectors are forbidden, so such a choice is possible. No set of at most $d-1$ columns is dependent, and the resulting kernel has dimension at least $k$.

// Target: probability-and-statistics.bigb