ギルバート＝バルシャモフ限界
q進数の符号 C {\displaystyle \ C} が長さ n {\displaystyle n} で最小ハミング距離 d {\displaystyle d} であるとき、その可能な最大サイズ(符号語の総数)を A q ( n , d ) {\displaystyle \ A_{q}(n,d)} とする。なお、q進数の符号は、 q {\displaystyle q} 個の要素の体 F q n {\displaystyle \mathbb {F} _{q}^{n}} 上の線型符号である。
すると、次が成り立つ。
A q ( n , d ) ≥ q n ∑ j = 0 d − 1 ( n j ) ( q − 1 ) j {\displaystyle {\begin{matrix}\\A_{q}(n,d)\geq {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}\\\\\end{matrix}}}
q が素数冪の場合、この限界を次の式が成り立つ最大の整数 k を使って A q ( n , d ) ≥ q k {\displaystyle A_{q}(n,d)\geq q^{k}} と簡略化できる。
A q ( n , d ) ≥ q n ∑ j = 0 d − 2 ( n − 1 j ) ( q − 1 ) j {\displaystyle A_{q}(n,d)\geq {\frac {q^{n}}{\sum _{j=0}^{d-2}{\binom {n-1}{j}}(q-1)^{j}}}}