リード・ソロモン符号の仕組み — 誤りと消失、GF(256)、QR・Voyagerへの応用

RS(n, k)では、k個のデータシンボルをn個の符号語シンボルへ符号化します。GF(256)を使う場合、1シンボルは1バイトです。同じバイト内の複数ビットが壊れても1シンボル誤りと数えます。

誤りは値が間違っていて、その場所も分からない状態です。消失は値が不明でも、その場所が分かる状態です。最小距離d=n−k+1のRS符号で、通常の一意復号が保証される条件は、誤りe個・消失s個に対して2e+s≤n−kです。ここでeは消失位置以外の誤り数です。

「正しい3個がある」だけでは、その3個を特定できません。場所が分からない誤り4個まで直せるという意味ではありません。誤りだけなら上限は⌊(n−k)/2⌋。冗長数が奇数の場合は切り捨てます。保証範囲を超えると、復号失敗だけでなく別の符号語への誤訂正も起こり得ます。

計算を追いやすくするため、ここではGF(256)ではなく、0〜6を使って7で割った余りを計算するGF(7)を使います。データ[1, 2, 3]からf(x)=1+2x+3x²を作り、異なる7点x=0,1,…,6で評価します。

送る値は[1, 6, 3, 6, 1, 2, 2]です。この例では元の係数をそのまま先頭に残しません。正しい位置と値が3組分かれば、次数2以下の多項式を補間できます。

異なる2つの次数2以下の多項式は、差を取るとゼロでない次数2以下の多項式になります。その根は高々2個なので、7点の評価列は少なくとも5か所で異なります。これがこの例の最小距離5と、誤り2個の一意訂正を説明します。一般に次数k未満を異なるn点で評価すると、最小距離はn−k+1になります。このようにSingleton限界に達する符号をMDS（最大距離分離）符号と呼びます。

評価型は体にn個の異なる点が必要です。GF(256)の非零元だけを使う通常の巡回型では長さ255を基本にします。ゼロも含めた評価型や拡張符号まで「最大255」と一律に制限するわけではありません。

GF(2⁸)=GF(256)では、8ビットを0/1の係数を持つ次数7以下の多項式として表します。バイト値131（0x83）はx⁷+x+1に対応します。加算と減算はXOR、乗算は多項式積を次数8の既約多項式で割った余りです。整数を256で割った余りの演算とは異なります。

0x83 XOR 0x05 = 0x86
p(x) = x⁸ + x⁴ + x³ + x² + 1 = 0x11D
0x80 × 0x02 = 0x1D   （このp(x)での体の乗算）
α = 0x02
α⁰ = 1, α¹ = 2, …, α⁷ = 128, α⁸ = 29, α²⁵⁵ = 1

0x11Dを使うこの表現では0x02が原始元で、べき乗は255個の非零元を巡ります。ゼロ以外のすべての元に逆元があり、ゼロ除算を除いて体内で演算が完結します。GF(7)のような素数体と違い、GF(256)の加算を普通の整数加算で代用してはいけません。

0x11DはQRやCDで使われる表現ですが、すべてのRS規格で共通ではありません。既約多項式、原始元、基底、シンボルの並び順まで一致させる必要があります。同じRS(255, 223)という名前だけでは、互換な符号化器は作れません。

元のデータをそのまま残してパリティを付ける方式を組織符号化と呼びます。ここではGF(256)、原始元α、r=n−k個の連続した根を持つ巡回型の一例を示します。開始指数bも規格ごとのパラメータです。

g(x) = ∏ (x − α^(b+j))   j = 0, …, r−1
R(x) = d(x) x^r mod g(x)
c(x) = d(x) x^r − R(x)

データ多項式d(x)をr桁ずらして、生成多項式で割った余りを引けば、c(x)はg(x)で割り切れます。標数2の体なので引き算はXORです。パリティを計算する際、一般の数の割り算や浮動小数点の多項式計算は使いません。

この巡回表現と先ほどの評価表現はRS符号を理解する異なる構成です。係数の扱い、座標の対応、スケーリングなどを定めずに、同じ入力から同じバイト列が出るとはいえません。短縮符号では、所定のデータ位置へ仮のゼロを補って符号化し、その位置を送らない構成も使われます。

受信多項式をv(x)とし、生成多項式の根でSⱼ=v(α^(b+j))（j=0,…,r−1）を計算します。これがシンドロームです。非零の値があれば符号語の条件を満たしていません。しかしすべてゼロでも「送信したデータと同じ」とは証明できません。破損によって別の有効な符号語になれば、検査を通ります。

1. シンドロームと、分かっている消失位置を得る。
2. Berlekamp–Massey法や拡張Euclid法などで誤り位置多項式を求める。
3. Chien探索で根を探し、位置へ変換する。
4. Forneyの公式などで誤り値を求めて修正し、訂正数・位置・シンドロームの整合を再確認する。

たとえばc(x)=Σcᵢxⁱという係数順で位置iのロケーターをXᵢ=αⁱとし、Λ(z)=∏(1−Xᵢz)と定義すると、根はz=Xᵢ⁻¹=α⁻ⁱです。「根の指数がそのまま配列の添字」とは限りません。配列が高次係数から並ぶ場合はさらに変換が必要です。

