Wikipedia の LDPC の項だけ読むとそんな難しくなさそうに見えるけど、実際に実装しようと思うと、むちゃくちゃ難しい。
H行列 (パリティ検査行列) が難しい
LDPC符号の設計では、性能に優れたパリティ検査行列(H行列)を用意するのがまず難しい。ここにいろんな要素がある。
- 正則(regular)か(各ノードの次数が一定)
- 構造的な性質(たとえば巡回構造をもつ QC-LDPC など)を持つか (復号効率に影響する)
- 系統的符号化 が可能な構造(systematic) を持つか(これは生成行列側の問題)
- girth(ループの最小長): Tannerグラフにおいて短いサイクルは復号性能を劣化させるため、girthが大きい方が望ましい。
数学的素養がないと難しすぎる。そして自力で設計するのは考えたくない。
Protographが難しい
そんなH行列、例え1つ設計できたとしても、任意のデータ長・符号化率を持つH行列をいくつも作ろうと思うと何倍も大変になってしまう。
そこで Protograph (原始グラフ) という性質の良い原型となるような小さなグラフをまず設計し、それを何らかの方法で拡大して任意の大きさのH行列を得るという設計方法がある。
パンクチャリングが難しい
パンクチャリングは性質の良いH行列を使うために,多少の計算効率を犠牲にしつつ柔軟な送信ビット長/符号化率を得るための方法といえる
良い性質の Protograph を得られたとしても、それを拡大するプロセスには制約がある。整数倍の行列しか作れないとか。
そうなると求めるデータ長・符号化率ぴったりの行列というのは結局作れない。
これを解決するのがパンクチャリング。符号化率の低い(0.4など)のProtographを拡大し、欲しい符号化率 (0.5など)になるまでパリティビットの一部を送信しないことで、ちょうどいいサイズを作れる。
ぴったりよりも大きい行列を使うので計算コストは増えるが、高性能なH行列設計を流用できるという利点がある。
エンコードもデコードも難しい
エンコードは既知の操作するだけやろ? という気持ちを打ち砕く。どっちも難しい。なんならデコードのほうが簡単かもしれない
- エンコードは生成行列(G行列)を得る必要がある。任意のH行列に対してG行列を導出するのが難しい。
- デコードには、確率伝播(Belief Propagation)アルゴリズムに基づく Sum-Product 法や、近似的な Min-Sum 法などがある。どちらもTannerグラフ上での繰り返し計算を必要とし、実装や収束性で難しい