Chapter 11

リード・ソロモン符号 — QR コード・CD・宇宙通信の主役

この章の位置づけ. CD や DVD の傷、QR コードの汚れ、探査機ボイジャーからの信号、地上デジタル放送、RAID-6、分散ストレージなどで使われているのがリード・ソロモン符号（RS 符号）である。 1960 年に MIT リンカーン研究所の Irving Reed と Gustave Solomon が 5 ページの論文で発表した。復号法は Peterson らの方法（1960〜61 年）が先にあったが、計算量が大きく、1968〜69 年にバーレカンプ・マッシー法が現れて実用が広がった。

RS 符号が強い理由は 2 つある。

1. MDS 符号である。06 章 4 節のシングルトン限界\(d_{\min} \le n-k+1\)を等号で満たし、冗長を最大限に活かしている。
2. バイト単位で誤りを数えるので、連続したビットがまとめて壊れるバースト誤りに強い。

この章で使う既出の用語（定義は各リンク先）. 標数（02 章 3 節）、原始元・離散対数（03 章 3 節）、有限体上の連立 1 次方程式と掃き出し法（03 章 4 節）、 \(\mathrm{GF}(2^m)\)と\(\mathrm{GF}(2^3)\)のべき表（05 章 2 節）、\(\mathrm{GF}(2^8)\)（05 章 3 節）、 符号化・シングルトン限界・MDS 符号・消失・バースト誤り・インターリーブ（06 章）、線形符号・シンドローム（07 章）、短縮符号（08 章 4 節）、 巡回符号・生成多項式・組織符号形式の符号化（09 章）、BCH 限界・誤り位置多項式・位置元・チェン探索（10 章）、LFSR（13 章、この章では名前だけ使う）

1. 構成

パラメータ

\(\mathrm{GF}(2^m)\)の要素 1 つをシンボルと呼び、符号語はシンボルを\(n\)個並べたものとする。実用では\(m = 8\)で、1 シンボルが 1 バイトである。訂正したいシンボル数を\(t\)とすると

である（\(d_{\min}\)は下で示す）。\(m = 8\)なら\(n = 255\)である。 符号長が\(2^m\)でなく\(2^m - 1\)なのは、符号語の各位置\(i\)を原始元のべき\(\alpha^i\)（\(i = 0, 1, \dots, 2^m-2\)、0 以外の全要素）に対応させるからである。\(\alpha\)の位数が\(2^m-1\)なので、\(\alpha^j\)が\(x^n + 1\)の根になるのは\(n = 2^m - 1\)（またはその倍数）のときで、09 章 1 節の巡回符号の条件を満たす。

訂正能力:

• 誤り（位置が分からない）: \(t = (n-k)/2\)シンボルまで
• 消失（位置は分かっていて値だけが分からない）: \(n-k\)シンボルまで（誤りの 2 倍）
• 両方が混ざる場合: \(2 \times (\text{誤りの数}) + (\text{消失の数}) \le n-k\)

直感的な理由は次のとおりである。検査シンボル\(n - k = 2t\)個から、復号のときに\(2t\)個のシンドロームの式が得られる（3 節）。位置の分からない誤り 1 個は「位置」と「値」の 2 つが未知なので式を 2 本使い、消失は位置が分かっているので「値」の 1 本で済む。消失の場合の復号方法は 3 節の最後で述べる。

生成多項式

\(\alpha\)を\(\mathrm{GF}(2^m)\)の原始元として

とする。BCH 符号（10 章）と同じく連続する\(2t\)個のべきを根に持つが、符号語の係数が\(\mathrm{GF}(2^m)\)の要素でよいので、\(x - \alpha^j\)をそのまま掛ければよく、最小多項式を求める必要は無い。\(g\)の根はすべて\(x^n + 1\)の根なので、\(g\)は\(x^n+1\)を割り切る。

MDS になる理由: 10 章 1 節の BCH 限界の証明は、「重み\(2t\)以下の符号語があるとすると、ヴァンデルモンド行列の行列式が 0 でないので、符号語の係数がすべて 0 になり矛盾する」というものだった。係数が 0 と 1 に限らず\(\mathrm{GF}(2^m)\)の任意の値でも、この議論はそのまま成り立つので\(d_{\min} \ge 2t + 1\)である。 一方\(\deg g = 2t\)なので検査シンボルは\(n - k = 2t\)個で、シングルトン限界は\(d_{\min} \le n - k + 1 = 2t + 1\)である。両側から挟まれて\(d_{\min} = 2t + 1 = n - k + 1\)、つまり MDS 符号である ∎

