リード・ソロモン誤り訂正

リード・ソロモン符号
名前の由来	アーヴィング・S・リードとギュスターヴ・ソロモン
分類
階層	線形ブロック符号 多項式符号 リード・ソロモン符号
ブロック長	ん
メッセージの長さ	け
距離	n − k + 1
アルファベットのサイズ	q = p m ≥ n   ( p は素数) 多くの場合、n = q − 1 です。
表記	[ n , k , n − k + 1] qコード
アルゴリズム
Berlekamp–Massey Euclidean ら
プロパティ
最大距離分離コード
ヴ t e

情報理論と符号理論において、リード・ソロモン符号は、 1960年にアーヴィング・S・リードとギュスターヴ・ソロモンによって導入された誤り訂正符号のグループです。 ^[1]ミニディスク、CD、DVD、ブルーレイディスク、QRコード、データマトリックス などの民生技術、DSLやWiMAXなどのデータ伝送技術、衛星通信、 DVB、ATSCなどの放送システム、 RAID 6などのストレージシステムなど、多くの用途があります。

リード・ソロモン符号は、シンボルと呼ばれる有限体要素の集合として扱われるデータブロックに対して作用する。リード・ソロモン符号は、複数のシンボルエラーを検出して訂正することができる。t = n  −  k 個のチェックシンボルをデータに追加することにより、リード・ソロモン符号は、最大t 個のエラーシンボルの任意の組み合わせを検出（訂正はできない）したり、未知の場所にある最大 ⌊ t /2⌋ 個のエラーシンボルを見つけて訂正したりすることができる。消失訂正符号としては、アルゴリズムに提供されている既知の場所にある最大t 個の消失を訂正したり、エラーと消失の組み合わせを検出して訂正したりすることができる。リード・ソロモン符号は、連続するb  + 1 個のビットエラーのシーケンスがサイズbのシンボルのうち最大 2 つに影響を与える可能性があるため、マルチバーストビットエラー訂正符号としても適している。 tの選択は符号の設計者次第であり、広い範囲内で選択することができる。

リード・ソロモン符号には、オリジナル ビューとBCHビューの 2 つの基本的なタイプがあります。BCH ビュー デコーダーはオリジナル ビュー デコーダーよりも高速で、必要な作業用ストレージが少なくて済むため、BCH ビューが最も一般的です。

リード・ソロモン符号は、当時MIT リンカーン研究所の職員であったアーヴィング・S・リードとギュスターヴ・ソロモンによって 1960 年に開発されました。彼らの独創的な論文は、「特定の有限体上の多項式符号」と題されていました (Reed & Solomon 1960)。リードとソロモンの論文で説明されている元の符号化方式では、符号化するメッセージに基づいて可変多項式が使用され、符号化する値の固定セット (評価ポイント) のみがエンコーダとデコーダに認識されていました。元の理論上のデコーダは、受信メッセージのn (符号化されたメッセージの長さ) の値からk (符号化されていないメッセージの長さ) のサブセットに基づいて潜在的な多項式を生成し、最も一般的な多項式を正しいものとして選択しましたが、これは最も単純な場合を除いて非現実的でした。この問題は当初、元の方式を、エンコーダとデコーダの両方が知っている固定多項式に基づくBCH コードのような方式に変更することで解決されましたが、後に、BCH 方式よりも遅いものの、元の方式に基づく実用的なデコーダが開発されました。この結果、リード・ソロモン コードには、元のエンコード方式を使用するものと BCH エンコード方式を使用するものの 2 つの主なタイプがあります。

また、1960年には、ダニエル・ゴレンスタインとニール・ツィラーが開発したBCH符号用の実用的な固定多項式デコーダーが、1960年1月にツィラーによってMITリンカーン研究所の報告書で説明され、その後1961年6月の論文でも説明されました。 ^[2]ゴレンスタイン-ツィラーデコーダーとBCH符号に関する関連研究は、W・ウェスリー・ピーターソン著「誤り訂正符号」 (1961年) で説明されています。^[3] 1963年までに(あるいはそれ以前に)、J・J・ストーン(および他の人)は、リード-ソロモン符号が固定生成多項式を使用するBCH方式を使用できることを認識し、そのような符号をBCH符号の特別なクラスにしました。^{[4]しかし、元の符号化方式に基づくリード-ソロモン符号はBCH符号のクラスではなく、評価点のセットによっては}巡回符号でさえありません。

1969 年に、改良された BCH 方式デコーダーがElwyn BerlekampとJames Masseyによって開発され、それ以来Berlekamp–Massey 復号アルゴリズムとして知られるようになりました。

1975年に杉山康雄によって拡張ユークリッド互除法に基づく別の改良BCH方式復号器が開発された。^[5]

1977 年、リード・ソロモン符号は連結誤り訂正符号の形でボイジャー計画に実装されました。量産された消費者向け製品への最初の商用応用は 1982 年のコンパクト ディスクで、2 つのインターリーブされたリード・ソロモン符号が使用されました。今日、リード・ソロモン符号はデジタル ストレージデバイスやデジタル通信規格に広く実装されていますが、徐々にBose-Chaudhuri-Hocquenghem (BCH) 符号に置き換えられつつあります。たとえば、リード・ソロモン符号はデジタル ビデオ放送(DVB) 規格DVB-Sで畳み込み内部符号と組み合わせて使用​​されていますが、BCH 符号はその後継であるDVB-S2ではLDPCとともに使用されています。

1986 年に、 Berlekamp-Welch アルゴリズムとして知られる独自の方式デコーダが開発されました。

1996 年に、リスト デコーダーまたはソフト デコーダーと呼ばれるオリジナル スキーム デコーダーのバリエーションが Madhu Sudan らによって開発され、このタイプのデコーダーの研究が続けられています ( Guruswami–Sudan リスト デコード アルゴリズムを参照)。

2002年に、Shuhong Gaoによって拡張ユークリッドアルゴリズムに基づいた別の独自の方式のデコーダが開発されました。^[6]

リード・ソロモン符号化は、メディアの欠陥に関連するバースト エラーを修正するために、大容量ストレージ システムで広く使用されています。

リード・ソロモン符号はコンパクト ディスクの重要な要素です。これは大量生産される消費者向け製品で強力なエラー訂正符号が初めて使用されたもので、DATとDVD は同様の方式を使用しています。CD では、28 方向畳み込みインター リーバで分離された 2 つの層のリード・ソロモン符号により、クロスインターリーブ リード・ソロモン符号 ( CIRC ) と呼ばれる方式が実現されています。CIRC デコーダーの最初の要素は、比較的弱い内部 (32,28) リード・ソロモン符号で、8 ビット シンボルの (255,251) 符号を短縮したものです。この符号は、32 バイト ブロックあたり最大 2 バイトのエラーを訂正できます。さらに重要なのは、訂正不可能なブロック、つまり 2 バイトを超えるエラーがあるブロックを消失としてフラグ付けすることです。消失を示すデコードされた 28 バイト ブロックは、デインターリーバによって (28,24) 外部符号の異なるブロックに分散されます。デインターリーブにより、内部コードから消去された 28 バイト ブロックは、28 個の外部コード ブロックのそれぞれで 1 つの消去されたバイトになります。外部コードは、ブロックごとに最大 4 つの消去を処理できるため、これを簡単に修正できます。

その結果、最大4000ビット、つまりディスク表面で約2.5 mmまでのエラーバーストを完全に修正できるCIRCが生まれました。このコードは非常に強力であるため、ほとんどのCD再生エラーは、修正不可能なエラーバーストではなく、レーザーがトラックをジャンプするトラッキングエラーによってほぼ確実に発生します。^[7]

DVD は同様の方式を使用しますが、ブロックがはるかに大きく、内部コード (208,192) と外部コード (182,172) で構成されています。

