概要
Berlekamp-Massey algorithm からスタートして、符号理論を全く知らないことに気づき、まわりまわって巡回符号、BCH符号について勉強してみたので備忘録的にまとめました。
内容
- 巡回符号
- BCH符号
について簡単にまとめてみる。
巡回符号
ある線形符号のn個の符号で構成される符号語として$(c_0, c_1, ..., c_{n-1})$があるとき、それをサイクリックに巡回させたものも符号語である時、この線形符号を巡回符号と呼ぶ。
一般的に巡回符号は符号語を係数とした多項式で書かれ、その多項式は排他的論理和（XOR）を加算としたガロア拡大体で定義されている。
細かい巡回符号の生成方法はウィキペディアにも詳しくまとめられているが、ここで面白いのは、情報多項式と$x^{n-m}$の積（つまりシフト演算）を計算だけすれば、その答えを生成多項式で割ることで符号化が実装できることである。すなわち、シフトレジスタを使うことで簡単に符号化ができる。対照的にハミング符号を用いる際は、符号長が大きくなるにつれて符号回路の複雑さが加速度的に増すことになる。
BCH符号
最もよく研究されている符号のうちの１つ。
細かい計算はWikipediaで事足りるので、簡単にまとめる。
自然数qの有限体を考え、$n = q^m-1$として、1のn乗根を、m次のガロア拡大体で求める($\alpha$)。
$\alpha$のi乗を解にもつ原始多項式を求め、生成関数をそれらの原始関数の最小公倍数の関数と定義する。
このとき、幾つの原始関数を選ぶところがdに対応している。つまり、3つの原始関数の最小公倍数関数を生成関数とすれば、d=3のBCH符号となる。
復号に関しては、いくつかやり方はあるが、パターソン方式などが有名である。
今日はここまで。
もうちょい勉強したいです。
終わり。