ブロック符号

ウィキペディア

ブロック符号

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/02/14 15:20 UTC 版)

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

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

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

形式定義

ブロック符号は、アルファベット $S$ で構成される文字列を符号化するもので、符号語は $S$ 内の各文字ごとに存在する。 $(k_{1},k_{2},\ldots ,k_{m})$ を $|S|$ 未満の自然数の並びとする。 $S={s_{1},s_{2},\ldots ,s_{n}}$ とし、ある単語 $W$ のスペルが $W=s_{k_{1}}s_{k_{2}}\ldots s_{k_{m}}$ であるとき、 $W$ を符号化したもの $C(W)$ は次のようになる。

$C(W)=C(s_{k_{1}})C(s_{k_{2}})\ldots C(s_{k_{m}})$

A[n,d]

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

情報レート

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

${\frac {\!log_{2}(A)}{n}}$

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

${\frac {\!log_{2}(2^{k})}{n}}={\frac {k}{n}}$

球充填

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

外部リンク

• ブロック符号 上原健（佐賀大学）、「情報代数と符号理論」講義資料9
• ブロック符号の数学的モデル 川添充（京都大学）