【誤り訂正符号】QC-LDPC符号における符号設計の概要

はじめに

LDPC (Low Density Parity Check) 符号は、通信分野を中心に利用される誤り訂正符号の一種です。QC (Quasi Cyclic) -LDPC符号は、その規則性（e.g. 単位行列や対角行列を巡回シフトさせた巡回行列を非ゼロ成分とする特徴）のために、符号設計や符号化及び復号処理を簡素にできる利点から、実用的なLDPC符号として広く利用されています。

関連記事

本記事の続きとして、QC-LDPC符号の符号設計アルゴリズムを紹介したものです。

目的

本記事では、QC-LDPC符号における符号設計の概要を説明します。

対象読者

・誤り訂正符号の初学者
・実用的なLDPC符号に関心がある方

参考文献

1. 前提知識

LDPC符号における符号化、通信路モデル、復号のおさらいを行います。

1.1 符号化

符号化では、元のデータである情報語（x）を入力とし、情報語にパリティ（p）を付与したものを符号語（c）として出力します。

c = [x : p]

符号化の際に利用する行列は、生成行列（G）と呼ばれ、情報語に対する行列積の形で符号語を生成できます。

c = Gx

この生成行列は、復号に用いる検査行列（H）とセットになっており、以下の規則に従います。

HG = 0

従って、下記のように符号語に対して検査行列をかけると、ゼロベクトルになります。

Hc = 0

検査行列は、通信路を通過した後の受信語に誤りが含まれていないかを検査する目的や、誤り訂正の復号処理の指針に利用する目的に利用されます。

1.2 通信路モデル

送信側では、符号語を送信語とした送信します。送信語は通信路を経由する際に、誤り（n）が付与され、受信語（r）として受信されます。

r = c + n

誤りの種類には、ガウス分布に従うものなどがありますが、ここでは特に指定をしません。

1.3 復号

復号では、符号化に用いた生成行列とのセットである検査行列を利用し、以下を満たすように、復号アルゴリズムを用いて受信語から復号語（$\hat{x}$）を生成します。

H\hat{x}=0

復号アルゴリズムは、sum-productやmin-sumと呼ばれる確率伝搬法に基づくアルゴリズムが有名です。いずれにしても、上記の式に従う復号語を生成することが目的になりますので、検査行列をどのように設計するか（i.e. 符号設計）によって誤り訂正能力が変わります。

2. 符号設計

LDPC符号の検査行列は、Low Density Parity Checkという名前から分かるように、非ゼロ成分が疎に分布された行列です。LDPC符号における符号設計とは、検査行列内の非ゼロ成分の配置を決めることになります。尚、非ゼロ成分はGF(2)上の1と考えておけば良いです。

コラム ： GF(N)上の非ゼロ成分とLDPC符号

GFとは、ガロア体を意味します。GF(N)の非ゼロ成分は1からN-1の値であり、演算はGF(N)に従うことになります。GF(N)と一般化すると、話が難しくなるため、本記事ではGF(2)で話を進めていますが、実用的なLDPC符号は、GF(2)上のLDPC符号が使われるケースがほとんどです。理由は、GF(2)の演算はANDやXORのビット演算となるために実装が容易だからです。LDPC符号に関する話で、特段の言及がない場合は、GF(2)を前提としていると考えれば良いです。

2.1 LDPC符号における検査行列の設計手順

具体的な検査行列の設計手順は以下となります。

1. 検査行列の列方向と行方向に含まれる非ゼロ成分の数を決める
2. 非ゼロ成分の配置を決める

手順1では、例えば、Density Evolutionと呼ばれる解析手法によって、検査行列の列方向と行方向に含まれる非ゼロ成分の数を決めます。Density Evolutionのイメージとしては、検査行列の列方向と行方向に非ゼロ成分の個数がいくつであるときに、どの程度の誤り率になるかをマクロ的に見積もるものです。Density Evolutionの詳細は割愛しますが、その結果としては、例えば、各列に非ゼロ成分は3個、各行に非ゼロ成分は6個のように具体的な値が得られます。