符号化

\(k\)個のデータシンボル\(u_0, \dots, u_{k-1}\)を係数とする多項式\(u(x) = u_{k-1}x^{k-1} + \cdots + u_0\)（情報多項式）に対し、09 章 2 節の CRC と同じ組織符号形式で

とする。\(x^{2t}\)を掛けてデータを上位の係数に寄せ、\(g\)で割った余り（次数\(2t\)未満）を下位に置く。データの後ろに\(2t\)個の検査シンボル（パリティバイト）を付けたことになり、\(T(x)\)は\(g(x)\)で割り切れる。

短縮符号: 実際の規格では\(n = 255\)より短い RS 符号がよく使われる（5 節の CD の RS(32,28) など）。これは 255 シンボルのうち先頭のデータシンボルを常に 0 とみなして送らない短縮符号で、訂正能力\(t\)はそのまま保たれる。

2. なぜバースト誤りに強いのか

RS 符号はシンボル（1 バイト）単位で誤りを数える。1 バイトの中で 1 ビット壊れても 8 ビット全部壊れても、どちらも「1 シンボルの誤り」である。

たとえば RS(255,223)（\(t=16\)）は 16 シンボルまで訂正できる。長さ\(b\)ビットの連続した破壊がまたぐバイト数は、位置によって最大\(\lceil (b-1)/8 \rceil + 1\)個である。これが 16 以下になる\(b \leq 121\)なら、どこで起きても必ず訂正できる。バイトの境界にそろっていれば 128 ビット（16 バイト）まで訂正できる。 各ビットを独立に扱う BCH 符号で同じ長さの連続誤りを訂正するには、訂正能力を 121 ビット以上にする必要があり、検査ビットは RS 符号の何倍も必要になる。誤りが固まって起きるという現実の性質を、シンボル単位で数えることで有利に使っている。

インターリーブとの組み合わせ

さらに長いバーストに対応するため、複数の符号語のシンボルを交互に並べて送る（インターリーブ、06 章 6 節）。 長いバーストが来ても、各符号語から見れば数シンボルずつに散らばるので、それぞれの訂正能力の範囲に収まる。

CD のCIRC（Cross-Interleaved Reed-Solomon Code）は 2 つの RS 符号とインターリーブを組み合わせたもので、約 4000 ビットの連続した誤りを訂正できるとされる。ディスク上では約 2.5 mm の傷に相当する。

3. 復号アルゴリズム（この章の本体）

受信語\(r(x) = T(x) + e(x)\)から誤りパターン\(e(x)\)を求めて取り除く。流れは10 章 4 節と同じで、誤り値が 1 とは限らない点だけが違う。 上の図は\(\mathrm{GF}(2^4)\)上の RS(15,11)（\(t = 2\)）で、誤りの位置と値を選ぶと、ここで述べる手順で訂正される様子が表示される。3 つ目の誤りを入れると訂正能力を超える。 各ステップの後に、次の例で実際の値を追う。

例（この節を通して使う）: \(\mathrm{GF}(2^3)\)（05 章 2 節の表、\(\alpha^3 = \alpha + 1\)）上の RS(7,3) 符号（\(n = 7\)、\(t = 2\)、\(k = 3\)）。生成多項式は

を掛けて

である（\(\alpha + \alpha^2 = 010 \oplus 100 = 110 = \alpha^4\)、\(\alpha^3 + \alpha^4 = 011 \oplus 110 = 101 = \alpha^6\) など、足し算はビットの XOR）。 情報多項式\(u(x) = 1\)の符号語は\(g(x)\)そのもので、係数を\(x^0\)から並べると\((\alpha^3, \alpha, 1, \alpha^3, 1, 0, 0)\)である。 これを送り、位置 1 に値\(\alpha^5\)、位置 5 に値\(\alpha^4\)の誤りが加わって

を受信したとする（位置 1 は\(\alpha + \alpha^5 = 010 \oplus 111 = 101 = \alpha^6\)）。

ステップ 1: シンドローム計算

• \(X_l = \alpha^{i_l}\): 位置元（\(i_l\)は壊れたシンボルの位置。10 章 4 節と同じ）
• \(Y_l\): 誤り値（そのシンボルに足された値）
• \(\nu\): 実際の誤りの個数（まだ分からない）

