タグ: モバイル編集 モバイルウェブ編集 |
|||
| (同じ利用者による、間の10版が非表示) | |||
| 71行目: | 71行目: | ||
符号語2: 1100 | 符号語2: 1100 | ||
<br> | <br> | ||
最小距離d<sub>min</sub>は、符号に含まれる任意の2つの符号語間のハミング距離の最小値のことである。<br> | |||
これにより、符号の誤り検出・訂正能力が決まる。<br> | これにより、符号の誤り検出・訂正能力が決まる。<br> | ||
<br> | <br> | ||
t個までの誤りを検出する場合: | t個までの誤りを検出する場合: | ||
<math>d_{min} \ge t + 1</math> | |||
t個までの誤りを訂正する場合 | t個までの誤りを訂正する場合 | ||
<math>d_{min} \ge 2t + 1</math> | |||
<br> | <br> | ||
エンコーダの基本構造<br> | エンコーダの基本構造<br> | ||
| 86行目: | 86行目: | ||
<br> | <br> | ||
デコーダの基本構造<br> | デコーダの基本構造<br> | ||
# | # 受信した符号語を解析する。 | ||
# | # 誤り検出を行う。 | ||
# | # 可能な場合は誤り訂正を実施する。 | ||
# | # 元の情報ビットを復元する。 | ||
<br> | <br> | ||
デコーディング方式には、以下に示すものがある。<br> | デコーディング方式には、以下に示すものがある。<br> | ||
| 101行目: | 101行目: | ||
実際の系では、上記の概念を組み合わせて、要求される性能と複雑さのバランスを取った設計が行われる。<br> | 実際の系では、上記の概念を組み合わせて、要求される性能と複雑さのバランスを取った設計が行われる。<br> | ||
<br><br> | <br><br> | ||
== 二元対称通信路 == | |||
二元対称通信路 (Binary Symmetric Channel, BSC) とは、情報理論における最も基本的な通信路モデルの1つである。<br> | |||
この通信路では、入力信号と出力信号はともに2値 (0と1) で表現される。<br> | |||
<br> | |||
この対称性が二元対称通信路の特徴である。<br> | |||
これは、入力された0が1に反転する確率と1が0に反転する確率が等しい。<br> | |||
<br> | |||
この確率をp ( <math>0 \le p \le 0.5</math> ) と表す。<br> | |||
<br> | |||
したがって、入力信号が正しく伝送される確率は、<math>1 - p</math> となる。<br> | |||
pは、通信路の反転確率あるいはビット誤り率 (BER : Bit Error Rate) と呼ばれる。<br> | |||
<br> | |||
[[ファイル:Information Theory Communication Channel Coding 2.png|フレームなし|中央]] | |||
<br> | |||
二元対称通信路の重要なものとして、通信路容量の計算が簡単に行えることが挙げられる。<br> | |||
通信路容量Cは以下の式で表される。<br> | |||
<math>C = 1 - H(p)</math><br> | |||
<br> | |||
ここで、H(p)は2値エントロピー関数で、次式で定義される。<br> | |||
<math>H(p) = -p \log_{2} p - (1 - p) \log_{2} (1 - p)</math><br> | |||
<br> | |||
[[ファイル:Information Theory Communication Channel Coding 1.png|フレームなし|中央]] | |||
<br> | |||
<math> | |||
\begin{array}{cc} | |||
\quad \begin{array}{cc} | |||
0 & \quad 1 | |||
\end{array} \\ | |||
\begin{array}{c} | |||
0 \\ | |||
1 | |||
\end{array} | |||
\begin{pmatrix} | |||
1 - p & p \\ | |||
p & 1 - p | |||
\end{pmatrix} | |||
\end{array} | |||
</math> | |||
<br> | |||
二元対称通信路の通信路容量が最大となる値pを求める場合、<math>\dfrac{d H(p)}{dp} = 0</math> となる値pを求めればよい。<br> | |||
したがって、<br> | |||
<math> | |||
\begin{align} | |||
\dfrac{d H(p)}{dp} &= 0 \\ | |||
&= - \log_{2} p - 1 - \dfrac{du}{dp} \log_{2} u + 1 \quad \therefore u = 1 - p \\ | |||
&= - \log_{2} p + \log_{2} u \\ | |||
&= - \log_{2} p + \log_{2} (1 - p) \\ | |||
&= \log_{2} \dfrac{1 - p}{p} = 0 | |||
\end{align} | |||
</math><br> | |||
<br> | |||
より、<br> | |||
<math> | |||
\begin{array}{lcl} | |||
\log_{2} \dfrac{1 - p}{p} &= 0 \\ | |||
\iff \dfrac{1 - p}{p} &= e^0 \\ | |||
\iff 1 - p &= p \\ | |||
\iff 2p &= 1 \\ | |||
\iff p &= \dfrac{1}{2} | |||
\end{array} | |||
</math><br> | |||
<br> | |||
<u>二元対称通信路において、H(p)はノイズによって引き起こされる不確実性の量を表す。</u><br> | |||
<u>つまり、pが大きくなるほど (0.5まで)、不確実性が増加して、結果として通信路容量が減少することを意味する。</u><br> | |||
<br> | |||
二元対称通信路モデルは、実際の通信システムでも頻繁に使用される。<br> | |||
例えば、デジタル通信における雑音の影響を模擬する場合や誤り訂正符号の性能評価を行う場合のベースラインモデルとして広く活用されている。<br> | |||
<br> | |||
特に、誤り訂正符号の設計において、ハミング符号やBCH符号等の線形ブロック符号は、この通信路モデルを前提として設計されている。<br> | |||
これらの符号は、通信路で発生するビット反転を検出して、場合によっては訂正することができる。<br> | |||
<br> | |||
また、シャノンの符号化定理との関連において、<br> | |||
通信路容量Cより小さい任意の伝送レートRに対して、任意に小さい誤り確率を実現できる符号化方式が存在することが証明されている。<br> | |||
<br> | |||
衛星通信や光ファイバー通信等の多くのデジタル通信システムにおいて、二元対称通信路は基本的なモデルとして使用されている。<br> | |||
ただし、実際の通信路はより複雑な特性を持つことが多く、より精密なモデル化が必要となる場合もある。<br> | |||
<br> | |||
例題: | |||
ビット誤り率 <math>p = 0.1 \quad \cdots 10[\%]</math> の二元対称通信路を考える。 | |||
入力メッセージとして、"1011"のビット列を送信する。 | |||
各ビットは、次のような確率で伝送される。 | |||
* 正しく伝送される確率 : <math>1 - p = 0.9 \quad \cdots 90[\%]</math> | |||
* 反転する確率 : <math>p = 0.1 \quad \cdots 10[\%]</math> | |||
例えば、この"1011"の4ビットのメッセージの伝送において、3番目のビットだけが反転した場合、出力は"1001"となる。 | |||
この特定のエラーパターンが発生する確率は、次式のように計算できる。 | |||
<math>0.9 \times 0.9 \times 0.1 \times 0.9 = 0.0729 \quad \cdots 7.29[\%]</math> | |||
これは | |||
1番目のビット : 正しく伝送 (確率0.9) | |||
2番目のビット : 正しく伝送 (確率0.9) | |||
3番目のビット : 反転 (確率0.1) | |||
4番目のビット : 正しく伝送 (確率0.9) | |||
<br> | |||
この通信路の通信路容量Cにおいて、<math>p = 0.1</math> の場合の2値エントロピー関数H(p)は、<br> | |||
<math> | |||
\begin{align} | |||
H(0.1) &= -0.1 \times \log_{2} (0.1) - 0.9 \times \log_{2} (0.9) \\ | |||
&\approx 0.469 \mbox{[bit]} | |||
\end{align} | |||
</math><br> | |||
<br> | |||
したがって、通信路容量は <math>C = 1 - H(0.1) \approx 1 - 0.469 \approx 0.531 \, \mbox{[bit]/[channel]}</math> 使用する。<br> | |||
これは、理想的な符号化を行うことにより、1回のチャネル使用あたり最大で約0.531[ビット]の情報を、任意に小さい誤り確率で伝送できることを意味する。<br> | |||
<br> | |||
上記の計算例は、実際の通信システムの設計において、必要な誤り訂正符号の強度を決定、あるいは、達成可能な通信速度を見積もる場合に重要となる。<br> | |||
<br><br> | |||
== 二元対称消失通信路 == | |||
==== 二元対称消失通信路とは ==== | |||
二元対称消失通信路 (Binary Erasure Channel: BEC) は、ビットが完全に消失する可能性のある通信路をモデル化する。<br> | |||
<br> | |||
二元対称消失通信路の特徴<br> | |||
* 誤りの検出が容易である。(消失位置が既知) | |||
* 理論解析が簡単である。 | |||
* 符号の性能評価に有効である。 | |||
<br> | |||
応用例<br> | |||
* パケット通信のモデル化 | |||
* インターネット通信の解析 | |||
* 消失訂正符号の設計 | |||
<br> | |||
[[ファイル:Information Theory Communication Channel Coding 3.png|フレームなし|中央]] | |||
<br> | |||
* 入力 | |||
*: 0, 1 | |||
* 出力 | |||
*: 0, 1, 消失記号 (ε) | |||
* 消失確率 | |||
*: <math>\varepsilon (0 < \varepsilon < 1)</math> | |||
* 正しく伝送される確率 | |||
*: <math>1 - p -\varepsilon</math> | |||
<br> | |||
遷移確率<br> | |||
* <math>P(Y = 0 | X = 0) = 1 - p - \varepsilon</math> | |||
* <math>P(Y = \varepsilon | X = 0) = \varepsilon</math> | |||
* <math>P(Y = 1 | X = 0) = p</math> | |||
*: <br> | |||
* <math>P(Y = 0 | X = 1) = p</math> | |||
* <math>P(Y = \varepsilon | X = 1) = \varepsilon</math> | |||
* <math>P(Y = 1 | X = 1) = 1 - p - \varepsilon</math> | |||
<br> | |||
これらの遷移確率は、二元対称消失通信路の特性を表しており、各状態からの遷移確率の合計は1になる。<br> | |||
二元対称消失通信路は対称的な性質を持っており、入力が0の場合と1の場合で対称的な遷移確率を持つ。<br> | |||
* 入力 X = 0 の場合 | |||
*: <math>(1 - p - \varepsilon) + \varepsilon + p = 1</math> | |||
* 入力 X = 1 の場合 | |||
*: <math>p + \varepsilon + (1 - p - \varepsilon) = 1</math> | |||
<br> | |||
==== 二元対称消失通信路の通信路容量 ==== | |||
二元対称消失通信路の通信路容量は、<math>C = 1 - H(\varepsilon)</math> で表される。<br> | |||
ここで、H(ε)は2値エントロピー関数であり、<math>H(\varepsilon) = -\varepsilon \log_{2}(\varepsilon) - (1 - \varepsilon) \log_{2}(1 - \varepsilon)</math> で表される。<br> | |||
<br> | |||
この式は、消失確率εが増加すると容量が減少することを示している。<br> | |||
<math>\varepsilon = 0</math> の時の通信路容量は1、<math>\varepsilon = 1</math> の時の通信路容量は0となる。<br> | |||
<br> | |||
導出過程: | |||
通信路容量は、相互情報量I(X;Y)の最大値として定義される。 | |||
<math>C = \mbox{max} I(X;Y)</math> | |||
二元対称消失通信路の場合、入力分布が一様分布 <math>(P(X = 0) = P(X = 1) = \dfrac{1}{2})</math> の時に最大になる。 | |||
相互情報量は以下のように展開できる。 | |||
<math> I(X;Y) = H(Y) - H(Y|X)</math> | |||
二元対称消失通信路では、<math>H(Y|X) = H(\varepsilon)</math> となる。 | |||
これは、各入力に対して確率εで消失することを表している。 | |||
最適な入力分布 (一様分布) の時、<math>H(Y) = 1</math> となる。 | |||
したがって、通信路容量は次式となる。 | |||
<math> C = H(Y) - H(Y|X) = 1 - H(\varepsilon)</math> | |||
<br><br> | |||
{{#seo: | |||
|title={{PAGENAME}} : Exploring Electronics and SUSE Linux | MochiuWiki | |||
|keywords=MochiuWiki,Mochiu,Wiki,Mochiu Wiki,Electric Circuit,Electric,pcb,Mathematics,AVR,TI,STMicro,AVR,ATmega,MSP430,STM,Arduino,Xilinx,FPGA,Verilog,HDL,PinePhone,Pine Phone,Raspberry,Raspberry Pi,C,C++,C#,Qt,Qml,MFC,Shell,Bash,Zsh,Fish,SUSE,SLE,Suse Enterprise,Suse Linux,openSUSE,open SUSE,Leap,Linux,uCLnux,Podman,電気回路,電子回路,基板,プリント基板 | |||
|description={{PAGENAME}} - 電子回路とSUSE Linuxに関する情報 | This page is {{PAGENAME}} in our wiki about electronic circuits and SUSE Linux | |||
|image=/resources/assets/MochiuLogo_Single_Blue.png | |||
}} | |||
__FORCETOC__ | __FORCETOC__ | ||
[[カテゴリ:情報理論]] | [[カテゴリ:情報理論]] | ||