リード・ソロモン誤り訂正は、USENETでマルチメディアファイルに付随してよく投稿されるparchiveファイルでも使用されます。分散オンラインストレージサービスWuala (2015 年に廃止) でも、ファイルを分割するときにリード・ソロモンが使用されていました。

PDF-417、MaxiCode、Datamatrix、QR コード、Aztec コードなどのほぼすべての 2 次元バーコードは、リード・ソロモン誤り訂正を使用して、バーコードの一部が破損していても正しく読み取ることができます。バーコード スキャナーがバーコード シンボルを認識できない場合は、消去されたものとして処理されます。

リード・ソロモン符号は 1 次元バーコードではあまり一般的ではありませんが、PostBarシンボルでは使用されます。

リード・ソロモン符号の特殊な形式、具体的にはコーシーRSとヴァンダーモンドRSは、消失チャネルを介したデータ伝送の信頼性の低さを克服するために使用できます。エンコード処理では、RS( N、  K )のコードが想定され、その結果、長さNシンボルのNコードワードが生成され、それぞれKシンボルのデータが格納され、消失チャネルを介して送信されます。

相手側で受信されたK 個のコードワードの任意の組み合わせは、 N 個のコードワードすべてを再構築するのに十分です。チャネルの消失可能性が適切にモデル化され、それより低いと判断されない限り、コード レートは通常 1/2 に設定されます。結論として、Nは通常 2 Kであり、送信されたコードワードすべてを再構築するには、送信されたコードワードの少なくとも半分を受信する必要があることを意味します。

リード・ソロモン符号は、xDSLシステムやCCSDSの宇宙通信プロトコル仕様でも前方誤り訂正の形式として使用されています。

リード・ソロモン符号の重要な応用例の一つは、ボイジャー計画によって送信されたデジタル画像を符号化することであった。

ボイジャーは、畳み込み符号と連結されたリード・ソロモン符号を導入しました。これは、それ以来、深宇宙や衛星（直接デジタル放送など）通信で非常に広く普及した手法です。

Viterbi デコーダは、短いバーストでエラーを生成する傾向があります。これらのバースト エラーを修正するには、短い、または簡略化されたリード ソロモン コードを使用するのが最適です。

連結リード・ソロモン/ビタビ復号畳み込み符号化の最新バージョンは、マーズ・パスファインダー、ガリレオ、火星探査ローバー、カッシーニのミッションで使用されており、最終的な限界であるシャノン容量の約1～1.5 dB以内で動作します。

これらの連結コードは現在、より強力なターボ コードに置き換えられています。

リード・ソロモン符号は、実際には符号のファミリーであり、各符号は 3 つのパラメータ、すなわちアルファベットサイズ、ブロック長、メッセージ長によって特徴付けられます。アルファベット記号の集合はの順序の有限体として解釈されるため、素数べき乗でなければなりません。リード・ソロモン符号の最も有用なパラメータ化では、ブロック長は通常メッセージ長の定数倍、つまりレートが定数であり、さらにブロック長はアルファベット サイズと等しいか、それより 1 小さいか、または です。^{[引用が必要]}${\displaystyle q}$ ${\displaystyle n}$ ${\displaystyle k}$${\displaystyle k<n\leq q}$ ${\displaystyle F}$${\displaystyle q}$${\displaystyle q}$ ${\displaystyle R={\frac {k}{n}}}$${\displaystyle n=q}$${\displaystyle n=q-1}$

リード・ソロモン符号にはさまざまなエンコード手順があり、したがって、すべてのコードワードのセットを記述する方法も異なります。Reed & Solomon (1960) のオリジナルの見解では、リード・ソロモン符号のすべてのコードワードは、 未満の次数の多項式の関数値のシーケンスです。リード・ソロモン符号のコードワードを取得するために、メッセージシンボル (それぞれ q サイズのアルファベット内) は、元を持つ有限体上のk未満の次数の多項式の係数として扱われます。次に、多項式p は体Fのn ≤ q の異なる点で評価され、値のシーケンスが対応するコードワードです。評価点のセットの一般的な選択肢には、{0, 1, 2, ..., n − 1}、{0, 1, α , α ² , ..., α ^{n −2} }、またはn < qの場合、{1, α , α ² , ..., α ^{n −1} }, ... が含まれます。ここで、αはFの原始要素です。 ${\displaystyle k}$${\displaystyle p}$${\displaystyle F}$${\displaystyle q}$${\displaystyle a_{1},\dots ,a_{n}}$

正式には、リード・ソロモン符号のコードワード 集合は次のように定義されます。より小さい次数の任意の2 つの異なる多項式は最大で 点で一致する ため、リード・ソロモン符号の任意の 2 つのコードワードは少なくとも の位置で一致しないことを意味します。 さらに、点で一致するが等しくない 2 つの多項式があるため、リード・ソロモン符号の距離はちょうど です。 この場合、相対距離は で、 はレートです。 相対距離とレートのこのトレードオフは漸近的に最適です。シングルトン境界により、すべてのコードが を満たすためです。 この最適なトレードオフを実現するコードであるリード・ソロモン符号は、最大距離分離可能コードのクラスに属します。 ${\displaystyle \mathbf {C} }$$${\displaystyle \mathbf {C} ={\Bigl \{}\;{\bigl (}p(a_{1}),p(a_{2}),\dots ,p(a_{n}){\bigr )}\;{\Big |}\;p{\text{ is a polynomial over }}F{\text{ of degree }}<k\;{\Bigr \}}\,.}$$${\displaystyle k}$${\displaystyle k-1}$${\displaystyle n-(k-1)=n-k+1}$${\displaystyle k-1}$${\displaystyle d=n-k+1}$${\displaystyle \delta =d/n=1-k/n+1/n=1-R+1/n\sim 1-R}$${\displaystyle R=k/n}$${\displaystyle \delta +R\leq 1+1/n}$

k未満の異なる多項式の数と異なるメッセージの数は両方とも に等しく、したがってすべてのメッセージをそのような多項式に一意にマッピングできますが、このエンコードにはさまざまな方法があります。Reed & Solomon (1960) の元の構成では、メッセージx を多項式pの係数として解釈しますが、後続の構成では、メッセージを最初のkポイントにおける多項式の値として解釈し、これらの値をk未満の多項式で補間することによって多項式p を取得します。後者のエンコード手順は、効率が若干劣りますが、体系的なコードを生成できるという利点があります。つまり、元のメッセージは常にコードワードのサブシーケンスとして含まれます。 ${\displaystyle q^{k}}$${\displaystyle a_{1},\dots ,a_{k}}$

Reed & Solomon (1960) のオリジナルの構成では、メッセージはの 多項式にマッピングされます。 のコードワードは、体のさまざまな点で評価することによって得られます。したがって、リード・ソロモン符号の古典的な符号化関数は次のように定義されます。 この関数は線形マッピングです。つまり、の要素を持つ次の-行列に対して を満たします。 ${\displaystyle m=(m_{0},\dots ,m_{k-1})\in F^{k}}$${\displaystyle p_{m}}$$${\displaystyle p_{m}(a)=\sum _{i=0}^{k-1}m_{i}a^{i}\,.}$$${\displaystyle m}$${\displaystyle p_{m}}$${\displaystyle n}$${\displaystyle a_{0},\dots ,a_{n-1}}$${\displaystyle F}$${\displaystyle C:F^{k}\to F^{n}}$$${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}}$$${\displaystyle C}$${\displaystyle C(m)=Am}$${\displaystyle n\times k}$${\displaystyle A}$${\displaystyle F}$$${\displaystyle C(m)=Am={\begin{bmatrix}1&a_{0}&a_{0}^{2}&\dots &a_{0}^{k-1}\\1&a_{1}&a_{1}^{2}&\dots &a_{1}^{k-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&a_{n-1}&a_{n-1}^{2}&\dots &a_{n-1}^{k-1}\end{bmatrix}}{\begin{bmatrix}m_{0}\\m_{1}\\\vdots \\m_{k-1}\end{bmatrix}}}$$

この行列は上のヴァンデルモンド行列です。言い換えると、リード・ソロモン符号は線形符号であり、古典的な符号化手順では、その生成行列は です。 ${\displaystyle F}$${\displaystyle A}$

体系的なリード・ソロモン符号を生成する代替の符号化手順があります。 1 つの方法では、ラグランジュ補間を使用して、となる多項式を計算します。その後、は他の点 で評価されます。 ${\displaystyle p_{m}}$$${\displaystyle p_{m}(a_{i})=m_{i}{\text{ for all }}i\in \{0,\dots ,k-1\}.}$$${\displaystyle p_{m}}$${\displaystyle a_{k},\dots ,a_{n-1}}$

$${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}}$$