すべて 0 なら誤り無しとして終了する。2 元 BCH 符号と違い、\(Y_l\)が 1 とは限らないので\(S_{2j} = S_j^2\)は成り立たず、\(2t\)個すべてを計算する。

例: 受信側は\(r(\alpha^j)\)を計算する。結果は\(e(x) = \alpha^5 x + \alpha^4 x^5\)に代入した値と同じなので、そちらで確かめる（\(\alpha^7 = 1\)なので指数は 7 で割った余り）:

\(S_1^2 = 1 \neq 0 = S_2\)で、確かに\(S_{2} = S_1^2\)は成り立っていない。

ステップ 2: 誤り位置多項式 Λ(x) を求める

右辺の\(\Lambda_1, \dots, \Lambda_\nu\)は、左辺の積を展開して\(x\)のべきごとにまとめたときの係数である。たとえば\(\Lambda_1 = -(X_1 + \cdots + X_\nu)\)、\(\Lambda_\nu = (-1)^\nu X_1 \cdots X_\nu\)で、標数 2 では符号は関係ない。 \(\Lambda(x)\)は\(x = X_l^{-1}\)のときに限って 0 になるので、根が誤り位置を教える。 \(X_l\)も\(\nu\)もまだ分からないので、係数\(\Lambda_1, \dots, \Lambda_\nu\)をシンドロームから求めるのがこのステップの目的である。10 章 4 節では未知数を\(X_l, Y_l\)の\(2\nu\)個と数えたが、ここではまず位置の情報だけを\(\Lambda\)の係数\(\nu\)個として求め、値\(Y_l\)はステップ 4 で別に求める。

シンドロームと\(\Lambda\)の係数の関係式:

方針: \(\Lambda(X_l^{-1}) = 0\)の両辺に\(Y_l X_l^{j+\nu}\)を掛けて\(l\)について足すと、\(Y_l X_l^{(\text{何か})}\)の和、つまりシンドロームが現れる。

導出: 各\(l\)について\(\Lambda(X_l^{-1}) = 1 + \Lambda_1 X_l^{-1} + \cdots + \Lambda_\nu X_l^{-\nu} = 0\)である。両辺に\(Y_l X_l^{j+\nu}\)を掛けて\(l = 1, \dots, \nu\)について足すと

\(\Lambda_i X_l^{-i}\)の項は\(\Lambda_i Y_l X_l^{j+\nu-i}\)になり、\(l\)について足すとステップ 1 の定義から\(\Lambda_i S_{j+\nu-i}\)である。添字\(j + \nu - i\)は\(j\)から\(j + \nu\)の範囲にあり、\(1 \le j \le \nu \le t\)なら\(2t\)を超えないので、計算済みのシンドロームである。よって

これは未知数\(\Lambda_1, \dots, \Lambda_\nu\)の\(\nu\)個についての\(\nu\)本の連立 1 次方程式である ∎

03 章 4 節の掃き出し法は\(\mathrm{GF}(p)\)で示したが、使ったのは「割り算は逆元を掛けること」だけなので、\(\mathrm{GF}(2^m)\)でもそのまま使える。誤り訂正の中心は、有限体上の連立 1 次方程式を解くことである。 \(\nu\)は分からないので、実際には\(\nu = t, t-1, \dots\)と仮定し、係数行列の行列式が 0 でなくなる最大の\(\nu\)を採る。

例: \(\nu = 2\)とすると、\(j = 1, 2\)の式は

で、\(S_1 = 1\)、\(S_2 = 0\)、\(S_3 = \alpha^6\)、\(S_4 = \alpha^5\)を入れると

となる。1 本目から\(\Lambda_2 = \alpha^6\)、2 本目から\(\Lambda_1 = \alpha^5 / \alpha^6 = \alpha^{-1} = \alpha^6\)。よって\(\Lambda(x) = 1 + \alpha^6 x + \alpha^6 x^2\)である。 （誤りは位置 1 と 5 なので\(X_1 X_2 = \alpha^{6}\)、\(X_1 + X_2 = \alpha + \alpha^5 = 010 \oplus 111 = 101 = \alpha^6\)で、係数と一致している。）

バーレカンプ・マッシー法

