バイナリ対称チャネル ( または BSC p ) は、 符号化理論 と 情報理論 で使用される一般的な 通信チャネルモデルです。このモデルでは、送信側が ビット (0 または 1)を送信し 、受信側がビットを受信します。ビットは「クロスオーバー 確率 」 pで「反転」され、それ以外の場合は正しく受信されます。このモデルは、電話回線や ディスク ドライブ ストレージなどのさまざまな通信チャネルに適用できます 。
ノイズのある通信路符号化定理は BSC p に適用され 、情報は任意の低いエラーで 通信路容量 までの任意の速度で送信できることを示しています 。通信路容量は ビットで、 は バイナリ エントロピー関数 です 。Forney のコードを含むコードは、情報を通信路を介して効率的に送信するために設計されています。
1 −
H
b
（ p ）
{\displaystyle 1-\operatorname {H} _{\text{b}}(p)}
H
b
{\displaystyle \operatorname {H} _{\text{b}}}
意味 バイナリ対称チャネルでは、メッセージの各ビットは、 伝送媒体上のノイズにより、確率 1- p で正しく送信され、確率 pで誤って送信されます。 交差確率 を持つバイナリ対称チャネル（ BSC p と表記 ）は、バイナリ入力とバイナリ出力を持ち、エラー確率 を持つチャネルです 。つまり、 が 送信 ランダム変数 で が受信変数である場合、チャネルは 条件付き確率 によって特徴付けられます 。
p
{\displaystyle p}
p
{\displaystyle p}
バツ
{\displaystyle X}
はい
{\displaystyle Y}
広報 [ はい = 0
|
バツ = 0 ]
= 1 − p
広報 [ はい = 0
|
バツ = 1 ]
= p
広報 [ はい = 1
|
バツ = 0 ]
= p
広報 [ はい = 1
|
バツ = 1 ]
= 1 − p
{\displaystyle {\begin{aligned}\operatorname {Pr} [Y=0|X=0]&=1-p\\\operatorname {Pr} [Y=0|X=1]&=p\\\operatorname {Pr} [Y=1|X=0]&=p\\\operatorname {Pr} [Y=1|X=1]&=1-p\end{aligned}}}
と仮定します 。 の場合 、受信機は出力を交換（0 を検出したら 1 と解釈し、その逆も同様）して、クロスオーバー確率 を持つ同等のチャネルを取得できます 。
0 ≤ p ≤ 1
/
2
{\displaystyle 0\leq p\leq 1/2}
p > 1
/
2
{\displaystyle p>1/2}
1 − p ≤ 1
/
2
{\displaystyle 1-p\leq 1/2}
容量 チャネルのノイズ量 (ビット反転の確率、 x 軸)に基づいて、ペイロードに使用できる チャネルの容量 ( y 軸) の割合を示すグラフ。 2進対称チャネルのチャネル容量はビット単位で 次 の よう になる:
Ｃ
BSSC について
= 1 −
H
b
（ p ） 、
{\displaystyle \ C_{\text{BSC}}=1-\operatorname {H} _{\text{b}}(p),}
ここで、は 2進エントロピー関数 であり 、次のように定義される:
H
b
（ p ）
{\displaystyle \operatorname {H} _{\text{b}}(p)}
H
b
（ x ） = x
ログ
2
1 x
+ （ 1 − x ）
ログ
2
1
1 − x
{\displaystyle \operatorname {H} _{\text{b}}(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}}
雑音のある通信路の符号化定理 シャノンの 雑音通信路符号化定理は、 任意の低い誤差で通信路を介して送信できる情報速度に関する結果を与えます。 の特定のケースを研究します 。
BSSC について
p
{\displaystyle {\text{BSC}}_{p}}
を特徴付ける ノイズは 、n 個の独立したランダム ビット (n は以下で定義) で構成される ランダム変数 です。ここで、各ランダム ビットは 確率 で 、 確率 で となります 。これは「 」と表記して示します 。
e
{\displaystyle e}
BSSC について
p
{\displaystyle {\text{BSC}}_{p}}
1
{\displaystyle 1}
p
{\displaystyle p}
0
{\displaystyle 0}
1 − p
{\displaystyle 1-p}
e ∈
BSSC について
p
{\displaystyle e\in {\text{BSC}}_{p}}
この定理が実際に意味するのは、メッセージが から選択され 、ランダム符号化関数 で符号化され 、ノイズの多い を介して送信された場合 、 の場合、または の場合、復号化によって元のメッセージを復元できる可能性が非常に高いということです 。事実上、チャネルのレートは定理で述べられている量によって制限されます。復号化エラーの確率は指数的に小さくなります。
{ 0 、 1
}
け
{\displaystyle \{0,1\}^{k}}
え
{\displaystyle E}
BSSC について
p
{\displaystyle {\text{BSC}}_{p}}
け
{\displaystyle k}
証拠 この定理は、確率的方法 を用いて直接証明することができます。 ランダムに選択される 符号化関数を考えてみましょう。これは、各メッセージ に対して 、値 がランダムに選択されることを意味します (等しい確率で)。与えられた符号化関数 に対して 、復号化関数は 次のように指定されます。受信したコードワード が与えられた場合、 ハミング 距離 が可能な限り小さくなるメッセージを探します (同点の場合は任意に決定します)。 ( は 最大尤度復号化 関数と呼ばれます 。)
え : { 0 、 1
}
け
→ { 0 、 1
}
ん
{\displaystyle E:\{0,1\}^{k}\to \{0,1\}^{n}}
メートル ∈ { 0 、 1
}
け
{\displaystyle m\in \{0,1\}^{k}}
え （ メートル ） ∈ { 0 、 1
}
ん
{\displaystyle E(m)\in \{0,1\}^{n}}
え
{\displaystyle E}
だ : { 0 、 1
}
ん
→ { 0 、 1
}
け
{\displaystyle D:\{0,1\}^{n}\to \{0,1\}^{k}}
ええ ∈ { 0 、 1
}
ん
{\displaystyle y\in \{0,1\}^{n}}
メートル ∈ { 0 、 1
}
け
{\displaystyle m\in \{0,1\}^{k}}
Δ （ ええ 、 え （ メートル ） ）
{\displaystyle \Delta (y,E(m))}
だ
{\displaystyle D}
証明は、確率を積分することにより、 少なくとも 1 つのそのような選択が定理の結論を満たすことを示すことによって続きます。 と は 固定されていると仮定します。まず、 が固定され 、ランダムに選択された場合、 ノイズ に対する失敗の確率は n に対して指数的に小さくなることを示します。この時点で、証明は固定されたメッセージ に対して有効です 。次に、この結果を拡張して、すべてのメッセージ に対して有効にします 。これは、復号エラー確率の証明が少なくとも半分のコードワードに対して有効であるという議論により、コードからコードワードの半分を削除することによって実現します。後者の方法は削除と呼ばれます。これにより、プロセス全体に 削除を伴うランダム符号化 という名前が付けられます。
（ え 、 だ ）
{\displaystyle (E,D)}
p
{\displaystyle p}
ϵ
{\displaystyle \epsilon }
メートル ∈ { 0 、 1
}
け
{\displaystyle m\in \{0,1\}^{k}}
え
{\displaystyle E}
BSSC について
p
{\displaystyle {\text{BSC}}_{p}}
メートル
{\displaystyle m}
メートル
{\displaystyle m}
シャノンの容量定理の逆 容量定理の逆は、基本的に、 バイナリ対称チャネルで達成できる最高のレートであると述べています。 正式には、定理は次のように述べています。
1
−
H
(
p
)
{\displaystyle 1-H(p)}
しかし、証明の背後にある直感は、レートがチャネル容量を超えて増加すると、エラーの数が急速に増加することを示しています。アイデアは、送信者が次元 のメッセージを生成し 、チャネルが 送信エラーを導入するというものです。チャネルの容量が のとき、 ブロック長 のコードに対する エラーの数は通常 です 。メッセージの最大数は です 。一方、チャネルの出力には の値が考えられます。2 つのメッセージ間で混乱が生じた場合は、 である可能性があります 。したがって になりますが、これは 、デコード エラーの確率を指数的に小さく保つために避けたいケースです。
k
{\displaystyle k}
BSC
p
{\displaystyle {\text{BSC}}_{p}}
H
(
p
)
{\displaystyle H(p)}
2
H
(
p
+
ϵ
)
n
{\displaystyle 2^{H(p+\epsilon )n}}
n
{\displaystyle n}
2
k
{\displaystyle 2^{k}}
2
n
{\displaystyle 2^{n}}
2
k
2
H
(
p
+
ϵ
)
n
≥
2
n
{\displaystyle 2^{k}2^{H(p+\epsilon )n}\geq 2^{n}}
k
≥
⌈
(
1
−
H
(
p
+
ϵ
)
n
)
⌉
{\displaystyle k\geq \lceil (1-H(p+\epsilon )n)\rceil }
コード ごく最近、いくつかの標準通信チャネルの容量を達成するために明示的なエラー訂正コードを設計するための多くの作業が行われており、現在も行われています。このようなコードを設計する動機は、コードの速度と訂正可能なエラーの割合を関連付けることです。
のチャネル容量または バイナリ消失チャネル に適合するコードの設計の背後にあるアプローチは、 より少ない数のエラーを高い確率で訂正し、可能な限り最高のレートを達成することです。シャノンの定理は、 で達成できる最高のレートを示します が、そのレートを達成する明示的なコードのアイデアは与えません。実際、そのようなコードは通常、高確率でエラーのごく一部のみを訂正し、非常に優れたレートを達成するように構築されます。最初のそのようなコードは、1966 年に George D. Forney によって作成されました。コードは、2 つの異なる種類のコードを連結した連結コードです。
BSC
{\displaystyle {\text{BSC}}}
BEC
{\displaystyle {\text{BEC}}}
BSC
p
{\displaystyle {\text{BSC}}_{p}}
フォーニーのコード フォーニーは、 雑音のある通信路符号化定理の容量を達成するために 連結コードを 構築した。彼のコードでは、
C
∗
=
C
out
∘
C
in
{\displaystyle C^{*}=C_{\text{out}}\circ C_{\text{in}}}
BSC
p
{\displaystyle {\text{BSC}}_{p}}
外部コードは、 体 、および上のブロック長 とレート のコードです。さらに、 最悪のケースのエラーを 最大で数分の 1 まで修正でき、時間内に実行できる の デコード アルゴリズム があります 。
C
out
{\displaystyle C_{\text{out}}}
N
{\displaystyle N}
1
−
ϵ
2
{\displaystyle 1-{\frac {\epsilon }{2}}}
F
2
k
{\displaystyle F_{2^{k}}}
k
=
O
(
log
N
)
{\displaystyle k=O(\log N)}
D
out
{\displaystyle D_{\text{out}}}
C
out
{\displaystyle C_{\text{out}}}
γ
{\displaystyle \gamma }
t
out
(
N
)
{\displaystyle t_{\text{out}}(N)}
内部コードは、ブロック長 、次元 、レート の コードです。さらに、 最大で を超える 復号 エラー 確率を持つ の 復号アルゴリズムがあり 、実行 時間は です。
C
in
{\displaystyle C_{\text{in}}}
n
{\displaystyle n}
k
{\displaystyle k}
1
−
H
(
p
)
−
ϵ
2
{\displaystyle 1-H(p)-{\frac {\epsilon }{2}}}
D
in
{\displaystyle D_{\text{in}}}
C
in
{\displaystyle C_{\text{in}}}
γ
2
{\displaystyle {\frac {\gamma }{2}}}
BSC
p
{\displaystyle {\text{BSC}}_{p}}
t
in
(
N
)
{\displaystyle t_{\text{in}}(N)}
外部コード の場合 、最初に思い浮かぶのはリード・ソロモン コードです。しかし、このようなコードの構築は 多項式時間 では実行できないことがわかります。このため、には 2 進線形コード が使用されます 。
C
out
{\displaystyle C_{\text{out}}}
C
out
{\displaystyle C_{\text{out}}}
内部符号については、 雑音通信路符号化定理により、
ブロック長 および次元の 線形符号 から 、レートが の容量を満たす 線形符号を 網羅的に検索することによって見つけます。
C
in
{\displaystyle C_{\text{in}}}
n
{\displaystyle n}
k
{\displaystyle k}
BSC
p
{\displaystyle {\text{BSC}}_{p}}
容量をほぼ満たす レート 。さらに、 のエンコードとデコードは に関して多項式時間で実行できることにも留意してください 。実際、エンコードには の時間がかかります 。さらに、説明したデコード アルゴリズムには ; および の時間がかかります 。
R
(
C
∗
)
=
R
(
C
in
)
×
R
(
C
out
)
=
(
1
−
ϵ
2
)
(
1
−
H
(
p
)
−
ϵ
2
)
≥
1
−
H
(
p
)
−
ϵ
{\displaystyle R(C^{*})=R(C_{\text{in}})\times R(C_{\text{out}})=(1-{\frac {\epsilon }{2}})(1-H(p)-{\frac {\epsilon }{2}})\geq 1-H(p)-\epsilon }
BSC
p
{\displaystyle {\text{BSC}}_{p}}
C
∗
{\displaystyle C^{*}}
N
{\displaystyle N}
C
∗
{\displaystyle C^{*}}
O
(
N
2
)
+
O
(
N
k
2
)
=
O
(
N
2
)
{\displaystyle O(N^{2})+O(Nk^{2})=O(N^{2})}
N
t
in
(
k
)
+
t
out
(
N
)
=
N
O
(
1
)
{\displaystyle Nt_{\text{in}}(k)+t_{\text{out}}(N)=N^{O(1)}}
t
out
(
N
)
=
N
O
(
1
)
{\displaystyle t_{\text{out}}(N)=N^{O(1)}}
t
in
(
k
)
=
2
O
(
k
)
{\displaystyle t_{\text{in}}(k)=2^{O(k)}}
デコードエラー確率 自然なデコードアルゴリズムは 次のとおりです。
C
∗
{\displaystyle C^{*}}
仮定する
y
i
′
=
D
in
(
y
i
)
,
i
∈
(
0
,
N
)
{\displaystyle y_{i}^{\prime }=D_{\text{in}}(y_{i}),\quad i\in (0,N)}
実行 する
D
out
{\displaystyle D_{\text{out}}}
y
′
=
(
y
1
′
…
y
N
′
)
{\displaystyle y^{\prime }=(y_{1}^{\prime }\ldots y_{N}^{\prime })}
の各コードブロックは、 の シンボルとみなされることに注意してください 。 の任意のインデックスでのエラーの確率は最大で であり、 のエラーは独立しているため 、 の エラー の予想数は、期待値の線形性により 最大になります。 ここで、 チャーノフ境界 を 適用すると、 を超えるエラーが発生する 確率が に制限されます 。 外部コードは 最大で の エラーを訂正できるため、これがの デコード エラー確率です 。 これを漸近的に表現すると、エラー確率 が得られます 。 したがって、 のデコードエラー確率は、 ノイズの多い通信路符号化定理に従って指数的に小さくなります。
C
in
{\displaystyle C_{\text{in}}}
C
out
{\displaystyle C_{\text{out}}}
i
{\displaystyle i}
D
in
{\displaystyle D_{\text{in}}}
γ
2
{\displaystyle {\tfrac {\gamma }{2}}}
BSC
p
{\displaystyle {\text{BSC}}_{p}}
D
in
{\displaystyle D_{\text{in}}}
γ
N
2
{\displaystyle {\tfrac {\gamma N}{2}}}
γ
N
{\displaystyle \gamma N}
e
−
γ
N
6
{\displaystyle e^{\frac {-\gamma N}{6}}}
C
out
{\displaystyle C_{\text{out}}}
γ
N
{\displaystyle \gamma N}
C
∗
{\displaystyle C^{*}}
2
−
Ω
(
γ
N
)
{\displaystyle 2^{-\Omega (\gamma N)}}
C
∗
{\displaystyle C^{*}}
を構築するための一般的な手法を示しました 。 と のより詳細な説明については 、 次の参考文献をお読みください。 最近、容量を達成するための他のいくつかのコードも構築されました。 LDPC コードは、より高速なデコード時間のためにこの目的のために検討されています。 [4]
C
∗
{\displaystyle C^{*}}
C
in
{\displaystyle C_{\text{in}}}
C
out
{\displaystyle C_{\text{out}}}
アプリケーション バイナリ対称チャネルは、メモリストレージに使用される ディスクドライブ をモデル化できます。チャネル入力はディスクに書き込まれるビットを表し、出力は後で読み取られるビットに対応します。エラーは、磁化反転、バックグラウンドノイズ、または書き込みヘッドのエラーによって発生する可能性があります。バイナリ対称チャネルがモデル化できる他のオブジェクトには、電話または無線通信回線 、または娘細胞が親細胞の DNA情報を含む 細胞分裂など があります。
このチャネルは、解析が最も簡単な ノイズ チャネルの 1 つであるため、理論家によってよく使用されます。 通信理論における多くの問題は、BSC に 還元 できます 。逆に、BSC を介して効率的に送信できれば、より複雑なチャネルのソリューションが生まれます。
参照
注記
参考文献 Cover, Thomas M.; Thomas, Joy A. (1991). 情報理論の要素 。ホーボーケン、ニュージャージー: Wiley。ISBN 978-0-471-24195-9 。 G. David Forney. 連結コード. MIT Press, Cambridge, MA, 1966年. Venkat Guruswamyの[1]誤り訂正符号：構成とアルゴリズムに関するコース、2006年秋。 MacKay, David JC (2003)。情報理論、推論、学習アルゴリズム。ケンブリッジ大学出版局 。ISBN 0-521-64298-1 。 Atri Rudra の「誤り訂正コード: 組み合わせ論、アルゴリズム、およびアプリケーション」(2007 年秋) コース、講義 9、10、29、および 30。 Madhu Sudan のアルゴリズムによるコーディング理論入門コース (2001 年秋)、講義 1 および 2。 通信の数学的理論 C. E Shannon、ACM SIGMOBILE モバイル コンピューティングおよび通信レビュー。 トム・リチャードソンとルディガー・アーバンケ著『現代符号理論』、ケンブリッジ大学出版局 
.svg/500px-Binary_symmetric_channel_(en).svg.png)
![{\displaystyle {\begin{aligned}\operatorname {Pr} [Y=0|X=0]&=1-p\\\operatorname {Pr} [Y=0|X=1]&=p\\\operatorname {Pr} [Y=1|X=0]&=p\\\operatorname {Pr} [Y=1|X=1]&=1-p\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/729fb9668be91ed00a76c0c0692425e24035648f)
![{\displaystyle \Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]\leq 2^{-{\delta }n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/82a899e77462a3f910919361829546220bb61636)
![{\displaystyle m]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5207e8f38d3e62e848453616fddca2474426b28a)