この関数は線形マッピングです。対応する体系的エンコーディング行列 G を生成するには、ヴァンデルモンド行列 A に A の左正方部分行列の逆行列を掛けます。 ${\displaystyle C}$

$${\displaystyle G=(A{\text{'s left square submatrix}})^{-1}\cdot A={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$$

${\displaystyle C(m)=Gm}$からの要素を持つ次の-行列について: ${\displaystyle n\times k}$${\displaystyle G}$${\displaystyle F}$$${\displaystyle C(m)=Gm={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}{\begin{bmatrix}m_{0}\\m_{1}\\\vdots \\m_{k-1}\end{bmatrix}}}$$

離散フーリエ変換は、本質的にはエンコード手順と同じです。つまり、生成多項式を使用して、評価ポイントのセットを上記のようにメッセージ値にマッピングします。 ${\displaystyle p_{m}}$$${\displaystyle C(m)={\begin{bmatrix}p_{m}(a_{0})\\p_{m}(a_{1})\\\cdots \\p_{m}(a_{n-1})\end{bmatrix}}}$$

逆フーリエ変換は、エラーのないn < q 個のメッセージ値のセットをk個の係数のエンコード多項式に戻すために使用できますが、これが機能するためには、メッセージをエンコードするために使用される評価ポイントのセットがαの増加累乗のセットでなければならないという制約があります。 $${\displaystyle a_{i}=\alpha ^{i}}$$ $${\displaystyle a_{0},\dots ,a_{n-1}=\{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}}$$

ただし、ラグランジュ補間は、評価ポイントのセットに対する制約や、エラーのないメッセージ値のセットの要件なしに同じ変換を実行し、体系的なエンコードや、Gao デコーダーのステップの 1 つで使用されます。

この見方では、メッセージは多項式 の係数として解釈されます。送信者は、次数 の関連する多項式 を計算し、多項式を送信します。多項式は、次数 のメッセージ多項式と、送信者と受信者の両方に知られている次数 の生成多項式を乗算することによって構築されます。生成多項式は、根がガロア体原始の連続した累乗である多項式として定義されます。${\displaystyle p(x)}$${\displaystyle s(x)}$${\displaystyle n-1}$${\displaystyle n\leq q-1}$${\displaystyle s(x)}$${\displaystyle s(x)}$${\displaystyle p(x)}$${\displaystyle k-1}$ ${\displaystyle g(x)}$${\displaystyle n-k}$${\displaystyle g(x)}$${\displaystyle \alpha }$ $${\displaystyle g(x)=\left(x-\alpha ^{i}\right)\left(x-\alpha ^{i+1}\right)\cdots \left(x-\alpha ^{i+n-k-1}\right)=g_{0}+g_{1}x+\cdots +g_{n-k-1}x^{n-k-1}+x^{n-k}}$$

「狭義のコード」の場合、. ${\displaystyle i=1}$

$${\displaystyle \mathbf {C} =\left\{\left(s_{1},s_{2},\dots ,s_{n}\right)\;{\Big |}\;s(a)=\sum _{i=1}^{n}s_{i}a^{i}{\text{ is a polynomial that has at least the roots }}\alpha ^{1},\alpha ^{2},\dots ,\alpha ^{n-k}\right\}.}$$

リード・ソロモン符号の BCH ビューの符号化手順は、各コードワードにプレフィックスとしてメッセージが含まれ、サフィックスとしてエラー訂正シンボルが単純に付加される、体系的な符号化手順を生成するように変更できます。ここで、 を送信する代わりに、エンコーダは、の最大単項式の係数が の対応する係数に等しく、 の低次の係数が で割り切れるように正確に選択されるように、送信される多項式を構築します。この場合、 の係数はの係数の部分列になります。全体的に体系的なコードを取得するには、メッセージをその係数のシーケンスとして解釈することによって、 メッセージ多項式を構築します。${\displaystyle s(x)=p(x)g(x)}$${\displaystyle s(x)}$${\displaystyle k}$${\displaystyle p(x)}$${\displaystyle s(x)}$${\displaystyle s(x)}$${\displaystyle g(x)}$${\displaystyle p(x)}$${\displaystyle s(x)}$${\displaystyle p(x)}$

正式には、チェック記号のためのスペースを確保するために を掛け、その積を で割って余りを求め、その余りを減算して補正することで構築されます。チェック記号は、余りを計算することで作成されます。 ${\displaystyle p(x)}$${\displaystyle x^{t}}$${\displaystyle t=n-k}$${\displaystyle g(x)}$${\displaystyle t}$${\displaystyle s_{r}(x)}$$${\displaystyle s_{r}(x)=p(x)\cdot x^{t}\ {\bmod {\ }}g(x).}$$

剰余の次数は最大 ですが、多項式内のの係数はゼロです。したがって、コードワードの次の定義では、最初の係数が の係数と同じであるという特性があります。 ${\displaystyle t-1}$${\displaystyle x^{t-1},x^{t-2},\dots ,x^{1},x^{0}}$${\displaystyle p(x)\cdot x^{t}}$${\displaystyle s(x)}$${\displaystyle k}$${\displaystyle p(x)}$$${\displaystyle s(x)=p(x)\cdot x^{t}-s_{r}(x)\,.}$$

その結果、コードワードは確かに の要素であり、つまり生成多項式 で割り切れる: ^[10]${\displaystyle s(x)}$${\displaystyle \mathbf {C} }$${\displaystyle g(x)}$ $${\displaystyle s(x)\equiv p(x)\cdot x^{t}-s_{r}(x)\equiv s_{r}(x)-s_{r}(x)\equiv 0\mod g(x)\,.}$$

この関数は線形マッピングです。対応する体系的なエンコード行列 G を生成するには、G の左の正方サブ行列を単位行列に設定し、各行をエンコードします。 ${\displaystyle s}$

$${\displaystyle G={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}}$$ 先頭のゼロを無視すると、最後の行 = になります。 ${\displaystyle g(x)}$

${\displaystyle C(m)=Gm}$からの要素を持つ次の-行列について: ${\displaystyle n\times k}$${\displaystyle G}$${\displaystyle F}$$${\displaystyle C(m)=Gm={\begin{bmatrix}1&0&0&\dots &0&g_{1,k+1}&\dots &g_{1,n}\\0&1&0&\dots &0&g_{2,k+1}&\dots &g_{2,n}\\0&0&1&\dots &0&g_{3,k+1}&\dots &g_{3,n}\\\vdots &\vdots &\vdots &&\vdots &\vdots &&\vdots \\0&\dots &0&\dots &1&g_{k,k+1}&\dots &g_{k,n}\end{bmatrix}}{\begin{bmatrix}m_{0}\\m_{1}\\\vdots \\m_{k-1}\end{bmatrix}}}$$

リード・ソロモン符号は、[ n , k , n − k + 1] 符号です。言い換えると、長さn ( F上)、次元k、ハミング距離が最小の線形ブロック符号です。リード・ソロモン符号は、最小距離がサイズ ( n、  k )の線形符号で可能な最大値になるという意味で最適です。これはシングルトン境界として知られています。このような符号は、最大距離分離型 (MDS) 符号とも呼ばれます。 ${\textstyle d_{\min }=n-k+1.}$

リード・ソロモン符号の誤り訂正能力は、その最小距離、またはブロック内の冗長性の尺度である によって決まります。誤りシンボルの位置が事前にわからない場合、リード・ソロモン符号は最大 個の誤りシンボルを訂正できます。つまり、ブロックに追加された冗長シンボルの半分の数の誤りを訂正できます。誤りの位置が事前にわかっている場合もあります (たとえば、復調器の信号対雑音比の「サイド情報」)。これらは消失 と呼ばれます。リード・ソロモン符号 (他のMDS 符号と同様) は、誤りの 2 倍の消失を訂正でき、 2 E + S ≤ n − kの関係が満たされる限り、誤りと消失の任意の組み合わせを訂正できます。ここで、は誤りの数、 はブロック内の消失の数です。 ${\displaystyle n-k}$${\displaystyle (n-k)/2}$ ${\displaystyle E}$${\displaystyle S}$

理論的な誤差境界は、 FSKのAWGNチャネルについては次の式で表すことができます: ^[11]他 の変調方式については次の式で表すことができます: ここで、、、は符号化されていないAWGNの場合のシンボル誤り率であり、は変調次数です。 $${\displaystyle P_{b}\approx {\frac {2^{m-1}}{2^{m}-1}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }}$$$${\displaystyle P_{b}\approx {\frac {1}{m}}{\frac {1}{n}}\sum _{\ell =t+1}^{n}\ell {n \choose \ell }P_{s}^{\ell }(1-P_{s})^{n-\ell }}$$${\textstyle t={\frac {1}{2}}(d_{\min }-1)}$${\displaystyle P_{s}=1-(1-s)^{h}}$${\displaystyle h={\frac {m}{\log _{2}M}}}$${\displaystyle s}$${\displaystyle M}$

リード・ソロモン符号の実際の用途では、 個の元を持つ有限体を使用するのが一般的です。この場合、各シンボルはビット値として表すことができます。送信者はデータ ポイントをエンコードされたブロックとして送信し、エンコードされたブロック内のシンボル数は です。したがって、8 ビット シンボルで動作するリード・ソロモン符号では、ブロックあたり 個のシンボルがあります。(バイト指向のコンピュータ システムが普及しているため、これは非常に一般的な値です。) ブロック内のデータシンボルの数、ただし は設計パラメータです。一般的に使用される符号は、個のシンボル ブロックに 8 ビットのデータ シンボルと 32 個の 8 ビット パリティ シンボルをエンコードします。これは 符号として表され、ブロックあたり最大 16 個のシンボル エラーを訂正できます。 ${\displaystyle F}$${\displaystyle 2^{m}}$${\displaystyle m}$${\displaystyle n=2^{m}-1}$${\displaystyle n=2^{8}-1=255}$${\displaystyle k}$${\displaystyle k<n}$${\displaystyle k=223}$${\displaystyle n=255}$${\displaystyle (n,k)=(255,223)}$

上で説明したリード・ソロモン符号の特性により、エラーがバースト的に発生するアプリケーションに特に適しています。これは、シンボル内の何ビットにエラーがあるかはコードにとって重要ではないためです。シンボル内の複数のビットが破損している場合は、1 つのエラーとしてカウントされます。逆に、データ ストリームがエラー バーストやドロップアウトではなく、ランダムな 1 ビット エラーによって特徴付けられる場合、リード・ソロモン符号は通常、バイナリ コードと比較して適切な選択ではありません。

リード・ソロモン符号は、畳み込み符号と同様に透過的な符号です。つまり、チャネル シンボルが途中で反転されていても、デコーダは動作します。その結果、元のデータが反転されます。ただし、リード・ソロモン符号は、符号が短縮されると透過性が失われます (このセクションの最後にある「備考」を参照)。短縮された符号の「欠落」ビットは、データが補完されているかどうかに応じて、0 または 1 で埋める必要があります (言い換えると、シンボルが反転されている場合は、0 埋めを 1 埋めに反転する必要があります)。このため、リード・ソロモン復号化の前に、データの意味 (つまり、真か補完か) を解決することが必須です。

リード・ソロモン符号が巡回符号であるかどうかは、構成の微妙な細部に依存します。リードとソロモンの元の見解では、符号語は多項式の値であり、符号が巡回するように評価点のシーケンスを選択できます。特に、 が体 の原始根である場合、定義により の非ゼロ元はすべてに対して の形を取ります(ただし ) 。上の各多項式は、符号語 を生成します。関数も同じ次数の多項式であるため、この関数は符号語 を生成します。が成り立つため、この符号語はから導出された元の符号語の巡回左シフトです。したがって、原始根のべき乗のシーケンスを評価点として選択すると、元の見解のリード・ソロモン符号は巡回 になります。BCH の見解のリード・ソロモン符号は常に巡回です。これは、BCH 符号が巡回 であるためです。 ${\displaystyle \alpha }$${\displaystyle F}$${\displaystyle F}$${\displaystyle \alpha ^{i}}$${\displaystyle i\in \{1,\dots ,q-1\}}$${\displaystyle q=|F|}$${\displaystyle p}$${\displaystyle F}$${\displaystyle (p(\alpha ^{1}),\dots ,p(\alpha ^{q-1}))}$${\displaystyle a\mapsto p(\alpha a)}$${\displaystyle (p(\alpha ^{2}),\dots ,p(\alpha ^{q}))}$${\displaystyle \alpha ^{q}=\alpha ^{1}}$${\displaystyle p}$

設計者は、リード・ソロモン コード ブロックの「自然な」サイズを使用する必要はありません。「短縮」と呼ばれる手法により、大きなコードから任意のサイズの小さなコードを作成できます。たとえば、広く使用されている (255,223) コードは、ソース ブロックの未使用部分に 95 個のバイナリ ゼロを埋め込んで送信しないことで、(160,128) コードに変換できます。デコーダーでは、ブロックの同じ部分にバイナリ ゼロがローカルにロードされます。

QR コード、バージョン 3 (29×29) はインターリーブ ブロックを使用します。メッセージは 26 データ バイトで構成され、2 つのリード ソロモン コード ブロックを使用してエンコードされます。各ブロックは (255,233) リード ソロモン コードで、(35,13) コードに短縮されています。

デルサルト・ゲータルス・ザイデル^[12]定理は短縮されたリード・ソロモン符号の応用例を示している。短縮と並行して、パンクチャリングと呼ばれる技術により、符号化されたパリティシンボルの一部を省略することができる。

このセクションで説明するデコーダーは、コードワードを係数のシーケンスとして BCH ビューで表します。エンコーダーとデコーダーの両方に既知の固定生成多項式を使用します。

ダニエル・ゴレンスタインとニール・ツィラーはデコーダーを開発し、1960年1月にツィラーがMITリンカーン研究所の報告書で説明し、その後1961年6月に論文で発表した。 ^[13]ゴレンスタイン・ツィラーデコーダーとBCHコードに関する関連研究は、W・ウェスリー・ピーターソン著『 Error Correcting Codes』（1961年）で説明されている。^[14]

送信されたメッセージは、多項式の係数としてみなされる。 ${\displaystyle (c_{0},\ldots ,c_{i},\ldots ,c_{n-1})}$$${\displaystyle s(x)=\sum _{i=0}^{n-1}c_{i}x^{i}.}$$

リード・ソロモン符号化手順の結果として、s ( x )はαが原始元で ある生成多項式で割り切れる 。$${\displaystyle g(x)=\prod _{j=1}^{n-k}(x-\alpha ^{j}),}$$

s ( x ) は生成元g ( x )の倍数なので、その根をすべて「継承」することになります。 したがって、 $${\displaystyle s(x){\bmod {(}}x-\alpha ^{j})=g(x){\bmod {(}}x-\alpha ^{j})=0.}$$$${\displaystyle s(\alpha ^{j})=0,\ j=1,2,\ldots ,n-k.}$$

送信された多項式は、エラー多項式によって転送中に破損し、 受信多項式を生成します。 $${\displaystyle e(x)=\sum _{i=0}^{n-1}e_{i}x^{i}}$$$${\displaystyle r(x)=s(x)+e(x).}$$

係数e _{i は}、 xのそのべき乗に誤差がない場合にはゼロとなり、誤差がある場合にはゼロ以外の値となる。xの異なるべき乗i _kにν個の誤差がある場合、 $${\displaystyle e(x)=\sum _{k=1}^{\nu }e_{i_{k}}x^{i_{k}}.}$$

デコーダーの目的は、エラーの数 ( ν )、エラーの位置 ( i _k )、およびそれらの位置でのエラー値 ( e _{i k} ) を見つけることです。それらからe ( x ) を計算し、r ( x ) から減算すると、最初に送信されたメッセージs ( x ) が得られます。

デコーダは、点 で受信した多項式を評価することから始めます。その評価の結果を「シンドローム」S _jと呼びます。これらは次のように定義されます 。前のセクションで示したように、 は に根を持つため、 注意してください。${\displaystyle \alpha ^{1}\dots \alpha ^{n-k}}$$${\displaystyle {\begin{aligned}S_{j}&=r(\alpha ^{j})=s(\alpha ^{j})+e(\alpha ^{j})=0+e(\alpha ^{j})\\&=e(\alpha ^{j})\\&=\sum _{k=1}^{\nu }e_{i_{k}}{(\alpha ^{j})}^{i_{k}},\quad j=1,2,\ldots ,n-k.\end{aligned}}}$$${\displaystyle s(\alpha ^{j})=0}$${\displaystyle s(x)}$${\displaystyle \alpha ^{j}}$

シンドロームを見る利点は、メッセージ多項式が欠落することです。言い換えると、シンドロームはエラーにのみ関連し、送信されるメッセージの実際の内容には影響されません。シンドロームがすべてゼロの場合、アルゴリズムはここで停止し、メッセージが送信中に破損しなかったことを報告します。

便宜上、エラー位置 X _kとエラー値 Y _kを次のように 定義する。$${\displaystyle X_{k}=\alpha ^{i_{k}},\quad Y_{k}=e_{i_{k}}.}$$

そして、シンドロームはこれらのエラーロケータとエラー値を使って次のように記述できる。 $${\displaystyle S_{j}=\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}.}$$

このシンドローム値の定義は、 以来の前のものと同等です。 ${\displaystyle {(\alpha ^{j})}^{i_{k}}=\alpha ^{j\cdot i_{k}}={(\alpha ^{i_{k}})}^{j}=X_{k}^{j}}$

シンドロームは、2 ν 個の未知数を持つn − k ≥ 2 ν方程式のシステムを与えますが、その方程式のシステムはX _kに関して非線形であり、明白な解はありません。ただし、X _kが既知である場合 (以下を参照)、シンドローム方程式は、 Y _{k の}エラー値 について簡単に解くことができる線形方程式のシステムを提供します。 $${\displaystyle {\begin{bmatrix}X_{1}^{1}&X_{2}^{1}&\cdots &X_{\nu }^{1}\\X_{1}^{2}&X_{2}^{2}&\cdots &X_{\nu }^{2}\\\vdots &\vdots &\ddots &\vdots \\X_{1}^{n-k}&X_{2}^{n-k}&\cdots &X_{\nu }^{n-k}\\\end{bmatrix}}{\begin{bmatrix}Y_{1}\\Y_{2}\\\vdots \\Y_{\nu }\end{bmatrix}}={\begin{bmatrix}S_{1}\\S_{2}\\\vdots \\S_{n-k}\end{bmatrix}},}$$

したがって、問題はX _kを見つけることです。なぜなら、左端の行列がわかっており、方程式の両辺にその逆行列を掛け合わせるとY _{kが得られるからです。}

このアルゴリズムのバリエーションでは、エラーの位置が既にわかっている場合（消失訂正符号として使用されている場合）、これで終わりです。エラーの位置（X _k）は、他の何らかの方法で既にわかっています（たとえば、FM送信では、ビットストリームが不明瞭であったり干渉によって克服されたセクションは、周波数分析から確率的に決定できます）。このシナリオでは、最大 個のエラーを訂正できます。 ${\displaystyle n-k}$

アルゴリズムの残りの部分はエラーを見つけるために使用され、これまで使用されていただけでなく までのシンドローム値が必要になります。これが、位置を知らなくても訂正できる数の 2 倍のエラー訂正シンボルを追加する必要がある理由です。 ${\displaystyle 2\nu }$${\displaystyle \nu }$

線形再帰関係があり、線形方程式のシステムが生成されます。これらの方程式を解くと、エラーの位置X _kが特定されます。

誤り位置多項式 Λ( x )を次のように 定義する。$${\displaystyle \Lambda (x)=\prod _{k=1}^{\nu }(1-xX_{k})=1+\Lambda _{1}x^{1}+\Lambda _{2}x^{2}+\cdots +\Lambda _{\nu }x^{\nu }.}$$

Λ( x )のゼロは逆数 です。これは上記の積表記法の構成からわかります。 の場合、乗算された項の 1 つがゼロ になり、多項式全体がゼロに評価されるからです。 ${\displaystyle X_{k}^{-1}}$${\displaystyle x=X_{k}^{-1}}$${\displaystyle (1-X_{k}^{-1}\cdot X_{k})=1-1=0}$$${\displaystyle \Lambda (X_{k}^{-1})=0.}$$

を となる任意の整数とします。両辺に を掛けても、やはり 0 になります。 ${\displaystyle j}$${\displaystyle 1\leq j\leq \nu }$${\displaystyle Y_{k}X_{k}^{j+\nu }}$$${\displaystyle {\begin{aligned}&Y_{k}X_{k}^{j+\nu }\Lambda (X_{k}^{-1})=0,\\&Y_{k}X_{k}^{j+\nu }(1+\Lambda _{1}X_{k}^{-1}+\Lambda _{2}X_{k}^{-2}+\cdots +\Lambda _{\nu }X_{k}^{-\nu })=0,\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu }X_{k}^{-1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu }X_{k}^{-2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j+\nu }X_{k}^{-\nu }=0,\\&Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j}=0.\end{aligned}}}$$

k = 1 からνまでを合計しても、やはりゼロになります。 $${\displaystyle \sum _{k=1}^{\nu }(Y_{k}X_{k}^{j+\nu }+\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}+\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}+\cdots +\Lambda _{\nu }Y_{k}X_{k}^{j})=0.}$$

