リード・ソロモン符号 — バースト誤りに強い符号の代数

この回で学ぶこと

前回までに扱ってきた畳み込み符号(とそのビタビ復号)は、ビットごとにほぼ独立に発生する誤り、つまり「ランダム誤り」に対して威力を発揮する符号でした。しかし現実の深宇宙リンクでは、誤りはいつも行儀よくランダムに散らばってくれるわけではありません。フェーディングによる一時的な信号レベルの落ち込み、PLLのサイクルスリップ、地上局のアンテナが一瞬別方向を向いてしまうような瞬間的な障害、あるいはビタビ復号器自体が一度誤った経路を選ぶと連鎖的に誤りを重ねてしまう性質(バーストエラーを生成しやすいという畳み込み符号自身の弱点)など、**誤りが時間的に連続して固まって発生する「バースト誤り」**は、深宇宙通信でも地上通信でも避けて通れない現象です。

畳み込み符号は、この手のバースト誤りに対しては相性が良くありません。ビタビ復号器は「誤りがある程度散らばっている」ことを暗黙に仮定しているため、誤りが1箇所に集中すると、その周辺で復号経路をまるごと見失い、局所的に誤りが増幅されてしまうことがあります。

この回で扱うリード・ソロモン符号(Reed-Solomon code、RS符号)は、まさにこのバースト誤りに強い符号として設計されたものです。鍵になるのは、ビットではなくシンボルという単位で符号化・復号を行うという発想の転換です。この回では、シンボルという概念を支える**有限体(ガロア体)$GF(2^m)$**の基礎から出発し、RS符号の代数的な構成、そしてなぜそれがバースト誤りに強いのかを数式で追っていきます。

直感的な導入: ビットからシンボルへ

まず素朴な疑問から始めましょう。畳み込み符号もRS符号も「誤り訂正符号」という同じ土俵にいるのに、なぜ片方はランダム誤りに強く、もう片方はバースト誤りに強いのでしょうか。

畳み込み符号は、送信データの1ビットずつに着目し、過去数ビットの文脈(拘束長)を使って各ビットの誤りを推定します。誤りがビット単位でポツポツと独立に発生するなら、この仕組みはうまく機能します。しかし、ひとたび連続した多数のビットが一気に破壊されると、拘束長の範囲全体が汚染されてしまい、ビタビ復号器の「文脈」そのものが信頼できなくなります。

一方、RS符号は情報をシンボルという、複数ビットをひとまとめにした単位で扱います。たとえば8ビットをひとまとめにして1シンボル(0〜255の値を取る)とすれば、たとえ生のビット列の中で7〜8ビット連続して誤りが発生したとしても、それは(運が良ければ)たった1つか2つのシンボルの誤りとして吸収されてしまいます。RS符号は「シンボル単位で見て何個のシンボルが誤ったか」しか気にしないため、1つのバーストが広い範囲のビットを巻き込んでいても、シンボル数で数えれば被害は小さく見える、というのがバースト誤りに強い理由の直感です。これを数式にするには、まず「シンボル」を数学的にきちんと定義する必要があります。それが有限体の役割です。

有限体(ガロア体)$GF(2^m)$の基礎

なぜ「ビットの集合」では不十分なのか

$m$ビットの並びは $2^m$ 通りありますが、単なる「$2^m$種類のラベル」のままでは、それらの間で意味のある足し算・掛け算ができません。RS符号を代数的に(多項式として)構成するには、シンボルの集合が四則演算(逆元も含む)について閉じている必要があります。この条件を満たす、有限個の元からなる数の体系が**有限体(finite field, ガロア体 Galois field)**です。

$m$ビットのシンボルに対応する有限体は $GF(2^m)$ と書かれ、$2^m$ 個の元を持ちます。整数の $\mathrm{mod}\ p$ 演算(素数 $p$)で作れる体 $GF(p)$ はよく知られていますが、$GF(2^m)$ はそれとは少し違う作り方をします。

原始多項式による構成

$GF(2^m)$ の元は、$GF(2) = \{0,1\}$(つまり通常の1ビット、排他的論理和が加算)を係数とする、次数 $m-1$ 以下の多項式として表現します。

$$a(x) = a_{m-1}x^{m-1} + \cdots + a_1 x + a_0, \qquad a_i \in \{0,1\}$$

