ブロック符号のソースを表示

'''ブロック符号'''（ブロックふごう、{{lang-en-short|Block code}}）は、[[符号理論]]における伝送路符号の種類である。メッセージに[[冗長性 (情報理論)|冗長性]]を加えることで、受信側でなるべく誤りのない復号を可能にしつつ、[[通信路容量]]を越えない情報レート（1秒間当たりの転送[[情報]]の量を[[ビット]]で表したもの）を提供する。

ブロック符号の特徴は、固定長の符号である点にあり、[[ハフマン符号]]のような情報源符号や[[畳み込み符号]]のような伝送路符号とは異なる。一般に、''k''桁の情報語を入力とし、''n''桁の符号語を生成する。

ブロック符号は、初期の[[携帯電話]]で伝送路符号として使われた。

== 形式定義 ==
ブロック符号は、[[アルファベット (計算機科学)|アルファベット]] <math>S</math> で構成される文字列を符号化するもので、符号語は <math>S</math> 内の各文字ごとに存在する。<math>(k_1,k_2,\ldots,k_m)</math> を <math>|S|</math> 未満の[[自然数]]の並びとする。<math>S={s_1,s_2,\ldots,s_n}</math> とし、ある単語 <math>W</math> のスペルが <math>W=s_{k_1}s_{k_2}\ldots s_{k_m}</math> であるとき、<math>W</math> を符号化したもの <math>C(W)</math> は次のようになる。

:<math>C(W) = C(s_{k_1})C(s_{k_2})\ldots C(s_{k_m})</math>

== A[n,d] ==
効率（転送レート）と訂正能力のトレードオフを示すものとして、符号語の長さと訂正能力（[[ハミング距離]] d で表される）を固定したときの最大符号語数が使われる。符号語長 n とハミング距離 d の場合の最大符号語数を ''A[n,d]'' と記述する。

== 情報レート ==
2進ブロック符号 <math>C</math> の符号語数を <math>A</math>、符号語長を ''n'' としたとき、<math>C</math> の情報レートは次のように定義される。

:<math>\frac{\!log_{2}(A)}{n}</math>

符号語のうち ''k'' ビットが独立情報ビットの場合、情報レートは次のようになる。

:<math>\frac{\!log_{2}(2^k)}{n}=\frac{k}{n}</math>

== 球充填 ==
ブロック符号は[[球充填]]と密接に関連している。2次元なら視覚化しやすい。同じ硬貨を複数枚テーブルに置き、平らになるようにする。すると、蜂の巣状の六角形のパターンが現れる。ただし、ブロック符号の次元はもっと高く、簡単には視覚化できない。符号理論では、''N''次元球モデルを使う。例えば、宇宙空間での通信に使われた[[ゴレイ符号]]は24次元の球充填に基づいている。2進数の符号の場合、この次元は上述の符号語長と同じである。

== 外部リンク ==
* [http://www.ma.is.saga-u.ac.jp/uehara/algcod06/codlec09.pdf ブロック符号]{{リンク切れ|date=2018年2月14日 (水) 15:20 (UTC)}} 上原健（佐賀大学）、「情報代数と符号理論」講義資料9
* [http://www.las.osakafu-u.ac.jp/~kawazoe/code/node32.html ブロック符号の数学的モデル] 川添充（京都大学）

{{DEFAULTSORT:ふろつくふこう}}

[[Category:符号理論]]
[[Category:数学に関する記事]]
[[Category:誤り検出訂正]]