各項をそれぞれ合計します。 $${\displaystyle \left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\left(\sum _{k=1}^{\nu }\Lambda _{1}Y_{k}X_{k}^{j+\nu -1}\right)+\left(\sum _{k=1}^{\nu }\Lambda _{2}Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\left(\sum _{k=1}^{\nu }\Lambda _{\nu }Y_{k}X_{k}^{j}\right)=0.}$$

合計の影響を受けない 定数値を抽出します。${\displaystyle \Lambda }$$${\displaystyle \left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu }\right)+\Lambda _{1}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -1}\right)+\Lambda _{2}\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j+\nu -2}\right)+\cdots +\Lambda _{\nu }\left(\sum _{k=1}^{\nu }Y_{k}X_{k}^{j}\right)=0.}$$

これらの合計は、既知のシンドローム値と等価であり、代入することができます。したがって、これは次のように簡約されます。 $${\displaystyle S_{j+\nu }+\Lambda _{1}S_{j+\nu -1}+\cdots +\Lambda _{\nu -1}S_{j+1}+\Lambda _{\nu }S_{j}=0.}$$

両辺から 引くと${\displaystyle S_{j+\nu }}$$${\displaystyle S_{j}\Lambda _{\nu }+S_{j+1}\Lambda _{\nu -1}+\cdots +S_{j+\nu -1}\Lambda _{1}=-S_{j+\nu }.}$$

