TECHNOLOGY REVIEW

高速衛星通信に適した誤り訂正符号 その２
名古屋工業大学
岡本英二
本稿は高速衛星通信に適した誤り訂正符号の構成について解説を行うものであり，近年様々なシステムにおいて用いられている LDPC 符号を中心に，その構造や特性について説明している．その１
では，AWGN と消失通信路のモデル，LDPC の符号化と復号化，高速衛星通信における誤り訂正符号の要求条件について述べた．今回のその２では消失通信路における Rateless 符号と，検査行列により符号化演算が行える LDGM 符号を紹介する．
なお章番号，図表番号，参考文献の番号は前号「その１」からの継続で番号付けを行っている．

5．Rateless 符号
Reed-Solomon 符号や Vandermonde 行列を用いた符号[13]は消失通信路にも有効に働くが，符号長に制限がありバースト消失にはあまり効果的でなく，長い符号長のガロア体上符号が適している．この消失通信路に有効な通信路符号化技術として LT 符号[9]，Raptor 符号[10]などの Rateless 符号と呼ばれる符号が提案されている．これらは消失符号（erasure code もしくは long erasure code）という名称で分類される．
Rateless 符号は原理的には符号語長を任意の長さに伸ばすことができ，受信側で全消失でなければいずれは正しく復号することができるというものである．ここでは LT 符号の構成について述べる．本符号群も任意の次元において構成できるが，以下では２値の GF(2)上で説明する．
符号化は以下のアルゴリズムで行う．

S1) 送信ビット列を K ビット毎に区切り，これを１パケットとする．
S2) 1  d  K の範囲を持ち確率密度関数が   d  で与えられる乱数 d を１つ生成する．なお
分布   d  と送受信器での乱数発生順は，予め送受信側で同期が取れているか，もしくは何らかの手段で送信側から受信側へ伝送され同じものが得られるものとする．

S3) 送信側のパケット中から一様乱数を用いて d ビットを選択し，排他的論理和を行いこれを符号化伝送ビットとして送信する．
S4) S2 から S3 を適当な回数繰り返す．
このように原理的には符号長を限りなく伸ばすことが可能である．なおこの符号化操作は疑似乱数を用いた即時的生成行列 G 作成と等価である．LT 符号の性能は主に   d  と K に依存する．
生成された拘束関係を示す２部グラフを図６に示す．

Space Japan Review, No. 68, June / July 20101

input node

output noderipple

図６ Rateless 符号に対する２部グラフの例
上部は入力ノードといい，ノード数は情報ビット数 K に等しい．下部は出力ノードといい，消失通信路を通った後の受信されたビット数に等しい．復号はこの２部グラフを用いて以下のアルゴリズムにより行われる．

S1) 受信ビット列に対応する図６のような２部グラフを描き，ある程度 output node が得られた時点（  K ）で復号を開始する．
S2) 出力ノードから枝が１本のものを１つ選ぶ．これを次数１ノード，もしくはリップルと呼ぶ．この枝に接続されている入力ノードの値は出力ノードと等しいため，ただちに復号できる（図６中２つ）．

S3) 復号された入力ノードに接続されているすべての出力ノードに対し，復号されたビットを減算する（ガロア体上では加算と同値）．

S4) 復号された入力ノードとそのノードからの枝，次数１で接続されていた出力ノードを消す．
S5) すべての入力ノードが無くなれば復号完了．そうでなければ残りの出力ノードから次数１のものを探し，有れば S2 に戻る．次数１ノードが無ければ復号は未完成で終了するか，もしくは追加の受信ビットを受信し S2 に戻る．

このように消失通信路に対する LT 符号の復号は硬値の代数演算で実行できる．なお図４と図６は原理的には同じものであり，ビリーフプロパゲーション（確率伝搬法）を Sum-product アルゴリズムにおいては軟値 LLR で，LT 復号においては硬値で実施しているものである．
Raptor 符号は LT 符号を内符号として用い，高い符号化率の LDPC 符号を外符号とした構成を持つ連接符号である．これにより高い復号性能を保ったまま LT 符号に比べ符号化復号化の計算量を抑えることが可能となる．このような Rateless 符号を用いた応用としてマルチキャスト配信[14,15]，動画配信[16]，マルチホップ協調通信[17]などへの適用が提案されている．