上の連立方程式を掃き出し法で解くと、計算量は\(t^3\)に比例する（\(O(t^3)\)と書く）。これより速い方法がある。 上の式を\(S_{j+\nu} = -(\Lambda_1 S_{j+\nu-1} + \cdots + \Lambda_\nu S_j)\)と書くと、「直前の\(\nu\)個の値の決まった組み合わせで次の値が決まる」という漸化式になっている。このような漸化式で数列を作る装置を線形帰還シフトレジスタ（LFSR）という（13 章で詳しく扱う）。 「\(S_1, S_2, \dots, S_{2t}\)を作り出す最も短い LFSR（最小の\(\nu\)とその係数）を求める」問題と読み替えると、\(O(t^2)\)で解ける。これがバーレカンプ・マッシー法である。

アルゴリズムの骨子（詳しい正しさの証明は省く）:

1. \(\Lambda(x)=1\)、\(L=0\)（現在の LFSR の長さ）から始める。
2. \(j = 1, \dots, 2t\)について、現在の\(\Lambda\)で予測した値と実際の\(S_j\)とのずれ\(\Delta = S_j + \Lambda_1 S_{j-1} + \cdots + \Lambda_L S_{j-L}\)を計算する。
3. \(\Delta \neq 0\)なら、前回\(\Delta \neq 0\)だったときの\(\Lambda\)（\(B(x)\)として保存しておく）を使って\(\Lambda(x) \leftarrow \Lambda(x) - \Delta\,\Delta_B^{-1}\, x^{j - j_B} B(x)\)と補正する。\(\Delta_B, j_B\)はそのときのずれと\(j\)である。
4. \(2L \le j - 1\)のときは、今の長さでは足りないので\(L \leftarrow j - L\)と増やし、\(B\)などを更新する。

同じ LFSR は13 章のストリーム暗号にも現れる。暗号では LFSR で数列を作り、誤り訂正では数列から LFSR を推定する。短い LFSR で作れてしまう数列は推定されやすいので、暗号にとっては弱点になる（13 章）。

ステップ 3: チェン探索（誤り位置の特定）

\(\Lambda(x)=0\)の根を、\(x = \alpha^{-i}\)（\(i=0,1,\dots,n-1\)）を順に代入して探す。\(\Lambda(\alpha^{-i})=0\)なら位置\(i\)が誤りである。 候補は\(n\)個で、1 つあたり\(\Lambda\)の計算は\(t\)回程度の掛け算なので、合計の計算量は\(O(nt)\)である。ハードウェアでは全位置を同時に調べられる。

例: \(i = 0, \dots, 6\)を代入すると、0 になるのは\(i = 1\)と\(i = 5\)だけである:

ステップ 4: フォニー・アルゴリズム（誤り値の計算）

\(\Lambda\)には誤りの位置しか入っていない。値\(Y_l\)を求めるには、\(Y_l\)を含むシンドロームと\(\Lambda\)を組み合わせる。 シンドロームを多項式\(S(x) = \sum_{j=1}^{2t}S_j x^{j-1}\)にまとめ、誤り評価多項式を

と定める。\(\bmod x^{2t}\)は、積のうち\(x^{2t}\)未満の項だけを残すことである。このとき誤り値は

で求まる。標数 2 では\(-Y_l = Y_l\)なので、符号は気にしなくてよい。

\(\Lambda'\)は形式的微分で、各項の\(x^n\)を\(n x^{n-1}\)に置き換えたものである。極限で定義する微分ではなく、係数の書き換え規則として定める。積の微分の公式\((fg)' = f'g + fg'\)は、この規則からも成り立つ。 \(n\)は「1 を\(n\)個足したもの」なので、標数 2 では\(n\)が偶数の項は 0 になって消え、奇数次の項だけが残る。