j は1 からvまでの任意の整数に選択されたことを思い出してください。この同値は、そのようなすべての値に当てはまります。したがって、 1 つだけではなく、 v 個の線形方程式があります。したがって、この線形方程式系は、エラー位置多項式の 係数 Λ _iについて解くことができます。 上記は、デコーダーがエラーの数ν を知っているが、その数はまだ決定されていないことを前提としています。PGZ デコーダーはν を直接決定するのではなく、連続する値を試して検索します。デコーダーは、最初に試行νの最大値を前提とし、その値に対して線形システムを設定します。方程式を解くことができる場合 (つまり、行列式がゼロ以外)、その試行値がエラーの数です。線形システムを解くことができない場合は、試行νが 1 つ減らされ、次に小さいシステムが調べられます (Gill nd、p. 35)。 $${\displaystyle {\begin{bmatrix}S_{1}&S_{2}&\cdots &S_{\nu }\\S_{2}&S_{3}&\cdots &S_{\nu +1}\\\vdots &\vdots &\ddots &\vdots \\S_{\nu }&S_{\nu +1}&\cdots &S_{2\nu -1}\end{bmatrix}}{\begin{bmatrix}\Lambda _{\nu }\\\Lambda _{\nu -1}\\\vdots \\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-S_{\nu +1}\\-S_{\nu +2}\\\vdots \\-S_{\nu +\nu }\end{bmatrix}}.}$$

