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


Dictionary Lists
翻訳と辞書 辞書検索 [ 開発暫定版 ]
スポンサード リンク

プロトキン限界 : ウィキペディア日本語版
プロトキン限界[ぷろときんげんかい]
プロトキン限界: Plotkin bound)とは、バイナリ符号のパラメータ(符号語の数)の限界値の1つ。
== 定義 ==
2進数の符号 C符号語の長さが n、すなわち \mathbb_2^n の部分集合であるとする。C における最小ハミング距離d とすると、次が成り立つ。
:d = \min_ d(x,y)
ここで d(x,y)xyハミング距離である。符号語の長さが n で最小ハミング距離が d のときの可能な最大符号語数を A_(n,d) とする。
定理 (プロトキン限界):
d が偶数で 2d > n の場合、
: A_(n,d) \leq 2 \left\lfloor\frac\right\rfloor
d が奇数で 2d+1 > n の場合、
: A_(n,d) \leq 2 \left\lfloor\frac\right\rfloor
d が偶数の場合、
: A_(2d,d) \leq 4d
d が奇数の場合、
: A_(2d+1,d) \leq 4d+4
となる。ここで \left\lfloor \ \right\rfloor床関数を意味する。
== 証明 ==
xyハミング距離d(x,y) とし、C に存在する符号語数を M とする(つまり、MA_(n,d) は等しい)。するとプロトキン限界は、\sum_ d(x,y) について2種類の方法で限界を求めることで得られる。
まず x として選択肢が r 個あるなら、y の選択肢は r-1 個になる。定義から全ての xy について d(x,y) \geq d であるから、次が成り立つ。
: \sum_ d(x,y) \geq M(M-1) d
また、C の符号語を並べた M \times n の行列を A とする(行が符号語に対応)。Ai番目の列にあるゼロの個数を s_i とする。つまり、i番目の行には M-s_i 個の1がある。d(x,y)=d(y,x) であるため、\sum_ d(x,y) という総和におけるある行の1や0の寄与は常に 2 である。従って、次が成り立つ。
: \sum_ d(x,y) = \sum_^n 2s_i (M-s_i)
M が偶数なら、右辺は s_i = M/2 のときに最大となり
: \sum_ d(x,y) \leq \frac n M^2
となる。以上の \sum_ d(x,y) の上限と下限を組み合わせると、次式が導かれる。
: M(M-1) d \leq \frac n M^2
2d>n の場合、この式は次のように変形できる。
: M \leq \frac
M が偶数の場合なので、次が成り立つ。
: M \leq 2 \lfloor \frac \rfloor
一方、M が奇数なら s_i = \frac のときに \sum_^n 2s_i (M-s_i) が最大化する。従って、次が成り立つ。
: \sum_ d(x,y) \leq \frac n (M^2-1)
以上の \sum_ d(x,y) の上限と下限を組み合わせると、次式が導かれる。
: M(M-1) d \leq \frac n (M^2-1)
または、2d > n なら
: M \leq \frac - 1
となる。Mは整数なので
: M \leq \lfloor \frac - 1 \rfloor = \lfloor \frac \rfloor -1 \leq 2 \lfloor \frac \rfloor
となり、限界の証明が完了する。

抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)
ウィキペディアで「プロトキン限界」の詳細全文を読む



スポンサード リンク
翻訳と辞書 : 翻訳のためのインターネットリソース

Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.