６．LDGM 符号
Low-density generator matrix （LDGM）符号は LDPC 符号の一種で，検査行列 H により符号化演算が行える組織 LDPC 符号である．ここではガロア体上の構成について説明する．

Space Japan Review, No. 68, June / July 2010

2

N-K

1

N-KK

1

low-density
nonzeroLDGM Staircase

low-density
nonzero
LDGM

(a)

(b)

1

low-density
1
nonzeroLDGM Triangle(c)

図７ LDGM 符号の検査行列 H の構成
図７に符号語長 N ，情報長 K の場合の  N  K  行 N 列検査行列の構造を示す[11]．組織符号では検査行列の左方が情報シンボル，右方がパリティシンボルに対応するため，図（a）に示すように，右方の部分行列を単位行列とする．左方は LDPC 符号の検査行列と同じように疎な非 0 シンボルがランダムに配置されており，通常は各行，各列とも重み 3 程度（次数 3）の正則な配置とする．なお LDGM 符号では右方の部分行列中の 1 は重みにカウントされない．これらにより（9）式の線形符号の必要十分条件を用いると  N  K  個の関係式が得られ，各行に対応する式は１つのパリティシンボルと少数の情報シンボルの和が 0 になるというものになるため，情報シンボルの加算によりパリティシンボルが得られ，結果  N  K 個のパリティシンボル列が算出できる．これを K 個の情報シンボルの後に付加することにより，符号長 Nの組織符号語が生成される．これが符号化操作の原理である．なお列重み j ，行重み k としたとき，kN   j  k  K(10)の関係が成り立つ．図７（b）（c）は LDGM 符号の拡張型であり，検査行列のパリティシンボル部に相関を追加することにより復号特性を向上させたものである．LDGM Staircase は一行目を除き対角の一行下に１を追加したもので，LDGM Triangle は LDGM Staircase の右方下三角行列にさらに疎な１をランダムに追加したものである．符号化に際しては１行中のパリティシンボル数が増えるが，図のように検査行列の右方は上三角が 0 であるため，１行目から順に計算することにより n 行目のパリティシンボル関係式に

 n  1 行目までのパリティシンボル算出結果を用いれば，１行ずつパリティシンボルを逐次計算でき，大幅な計算量の増加は生じない．
いずれの構成においても，消失通信路における復号操作は図６の２部グラフを用いた代数復号と全く同様に行うことができる．すなわち，消失位置が受信側で既知でありそれ以外の受信は正しいため，検査行列の関係式の１行中に１つだけ消失があるものを加（減）算処理により復元する．これを繰り返し，すべて復元するか，１つだけ消失の行が無くなれば終了とするものである．実は LDGM 符号は符号長，符号化率が固定となっている点が異なるのみで，基本的に Rateless 符号と同じ構造である．明示的に符号設計が固定であるため，パケット伝送との親和性が高いという利点がある．
計算機シミュレーションにより図８のような消失通信路での伝送システムにおける LDGM 符号の特性を算出した．シミュレーション条件は表２の通りである．図８のように理想的なインターリーバを仮定し，バースト消失通信路はランダム消失に変換されているものとする．

Space Japan Review, No. 68, June / July 20103

表２ 消失通信路における LDGM 符号伝送特性のシミュレーション条件

符号LDGM, LDGM Staircase,
LDGM Triangle

符号長N=400, 1000

重み(j,k)順に(7,7) (3,3) (3,3)

符号化率1/2

シンボル次数GF(24)インターリーバ

理想等価伝搬路

ランダム消失通信路消失率 pLDGM
encoderπdata symbol

LDGM
decoderπ-1data symbol

bursterasurechannel

図８ バースト消失通信路での伝送システム

1.E+00
LDGM, N=400, K=200
LDGM Staircase, N=400, K=200