最後のステップで見つかった係数 Λ _iを使用して、エラー位置多項式を構築します。エラー位置多項式の根は、網羅的な検索によって見つけることができます。エラー ロケータX _{k は}、それらの根の逆数です。エラー位置多項式の係数の順序は逆にすることができます。その場合、その逆の多項式の根がエラー ロケータになります(逆数ではありません)。チェン検索は、このステップの効率的な実装です。 ${\displaystyle X_{k}}$${\displaystyle X_{k}^{-1}}$

エラー位置X _kがわかれば、エラー値を決定することができます。これは、上記のエラー方程式行列のY _{k を}直接解くか、 Forney アルゴリズムを使用して行うことができます。

X _kの対数底を取ってi _{k を}計算します。これは通常、事前に計算されたルックアップ テーブルを使用して行われます。 ${\displaystyle \alpha }$

最後に、i _kとe _{i k}からe ( x )が生成され、 r ( x )から減算されて、エラーが修正された 元の送信メッセージs ( x )が得られます。

RS(7,3)コードに対して、 GF (929)で定義されたα = 3、t = 4 （ PDF417バーコードで使用）のリード・ソロモンコードを考える。生成多項式は、 メッセージ多項式がp ( x ) = 3 x ² + 2 x + 1の場合、体系的なコードワードは次のようにエンコードされる。 送信エラーにより、次のように受信される可能性がある。 シンドロームは、rをαの累乗で評価することによって計算される。その結果、 次の システムが得られる。 $${\displaystyle g(x)=(x-3)(x-3^{2})(x-3^{3})(x-3^{4})=x^{4}+809x^{3}+723x^{2}+568x+522.}$$$${\displaystyle s_{r}(x)=p(x)\,x^{t}{\bmod {g}}(x)=547x^{3}+738x^{2}+442x+455,}$$ $${\displaystyle s(x)=p(x)\,x^{t}-s_{r}(x)=3x^{6}+2x^{5}+1x^{4}+382x^{3}+191x^{2}+487x+474.}$$$${\displaystyle r(x)=s(x)+e(x)=3x^{6}+2x^{5}+123x^{4}+456x^{3}+191x^{2}+487x+474.}$$$${\displaystyle S_{1}=r(3^{1})=3\cdot 3^{6}+2\cdot 3^{5}+123\cdot 3^{4}+456\cdot 3^{3}+191\cdot 3^{2}+487\cdot 3+474=732,}$$ $${\displaystyle S_{2}=r(3^{2})=637,\quad S_{3}=r(3^{3})=762,\quad S_{4}=r(3^{4})=925,}$$$${\displaystyle {\begin{bmatrix}732&637\\637&762\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}-762\\-925\end{bmatrix}}={\begin{bmatrix}167\\004\end{bmatrix}}.}$$

ガウス消去法を使用すると 、 根 x 1 = 757 = 3 −3 および x 2 = 562 = 3 −4 になり_ます。^係数を逆_にし^て、 正の指数を持つ 根 27 = 3 ³および 81 = 3 ⁴を生成することもできますが、通常は使用されません。根の対数は、エラー位置に対応します (右から左、位置 0 はコードワードの最後の項です)。 $${\displaystyle {\begin{bmatrix}001&000\\000&001\end{bmatrix}}{\begin{bmatrix}\Lambda _{2}\\\Lambda _{1}\end{bmatrix}}={\begin{bmatrix}329\\821\end{bmatrix}},}$$$${\displaystyle \Lambda (x)=329x^{2}+821x+001,}$$$${\displaystyle R(x)=001x^{2}+821x+329,}$$