これは $m$ ビットのベクトル $(a_{m-1}, \dots, a_1, a_0)$ とそのまま対応します。加算はビットごとのXOR(=係数ごとの $\mathrm{mod}\ 2$ 加算)で自然に定義できます。問題は乗算です。2つの多項式を単純に掛けると次数が $m-1$ を超えてしまうため、次数 $m$ の既約多項式(これ以上因数分解できない多項式)$p(x)$ を1つ選び、乗算結果を常に $p(x)$ で割った余りに置き換えます。

$$a(x) \cdot b(x) \pmod{p(x)}$$

この $p(x)$ を**原始多項式(primitive polynomial)**として適切に選ぶと、非零元全体 $GF(2^m)\setminus\{0\}$(全部で $2^m-1$ 個)が、ある1つの元 $\alpha$(原始元、primitive element)のべき乗だけで漏れなく生成される、という美しい性質が成り立ちます。

$$GF(2^m)\setminus\{0\} = \{\alpha^0, \alpha^1, \alpha^2, \dots, \alpha^{2^m-2}\}, \qquad \alpha^{2^m-1} = \alpha^0 = 1$$

つまり非零元は、位数 $2^m-1$ の巡回群をなします。この「べき乗表現」があるおかげで、乗算は指数どうしの足し算に帰着でき($\alpha^i \cdot \alpha^j = \alpha^{(i+j) \bmod (2^m-1)}$)、実装上も理論上も非常に扱いやすくなります。

具体例: $GF(2^3)$

抽象的な話だけでは掴みにくいので、最小の非自明な例として $m=3$、つまり $GF(8)$ を見てみましょう。原始多項式として $p(x) = x^3+x+1$ を選びます。$\alpha$ を $p(\alpha)=0$、すなわち $\alpha^3 = \alpha+1$ を満たす元とすると、べき乗表は次のようになります。

$$\begin{aligned} \alpha^0 &= 1 \\ \alpha^1 &= \alpha \\ \alpha^2 &= \alpha^2 \\ \alpha^3 &= \alpha+1 \\ \alpha^4 &= \alpha^2+\alpha \\ \alpha^5 &= \alpha^2+\alpha+1 \\ \alpha^6 &= \alpha^2+1 \\ \alpha^7 &= 1 \ (= \alpha^0 \text{ に戻る}) \end{aligned}$$

ちょうど $\alpha^0$ から $\alpha^6$ までの7個($=2^3-1$)が、$GF(8)$ のすべての非零元を尽くしていることが確認できます。実務で使われる $GF(2^8)$($m=8$、256元)も原理はまったく同じで、単に表が $255$ 行になるだけです。1シンボル $=1$ バイト(8ビット)という対応が自然に取れるため、$GF(2^8)$ は計算機との相性が良く、RS符号で圧倒的によく使われる体です。

リード・ソロモン符号の代数的構成

情報多項式とその評価によるエンコード

有限体 $GF(2^m)$ が手に入ったので、いよいよRS符号を構成します。基本アイデアは驚くほどシンプルです。**「$k$個の点を通る次数 $k-1$以下の多項式は、その$k$個の点によって一意に決まる」**という、多項式の基本性質を利用します。

$k$個の情報シンボル $m_0, m_1, \dots, m_{k-1} \in GF(2^m)$ を、次数 $k-1$以下の多項式の係数とみなします。

$$M(x) = m_0 + m_1 x + m_2 x^2 + \cdots + m_{k-1}x^{k-1}$$

符号語は、この多項式を体の非零元すべての点で評価した値の並びとして定義します。

$$c = \big(M(\alpha^0),\, M(\alpha^1),\, M(\alpha^2),\, \dots,\, M(\alpha^{n-1})\big), \qquad n = 2^m - 1$$

情報はたった $k$個の係数しか持っていないのに、それを $n \; (>k)$個の評価点でオーバーサンプリングして送っていることになります。この「余分な情報」の中に誤り訂正能力が宿っています。もし通信路でいくつかのシンボルが化けても、残った十分な数の評価点さえ正しければ、多項式 $M(x)$ を(ラグランジュ補間などで)一意に復元できる、というのが直感的な仕組みです。