再検査も誤訂正を完全には排除しません。必要に応じて別の誤り検出を組み合わせます。意図的な改ざんに対してはMACや電子署名などが別途必要で、RS符号は認証の代わりにはなりません。

QRコードはGF(256)のRS符号を使います。QRの用語でいう「コード語」は8ビット（1バイト）で、ここまでのRS符号の説明では1シンボルに相当します。nシンボルからなるRS符号語全体とは区別してください。デンソーウェーブが示すL/M/Q/Hのコード語の復元能力の目安は次のとおりです。

これは画像面積の許容欠損率や安全なロゴ面積ではありません。バージョンとレベルによりブロック構成・データ数・パリティ数が変わるため、固定の「冗長率」をレベルごとに付けるのも不正確です。訂正予算は各RSブロックで考え、複数ブロックのパリティを自由に融通できるとは考えません。

位置検出パターンや形式情報の破損、撮影条件によっても読み取りは失敗します。規格の現行版はISO/IEC 18004:2024です。本記事は規格の全文を転載せず、公開されているデンソーウェーブの説明を割合の根拠としています。詳しくはQRコードの誤り訂正レベルを参照してください。

CDのCIRC（Cross-Interleaved Reed–Solomon Code）ではC2がRS(28, 24)、C1がRS(32, 28)です。符号化はC2側からインターリーブを経てC1側へ進み、復号は逆向きになります。各符号を単独で見ると、未知位置の誤り2シンボルを訂正できますが、全体では並べ替えや消失情報も使います。ECMA-130の附属書Cでこの構成を確認できます。

DVD-ROMのECMA-267では、列方向のRS(208, 192)と行方向のRS(182, 172)を組み合わせます。DVDまでCIRCと呼ぶのは誤りです。Blu-rayのBD-RE白書（2004年）では、主データを守るLDC（Long Distance Code）と、バースト箇所を知らせるBIS（Burst Indicator Subcode）を組み合わせています。

インターリーブは連続した破損を複数の符号語へ分散する仕組みです。RS自体も1バイト内のビット破損をまとめて扱えるため、バースト誤りに適性があります。「インターリーブがなければバーストを一切直せない」わけではありません。実際の傷への耐性は方向・形・読取系・配置・復号方式に依存し、傷の長さだけで完全訂正を保証できません。

NASA/JPLの技術資料によると、Voyagerは天王星・海王星への遠距離通信を見越した実験的なRSデータ符号化器を搭載していました。後年の運用・ソフトウェア変更を、存在しなかった符号化器をソフトウェアだけで新設した話に置き換えてはいけません。RS符号と畳み込み符号を組み合わせた連接符号化は、遠距離でのデータ伝送改善の一部でした。圧縮や地上受信設備などの改善とも区別が必要です。

宇宙通信のCCSDS 131.0-B-5（2023年）第4章には、8ビットシンボル、t=8または16のRS方式が規定されています。RS(255, 223)ならパリティは32シンボルで、未知位置の誤り16シンボルまでが通常の訂正保証範囲です。CCSDS方式は体の表現や根の取り方も規定しており、前節のQR向けパラメータをそのまま流用できません。

2026年10月21日の確認ではJAXAの文書一覧は131.0-B-6（2026年4月）を掲載しています。ここで数式の参照に使ったB-5を最新版とは扱いません。実装時は適用する最新版とミッションの仕様を確認してください。特定の火星探査機が同じRS方式を常にTurbo・LDPCと併用する、といった一般化もしていません。

DVB-TのETSI EN 300 744 V1.6.2では、188バイトに16バイトのパリティを加える短縮RS(204, 188)を外符号に使い、未知位置の誤り8バイトまでを訂正します。インターリーブと内側の畳み込み符号も使います。これはDVB-Tの構成であり、世代の違う放送規格まで同じと考えてはいけません。

MDSは、同じn・kで最小距離が最大という性質です。雑音の統計や軟判定情報まで含めて、シャノン限界に最も近い方式だという意味ではありません。長いブロック、軟判定、反復復号が有効な通信路ではTurboやLDPCなども選択肢になります。

復号計算量も工程別です。r=n−kをパリティ数とし、有限体の1演算を一定コストとして数えます。素朴なシンドローム計算はO(nr)、通常のBerlekamp–Massey法による位置多項式の計算はO(r²)です。消失なしでt=⌊r/2⌋個までの誤りを扱う場合、n個の候補位置を調べるChien探索はO(nt)です。より一般には、探索対象の位置多項式の次数をℓとするとO(nℓ)で、誤りと消失をまとめた位置多項式ならℓ=e+sです。工程ごとの演算回数と、実装・ハードウェア上の実行時間を区別してください。

• シンボルの大きさとn・kを確認し、未知位置の誤りと既知位置の消失を分ける。
• 通常の一意訂正保証は2e+s≤n−k。保証外は失敗だけでなく誤訂正もあり得る。
• 体の多項式・基底・原始元・根の開始位置・配列順・短縮方法をそろえる。
• ゼロのシンドロームを、元のデータとの一致や改ざん防止の証拠にしない。
• QRの復元割合や光ディスクの訂正能力を、画像面積・傷の長さの保証へ置き換えない。

まずGF(7)の表を手計算し、次に実規格のパラメータへ進むと、数式と製品の保証範囲を切り分けて理解できます。本記事の例は原理の説明であり、規格準拠の符号化・復号実装そのものではありません。