エラー値を計算するには、Forney アルゴリズムを適用します。 $${\displaystyle \Omega (x)=S(x)\Lambda (x){\bmod {x}}^{4}=546x+732,}$$ $${\displaystyle \Lambda '(x)=658x+821,}$$ $${\displaystyle e_{1}=-\Omega (x_{1})/\Lambda '(x_{1})=074,}$$ $${\displaystyle e_{2}=-\Omega (x_{2})/\Lambda '(x_{2})=122.}$$

受信した多項式r ( x )を減算すると元のコードワードsが再現されます。 ${\displaystyle e_{1}x^{3}+e_{2}x^{4}=74x^{3}+122x^{4}}$

Berlekamp -Massey アルゴリズムは、エラー位置多項式を見つけるための代替反復手順です。各反復中に、想定されるエラー数eで Λ( x ) の現在のインスタンスに基づいて不一致を計算し、 再計算された Δ がゼロになるように Λ( x ) とe を調整します。記事Berlekamp-Massey アルゴリズムに手順の詳細な説明があります。次の例では、C ( x ) を使用して Λ( x ) を表します。 $${\displaystyle \Delta =S_{i}+\Lambda _{1}\ S_{i-1}+\cdots +\Lambda _{e}\ S_{i-e}}$$

上記の Peterson Gorenstein Zierler の例と同じデータを使用します。

Cの最終値はエラーロケータ多項式Λ( x )です。

エラー位置多項式とエラー値多項式の両方を計算する別の反復法は、杉山の拡張ユークリッド互除法の適応に基づいています。

t個のシンドロームとe個のエラーに対してS ( x )、Λ( x )、Ω( x )を定義します。 $${\displaystyle {\begin{aligned}S(x)&=S_{t}x^{t-1}+S_{t-1}x^{t-2}+\cdots +S_{2}x+S_{1}\\[1ex]\Lambda (x)&=\Lambda _{e}x^{e}+\Lambda _{e-1}x^{e-1}+\cdots +\Lambda _{1}x+1\\[1ex]\Omega (x)&=\Omega _{e}x^{e}+\Omega _{e-1}x^{e-1}+\cdots +\Omega _{1}x+\Omega _{0}\end{aligned}}}$$

重要な方程式は次のとおりです。 $${\displaystyle \Lambda (x)S(x)=Q(x)x^{t}+\Omega (x)}$$

t = 6 およびe = 3の場合: $${\displaystyle {\begin{bmatrix}\Lambda _{3}S_{6}&x^{8}\\\Lambda _{2}S_{6}+\Lambda _{3}S_{5}&x^{7}\\\Lambda _{1}S_{6}+\Lambda _{2}S_{5}+\Lambda _{3}S_{4}&x^{6}\\S_{6}+\Lambda _{1}S_{5}+\Lambda _{2}S_{4}+\Lambda _{3}S_{3}&x^{5}\\S_{5}+\Lambda _{1}S_{4}+\Lambda _{2}S_{3}+\Lambda _{3}S_{2}&x^{4}\\S_{4}+\Lambda _{1}S_{3}+\Lambda _{2}S_{2}+\Lambda _{3}S_{1}&x^{3}\\S_{3}+\Lambda _{1}S_{2}+\Lambda _{2}S_{1}&x^{2}\\S_{2}+\Lambda _{1}S_{1}&x\\S_{1}\end{bmatrix}}={\begin{bmatrix}Q_{2}x^{8}\\Q_{1}x^{7}\\Q_{0}x^{6}\\0\\0\\0\\\Omega _{2}x^{2}\\\Omega _{1}x\\\Omega _{0}\end{bmatrix}}}$$

Λ とシンドロームの関係により、中間の項はゼロになります。

拡張ユークリッドの互除法は、次のような形式の多項式の列を見つけることができる。

ここで、 Rの次数はiが増加するにつれて減少する。Rの次数i ( x ) < t /2になる_と、

B ( x ) とQ ( x ) は保存する必要がないため、アルゴリズムは次のようになります。

R −1  := x t
 R 0   := S ( x )
 A −1  := 0
 A 0   := 1
 i  := 0
ただし、R iの次数≥ t /2
   i  := i + 1
   Q  := R i -2 / R i -1 
  R i  := R i -2 - Q  R i -1 
  A i  := A i -2 - Q  A i -1

Λ( x )の低次の項を1にするには、Λ( x )とΩ( x )をA _i (0)で割ります。

A _{i (0)はA i}の定数（低次）項である。

上記の Peterson–Gorenstein–Zierler の例と同じデータを使用します。

離散フーリエ変換は復号に使用できる。^[15]シンドローム名との衝突を避けるため、符号化されたコードワードをc(x) = s(x)とする。r ( x )とe ( x )は上記と同じである。C ( x )、E ( x )、R ( x )をc ( x )、e ( x )、r ( x )の離散フーリエ変換として定義する。r ( x ) = c ( x ) + e ( x )であり、離散フーリエ変換は線形演算子であるため、R ( x ) = C ( x ) + E ( x )である。

離散フーリエ変換を使用してr ( x ) をR ( x ) に変換します。離散フーリエ変換の計算はシンドロームの計算と同じなので、R ( x ) とE ( x )の係数はシンドロームと同じです。 $${\displaystyle R_{j}=E_{j}=S_{j}=r(\alpha ^{j})\qquad {\text{for }}1\leq j\leq t}$$

から をシンドロームとして使用し(これらは同じです)、上記のいずれかのデコーダーのメソッドを使用してエラー ロケータ多項式を生成します。 ${\displaystyle R_{1}}$${\displaystyle R_{t}}$

v = エラー数とします。既知の係数、エラー位置多項式、および次の式 を使用してE ( x ) を生成します。${\displaystyle E_{1}}$${\displaystyle E_{t}}$$${\displaystyle {\begin{aligned}E_{0}&=-{\frac {1}{\Lambda _{v}}}(E_{v}+\Lambda _{1}E_{v-1}+\cdots +\Lambda _{v-1}E_{1})\\E_{j}&=-(\Lambda _{1}E_{j-1}+\Lambda _{2}E_{j-2}+\cdots +\Lambda _{v}E_{j-v})&{\text{for }}t<j<n\end{aligned}}}$$

次にC ( x )= R ( x ) −E ( x )を計算し、 C ( x )の逆変換（多項式補間）を行ってc ( x )を生成します。

シングルトン境界は、サイズ ( n、k )の線形ブロック符号の最小距離d の上限がn − k + 1であることを示します。距離d は、通常、誤り訂正能力を⌊( d −1) / 2⌋に制限するものと理解されていました。リード・ソロモン符号は、この境界を等式で達成し、最大⌊( n − k ) / 2⌋の誤りを訂正できます。ただし、この誤り訂正境界は正確ではありません。

1999年、 MITのマドゥ・スーダンとベンカテサン・グルスワミは「リード・ソロモン符号と代数幾何学符号の改良復号法」を発表し、符号の最小距離の半分を超える誤りの訂正を可能にするアルゴリズムを紹介した。^[16]これはリード・ソロモン符号に適用され、より一般的には代数幾何学符号にも適用される。このアルゴリズムはコードワードのリストを生成し（リスト復号アルゴリズム）、 とその拡張上の多項式の補間と因数分解に基づいている。 ${\displaystyle GF(2^{m})}$

2023年に、3つの興味深い研究^{[17] [18] [19]}に基づいて、符号理論家は、ランダムな評価ポイントで定義されたリード・ソロモン符号が、線形サイズのアルファベットに対してリストデコード能力（最大n − kエラー）を高い確率で達成できることを示しました。ただし、この結果はアルゴリズム的というよりは組み合わせ的です。

上で説明した代数的復号法はハード決定法であり、すべてのシンボルについてその値についてハード決定が行われることを意味します。たとえば、復号器は各シンボルに、チャネル復調器のシンボルの正しさに対する信頼度に対応する追加の値を関連付けることができます。反復ソフト決定ビリーフプロパゲーション復号法を使用して理論限界に近いエラー訂正性能を実現するLDPCおよびターボ符号の出現により、従来の代数符号にソフト決定復号を適用することへの関心が高まっています。2003 年、Ralf Koetter とAlexander Vardy は、Sudan と Guruswami の研究に基づいた、リード・ソロモン符号の多項式時間ソフト決定代数リスト復号アルゴリズムを発表しました。^[20] 2016 年、Steven J. Franke と Joseph H. Taylor は新しいソフト決定復号器を発表しました。^[21]

ここでは、エンコーダー用の 簡単なMATLAB実装を紹介します。

次にデコード部分です。

このセクションで説明するデコーダーは、コードワードを多項式値のシーケンスとして捉えるリード・ソロモンのオリジナル ビューを使用します。この多項式は、エンコードされるメッセージに基づいています。エンコーダーとデコーダーでは同じ固定値セットが使用され、デコーダーは受信したメッセージからエンコード多項式 (およびオプションでエラー検出多項式) を復元します。

Reed & Solomon (1960) は、最も一般的なメッセージ多項式を見つけることでエラーを訂正する理論的なデコーダについて説明しました。デコーダは、値のセットから までと、コードワードの値のシーケンスを生成するために使用されたエンコード方法のみを認識します。元のメッセージ、多項式、およびエラーは不明です。デコード手順では、一度に k 個取られた n 個のコードワード値のさまざまなサブセットに対してラグランジュ補間などの方法を使用して、受信コードワードのエラーを合理的に除去するのに十分な数の一致する多項式が生成されるまで、潜在的な多項式を繰り返し生成できます。多項式が決定されると、対応するコードワード値を再計算することで、コードワードのエラーを訂正できます。残念ながら、最も単純な場合を除いて、サブセットが多すぎるため、アルゴリズムは実用的ではありません。サブセットの数は二項係数、であり、サブセットの数は控えめなコードでも実行不可能です。3 つのエラーを修正できるコード の場合、単純な理論上のデコーダーは 3,590 億個のサブセットを検査します。${\displaystyle a_{1}}$${\displaystyle a_{n}}$${\textstyle {\binom {n}{k}}={n! \over (n-k)!k!}}$${\displaystyle (255,249)}$

1986 年に、 Berlekamp-Welch アルゴリズムと呼ばれるデコーダが開発されました。このデコーダは、元のメッセージ多項式と、エラーに対応する入力値にゼロを生成するエラー「ロケータ」多項式を復元できるデコーダで、時間の計算量は です( はメッセージ内の値の数)。復元された多項式は、元のメッセージを復元 (必要に応じて再計算) するために使用されます。 ${\displaystyle O(n^{3})}$${\displaystyle n}$

RS(7,3)、GF(929)、評価点集合a _i = i − 1 を用いると、

メッセージ多項式が

コードワードは

送信エラーにより、代わりにこれが受信される可能性があります。

重要な方程式は次のとおりです。

$${\displaystyle b_{i}E(a_{i})-Q(a_{i})=0}$$

最大エラー数をe = 2 と仮定します。重要な方程式は次のようになります。

$${\displaystyle b_{i}(e_{0}+e_{1}a_{i})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+q_{3}a_{i}^{3}+q_{4}a_{i}^{4})=-b_{i}a_{i}^{2}}$$