手順2では、検査行列の列方向と行方向に含まれる非ゼロ成分の個数が決まった状態から、それらをどのように配置するかを決めます。配置を決める際には、ハミング距離が短いものをできるだけ含まないようにすることを目指します。ハミング距離が短い符号は、僅かな誤りに対しても復号処理による訂正ができず、誤り訂正の能力が低くなってしまうからです。実際に配置を決定する際には、ハミング距離の分布を決めるというよりは、誤り訂正能力への寄与が大きい、最小ハミング距離が長くなるようにします。最小ハミング距離が長くなるように検査行列の非ゼロ成分を配置するとしても、検査行列のサイズが実用的なサイズ、例えば、100行x1000列になると、場合の数が多いために探索に膨大な時間を費やすことになります。QC-LDPC符号を採用する利点の一つは、その規則性から検査行列の非ゼロ成分の配置を決める際の探索範囲を小さくできることにあります。しかしながら、最小ハミング距離を直接的に長くする符号設計は難しい状況にあるために、間接的に最小ハミング距離を長くする符号設計を行います。「間接的に」とは、検査行列の非ゼロ成分（QC-LDPC符号の場合は巡回行列）を頂点とする検査行列内のループに着目した符号設計を意味します。こちらに関しては、冒頭の関連記事に示した記事にて、具体的なアルゴリズムを紹介しています。

3. QC-LDPC符号

QC-LDPC符号における検査行列の表現方法を説明します。

3.1 非ゼロ成分を巡回行列で表現

QC-LDPC符号では、検査行列の非ゼロ成分を表現する際に、単位行列を巡回シフトさせた巡回行列（以降は、右巡回シフトを前提）を用います。例として、4x4単位行列に対する巡回シフト0,1,2,3の巡回行列を以下に示します。尚、単位行列は巡回シフト0の巡回行列になります。

• 右巡回シフト0 (=4x4単位行列)
  

• 右巡回シフト1
  

• 右巡回シフト2
  

• 右巡回シフト3
  

4x4の巡回行列としては、巡回シフト数（0,1,2,3）に応じた4パターンがあります。仮に、巡回行列という制約がなく、4x4の行列における各列と各行に1を必ず一つ配置することを考えた場合、24パターン（4の階乗）となります。つまり、NxNの巡回行列を利用することで、検査行列の非ゼロ成分を探索する範囲をNの階乗からNへと小さくできると言えます。

3.2 QC-LDPC符号の検査行列の表現

巡回シフト数や巡回行列の配置を決める際には、事前情報として以下のパラメータを指定します。値は参考値です。尚、行または列ブロックとは、巡回行列単位で見た行列の区間を意味します。

• 巡回行列サイズ：4
• 行ブロック：3
• 列ブロック：6
• 行方向の非ゼロ成分の数：4
• 列方向の非ゼロ成分の数：2

上記のパラメータを指定した場合のQC-LDPC符号の検査行列の例を示します。

巡回行列の規則性から、上記の行列は下記のように巡回シフト数で簡素に表現することができます。尚、ゼロ行列は-1と表記しています。

先に述べたように、間接的に最小ハミング距離ができるだけ長くなるように、巡回行列の配置と巡回シフト数を決定することで、誤り訂正能力が高いLDPC符号を設計することができるようになります。QC-LDPC符号では、巡回行列の利用によって検査行列内の非ゼロ成分の配置を探索する範囲を小さくできるため、符号設計が比較的容易になります。

4. まとめ

本記事では、QC-LDPC符号の概要と符号設計における利点を紹介しました。
QC-LDPC符号は、検査行列の非ゼロ成分を巡回行列で表したLDPC符号です。巡回行列の性質を利用することで、符号設計における検査行列の非ゼロ成分の配置を決める際の探索範囲を小さくできるという利点があることを紹介しました。