実際のCCSDS標準などの実装では、この「評価による構成」と数学的に等価な、生成多項式を使う構成がよく用いられます。

$$g(x) = \prod_{i=1}^{n-k} (x - \alpha^{i}) = (x-\alpha)(x-\alpha^2)\cdots(x-\alpha^{n-k})$$

を固定し、情報多項式 $m(x)$(次数 $k-1$以下)に対して符号語多項式を

$$c(x) = x^{n-k}\, m(x) \; - \; \big[x^{n-k}\, m(x) \bmod g(x)\big]$$

と定義します。こうすると $c(x)$ は $g(x)$ で割り切れる(すなわち $\alpha, \alpha^2, \dots, \alpha^{n-k}$ をすべて根に持つ)次数 $n-1$以下の多項式となり、しかも情報シンボル $m_0,\dots,m_{k-1}$ がそのまま符号語の上位係数として現れる**組織符号(systematic code)**になります。これはシフトレジスタ(LFSR)で効率よく実装できるため、実際のハードウェアエンコーダはほぼ例外なくこの生成多項式方式を使います。以下の議論では、符号の性質(最小距離など)を見通しよく導ける「評価による構成」を主に使います。

$(n,k)$パラメータ

このようにして得られる符号を RS$(n,k)$符号 と呼びます。

$$n = 2^m - 1 \quad (\text{符号長、シンボル数}), \qquad k \quad (\text{情報シンボル数}), \qquad n-k \quad (\text{検査シンボル数})$$

符号化率は $R = k/n$ です。$n$ が $2^m-1$ という体のサイズで頭打ちになる点に注意してください。これは、評価点として使える非零元が体の中に $2^m-1$個しかないためです(必要ならば $0$ も評価点に加えて $n=2^m$ まで拡張したり、複数の体を組み合わせて $n$ を延長する技法もありますが、基本形はこの制約を持ちます)。

最小距離とMDS符号の性質

RS符号の最も重要な性質が、この最小距離 $d_{\min}$ です。結論から言うと、

$$d_{\min} = n-k+1$$

が成り立ちます。これを導いてみましょう。2つの異なる情報多項式 $M_1(x) \ne M_2(x)$(どちらも次数 $k-1$以下)を考えます。その差 $D(x) = M_1(x)-M_2(x)$ もまた次数 $k-1$以下の、恒等的にゼロではない多項式です。体上の多項式の基本定理より、次数 $k-1$以下の非零多項式の根は高々$k-1$個しかありません。つまり $D(x)$ が $0$ になる評価点 $\alpha^i$ は、$n$個の評価点のうち高々$k-1$個です。

言い換えると、$M_1$ と $M_2$ の符号語が一致できるシンボル位置は高々$k-1$個であり、残りの少なくとも $n-(k-1) = n-k+1$個の位置では、2つの符号語は必ず異なるシンボルを持ちます。したがって、任意の異なる2符号語間のハミング距離は

$$d_{\min} \ge n-k+1$$

を満たします。一方、任意の線形符号に対して一般に成り立つシングルトン限界(Singleton bound)

$$d_{\min} \le n-k+1$$

と合わせると、RS符号はこの上限をぴったり達成していること、すなわち

$$d_{\min} = n-k+1$$

が結論できます。この上限を達成する符号は**MDS符号(Maximum Distance Separable code、最大距離分離符号)**と呼ばれ、RS符号は数ある符号の中でも「与えられた $(n,k)$ に対して理論上可能な最良の最小距離を持つ」という、代数的に非常に特別な地位を占めています。

誤り訂正能力とバースト誤りへの強さ

一般に、最小距離 $d_{\min}$ の符号は

$$t = \left\lfloor \frac{d_{\min}-1}{2} \right\rfloor$$

個までのシンボル誤りを確実に訂正できます(有界距離復号、bounded-distance decoding)。RS符号では $d_{\min}=n-k+1$ なので、

$$t = \left\lfloor \frac{n-k}{2} \right\rfloor$$

シンボルの誤りが訂正能力の上限です。検査シンボルを $n-k=2t$個用意し、そのちょうど半分の $t$個までのシンボル誤りを直せる、という綺麗な関係になっています。