$${\displaystyle {\begin{bmatrix}001&000&928&000&000&000&000\\006&006&928&928&928&928&928\\123&246&928&927&925&921&913\\456&439&928&926&920&902&848\\057&228&928&925&913&865&673\\086&430&928&924&904&804&304\\121&726&928&923&893&713&562\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q_{0}\\q_{1}\\q_{2}\\q_{3}\\q_{4}\end{bmatrix}}={\begin{bmatrix}000\\923\\437\\541\\017\\637\\289\end{bmatrix}}}$$

ガウス消去法を使用する:

$${\displaystyle {\begin{bmatrix}001&000&000&000&000&000&000\\000&001&000&000&000&000&000\\000&000&001&000&000&000&000\\000&000&000&001&000&000&000\\000&000&000&000&001&000&000\\000&000&000&000&000&001&000\\000&000&000&000&000&000&001\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q_{0}\\q_{1}\\q_{2}\\q_{3}\\q_{4}\end{bmatrix}}={\begin{bmatrix}006\\924\\006\\007\\009\\916\\003\end{bmatrix}}}$$

E(x) = 0 : {2, 3}のP(x)を再計算してbを修正すると、修正されたコードワードが得られます。

2002年に、Shuhong Gaoによって拡張ユークリッドアルゴリズムに基づいた改良されたデコーダが開発されました。^[6]

上記の Berlekamp Welch の例と同じデータを使用します。

• ${\displaystyle R_{-1}=\prod _{i=1}^{n}(x-a_{i})}$
• ${\displaystyle R_{0}=}$i = 1 からnまでのラグランジュ補間${\displaystyle \{a_{i},b(a_{i})\}}$
• ${\displaystyle A_{-1}=0}$
• ${\displaystyle A_{0}=1}$

Q ( x )とE ( x )をE ( x )の最も重要な係数708 で割ります。(オプション)

P ( x ) ( E ( x ) = 0 : {2, 3} )を再計算してbを修正すると、修正されたコードワードが得られます。

• BCH コード
• ベルレカンプ・マッシーアルゴリズム
• ベルレカンプ・ウェルチアルゴリズム
• チエン検索
• 循環コード
• 折り畳みリード・ソロモン符号
• 前方誤り訂正

• Gill, John (nd)、EE387 ノート #7、配布資料 #28 (PDF) 、スタンフォード大学、 2014 年 6 月 30 日のオリジナル(PDF)からアーカイブ、2010 年4 月 21 日取得
• Hong, Jonathan; Vetterli, Martin (1995 年 8 月)、「BCH デコードのためのシンプルなアルゴリズム」(PDF)、IEEE Transactions on Communications、43 (8): 2324–33、doi :10.1109/26.403765
• リン・シュウ、コステロ・ジュニア、ダニエル・J.（1983）、誤り制御符号化：基礎と応用、プレンティス・ホール、ISBN 978-0-13-283796-5
• Massey, JL (1969)、「シフトレジスタ合成と BCH デコード」(PDF)、IEEE Transactions on Information Theory、IT-15 (1): 122–127、doi :10.1109/tit.1969.1054260、S2CID  9003708
• ピーターソン、ウェスリー W. (1960)、「ボーズ-チャウドゥリ符号の符号化と誤り訂正手順」、IRE 情報理論取引、IT-6 (4): 459–470、doi :10.1109/TIT.1960.1057586
• リード、アーヴィング S. ;ソロモン、ギュスターヴ(1960)、「特定の有限体上の多項式コード」(PDF)、産業応用数学協会誌、8 (2): 300–304、doi :10.1137/0108018
• ウェルチ、LR (1997)、リード・ソロモン符号の本来の見方(PDF)、講義ノート
• Berlekamp, Elwyn R. (1967)、「非バイナリ BCH デコード」、国際情報理論シンポジウム、サンレモ、イタリア、OCLC  45195002、AD0669824
• Berlekamp、Elwyn R. (1984) [1968]、代数符号化理論(改訂版)、カリフォルニア州ラグナ ヒルズ: Aegean Park Press、ISBN 978-0-89412-063-3
• Cipra、Barry Arthur (1993)、「The Ubiquitous Reed–Solomon Codes」、SIAM ニュース、26 (1)
• Forney, Jr., G. (1965 年 10 月)、「BCH コードのデコードについて」、IEEE Transactions on Information Theory、11 (4): 549–557、doi :10.1109/TIT.1965.1053825
• Koetter, Ralf (2005)、リード・ソロモン符号、MIT 講義ノート 6.451 (ビデオ)、2013-03-13 にオリジナルからアーカイブ
• MacWilliams, FJ; Sloane, NJA (1977)、誤り訂正符号の理論、North-Holland、ISBN 978-0-444-85010-2
• リード、アーヴィング S. ; チェン、シュエミン (2012) [1999]、データネットワークのエラー制御コーディング、Springer、ISBN 9781461550051

• リード・ソロモン符号入門：原理、アーキテクチャ、実装（CMU）
• RAID のようなシステムにおけるフォールトトレランスのためのリード・ソロモン符号化に関するチュートリアル
• リード・ソロモン符号の代数的ソフト復号
• Wikiversity: コーダーのためのリード・ソロモン符号
• BBC R&D ホワイトペーパー WHP031
• ガイゼル、ウィリアム A. (1990 年 8 月)、リード ソロモン誤り訂正符号化のチュートリアル、技術覚書、NASA、TM-102162
• Dave Forney博士(scholarpedia.org)による連結コード。
• リード、ジェフ A. (1995 年 4 月)、CRC およびリード ソロモン ECC (PDF)

• Phil Karn (別名 KA9Q) による C の FEC ライブラリには、リード ソロモン コーデック (任意バージョンと最適化バージョン (223,255) の両方) が含まれています。
• Schifra オープンソース C++ リード・ソロモン コーデック
• ヘンリー・ミンスキーの RSCode ライブラリ、リード・ソロモン エンコーダ/デコーダ
• オープンソースの C++ リード・ソロモン ソフトデコード ライブラリ
• エラーと消失のリード・ソロモン復号法の Matlab 実装
• 通信パッケージにおける Octave の実装
• リード・ソロモンコーデックの Pure-Python 実装