人工衛星から地球へ大きな観測画像ファイルを送る場面を想像してみましょう。電波は雲や大気の擾乱、アンテナの一時的な遮蔽によって、ところどころでパケットがまるごと「消えて」しまいます。受信側は「いま何番目のパケットが欠けたか」は分かりますが、地上から「もう一度送って」と頼もうにも、衛星との往復遅延が大きく、そもそも片方向のブロードキャストでは返信路が存在しないこともあります。送り直しが効かないこの状況で、どうすれば確実にファイルを届けられるのでしょうか。
素朴な発想は「最初から多めに冗長を付けて送る」ことです。しかし冗長の量を固定すると、消失が少ない日には無駄になり、消失が多い日には足りなくなります。理想は、送信側が符号化シンボルを「水道の蛇口」のように無限に流し続け、受信側はどれでもよいから十分な個数のシンボルをバケツに集めた瞬間に元データを復元できるという仕組みです。これを実現するのが本記事の主役、ファウンテン符号(fountain code)です。噴水(fountain)から飛び散る水滴のうちどれを受け取るかは問わず、コップ一杯ぶん集めれば渇きが癒える、というイメージからこの名が付きました。
ファウンテン符号を理解すると、次のような分野への応用が見えてきます。
- 衛星・深宇宙ブロードキャスト: 片方向で大容量データを多数の受信機へ配信するとき、受信機ごとに消失パターンが違っても各自が独立に復元できます。CCSDSの一部規格やDVB-H/IPDCのデータ配信でファウンテン符号が利用されています
- モバイル動画配信(3GPP MBMS): 携帯ネットワークの一斉配信(eMBMS)では、Raptor符号(RaptorQ)がアプリケーション層の前方誤り訂正(AL-FEC)として標準採用されています
- 大規模ファイル配信・分散ストレージ: P2P配信やオブジェクトストレージで、サーバが返答を待たずにシンボルを撒き続け、クライアントは届いた分だけで復元する設計に向いています
本記事では、まず「消失チャネル」とは何かを整理し、なぜレートレスな符号が必要かという動機を明確にします。その上でLuby Transform符号(LT符号)の度数分布(Ideal Soliton / Robust Soliton)が、少ない冗長で高確率の復号を実現する理由を式で導きます。さらに、LT符号の弱点を前処理符号(precode)で補うRaptor符号の構造を説明し、最後にPythonでLT符号化とBP(peeling)復号を実装して、受信シンボル数に対する復号成功率の曲線を可視化して読み取ります。
本記事の内容
- 消失チャネルとレートレス符号の動機 — なぜフィードバックなしで信頼通信できるのか
- LT符号の符号化・復号の仕組みと、BP(peeling)復号の動作原理
- Ideal Soliton分布とRobust Soliton分布の導出 — 度数分布がなぜこの形なのか
- Raptor符号の構造 — 前処理符号による線形時間復号とオーバーヘッド低減
- PythonによるLT符号化・peeling復号の実装と、復号成功率曲線の測定・考察
前提知識
この記事を読む前に、以下の記事を読んでおくと理解が深まります。
- 誤り訂正符号とは — 基礎と分類 — 前方誤り訂正(FEC)、符号化率、冗長の考え方
- LDPC符号の理論 — スパースグラフ符号の原理と復号アルゴリズム — スパースなグラフ符号とメッセージパッシング復号
- タナーグラフと反復復号 — 二部グラフ上での復号の見方(ファウンテン符号でも同じ枠組みを使います)
- AWGN通信路モデル — チャネルモデルの基礎(本記事ではAWGNではなく消失チャネルを扱います)
消失チャネルとレートレス符号 — なぜ必要か
パケット消失という現実
通信路の誤りには大きく2種類あります。一つはビットが0と1の間で反転する「ビット誤り」、もう一つはシンボルやパケットがまるごと失われる「消失」(erasure)です。インターネットのパケット通信や衛星のパケット配信では、後者が支配的です。なぜなら、各パケットには通常CRC(巡回冗長検査)が付いていて、ビット誤りが起きたパケットは受信側で検出され、破棄されるからです。つまり受信機の視点では「正しく届いたパケット」か「まったく届かなかったパケット」かのどちらかで、中間の「壊れたパケット」は存在しないとみなせます。
このように、各シンボルが確率 $p$ で消失し、残りは完全に正しく届くチャネルを二元消失通信路(BEC: Binary Erasure Channel)、より一般にシンボル単位ならパケット消失チャネルと呼びます。消失の特徴は「どこが消えたか」が受信側に分かることです。ビット反転の場合は「どこが間違っているか」が分からないのに対し、消失では誤りの位置が既知なので、訂正は格段に楽になります。実際、$k$ 個の情報シンボルから $n$ 個の符号化シンボルを作るMDS符号(例: リード・ソロモン符号)を使えば、$n$ 個のうちどれでも $k$ 個が届けば原理的に復元できます。
固定レート符号の限界とフィードバックの問題
ところが、ここに二つの厄介な問題があります。
第一に、消失率 $p$ を事前に正確に知ることが難しい点です。固定レート $R = k/n$ の符号を設計するには、最悪の消失率を見積もって $n$ を決めねばなりません。消失が想定より軽ければ冗長が無駄になり、想定より重ければ復号できずに全滅します。チャネルが時間変動する衛星リンクでは、この見積もりが常に外れます。
第二に、再送(ARQ)に頼れない場面がある点です。TCPのような双方向通信なら「届かなかったパケットを送り直して」と要求できますが、深宇宙通信のように往復遅延が数十分に及ぶ場合や、一つの送信機から多数の受信機へ同じデータを撒くブロードキャストでは、再送要求は非現実的です。多数の受信機がそれぞれ異なるパケットを取りこぼすと、再送要求が殺到し(フィードバック爆発)、ネットワークが破綻します。
ここで理想的な符号の性質を整理しましょう。$k$ 個の情報シンボルから、いくらでも多くの符号化シンボルをオンザフライで生成でき、受信側は順番や種類を問わず、わずかに $k$ より多い個数 $k(1+\varepsilon)$ のシンボルを集めるだけで 高い確率で元の $k$ シンボルを復元できる——このような符号があれば、消失率を知る必要も、再送する必要もありません。送信機はただシンボルを流し続け、各受信機は十分集まった時点で「もう要らない」と蛇口を閉じればよいのです。
このように符号化率をあらかじめ固定しない符号をレートレス符号(rateless code)、あるいは噴水のイメージからファウンテン符号(fountain code)と呼びます。ここで、無限に近い符号化シンボルを生成しながら $k(1+\varepsilon)$ 個程度で復元できるという「うますぎる話」が、いったいどんな仕掛けで成立するのかが核心です。次節では、その最初の実用的な構成であるLT符号を見ていきましょう。
LT符号とは — XORで作る噴水
直感: ランダムに選んだ情報の「混ぜ合わせ」
LT符号(Luby Transform code)は、2002年にマイケル・ルビー(Michael Luby)が提案した、最初の実用的なファウンテン符号です。その符号化は驚くほど単純で、「情報シンボルをランダムにいくつか選んで、XOR(排他的論理和)で混ぜ合わせる」 だけです。
具体的な場面で考えましょう。手元に $k$ 個の情報シンボル $s_1, s_2, \dots, s_k$ があるとします(各シンボルは1ビットでもよいし、数百バイトのパケットでもよく、XORはビット単位で行います)。1個の符号化シンボル(出力シンボル、あるいは滴を意味するdropletとも呼ばれます)を作るには、次の二段階を踏みます。
- ある確率分布 $\rho(d)$ に従って度数 $d$(その符号化シンボルが何個の情報シンボルを混ぜるか)を選ぶ
- $k$ 個の情報シンボルから一様ランダムに $d$ 個を選び、それらをすべてXORしたものを符号化シンボルとする
たとえば度数 $d=3$ で情報シンボル $s_2, s_5, s_9$ が選ばれたなら、その符号化シンボルは $t = s_2 \oplus s_5 \oplus s_9$ です。送信機はこの操作を繰り返し、必要なだけ符号化シンボルを生成し続けられます。各符号化シンボルには「どの情報シンボルを混ぜたか」という情報(隣接関係)が、乱数シードなどの形で受信側と共有されます。実際には送受信が同じ擬似乱数生成器を使い、シンボルのインデックスからシードを決めることで、隣接関係を別途送らずに済ませます。
XORで混ぜるだけなのに、なぜこれで復号できるのでしょうか。鍵はXORの可逆性にあります。$t = s_2 \oplus s_5 \oplus s_9$ という式で、もし $s_5$ と $s_9$ がすでに分かっていれば、$s_2 = t \oplus s_5 \oplus s_9$ として $s_2$ を取り出せます。つまり「度数1の式(中身が1個だけのシンボル)」から始めて、判明したシンボルを他の式から引き算(XOR)していけば、芋づる式に未知シンボルが解けていきます。この芋づる式の復号こそがファウンテン符号の心臓部です。
LT符号もタナーグラフで表せる
この符号化と復号の関係は、タナーグラフと反復復号で扱った二部グラフとまったく同じ枠組みで描けます。上段に $k$ 個の情報シンボル(変数ノード)、下段に受信した符号化シンボル(検査ノードに相当)を並べ、符号化シンボルが混ぜた情報シンボルとの間にエッジを引きます。すると、ある符号化シンボルの度数とは、そのノードから出るエッジの本数に他なりません。
LDPC符号との違いは二つあります。第一に、LDPCはパリティ検査行列が固定でしたが、LT符号ではグラフが受信のたびにランダムに(かつ送信側で動的に)生成されます。第二に、消失チャネルでは「届いたシンボルは完全に正しい」ため、復号はビット反転の確率的な伝搬ではなく、確定的なXOR代入の連鎖になります。これが次に述べるBP(peeling)復号です。
XORで混ぜて芋づる式に解く、というアイデアの骨格が見えたところで、この復号アルゴリズムを正確に定式化しましょう。
BP(peeling)復号の仕組み
度数1から始まる連鎖
消失チャネル上のLT符号の復号は、peeling(剥がし取り)復号、あるいはBP(Belief Propagation)復号と呼ばれます。確率的なメッセージは登場せず、次の単純な規則を繰り返すだけです。受信した符号化シンボルの集合を考え、各符号化シンボルが「まだ判明していない情報シンボル」を何個含むか(現在の実効度数)を管理します。
復号アルゴリズムは次の手順で進みます。
- リプル(ripple)の探索: 実効度数が1の符号化シンボルを探す。そのようなシンボル $t$ は、ただ一つの未知情報シンボル $s_j$ だけを含むので、ただちに $s_j = t$ と確定できる。確定待ちの度数1シンボルの集合を「リプル」と呼ぶ
- 代入(剥がし取り): いま確定した $s_j$ を、$s_j$ を含む他のすべての符号化シンボルからXORで除去する。すなわち、$s_j$ に接続する各符号化シンボル $t’$ を $t’ \leftarrow t’ \oplus s_j$ で更新し、グラフからエッジ $(s_j, t’)$ を削除する。これにより $t’$ の実効度数が1減る
- 繰り返し: 度数が1に減った符号化シンボルが新たに生まれたら、それも確定できる。手順1〜2を、すべての情報シンボルが確定するか、度数1のシンボルが尽きるまで繰り返す
度数1のシンボルが一つも無くなった時点でまだ未知シンボルが残っていれば、その回の復号は失敗です。逆に $k$ 個すべてが確定すれば成功です。
この過程を一言でいえば「度数1の式を解いては、その結果を他の式に代入して新たな度数1の式を作り出す」連鎖です。連鎖が最後まで途切れずに続くかどうかが、復号の成否を決めます。そして、連鎖が途切れないようにするには、復号の各段階で「ちょうど度数1になったシンボル」が枯渇しないよう、符号化シンボルの度数分布 $\rho(d)$ をうまく設計しなければなりません。これがファウンテン符号設計の核心であり、次節で導くSoliton分布の出番です。
復号が失敗する二つの様子
度数分布の設計動機を理解するため、復号が失敗する典型を二つ押さえておきましょう。
一つ目は、最初から度数1のシンボルが一つも無い場合です。度数2以上のシンボルしか手元になければ、どの式も未知数を2個以上含み、芋づるの最初の一手が打てません。復号は1ステップも進まずに止まります。したがって度数分布は、ある程度の確率で度数1を生成しなければなりません。
二つ目は、途中でリプルが空になる場合です。序盤は順調でも、剥がし取りの結果として新たに度数1になるシンボルが供給されなくなると、まだ未知シンボルが残っているのに連鎖が止まります。これを防ぐには、復号の進行に合わせて「ちょうど良いペース」で度数1のシンボルが補充され続ける必要があります。多すぎても(冗長を浪費し)少なすぎても(連鎖が切れる)いけない、この微妙なバランスを実現する分布を次に導きます。
Ideal Soliton分布の導出
リプルを枯らさないという要請
度数分布 $\rho(d)$($d=1,\dots,k$ に対する確率)を設計する目標を、より定量的に述べましょう。peeling復号のある時点で、まだ未確定の情報シンボルが $k$ 個から徐々に減っていきます。理想は、復号の各ステップでちょうど1個の符号化シンボルが新たに度数1になることです。リプルのサイズが常に1前後に保たれれば、無駄な冗長(度数1が同時に何個もある状態)も、連鎖の途切れ(リプルが0になる状態)も避けられます。
この「各ステップでちょうど1個ずつ供給される」という理想を満たすように逆算して得られるのが、Ideal Soliton分布(理想ソリトン分布)です。ソリトン(soliton)とは、形を崩さずに伝わる孤立波のことで、リプルのサイズが崩れずに一定に保たれる様子になぞらえた命名です。
導出
復号過程をモデル化します。情報シンボルが全部で $k$ 個あり、復号がある程度進んで、残りの未確定シンボルが $L$ 個になった瞬間を考えます。このとき、ある符号化シンボルが「ちょうど未確定シンボルを1個だけ含む(=いま度数1になっている)」確率を見積もり、それが各ステップでちょうど1個に相当するよう $\rho(d)$ を定めます。
まず度数1のシンボルの扱いです。最初から度数1で生成されたシンボルは、初期リプルとして1個ぶんの「種」を供給すればよいので、$k$ 個から1個を初期供給するために
$$ \rho(1) = \frac{1}{k} $$
と置きます。これが連鎖の口火を切る確率です。
次に度数 $d \geq 2$ のシンボルを考えます。度数 $d$ のシンボルは、$k$ 個の情報シンボルから $d$ 個をランダムに選んでいます。復号が進んで未確定シンボルが残り $L$ 個になったとき、このシンボルの $d$ 個のうち $d-1$ 個がすでに確定済み、残り1個が未確定、という状態になれば、剥がし取りによって実効度数が1になり、リプルへ供給されます。各ステップ($L$ が1ずつ減る)でちょうど1個のシンボルが度数1になってほしい、という条件を課して逆算すると、度数 $d$ の確率は次の形になります。
$$ \rho(d) = \frac{1}{d(d-1)}, \quad d = 2, 3, \dots, k $$
この式が妥当であることは、規格化(全確率が1になること)を確かめれば納得できます。$d \geq 2$ の和を計算します。ここで $\dfrac{1}{d(d-1)}$ を部分分数に分解すると $\dfrac{1}{d-1} – \dfrac{1}{d}$ となることを使います。
$$ \sum_{d=2}^{k} \frac{1}{d(d-1)} = \sum_{d=2}^{k}\left(\frac{1}{d-1} – \frac{1}{d}\right) $$
右辺は隣り合う項が次々に打ち消し合う望遠鏡和(telescoping sum)になっており、最初の項 $\frac{1}{1}$ と最後の項 $\frac{1}{k}$ だけが残ります。すなわち
$$ \sum_{d=2}^{k} \frac{1}{d(d-1)} = 1 – \frac{1}{k} $$
です。これに度数1の確率 $\rho(1) = \frac{1}{k}$ を足すと
$$ \sum_{d=1}^{k} \rho(d) = \frac{1}{k} + \left(1 – \frac{1}{k}\right) = 1 $$
となり、確かに確率分布として規格化されています。
Ideal Solitonの直感と弱点
得られたIdeal Soliton分布 $\rho(1)=1/k$, $\rho(d)=1/\{d(d-1)\}\ (d\geq 2)$ を眺めると、度数2の確率が $\rho(2)=1/2$ と最も大きく、度数が増えるにつれて急速に小さくなる一方で、裾は $1/k$ までゆっくり伸びています。この「度数2が主役で、たまに大きな度数も混ぜる」構造が、リプルを一定に保つ秘訣です。度数2のシンボルは、1個が確定するたびに別の1個を度数1へ押し出す「バトンタッチ」の役割を果たし、ときおり現れる大度数のシンボルが、グラフ全体をくまなくカバーして取り残しを防ぎます。
期待度数(平均的に1シンボルが混ぜる情報シンボル数)は
$$ \bar{d} = \sum_{d=1}^{k} d\,\rho(d) = \frac{1}{k}\cdot 1 + \sum_{d=2}^{k} d\cdot\frac{1}{d(d-1)} = \frac{1}{k} + \sum_{d=2}^{k}\frac{1}{d-1} \approx \ln k $$
と、おおむね $\ln k$ のオーダーになります。符号化・復号の計算量が $1$ シンボルあたり平均度数に比例することから、LT符号全体の計算量は $O(k\ln k)$ 程度になることがここから分かります。
しかし、Ideal Soliton分布には致命的な弱点があります。それは期待値としては理想的でも、分散(ばらつき)に対して極めて脆いことです。実際の復号では、リプルのサイズは確率的に揺らぎます。Ideal Solitonでは期待リプルサイズがちょうど1なので、ほんの少し下振れしただけでリプルが0になり、連鎖が途切れてしまいます。期待値が1ぴったりということは、「平均すると綱渡りの綱の上にいる」ようなもので、わずかな風(ランダムな揺らぎ)で落ちてしまうのです。この脆さを克服するために、リプルにわざと「のりしろ」を持たせたのが、次のRobust Soliton分布です。
Robust Soliton分布の導出
のりしろを足すという発想
Ideal Solitonの問題は、リプルの期待サイズが1しかなく、揺らぎに対する余裕がないことでした。そこで、リプルの期待サイズを1ではなく、ある程度大きな値 $\approx R$ に保つように分布を修正します。リプルに余裕(のりしろ)を持たせれば、多少下振れしてもリプルが空にならず、復号が途切れにくくなります。さらに、復号の終盤で「ごく少数の取り残し」が生じるのを防ぐため、わざと大きな度数のスパイクを一つ加えて、グラフ全体を確実に覆います。この二つの修正を施したのがRobust Soliton分布です。
まず、リプルサイズの目標値に関わるパラメータ $R$ を導入します。理論的な見積もりから、適切な値は
$$ R = c \cdot \ln\!\left(\frac{k}{\delta}\right)\sqrt{k} $$
と置かれます。ここで $\delta$ は許容する復号失敗確率の上限、$c$ は $0$ より大きい調整用の定数(実用上 $0.1$ 前後がよく使われます)です。$R$ はおおよそ「復号が成功するために維持すべきリプルの目標サイズ」を表し、$\sqrt{k}$ に比例して増えます。
追加成分 $\tau(d)$ の定義
Robust Solitonでは、Ideal Soliton $\rho(d)$ に、次の追加成分 $\tau(d)$ を足します。
$$ \tau(d) = \begin{cases} \dfrac{R}{d\,k} & d = 1, 2, \dots, \dfrac{k}{R} – 1 \\[2mm] \dfrac{R}{k}\ln\!\left(\dfrac{R}{\delta}\right) & d = \dfrac{k}{R} \\[2mm] 0 & d = \dfrac{k}{R} + 1, \dots, k \end{cases} $$
この $\tau(d)$ の各部分の役割を説明します。$d = 1$ から $k/R – 1$ までの $\tau(d) = R/(dk)$ の部分は、小さい度数の確率を底上げして、リプルの期待サイズを $1$ から $R$ 程度へ引き上げる「のりしろ」を担います。これがロバスト性の源です。$d = k/R$ における大きなスパイク $\tau(k/R) = (R/k)\ln(R/\delta)$ は、復号終盤に少数の情報シンボルが取り残されるのを防ぐための「大掃除」用の項で、グラフ全体を確実にカバーします。
規格化と最終形
Ideal Soliton $\rho(d)$ と追加成分 $\tau(d)$ を足したものを、まだ規格化されていない分布として扱います。その総和を $\beta$ と置きます。
$$ \beta = \sum_{d=1}^{k}\bigl(\rho(d) + \tau(d)\bigr) $$
$\rho(d)$ の和は1ですから、$\beta = 1 + \sum_d \tau(d)$ であり、$\tau$ を足したぶんだけ $\beta$ は1より少し大きくなります。これを1に戻すために全体を $\beta$ で割って、Robust Soliton分布 $\mu(d)$ を得ます。
$$ \mu(d) = \frac{\rho(d) + \tau(d)}{\beta}, \quad d = 1, 2, \dots, k $$
これがRobust Soliton分布です。$\sum_d \mu(d) = 1$ は、分子の総和が $\beta$、分母が $\beta$ なので自動的に満たされます。
オーバーヘッドの意味
Robust Soliton分布を用いると、ルビーは次の重要な定理を示しました。$k$ 個の情報シンボルを復号失敗確率 $\delta$ 以下で復元するには、
$$ N = k\beta = k + O\!\left(\sqrt{k}\,\ln^2\!\left(\frac{k}{\delta}\right)\right) $$
個の符号化シンボルを集めれば十分です。ここで重要なのは、必要シンボル数 $N$ が $k$ に対してわずか $\sqrt{k}$ のオーダーの追加で済む、すなわち相対的なオーバーヘッド $\varepsilon = N/k – 1$ が $k\to\infty$ で0に近づくという点です。言い換えると、情報シンボル数より数パーセント多く集めるだけで、高い確率で復元できる——冒頭で述べた「うますぎる話」が、Robust Soliton分布という具体的な度数設計によって実現されているわけです。
平均度数も $\bar{d} = O(\ln(k/\delta))$ 程度に保たれるため、符号化・復号の総計算量は $O(k\ln(k/\delta))$ です。これは $k$ に対してほぼ線形(対数係数つき)で、長いファイルにも実用的に使えます。
ここまでで、LT符号がなぜ少ない冗長で復号できるのかが、度数分布の設計から理解できました。しかし、LT符号にはまだ改善の余地があります。それは「平均度数が $\ln k$ で増えるため、$k$ が大きいと1シンボルあたりの計算量が無視できない」ことと、「ごく一部の情報シンボルが最後まで取り残される確率が残る」ことです。これらを抜本的に解決するのが、次に述べるRaptor符号です。
Raptor符号 — 前処理符号による線形時間化
LT符号の限界をどう超えるか
LT符号でオーバーヘッドを小さく保つには、平均度数 $\bar{d} \approx \ln k$ が必要でした。これは「すべての情報シンボルを最後の1個まで取りこぼさずに覆う」ためのコストです。グラフ理論でいうと、ランダムなグラフですべてのノードを少なくとも1本のエッジで覆うには、クーポンコレクター問題と同様に $\ln k$ 倍の対数係数が避けられません。この対数係数こそが、LT符号の計算量を厳密な線形 $O(k)$ にできない原因です。
ここで発想を転換します。「LT符号だけで全シンボルを完璧に覆う」のをやめて、LT符号には大半(たとえば99%)のシンボルだけ復元させ、取りこぼした少数のシンボルは別の前処理符号で埋め合わせる、という二段構えにすればどうでしょうか。LT段に「全カバー」を要求しなければ、平均度数を定数オーダーまで下げられ、計算量が真に線形になります。この二段構えがRaptor符号(Rapid Tornado code)の核心アイデアです。2006年にアミン・ショクロラヒ(Amin Shokrollahi)によって提案されました。
Raptorの構造: 前処理符号 + 弱いLT符号
Raptor符号は二層構造を持ちます。
第1層(前処理符号 / precode): まず $k$ 個の情報シンボルに、高レートの固定レート消失訂正符号(典型的にはLDPC符号や、LDPCとHDPCの組み合わせ)を適用し、$k’ = k/R_p$ 個の中間シンボル(intermediate symbols)を生成します。ここで $R_p$ は1に近い前処理レート(たとえば $0.98$)で、わずかな冗長を加えるだけです。この前処理符号は、後段で「もし数パーセントの中間シンボルが復元できなくても、残りから埋め合わせられる」役割を担います。
第2層(LT符号): 次に、中間シンボル $k’$ 個に対して、平均度数が定数の弱いLT符号(weakened LT code)を適用し、必要なだけ符号化シンボルを生成して送信します。LT段の度数分布は、もはや全カバーを目指さないので、平均度数を $O(1)$($k$ に依存しない定数)に抑えられます。
復号は送信と逆順に行います。受信した符号化シンボルから、まずLT符号のpeeling復号で中間シンボルの大半を復元します。LT段は全カバーを保証しないので、ここで少数の中間シンボルが取り残されます。しかし前処理符号の冗長があるおかげで、取り残された中間シンボルを前処理符号の復号(これも消失訂正)で埋め合わせ、最終的にすべての中間シンボルを復元します。中間シンボルが揃えば、その先頭 $k$ 個(または前処理符号の逆変換)から元の情報シンボルが得られます。
なぜ線形時間でオーバーヘッドも小さいのか
この二段構えの効果を直感的に整理します。LT段の平均度数を定数 $D = O(1)$ にできるので、符号化・復号の計算量はシンボル数に比例して $O(k)$、すなわち真の線形時間になります。一方、LT段が取りこぼす数パーセントは、前処理符号がきわめて低いオーバーヘッドで救済します。前処理符号自体が線形時間で復号できるLDPC系であれば、全体としても線形時間が保たれます。
結果として、Raptor符号は次の理想的な性質を同時に達成します。第一に、符号化・復号がともに $O(k)$ の線形時間です。第二に、相対オーバーヘッド $\varepsilon$ を、$k$ によらず小さな定数(実用的なRaptorQでは数パーセント、理論的には任意に小さく)に保てます。第三に、LT符号の弱点だった「終盤の取り残し」が前処理符号で構造的に解消されるため、復号失敗確率が急峻に下がります。
実用面では、3GPPのMBMS(マルチメディア同報)やDVB-Hで標準化されたRaptor符号(RFC 5053)と、その改良版RaptorQ(RFC 6330)が広く使われています。RaptorQは、ガロア体 $\mathrm{GF}(256)$ 上の演算を一部に用いることで、わずか2シンボルのオーバーヘッドでほぼ確実に復号できる、極めて高性能なファウンテン符号です。
理論の全体像が見えたので、ここからは最もシンプルなLT符号を実際にPythonで実装し、Robust Soliton分布のもとで「受信シンボル数を増やすと復号成功率がどう立ち上がるか」を自分の目で確かめましょう。
PythonによるLT符号とpeeling復号の実装
度数分布の実装
まず、Ideal Soliton分布とRobust Soliton分布を生成する関数を実装します。これらは符号化のたびに度数 $d$ をサンプリングするための確率質量関数です。
import numpy as np
import matplotlib.pyplot as plt
def ideal_soliton(k):
"""Ideal Soliton分布 rho(d) を返す (d=1..k)"""
rho = np.zeros(k + 1) # インデックス0は未使用
rho[1] = 1.0 / k
for d in range(2, k + 1):
rho[d] = 1.0 / (d * (d - 1))
return rho[1:] # d=1..k を返す
def robust_soliton(k, c=0.1, delta=0.5):
"""Robust Soliton分布 mu(d) を返す (d=1..k)"""
rho = ideal_soliton(k) # d=1..k
R = c * np.log(k / delta) * np.sqrt(k) # リプル目標サイズの目安
tau = np.zeros(k) # d=1..k に対応 (インデックスは d-1)
kR = int(round(k / R))
for d in range(1, k + 1):
if d < kR:
tau[d - 1] = R / (d * k)
elif d == kR:
tau[d - 1] = R / k * np.log(R / delta)
# d > kR は 0 のまま
unnormalized = rho + tau
beta = unnormalized.sum()
return unnormalized / beta # 規格化した mu(d)
# 度数分布を比較
k = 100
mu = robust_soliton(k, c=0.1, delta=0.5)
rho = ideal_soliton(k)
plt.figure(figsize=(8, 5))
plt.plot(range(1, k + 1), rho, 'o-', ms=3, label='Ideal Soliton $\\rho(d)$')
plt.plot(range(1, k + 1), mu, 's-', ms=3, label='Robust Soliton $\\mu(d)$')
plt.xlabel('degree $d$')
plt.ylabel('probability')
plt.title(f'Degree distributions (k={k})')
plt.xlim(0, 30)
plt.legend()
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.show()
このグラフから、二つの分布の違いがはっきり読み取れます。Ideal Soliton(丸)は度数2で $1/2$ という鋭いピークを持ち、その後 $1/\{d(d-1)\}$ に従って急降下します。一方Robust Soliton(四角)は、小さい度数(特に度数1や2の付近)の確率が底上げされており、これがリプルにのりしろを与える成分です。さらにグラフをよく見ると、$d = k/R$ 付近に小さなスパイクが現れ、これが終盤の取り残しを防ぐ「大掃除」成分に対応します。期待値ではなく揺らぎへの耐性を、確率分布の形そのもので買っていることが視覚的に分かります。
LT符号化の実装
次に、Robust Soliton分布に従ってLT符号化を行う関数を実装します。各符号化シンボルは「混ぜた情報シンボルのインデックス集合」と「XOR結果(ここではビット列をnumpy配列で表現)」のペアとして保持します。
def lt_encode(symbols, num_encoded, degree_dist, rng):
"""LT符号化: symbols (k個の情報シンボル) から num_encoded 個の符号化シンボルを生成
symbols: shape (k, sym_len) のndarray (各行が1シンボル, 0/1のビット列)
degree_dist: 度数分布 mu(d), d=1..k に対応する確率配列
戻り値: [(隣接インデックスのset, XOR結果ndarray), ...]
"""
k = len(symbols)
degrees = np.arange(1, k + 1)
encoded = []
for _ in range(num_encoded):
# 度数 d を分布からサンプリング
d = rng.choice(degrees, p=degree_dist)
# k個からd個を一様ランダムに選ぶ (重複なし)
idx = rng.choice(k, size=d, replace=False)
# 選んだ情報シンボルをXOR
xor = np.zeros(symbols.shape[1], dtype=np.uint8)
for j in idx:
xor ^= symbols[j]
encoded.append((set(idx.tolist()), xor))
return encoded
ここでは符号化シンボルごとに、度数 $d$ を分布からサンプルし、$k$ 個から $d$ 個の情報シンボルを選んでXORしています。隣接インデックスを set で保持しているのは、後の復号で「確定したシンボルを式から取り除く」操作(集合からの要素削除)を効率よく行うためです。実際のシステムでは隣接関係を乱数シードで送受信間に共有しますが、ここでは復号の本質に集中するため、隣接集合を直接受け渡しています。
peeling復号の実装
復号は、度数1の符号化シンボルを起点に、確定したシンボルを他の式から剥がし取る連鎖です。
def lt_decode(encoded, k):
"""peeling(BP)復号: 符号化シンボル集合から k 個の情報シンボルを復元
encoded: [(隣接インデックスset, XOR結果ndarray), ...]
戻り値: (復元シンボルの配列 or None, 成功フラグ)
"""
# 各符号化シンボルを [隣接set, 値] のリストに変換 (破壊的に編集する)
eqs = [[set(adj), val.copy()] for adj, val in encoded]
decoded = [None] * k # 確定した情報シンボル
num_decoded = 0
while True:
# 実効度数1の式 (リプル) を探す
ripple = [e for e in eqs if len(e[0]) == 1]
if not ripple:
break # リプルが空: これ以上進めない
for eq in ripple:
if len(eq[0]) != 1:
continue # 直前の剥がしで度数が変わった場合スキップ
j = next(iter(eq[0])) # 唯一の未知シンボル
if decoded[j] is None:
decoded[j] = eq[1].copy() # s_j を確定
num_decoded += 1
# s_j を含む他の全ての式から剥がし取る
for other in eqs:
if j in other[0]:
other[1] ^= decoded[j] # XORで除去
other[0].discard(j) # エッジを削除
if num_decoded == k:
return np.array(decoded), True
success = (num_decoded == k)
result = np.array([d if d is not None else np.zeros_like(encoded[0][1])
for d in decoded]) if success else None
return result, success
この復号器は、まず実効度数1の式(リプル)を集め、それぞれについて唯一の未知シンボルを確定し、確定値を他のすべての式からXORで除去します。除去によって度数が1に減った式は次のループのリプルに加わり、連鎖が続きます。リプルが空になった時点で num_decoded が $k$ に届いていなければ失敗、届いていれば成功です。XORの可逆性により、各代入は確定的で、誤りが伝搬することはありません。
復号成功率曲線の測定
いよいよ本題です。受信した符号化シンボル数 $N$ を、情報シンボル数 $k$ に対するオーバーヘッド比 $N/k$ として変化させ、各 $N$ で多数の試行を行って復号成功率を測定します。
def success_rate(k, overhead, num_trials, degree_dist, sym_len=8, seed=0):
"""与えたオーバーヘッドでの復号成功率を測定"""
rng = np.random.default_rng(seed)
N = int(round(k * overhead)) # 受信する符号化シンボル数
successes = 0
for _ in range(num_trials):
# ランダムな情報シンボル (k個, 各sym_lenビット)
symbols = rng.integers(0, 2, size=(k, sym_len), dtype=np.uint8)
encoded = lt_encode(symbols, N, degree_dist, rng)
decoded, ok = lt_decode(encoded, k)
# 完全一致を確認
if ok and np.array_equal(decoded, symbols):
successes += 1
return successes / num_trials
# パラメータ
k = 100
mu = robust_soliton(k, c=0.1, delta=0.5)
overheads = np.arange(1.0, 2.05, 0.1) # N/k = 1.0 .. 2.0
rates = [success_rate(k, ov, num_trials=200, degree_dist=mu, seed=i)
for i, ov in enumerate(overheads)]
plt.figure(figsize=(8, 5))
plt.plot(overheads, rates, 'o-', color='crimson')
plt.axhline(0.5, color='gray', ls=':', alpha=0.7)
plt.xlabel('overhead $N/k$ (received symbols / info symbols)')
plt.ylabel('decoding success rate')
plt.title(f'LT code (Robust Soliton) decoding success vs overhead (k={k})')
plt.grid(True, alpha=0.3)
plt.ylim(-0.02, 1.02)
plt.tight_layout()
plt.show()
この成功率曲線から、ファウンテン符号の本質的な振る舞いが読み取れます。第一に、オーバーヘッド $N/k$ がちょうど1付近(受信数が情報数と同じ)では成功率はほぼ0です。これは当然で、$k$ 個ぴったりの式では、ランダムなXORの連鎖がすべてのシンボルを覆い切る可能性がほとんどないからです。第二に、$N/k$ がおよそ $1.2$ から $1.6$ にかけて、成功率が0から1へと急峻に立ち上がる(しきい値的な遷移) ことが見て取れます。わずか数十パーセントのオーバーヘッドを与えるだけで、復号がほぼ確実に成功する領域に入ります。これがファウンテン符号の威力です。第三に、$k=100$ という小さな値ではしきい値がやや高め(オーバーヘッドが大きめ)に出ますが、理論によれば $k$ を大きくするほど遷移は急峻になり、必要なオーバーヘッドは小さくなっていきます。
度数分布による違いを見る
最後に、Ideal Soliton分布とRobust Soliton分布で成功率曲線を比較し、ロバスト化の効果を確認します。
k = 100
mu_robust = robust_soliton(k, c=0.1, delta=0.5)
rho_ideal = ideal_soliton(k)
rho_ideal = rho_ideal / rho_ideal.sum() # 念のため規格化
overheads = np.arange(1.0, 2.55, 0.1)
rates_robust = [success_rate(k, ov, 200, mu_robust, seed=i)
for i, ov in enumerate(overheads)]
rates_ideal = [success_rate(k, ov, 200, rho_ideal, seed=100 + i)
for i, ov in enumerate(overheads)]
plt.figure(figsize=(8, 5))
plt.plot(overheads, rates_robust, 'o-', color='crimson',
label='Robust Soliton')
plt.plot(overheads, rates_ideal, 's--', color='steelblue',
label='Ideal Soliton')
plt.xlabel('overhead $N/k$')
plt.ylabel('decoding success rate')
plt.title(f'Ideal vs Robust Soliton (k={k})')
plt.legend()
plt.grid(True, alpha=0.3)
plt.ylim(-0.02, 1.02)
plt.tight_layout()
plt.show()
この比較グラフから、Robust Soliton分布の優位性が読み取れます。同じオーバーヘッドで比べると、Robust Soliton(赤丸)のほうがIdeal Soliton(青四角)よりも低いオーバーヘッドで高い成功率に達します。Ideal Solitonはリプルの期待サイズが1しかないため、ランダムな揺らぎでリプルが頻繁に枯渇し、成功率の立ち上がりが鈍く、また高オーバーヘッドでも1に届きにくい傾向があります。一方Robust Solitonは、のりしろ成分と大掃除のスパイクによって連鎖の途切れと取り残しを抑え、より少ない冗長で確実に復号します。理論で「Ideal Solitonは脆く、Robust Solitonがそれを補強する」と述べたことが、シミュレーションで具体的に裏付けられたわけです。
なお、ここで実装したLT符号は平均度数が $\ln k$ 程度に増えるため、$k$ が非常に大きいと1シンボルあたりの計算が重くなります。前述したRaptor符号は、この計算量を定数度数の弱いLT符号と前処理符号の二段構えで線形時間に抑える発展形であり、実システムではそちらが使われます。
まとめ
本記事では、消失チャネル上でフィードバックなしに信頼通信を実現するファウンテン符号(LT符号・Raptor符号)について解説しました。
- レートレス符号の動機: 消失率が未知で再送も使えないブロードキャストや深宇宙通信では、符号化率を固定しないファウンテン符号が威力を発揮します。送信機はシンボルを撒き続け、受信機は $k(1+\varepsilon)$ 個集めた時点で復元できます
- LT符号とpeeling復号: 情報シンボルをランダムにXORして符号化し、復号は度数1の式から確定値を他の式に剥がし取る連鎖です。XORの可逆性により誤り伝搬がなく、確定的に解けます
- Soliton分布: Ideal Soliton $\rho(d)=1/\{d(d-1)\}$ はリプルを各ステップ1個ずつ供給する理想形ですが、揺らぎに脆い。Robust Soliton はのりしろ成分 $\tau(d)$ を加えてリプルに余裕を持たせ、必要シンボル数を $k + O(\sqrt{k}\ln^2(k/\delta))$ に抑えます
- Raptor符号: 前処理符号(LDPC系)で中間シンボルを作り、定数度数の弱いLT符号を重ねる二段構えにより、線形時間 $O(k)$ の符号化・復号と、$k$ によらない小さなオーバーヘッドを同時に達成します
- 実装と検証: PythonでLT符号化・peeling復号を実装し、受信シンボル数に対する復号成功率がしきい値的に立ち上がること、Robust SolitonがIdeal Solitonより少ない冗長で確実に復号することを確認しました
ファウンテン符号は、シャノンの符号化定理が示す「消失チャネル容量 $1-p$ に漸近的に到達できる符号」を、再送なしの片方向通信という厳しい条件下で実現した、応用上きわめて重要な符号です。グラフ上のメッセージパッシングという視点は、LDPC符号やターボ符号と共通しており、現代の誤り訂正符号を貫く一本の太い糸になっています。
次のステップとして、以下の記事も参考にしてください。
- LDPC符号の理論 — スパースグラフ符号の原理と復号アルゴリズム — Raptorの前処理符号としても使われるスパースグラフ符号
- タナーグラフと反復復号 — 本記事のpeeling復号と共通する二部グラフ上の復号
- 誤り訂正符号とは — 基礎と分類 — FEC全体の中でのファウンテン符号の位置づけ