翻訳と辞書 Words near each other ・ プロトカテクアルデヒド ・ プロトカテク酸 ・ プロトカテク酸-3,4-ジオキシゲナーゼ ・ プロトカテク酸-4,5-ジオキシゲナーゼ ・ プロトカテク酸エチル ・ プロトカテク酸デカルボキシラーゼ ・ プロトカルチャー ・ プロトカルチャー (アルバム) ・ プロトカルチャー (マクロスシリーズ) ・ プロトカルチャー (曖昧さ回避) ・ プロトキン限界 ・ プロトクロロフィリドレダクターゼ ・ プロトクロロフィル ・ プロトケラス科 ・ プロトケラトプス ・ プロトケラトプスとヴェロキラプトルの格闘の化石 ・ プロトゲネイア (小惑星) ・ プロトゲネス ・ プロトコ(ー)ル(診療記録、 試験計画書) ・ プロトコニッド Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク プロトキン限界 ： ウィキペディア日本語版 プロトキン限界[ぷろときんげんかい] プロトキン限界（英: Plotkin bound）とは、バイナリ符号のパラメータ（符号語の数）の限界値の1つ。 == 定義 == 2進数の符号 $C$ の符号語の長さが $n$、すなわち $\backslash mathbb\_2^n$ の部分集合であるとする。$C$ における最小ハミング距離を $d$ とすると、次が成り立つ。 :$d\; =\; \backslash min\_\; d(x,y)$ ここで $d(x,y)$ は $x$ と $y$ のハミング距離である。符号語の長さが $n$ で最小ハミング距離が $d$ のときの可能な最大符号語数を $A\_(n,d)$ とする。 定理 （プロトキン限界）: $d$ が偶数で $2d\; >\; n$ の場合、 :$A\_(n,d)\; \backslash leq\; 2\; \backslash left\backslash lfloor\backslash frac\backslash right\backslash rfloor$ $d$ が奇数で $2d+1\; >\; n$ の場合、 :$A\_(n,d)\; \backslash leq\; 2\; \backslash left\backslash lfloor\backslash frac\backslash right\backslash rfloor$ $d$ が偶数の場合、 :$A\_(2d,d)\; \backslash leq\; 4d$ $d$ が奇数の場合、 :$A\_(2d+1,d)\; \backslash leq\; 4d+4$ となる。ここで $\backslash left\backslash lfloor\; \backslash \; \backslash right\backslash rfloor$ は床関数を意味する。 == 証明 == $x$ と $y$ のハミング距離を $d(x,y)$ とし、$C$ に存在する符号語数を $M$ とする（つまり、$M$ と $A\_(n,d)$ は等しい）。するとプロトキン限界は、$\backslash sum\_\; d(x,y)$ について2種類の方法で限界を求めることで得られる。 まず $x$ として選択肢が $r$ 個あるなら、$y$ の選択肢は $r-1$ 個になる。定義から全ての $x$ と $y$ について $d(x,y)\; \backslash geq\; d$ であるから、次が成り立つ。 :$\backslash sum\_\; d(x,y)\; \backslash geq\; M(M-1)\; d$ また、$C$ の符号語を並べた $M\; \backslash times\; n$ の行列を $A$ とする（行が符号語に対応）。$A$ の $i$番目の列にあるゼロの個数を $s\_i$ とする。つまり、$i$番目の行には $M-s\_i$ 個の1がある。$d(x,y)=d(y,x)$ であるため、$\backslash sum\_\; d(x,y)$ という総和におけるある行の1や0の寄与は常に $2$ である。従って、次が成り立つ。 :$\backslash sum\_\; d(x,y)\; =\; \backslash sum\_^n\; 2s\_i\; (M-s\_i)$ $M$ が偶数なら、右辺は $s\_i\; =\; M/2$ のときに最大となり :$\backslash sum\_\; d(x,y)\; \backslash leq\; \backslash frac\; n\; M^2$ となる。以上の $\backslash sum\_\; d(x,y)$ の上限と下限を組み合わせると、次式が導かれる。 :$M(M-1)\; d\; \backslash leq\; \backslash frac\; n\; M^2$ $2d>n$ の場合、この式は次のように変形できる。 :$M\; \backslash leq\; \backslash frac$ $M$ が偶数の場合なので、次が成り立つ。 :$M\; \backslash leq\; 2\; \backslash lfloor\; \backslash frac\; \backslash rfloor$ 一方、$M$ が奇数なら $s\_i\; =\; \backslash frac$ のときに $\backslash sum\_^n\; 2s\_i\; (M-s\_i)$ が最大化する。従って、次が成り立つ。 :$\backslash sum\_\; d(x,y)\; \backslash leq\; \backslash frac\; n\; (M^2-1)$ 以上の $\backslash sum\_\; d(x,y)$ の上限と下限を組み合わせると、次式が導かれる。 :$M(M-1)\; d\; \backslash leq\; \backslash frac\; n\; (M^2-1)$ または、$2d\; >\; n$ なら :$M\; \backslash leq\; \backslash frac\; -\; 1$ となる。Mは整数なので :$M\; \backslash leq\; \backslash lfloor\; \backslash frac\; -\; 1\; \backslash rfloor\; =\; \backslash lfloor\; \backslash frac\; \backslash rfloor\; -1\; \backslash leq\; 2\; \backslash lfloor\; \backslash frac\; \backslash rfloor$ となり、限界の証明が完了する。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「プロトキン限界」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.