1.E‐01LDGM Triangle, N=400, K=200

packet error ratio

LDGM, N=1000, K=500
LDGM Staircase, N=1000, K=500

1.E‐02LDGM Triangle, N=1000, K=500

1.E‐03

1.E‐04

1.E‐05

1.E‐06
0.1

0.2

0.3
0.4
symbol erasure probability p0.5

0.6

図９ シンボル消失確率に対するパケット誤り率特性
図９に LDGM 符号語を１パケットとして縦軸の誤り率を算出したパケット誤り率（PER）特性を示す．このように LDGM 符号長 N の伸長に伴い消失確率に対しての PER 特性が改善されていることが分かる．[8]によると LDGM 符号では(冗長度－10)%程度の消失に対応できることが経験則として分かっており，Space Japan Review, No. 68, June / July 20104

N  1000 の符号では約 40%以下の消失を回復しており，ほぼその程度の性能を得ている．また表２の符号設定では LDGM，LDGM Staircase，LDGM Triangle の順に特性がよくなることが分かる．このように
LDGM 符号は符号化，復号化の演算をすべて代数計算で行うことができ，長い符号長を構成することが可能な線形符号であるため，大容量衛星通信のような消失通信路における高速伝送に適していると考えられる．

７．まとめ
以上のように高速衛星通信に適した誤り訂正符号の構成としては，代数演算符号化，復号化を行う長い線形符号が適しており，代表的な物として消失符号が有効であることが示された．LT 符号，Raptor 符号，
LDGM 符号は原理的には同じ構造を持つ符号であり，物理層でなくても実行できるため，L2 以上のレイヤでの処理がパケット構造との親和性も高く有効であると考えられる．また複数のレイヤをまたいで構成するクロスレイヤ誤り訂正なども考えられ，より効果的な符号化技術が衛星通信のさらなる高速，高品質化に寄与すると予想される．
なおこれらの符号の性能指標としては，いかに少ない冗長シンボルで消失を取り除くことができるか，すなわち符号の伝送効率が通信路容量を達成できるかという点が重要であるが，本稿ではこの観点の説
明は省略した．詳しくはそれぞれの参考文献を参照されたい．■
著者紹介
岡本英二 名古屋工業大学大学院工学研究科・准教授
平 5 京都大・工卒．平 7 同大学院修士課程了．平 7-14 郵政省通信総合研究所（現・独立行政法人情報通信研究機構）．在籍中 ETS-VI，COMETS 衛星の実験研究，ミリ波加入者系無線アクセスシステムの研究開発に従事．平 15 より名古屋工業大．現在は無線通信システムに関する教育研究に従事．博士（情報学）．

謝辞：

本研究の一部は大幸財団の援助により行われました．深謝いたします．

参考文献[13] L. Rizzo, “Effective erasure codes for reliable computer communication protocols,” ACM SIGCOMM
Computer Communication Review, vol. 27, no. 2, pp. 24-36, Apr. 1997.
[14] 大和良平，梅原大祐，森広芳照，野口拓，川合誠，“誤りパケットを利用した Tornado 型符号の復号法，”，信学論 B, vol. J89-B, no.5, pp.763-772, May 2006.
[15] 佐々木力，小林修，田上敦士，長谷川輝之，阿野茂浩，長谷川亨，“LT 符号を用いたマルチキャス
ト配信における差分ダウンロード方式，”信学論 B，vol.J89-B, no.8, pp. 1379-1389, Aug. 2006.
[16] 外村喜秀，白井大介，北村匡彦，仲地孝之，藤井竜也，貴家仁志，“動画像配信のための下位互換性を考慮したパケットレベル LDGM 符号の構成と理論解析，”信学論 A，vol.J93-A, no. 3,
pp.212-215, Mar. 2010.
[17] J. Castura and Y. Mao, "Rateless coding and relay networks," IEEE Signal Processing Mag.,
vol. 24, no. 5, pp. 27-35, Sep. 2007.

Space Japan Review, No. 68, June / July 20105