ここで最初の直感に戻りましょう。RS符号が「何個までの誤りを直せるか」を数えるとき、単位はあくまでシンボルであってビットではないという点が本質です。1シンボルが $m$ビットからなるとすると、たとえ物理的な誤りが数ビットにわたって連続して発生しても(たとえば $m$ビット以下に収まる短いバースト)、それが破壊するシンボルはたかだか1個(バーストが2つのシンボル境界にまたがった場合でも高々2個)です。つまり、

$$\text{1回の連続バースト誤りが破壊するビット数} \lesssim m \times (\text{破壊されるシンボル数})$$

という関係があるため、$t$個のシンボル誤り訂正能力は、最大でおよそ $m \cdot t$ ビット程度の連続したバースト誤り1回を丸ごと吸収できることに相当します(バーストがシンボル境界をまたいで散らばる場合はこれより少し目減りします)。畳み込み符号がビット単位でしか誤りを数えられず、バーストの中の個々のビット誤りに翻弄されてしまうのに対し、RS符号は「バーストが少数のシンボルに押し込められる」という性質を利用して、はるかに効率よく訂正能力を使い切ることができるのです。

復号の概要

RS復号の完全な代数的導出はこの回の範囲を超えますが、全体の流れだけ押さえておきましょう。受信語を $r(x) = c(x) + e(x)$($e(x)$ が誤りパターン)とすると、復号は次のようなステップで進みます。

1. シンドローム計算: 生成多項式の根 $\alpha^1,\dots,\alpha^{n-k}$ において受信語を評価する。$S_i = r(\alpha^i)$ とすると、誤りがなければ $c(\alpha^i)=0$ なので $S_i = e(\alpha^i)$ となり、誤りの情報だけが抽出される。すべての $S_i=0$ なら誤りなしと判定できる。
2. 誤り位置多項式の決定: シンドロームから、誤りが発生した位置を特定するための多項式(誤り位置多項式)を求める。この計算にはBerlekamp-Massey法(誤り数が最小のフィードバックシフトレジスタを合成するアルゴリズム)や、同等なEuclidの互除法に基づく方法がよく使われる。
3. 誤り位置の特定: 誤り位置多項式の根を、体のすべての元に対してしらみつぶしに評価して探す。この手続きはChien探索と呼ばれる。
4. 誤り値(大きさ)の計算: 誤り位置が分かったら、その位置での誤りシンボルの値をForneyのアルゴリズムで計算し、受信語から差し引いて訂正する。

これらのアルゴリズムはいずれも $GF(2^m)$上の四則演算(と、既に見た指数表現による高速な乗除算)だけで完結する、有限体上の代数計算です。詳細な導出には踏み込みませんが、「シンドロームで誤りの有無を検知し、代数的なアルゴリズムで位置と大きさを一気に求める」という骨格を覚えておいてください。

実務での使われ方

RS符号は深宇宙通信に限らず、CD/DVD、地上デジタル放送、QRコード、フラッシュメモリのエラー訂正など、身の回りの至るところで使われている符号ですが、深宇宙探査機の歴史においても中心的な役割を果たしてきました。

CCSDS標準では、勧告書 CCSDS 131.0-B (TM Synchronization and Channel Coding) において、$GF(2^8)$(1シンボル=1バイト)上のRS$(255,223)$符号が標準として規定されています。$n=255=2^8-1$、$k=223$、検査シンボル数 $n-k=32$、したがって

$$t = \left\lfloor \frac{255-223}{2}\right\rfloor = 16$$

シンボル(バイト)までの誤りを1つの符号語(255バイト)内で訂正できます。実運用では、この基本のRS符号語を複数個**インターリーブ(interleave)**して送信するのが一般的です。インターリーブとは、複数の符号語のシンボルを時間軸上でシャッフルして送る技術で、こうすることで、実際のリンク上で発生する長いバースト誤りを、インターリーブ深さの数だけ多くの符号語に薄く分散させることができます。CCSDS標準ではインターリーブ深さ $I=1,2,3,4,5,8$ などが規定されています。