方針: \(S(x)\)を\(X_l, Y_l\)で書き、\(\Lambda\)を掛けると等比数列の和が現れて簡単になることを使う。\(x = X_l^{-1}\)を代入すると、\(\Omega\)と\(\Lambda'\)のどちらも\(l\)番目の項だけが残る。

導出: シンドロームの定義\(S_j = \sum_l Y_l X_l^j\)を\(S(x)\)に入れると

これに\(\Lambda(x) = \prod_p (1 - X_p x)\)を掛ける。\(l\)番目の項には因子\((1 - X_l x)\)が含まれ、等比数列の和の公式から\((1 - X_l x)\sum_{j=0}^{2t-1}(X_l x)^j = 1 - (X_l x)^{2t}\)なので

\(\nu \le t\)なので\(\prod_{p\neq l}\)の次数は\(t - 1\)以下であり、\((X_l x)^{2t}\)を含む部分はすべて\(x^{2t}\)以上の項になる。それを捨てると

\(x = X_l^{-1}\)を代入すると、\(l\)以外の項は因子\((1 - X_l X_l^{-1}) = 0\)を含むので消え、\(\Omega(X_l^{-1}) = Y_l X_l \prod_{p \neq l}(1 - X_p X_l^{-1})\)となる。 一方\(\Lambda(x) = \prod_p(1 - X_p x)\)を積の微分の公式で微分すると\(\Lambda'(x) = \sum_l (-X_l)\prod_{p \neq l}(1 - X_p x)\)で、\(x = X_l^{-1}\)を入れると同じ理由で 1 項だけ残り\(\Lambda'(X_l^{-1}) = -X_l \prod_{p\neq l}(1-X_pX_l^{-1})\)となる。 割ると\(X_l\)と\(\prod\)が約分されて\(\Omega(X_l^{-1}) / \Lambda'(X_l^{-1}) = -Y_l\)である ∎

例: \(S(x) = 1 + 0 \cdot x + \alpha^6 x^2 + \alpha^5 x^3\)、\(\Lambda(x) = 1 + \alpha^6 x + \alpha^6 x^2\)。積を\(x^3\)の項まで計算すると

• \(x^0\): \(1\)
• \(x^1\): \(\alpha^6\)
• \(x^2\): \(\alpha^6 + \alpha^6 = 0\)
• \(x^3\): \(\alpha^5 + \alpha^6 \cdot \alpha^6 = \alpha^5 + \alpha^5 = 0\)

なので\(\Omega(x) = 1 + \alpha^6 x\)。\(\Lambda'(x) = \alpha^6\)である（\(\alpha^6 x^2\)の微分は\(2\alpha^6 x = 0\)）。

• 位置 1（\(X^{-1} = \alpha^6\)）: \(\Omega(\alpha^6) = 1 + \alpha^{12} = 1 + \alpha^5 = 001 \oplus 111 = 110 = \alpha^4\)で、\(Y = \alpha^4 / \alpha^6 = \alpha^{-2} = \alpha^5\)。
• 位置 5（\(X^{-1} = \alpha^2\)）: \(\Omega(\alpha^2) = 1 + \alpha^{8} = 1 + \alpha = 011 = \alpha^3\)で、\(Y = \alpha^3 / \alpha^6 = \alpha^{-3} = \alpha^4\)。

加えた誤り値\(\alpha^5\)、\(\alpha^4\)と一致した。

ステップ 5: 訂正

体\(\mathrm{GF}(2^m)\)では引き算は XOR である。

例: 位置 1 は\(\alpha^6 + \alpha^5 = 101 \oplus 111 = 010 = \alpha\)、位置 5 は\(\alpha^4 + \alpha^4 = 0\)となり、送った\(g(x)\)に戻る。

消失（位置が分かっている場合）

位置\(i_l\)が最初から分かっているなら、ステップ 2 と 3 は不要である。\(\Lambda(x) = \prod_l (1 - \alpha^{i_l} x)\)を直接作り、ステップ 4 で値を求めればよい。 未知数は値だけなので、\(2t\)個のシンドロームで\(2t = n - k\)個まで復元できる。これが 1 節の「消失なら 2 倍」の理由である。

4. 実例: QR コードの RS 符号

QR コードは\(\mathrm{GF}(2^8)\)を既約多項式\(x^8+x^4+x^3+x^2+1\)（係数を並べたビット列\(1\,0001\,1101\)を 16 進で書いて 0x11D）で作り、原始元\(\alpha = x\)（ビット\(00000010\)）を使う。この多項式が原始多項式であることは05 章 3 節で述べた。

位置の分からない誤りは検査シンボル 2 個で 1 個訂正できる（1 節の\(t = (n-k)/2\)）ので、訂正できる割合は検査シンボルの割合のほぼ半分になる。

QR コードの中央にロゴを重ねても読み取れるのはこのためである。レベル H なら符号語の約 30% が読めなくても復元できるので、中央の一部を隠しても元のデータが得られる。

5. RS 符号の応用一覧

6. まとめ

これで第 II 部（誤り検出・訂正）は終わりである。次章から暗号に入る。第 I 部で作った合同算術や\(\mathrm{GF}(2^8)\)が、暗号でも中心的な役割を果たす。