出典: フリー百科事典『ウィキペディア(Wikipedia)』
ギルバート=バルシャモフ限界(英: Gilbert-Varshamov bound)とは、符号(線型符号とは限らない)のパラメータの限界を指す。「ギルバート=シャノン=バルシャモフ限界」(GSV限界)とも。
q進数の符号
が長さ
で最小ハミング距離
であるとき、その可能な最大サイズ(符号語の総数)を
とする。なお、q進数の符号は、
個の要素の体
上の線型符号である。
すると、次が成り立つ。
![{\displaystyle {\begin{matrix}\\A_{q}(n,d)\geq {\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}\\\\\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86d9dec693f89efcada6dc0cd8d97727b5ac4985)
q が素数冪の場合、この限界を次の式が成り立つ最大の整数 k を使って
と簡略化できる。
![{\displaystyle A_{q}(n,d)\geq {\frac {q^{n}}{\sum _{j=0}^{d-2}{\binom {n-1}{j}}(q-1)^{j}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b39594aa1d02e457bfaf9931de28e4e244d359a8)
符号
の符号語の長さを
、最小ハミング距離を
、最大符号語数を
![{\displaystyle |C|=A_{q}(n,d)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2578aa6b72954a9f4fdd3252e9c10f0c7655d742)
とする。すると、全ての
について少なくとも1つの符号語
が存在し、
と
の間のハミング距離
に対して次が成り立つ。
![{\displaystyle d(x,c_{x})\leq d-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/15d6ec12b361133a9d50ce263ef655eccc3d27e9)
さもなくば、
を符号語として追加しても、その符号の最小ハミング距離
は変化しない(
が最大であるという前提に矛盾する)。
それゆえ、
全体は
を中心とする半径
の全ての球の和集合に含まれる。
![{\displaystyle \mathbb {F} _{q}^{n}=\cup _{c\in C}B(c,d-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4b5b5fa8f32a8539a6a3054bd5eca83ad11dbe7d)
ここで、各球の大きさは
![{\displaystyle {\begin{matrix}\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}\\\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cffaf12b6c703c725534993c2199f2e9b9e8f803)
となる。これは、n桁の符号語のうち最大 d-1 桁を(球の中心である符号語の対応する桁の値から)変化させ、
種類の異なる値とすることができる(符号はq進数で、
種類の値を取りうる)。したがって、次のような推論が成り立つ。
![{\displaystyle {\begin{matrix}|\mathbb {F} _{q}^{n}|&=&|\cup _{c\in C}B(c,d-1)|\\\\&\leq &\cup _{c\in C}|B(c,d-1)|\\\\&=&|C|\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}\\\\\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d584b31d1f814bc81b936e444929844fe63cc7ed)
すなわち:
![{\displaystyle {\begin{matrix}A_{q}(n,d)&\geq &{\frac {q^{n}}{\sum _{j=0}^{d-1}{\binom {n}{j}}(q-1)^{j}}}\\\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/68136f84a620536a2367a0fecbf5ef43efb49ce1)
となる(
であるため)。
関連項目[編集]