プロトキン限界(英: Plotkin bound)とは、バイナリ符号のパラメータ(符号語の数)の限界値の1つ。
2進数の符号
の符号語の長さが
、すなわち
の部分集合であるとする。
における最小ハミング距離を
とすると、次が成り立つ。
![{\displaystyle d=\min _{x,y\in C,x\neq y}d(x,y)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e73f891020bc785b36d30140365ccd451b750513)
ここで
は
と
のハミング距離である。符号語の長さが
で最小ハミング距離が
のときの可能な最大符号語数を
とする。
定理 (プロトキン限界):
が偶数で
の場合、
![{\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d}{2d-n}}\right\rfloor }](https://wikimedia.org/api/rest_v1/media/math/render/svg/8667aed4d70fb4c5554331a055b1ceed252c68e3)
が奇数で
の場合、
![{\displaystyle A_{2}(n,d)\leq 2\left\lfloor {\frac {d+1}{2d+1-n}}\right\rfloor }](https://wikimedia.org/api/rest_v1/media/math/render/svg/0d75bbace9e17447bf765483aad84214e88cb811)
が偶数の場合、
![{\displaystyle A_{2}(2d,d)\leq 4d}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d04796ed0a4f21a328cc16c14a6d6da51f72e5c7)
が奇数の場合、
![{\displaystyle A_{2}(2d+1,d)\leq 4d+4}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ae6593f7fbbae83b1e128b7e9e9624e7a987ed8)
となる。ここで
は床関数を意味する。
と
のハミング距離を
とし、
に存在する符号語数を
とする(つまり、
と
は等しい)。するとプロトキン限界は、
について2種類の方法で限界を求めることで得られる。
まず
として選択肢が
個あるなら、
の選択肢は
個になる。定義から全ての
と
について
であるから、次が成り立つ。
![{\displaystyle \sum _{x,y\in C}d(x,y)\geq M(M-1)d}](https://wikimedia.org/api/rest_v1/media/math/render/svg/07cea4be3c3368c12ebab6512209b5fa3b4a2a0a)
また、
の符号語を並べた
の行列を
とする(行が符号語に対応)。
の
番目の列にあるゼロの個数を
とする。つまり、
番目の行には
個の1がある。
であるため、
という総和におけるある行の1や0の寄与は常に
である。従って、次が成り立つ。
![{\displaystyle \sum _{x,y\in C}d(x,y)=\sum _{i=1}^{n}2s_{i}(M-s_{i})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fd8185bafa4b639b532cdd9f006d620ae426c1d)
が偶数なら、右辺は
のときに最大となり
![{\displaystyle \sum _{x,y\in C}d(x,y)\leq {\frac {1}{2}}nM^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/45f856fb7b7add35788bc2427c1b8c58bf55c67c)
となる。以上の
の上限と下限を組み合わせると、次式が導かれる。
![{\displaystyle M(M-1)d\leq {\frac {1}{2}}nM^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/51149bf39b54b55836578a384cb5c057fd22bbcc)
の場合、この式は次のように変形できる。
![{\displaystyle M\leq {\frac {2d}{2d-n}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/34f78413945e7c26eaed39045142fd306d0fca8e)
が偶数の場合なので、次が成り立つ。
![{\displaystyle M\leq 2\lfloor {\frac {d}{2d-n}}\rfloor }](https://wikimedia.org/api/rest_v1/media/math/render/svg/bbddedddbaa286873a0e716cb3a8c2a8ee3507ea)
一方、
が奇数なら
のときに
が最大化する。従って、次が成り立つ。
![{\displaystyle \sum _{x,y\in C}d(x,y)\leq {\frac {1}{2}}n(M^{2}-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5f781db20064fcb257651ff2ebe6ff04b3628c82)
以上の
の上限と下限を組み合わせると、次式が導かれる。
![{\displaystyle M(M-1)d\leq {\frac {1}{2}}n(M^{2}-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f4a27cb617c7de0c6d411974ee9dcc35581722ee)
または、
なら
![{\displaystyle M\leq {\frac {2d}{2d-n}}-1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/93f8289523bd6a0f4665599c68a093992c3faf35)
となる。Mは整数なので
![{\displaystyle M\leq \lfloor {\frac {2d}{2d-n}}-1\rfloor =\lfloor {\frac {2d}{2d-n}}\rfloor -1\leq 2\lfloor {\frac {d}{2d-n}}\rfloor }](https://wikimedia.org/api/rest_v1/media/math/render/svg/14417fb7d3869aa90d057c37542fab9789f05e7a)
となり、限界の証明が完了する。
- Binary codes with specified minimum distance, M. Plotkin, IRE Transactions on Information Theory, 6:445-450, 1960.