歴史的には、ボイジャー2号が天王星(1986年)・海王星(1989年)へ接近するにあたり、地球からの距離が伸びて受信電力がますます弱くなる中でも科学データ量を確保するため、搭載ソフトウェアの更新によってRS$(255,223)$符号を畳み込み符号(拘束長7、符号化率1/2)の外符号として追加する、という改良が行われました。畳み込み符号+ビタビ復号を内符号、RS符号を外符号として直列に組み合わせるこの構成は、後にCCSDS標準の基本形として広く採用されることになります。なぜ内側に畳み込み符号、外側にRS符号を置くのかというと、ビタビ復号器は復号に失敗すると誤りをバースト状に吐き出しやすいという性質があり、その「バースト状の出力誤り」こそがRS符号の最も得意とする誤りパターンだからです。この内符号・外符号を組み合わせる考え方は**連接符号(concatenated code)**と呼ばれ、次回のテーマになります。

ガリレオ探査機も、高利得アンテナの展開に失敗し低利得アンテナのみでの通信を強いられるという厳しい制約の中、地上局側に特別に開発された「Big Viterbi Decoder」による長い拘束長の畳み込み符号と、RS符号を組み合わせた連接符号を採用することで、限られたリンク容量から可能な限り多くの科学データを持ち帰ることに成功しました。これらの事例は、RS符号(および連接符号という発想)が、リンクが最も苦しい局面でミッションを救ってきた実例と言えます。

演習問題

1. $GF(2^3)$($p(x)=x^3+x+1$、本文中のべき乗表を利用)において、$\alpha^5 \cdot \alpha^4$ を(a) 指数の足し算 $\alpha^{(5+4)\bmod 7}$ として、(b) 多項式としての掛け算を $p(x)$ で割った余りとして、それぞれ計算し、両者が一致することを確認してください。
2. CCSDS標準のRS$(255,223)$符号について、検査シンボル数 $n-k$、最小距離 $d_{\min}$、誤り訂正能力 $t$(シンボル単位)を求めてください。また1シンボル=8ビットとして、1回の連続バースト誤りが最大何ビット程度までなら理論上吸収できる可能性があるか、目安を見積もってください。
3. シングルトン限界 $d_{\min}\le n-k+1$ はなぜ成り立つのか(検査シンボルを $n-k$個しか持たない符号が、原理的にどれだけの最小距離を持ちうるかという直感でよい)を自分の言葉で説明し、RS符号が「MDS符号」と呼ばれる理由を述べてください。
4. なぜCCSDSの連接符号では、畳み込み符号(ビタビ復号)を内符号、RS符号を外符号として使う(その逆ではなく)のが合理的なのか、この回で学んだ「RS符号がバースト誤りに強い理由」とビタビ復号器の誤り特性を踏まえて説明してください。

まとめと次回予告

この回では、畳み込み符号が苦手とする「バースト誤り」に強い符号として、リード・ソロモン符号を導入しました。有限体 $GF(2^m)$上のシンボルという単位を導入し、情報シンボル列を係数とする多項式を$n$個の点で評価することで符号語を作るという代数的構成、そしてその最小距離が $d_{\min}=n-k+1$ というシングルトン限界を達成するMDS符号であることを見ました。この性質から誤り訂正能力 $t=\lfloor (n-k)/2\rfloor$ シンボルが導かれ、シンボル単位で数えることで1回のバーストが少数の誤りに圧縮される、というのがRS符号がバースト誤りに強い理由でした。復号はシンドローム計算・Berlekamp-Massey法・Chien探索・Forneyのアルゴリズムという一連の代数的手続きで行われることも紹介しました。

次回は、この回の最後に触れた**連接符号(concatenated code)**を扱います。畳み込み符号(内符号)とRS符号(外符号)、そしてインターリーブを組み合わせることで、それぞれの符号が単独では対処しきれない誤りパターンを互いに補い合い、深宇宙リンクにさらなる符号化利得をもたらす仕組みを見ていきます。

参考文献

• S. B. Wicker, V. K. Bhargava (eds.), Reed-Solomon Codes and Their Applications, IEEE Press
• R. E. Blahut, Theory and Practice of Error Control Codes, Addison-Wesley
• CCSDS 131.0-B, TM Synchronization and Channel Coding
• J. H. Yuen (ed.), Deep Space Telecommunications Systems Engineering, JPL Publication 82-76
• S. Lin, D. J. Costello, Error Control Coding, 2nd ed., Prentice Hall