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

誤り訂正符号

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

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

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

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

歴史

リード・ソロモン符号は、1960年に当時MITリンカーン研究所に所属していたアーヴィング・S・リードとグスタフ・ソロモンによって開発されました。彼らの画期的な論文は「特定の有限体上の多項式符号」と題されていました。^[1]リードとソロモンの論文で説明されたオリジナルの符号化方式は、符号化するメッセージに基づく可変多項式を用いていましたが、符号化する値（評価点）の固定集合のみが符号化側と復号側で既知でした。オリジナルの理論的な復号器は、受信メッセージのn （符号化済みメッセージ長）の値からk（符号化されていないメッセージ長）の部分集合に基づいて潜在的な多項式を生成し、最もよく使われる多項式を正しいものとして選択していましたが、これは非常に単純なケースを除いて非現実的でした。この問題は当初、オリジナルの方式を、符号化側と復号側の両方が既知である固定多項式に基づくBCH符号のような方式に変更することで解決されましたが、後にオリジナルの方式に基づく実用的な復号器が開発されましたが、BCH方式よりも速度は低下しました。この結果、リード・ソロモン符号には、元のエンコード方式を使用するものと BCH エンコード方式を使用するものの 2 つの主な種類があります。

また 1960 年には、ダニエル ゴレンスタインとニール ツィーラーによって開発されたBCH 符号用の実用的な固定多項式デコーダーが、 1960 年 1 月にMIT リンカーン研究所でツィーラーによって報告され、その後 1961 年 6 月の記事でも説明されました。 ^[2]ゴレンスタイン - ツィーラー デコーダーと BCH 符号に関する関連作業は、W. ウェスリー ピーターソン著の「Error-Correcting Codes」 (1961 年) に記載されています。 [ ^{3 ] [ページ必要]} 1963 年 (あるいはそれ以前) までに、JJ ストーン (およびその他) ^{[誰? ]}は、リード - ソロモン符号は固定生成多項式を使用する BCH 方式を使用でき、そのような符号を BCH 符号の特別なクラスにできることを認識しましたが、 ^[4]

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

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

1977年、リード・ソロモン符号は連結誤り訂正符号の形でボイジャー計画に実装されました。量産消費者製品への最初の商用応用は1982年のコンパクトディスクで、2つのインターリーブされたリード・ソロモン符号が使用されました。今日、リード・ソロモン符号はデジタルストレージデバイスやデジタル通信規格に広く実装されていますが、徐々にボーズ・ショードゥリ・オッケンゲム（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 デコーダーの最初の要素は、8 ビット シンボルの (255,251) 符号を短縮した、比較的弱い内部 (32,28) リード・ソロモン符号です。この符号は、32 バイト ブロックあたり最大 2 バイトのエラーを訂正できます。さらに重要なのは、訂正不可能なブロック、つまり 2 バイトを超えるエラーがあるブロックを消失としてフラグ付けすることです。消失を示すデコードされた 28 バイト ブロックは、デインターリーバによって (28,24) 外部符号の異なるブロックに拡散されます。デインターリーブにより、内側のコードから消去された28バイトのブロックは、外側の28個のコードブロックそれぞれにおいて1バイトの消去されたバイトになります。外側のコードはブロックごとに最大4つの消去を処理できるため、このエラーは簡単に修正できます。

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

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

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

バーコード

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

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

データ転送

リード・ソロモン符号の特殊な形式、特にコーシーRS符号とヴァンダーモンドRS符号は、消失訂正チャネルを介したデータ伝送の信頼性の低さを克服するために使用できます。符号化プロセスでは、RS( N ,  K )符号を前提としており、その結果、長さNシンボルのN個の符号語が生成され、それぞれKシンボルのデータが格納され、消失訂正チャネルを介して送信されます。

相手側で受信したK個のコードワードの任意の組み合わせで、N個のコードワードすべてを再構成できます。チャネルの消失確率が適切にモデル化され、それよりも小さいと判断されない限り、符号化率は一般的に1/2に設定されます。つまり、Nは通常2 Kであり、送信されたコードワードすべてを再構成するには、送信されたコードワードの少なくとも半分を受信する必要があることを意味します。

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

宇宙伝送

深宇宙連結符号化システム。^[8]表記法：RS(255, 223) + CC（「制約長」= 7、符号化率= 1/2）。

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

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

ビタビ復号器は短いバーストエラーを生成する傾向があります。これらのバーストエラーの訂正には、短い、あるいは簡略化されたリード・ソロモン符号が最適です。

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

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

NASAミッションで使用されるチャネル符号化方式^[9]

年	コード	ミッション
1958年～現在	コード化されていない	エクスプローラー、マリナー、その他多数
1968～1978年	畳み込み符号（CC）（25, 1/2）	パイオニア、ヴィーナス
1969–1975	リード・ミュラー符号（32, 6）	マリナー、バイキング
1977年～現在	バイナリゴレイコード	ボイジャー
1977年～現在	RS(255, 223) + CC(7, 1/2)	ボイジャー、ガリレオ、その他多数
1989–2003	RS(255, 223) + CC(7, 1/3)	ボイジャー
1989–2003	RS(255, 223) + CC(14, 1/4)	ガリレオ
1996年～現在	RS + CC (15, 1/6)	カッシーニ、マーズ・パスファインダーなど
2004年～現在	ターボコード[注 1]	メッセンジャー、ステレオ、MRO、MSL、その他
設立2009年	LDPCコード	コンステレーション、M2020、MAVEN

構造（エンコード）

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

リードとソロモンの当初の見解：値の列としてのコードワード

リード・ソロモン符号には異なる符号化手順があり、したがって、すべての符号語の集合を記述する方法も異なります。リードとソロモンのオリジナルの見解では、リード・ソロモン符号のすべての符号語は 未満の次数の多項式の関数値のシーケンスです。^[1]リード・ソロモン符号の符号語を得るために、メッセージ記号（それぞれ q サイズのアルファベット内に収まる）は、を元とする有限体上の 未満の次数の多項式の係数として扱われます。次に、多項式は体 の任意の順序で一連の異なる点において評価され、値のシーケンスが対応する符号語になります。評価点の集合の一般的な選択肢としては、 、、または、、… があり、 はの原始元です。 ${\displaystyle k}$ ${\displaystyle p}$ ${\displaystyle k}$ ${\displaystyle F}$ ${\displaystyle q}$ ${\displaystyle p}$ ${\displaystyle n\leq q}$ ${\displaystyle a_{1},\dots ,a_{n}}$ ${\displaystyle F}$ ${\displaystyle \{0,1,2,\dots ,n-1\}}$ ${\displaystyle \{0,1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-2}\}}$ ${\displaystyle n<q}$ ${\displaystyle \{1,\alpha ,\alpha ^{2},\dots ,\alpha ^{n-1}\}}$ ${\displaystyle \alpha }$ ${\displaystyle F}$

正式には、リード・ソロモン符号の符号語集合は次のように定義されます。より小さい次数の任意の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 の最初の構築では、メッセージxを多項式pの係数として解釈しますが、後続の構築では、メッセージを最初のk点における多項式の値として解釈し、これらの値をk未満の次数の多項式で補間することによって多項式pを取得します。後者のエンコード手順は、効率がやや劣るものの、体系的なコードを生成できるという利点があります。つまり、元のメッセージは常にコードワードのサブシーケンスとして含まれています。^[1] ${\displaystyle q^{k}}$ ${\displaystyle a_{1},\dots ,a_{k}}$

シンプルな符号化手順：係数の列としてのメッセージ

リードとソロモンの元々の構成では、メッセージはの多項式にマッピングされます。のコードワードは、体の異なる点で評価することによって得られます。^[1]したがって、リード・ソロモン符号の古典的な符号化関数は次のように定義されます。 ${\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}=m_{0}+m_{1}a+m_{2}a^{2}+\cdots +m_{k-1}a^{k-1}}$$ ${\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)=mA}$ ${\displaystyle k\times n}$ ${\displaystyle A}$ ${\displaystyle F}$

$${\displaystyle C(m)=mA={\begin{bmatrix}m_{0}&m_{1}&m_{2}&\cdots &m_{k-1}\end{bmatrix}}{\begin{bmatrix}1&1&1&\dots &1\\a_{0}&a_{1}&a_{2}&\dots &a_{n-1}\\a_{0}^{2}&a_{1}^{2}&a_{2}^{2}&\dots &a_{n-1}^{2}\\\vdots &\vdots &\vdots &\ddots &\vdots \\a_{0}^{k-1}&a_{1}^{k-1}&a_{2}^{k-1}&\dots &a_{n-1}^{k-1}\end{bmatrix}}}$$

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

体系的な符号化手順：メッセージは初期値列として

体系的なリード・ソロモン符号を生成するための代替的な符号化手順があります。一つの方法は、ラグランジュ補間を用いて、となる多項式を計算します。そして、他の点 において が評価されます。 ${\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)=mG}$の要素を持つ次の-行列について。 ${\displaystyle k\times n}$ ${\displaystyle G}$ ${\displaystyle F}$ $${\displaystyle C(m)=mG={\begin{bmatrix}m_{0}&m_{1}&m_{2}&\cdots &m_{k-1}\end{bmatrix}}{\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 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 つで使用されます。

BCHの視点：係数の列としてのコードワード

BCHコードとBCHビューのほとんどの実装では、最上位項が先頭に来ることに注意してください。このビューでは、メッセージは多項式の係数として解釈されます。 ${\displaystyle m(x)}$

$${\displaystyle m(x)=m_{k-1}x^{k-1}+m_{k-2}x^{k-2}+\cdots +m_{1}x+m_{0}}$$

生成多項式は 、その根がガロア体原始の連続するべきである多項式として定義されます。 「狭義のコード」の場合、。 ${\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)=x^{n-k}+g_{n-k-1}x^{n-k-1}+\cdots +g_{1}x+g_{0}}$$
${\displaystyle i=1}$

エンコードでは、 の正確な倍数であるコードワード多項式を計算します。 ${\displaystyle c(x)=c_{n-1}x^{n-1}+c_{n-2}x^{n-2}+\cdots +c_{1}x+c_{0}}$ ${\displaystyle g(x)}$

簡単なエンコード手順

送信者は、次数 の関連多項式 を計算し、その多項式 を送信します。この多項式は、次数 のメッセージ多項式と、送信者と受信者の両方が知っている次数 の生成多項式を乗算することによって構成されます。 ${\displaystyle c(x)}$ ${\displaystyle n-1}$ ${\displaystyle n\leq q-1}$ ${\displaystyle c(x)}$ ${\displaystyle c(x)}$ ${\displaystyle m(x)}$ ${\displaystyle k-1}$ ${\displaystyle g(x)}$ ${\displaystyle n-k}$ ${\displaystyle c(x)=m(x)g(x)}$

この関数は線形写像です。つまり、の要素を持つ次の-行列に対して を満たします。 ${\displaystyle C}$ ${\displaystyle C(m)=mA}$ ${\displaystyle k\times n}$ ${\displaystyle A}$ ${\displaystyle F}$

$${\displaystyle A={\begin{bmatrix}1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &\cdots &0\\0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\0&\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0\\0&\cdots &\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}\\\end{bmatrix}}}$$

${\displaystyle C(m)=mA}$の要素を持つ次の行列について。 ${\displaystyle k\times n}$ ${\displaystyle G}$ ${\displaystyle F}$

$${\displaystyle c(x)=mA={\begin{bmatrix}m_{k-1}&\cdots &m_{1}&m_{0}\end{bmatrix}}{\begin{bmatrix}1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &\cdots &0\\0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0&\cdots &0\\\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots &\vdots \\0&\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}&0\\0&\cdots &\cdots &0&1&g_{n-k-1}&\cdots &g_{1}&g_{0}\\\end{bmatrix}}}$$

体系的なエンコード手順

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

正式には、チェックシンボルのためのスペースを確保するために を掛け、その積を で割って余りを求め、さらにその余りを で引くことで補正することで構築されます。チェックシンボルは、余りを計算することで生成されます。 ${\displaystyle c(x)}$ ${\displaystyle x^{t}}$ ${\displaystyle t=n-k}$ ${\displaystyle g(x)}$ ${\displaystyle t}$ ${\displaystyle r(x)}$ $${\displaystyle r(x)=c(x)\cdot x^{t}\ {\bmod {\ }}g(x).}$$

剰余の次数は最大 であるが、多項式におけるの係数は0である。したがって、次のコードワードの定義は、最初の係数が の係数と同一であるという性質を持つ。 ${\displaystyle t-1}$ ${\displaystyle x^{t-1},x^{t-2},\dots ,x^{1},x^{0}}$ ${\displaystyle c(x)\cdot x^{t}}$ ${\displaystyle c(x)}$ ${\displaystyle k}$ ${\displaystyle c(x)}$ $${\displaystyle c(x)=m(x)\cdot x^{t}-r(x)\,.}$$

その結果、は で割り切れる。^[10] ${\displaystyle c(x)}$ ${\displaystyle g(x)}$

$${\displaystyle c(x)\equiv m(x)\cdot x^{t}-r(x)\equiv r(x)-r(x)\equiv 0\mod g(x)\,.}$$

この関数は線形写像です。対応する体系的符号化行列 G を生成するには、行列 A に A の左正方部分行列の逆行列を乗算します（または、G の左正方部分行列を単位行列に設定し、各行を符号化します）。 ${\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)=mG}$の要素を持つ次の行列について。 ${\displaystyle k\times n}$ ${\displaystyle G}$ ${\displaystyle F}$

$${\displaystyle c(x)=mG={\begin{bmatrix}m_{k-1}&\ldots &m_{1}&m_{0}\end{bmatrix}}{\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}}}$$

プロパティ

リード・ソロモン符号は[ 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}$

リード・ソロモン符号（N=255、K=233、QPSK、AWGN）の理論的なBER性能。階段状の特性。

理論的な誤差境界は、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)}$

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

リード・ソロモン符号は、畳み込み符号と同様に透過的な符号です。つまり、チャネルシンボルが途中で反転されていても、デコーダは動作します。その結果、元のデータが反転されます。しかし、リード・ソロモン符号は、符号が短縮されると透過性を失います（このセクションの最後にある「備考」を参照）。短縮された符号の「欠落」ビットは、データが補数化されているかどうかに応じて、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コード Ver 3 (29×29) はインターリーブブロックを使用します。メッセージは26データバイトで構成され、2つのリード・ソロモン符号ブロックを使用して符号化されます。各ブロックは(255,233)リード・ソロモン符号であり、(35,13)コードに短縮されています。

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

BCHビューデコーダー

このセクションで説明するデコーダは、符号語を係数列としてBCHで表現します。デコーダは、エンコーダとデコーダの両方に既知である固定の生成多項式を使用します。

Peterson-Gorenstein-Zierler デコーダ

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

処方

送信されたメッセージは、多項式の係数としてみなされる。 ${\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 つ減らし、次に小さい系を調べます。^[15] $${\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 ₁ = 757 = 3 ⁻³、x ₂ = 562 = 3 ⁻⁴と なり ます。係数を逆にして、 正の指数を持つ根 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アルゴリズムは、誤り位置多項式を求めるための代替反復手順です。各反復処理において、Λ( x )の現在のインスタンスに基づいて、想定される誤り数e : におけるずれを計算し、再計算されたΔがゼロになるようにΛ( 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 の例と同じデータを使用します。

n	S n +1	d	C	B	b	メートル
0	732	732	197 × + 1	1	732	1
1	637	846	173 × + 1	1	732	2
2	762	412	634 × 2 + 173 × + 1	173 × + 1	412	1
3	925	576	329 × 2 + 821 × + 1	173 × + 1	412	2

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}}}$$

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

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

A _i ( x ) S ( x ) + B _i ( x ) x ^t = R _i ( x )

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

A _i ( x ) = Λ( x )

B _i ( x ) = −Q( x )

R _i ( x ) = Ω( x ) です。

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)で割ります。

Λ( x ) = A _i / A _i (0)

Ω( x ) = R _i / A _i (0)

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

例

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

私	R i	A i
−1	001 × 4 + 000 × 3 + 000 × 2 + 000 × + 000	000
0	925 × 3 + 762 × 2 + 637 × + 732	001
1	683 × 2 + 676 × + 024	697 × + 396
2	673 × + 596	608 × 2 + 704 × + 544

Λ( x ) = A ₂ / 544 = 329 x ² + 821 x + 001

Ω( x ) = R ₂ / 544 = 546 x + 732

離散フーリエ変換を用いたデコーダ

離散フーリエ変換は復号に使用できる。^[16]シンドローム名との衝突を避けるため、符号化されたコードワードを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のマドゥ・スーダンとベンカテサン・グルスワミは、「リード・ソロモン符号と代数幾何学符号の改良復号法」を発表し、符号の最小距離の半分を超える誤り訂正を可能にするアルゴリズムを紹介した。^{[17]これはリード・ソロモン符号、そしてより一般的には}代数幾何学符号に適用される。このアルゴリズムは符号語のリストを生成する（リスト復号アルゴリズムである）もので、 GF (2 ^m )とその拡張上の多項式の補間と因数分解に基づいている。

2023年に、符号理論家は、ランダム評価点上で定義されたリード・ソロモン符号が、線形サイズのアルファベットに対してリスト復号能力（最大n - kエラー）を高い確率で達成できることを示した。 ^{[18] [19] [20]}これらの結果は、復号を実行するためのアルゴリズムを提供していない。

ソフトデコード

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

リード・ソロモンのオリジナルビューデコーダー

このセクションで説明するデコーダは、リード・ソロモンの本来の考え方に基づき、コードワードを多項式値の列として捉えます。この多項式は、エンコードされるメッセージに基づいています。エンコーダとデコーダは同じ固定値セットを使用し、デコーダは受信メッセージからエンコード多項式（およびオプションでエラー検出多項式）を復元します。

理論的なデコーダー

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

ベルレカンプ・ウェルチ・デコーダー

1986年、ベルレカンプ・ウェルチアルゴリズムとして知られるデコーダが開発されました。このデコーダは、元のメッセージ多項式と、エラーに対応する入力値にゼロを生成するエラー「ロケータ」多項式を、時間計算量O ( n ³ )で復元できるデコーダです。ここで、nはメッセージ内の値の個数です。復元された多項式は、元のメッセージを復元（必要に応じて再計算）するために使用されます。

例

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

a = {0, 1, 2, 3, 4, 5, 6}

メッセージ多項式が

p ( x ) = 003 x ² + 002 x + 001

コードワードは

c = {001, 006, 017, 034, 057, 086, 121}

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

b = c + e = {001, 006, 123, 456, 057, 086, 121}

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

b _i E ( a _i ) - Q ( a _i ) = 0

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

b _i ( e ₀ + e ₁ a _i ) - ( q ₀ + q ₁ a _i + q ₂ a²
_i+ q ₃ a³
_私+ q ₄ a⁴
_私) = - b _i a²
_i

$${\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}}}$$

Q ( x ) = 003 x ⁴ + 916 x ³ + 009 x ² + 007 x + 006

E ( x ) = 001 x ² + 924 x + 006

⁠Q ( x )/元）​​⁠ = P ( x ) = 003 x ² + 002 x + 001

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

c = {001, 006, 017, 034, 057, 086, 121} }}

Gaoデコーダー

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

例

• ${\displaystyle R_{-1}=\prod _{i=1}^{n}(x-a_{i})}$
• ${\displaystyle R_{0}=}$のラグランジュ補間 ${\displaystyle (a_{i},b(a_{i}))}$ ${\displaystyle i=1}$ ${\displaystyle n}$
• ${\displaystyle A_{-1}=0}$
• ${\displaystyle A_{0}=1}$
• を生成し、の度合いまで生成する。この例では ${\displaystyle R_{i}}$ ${\displaystyle A_{i}}$ ${\displaystyle R_{i}<(n+k)/2}$ ${\displaystyle (n+k)/2=(7+3)/2=5}$

私	R i	A i
−1	001 × 7 + 908 × 6 + 175 × 5 + 194 × 4 + 695 × 3 + 094 × 2 + 720 × + 000	000
0	055 × 6 + 440 × 5 + 497 × 4 + 904 × 3 + 424 × 2 + 472 × + 001	001
1	702 × 5 + 845 × 4 + 691 × 3 + 461 × 2 + 327 × + 237	152 × + 237
2	266 × 4 + 086 × 3 + 798 × 2 + 311 × + 532	708 × 2 + 176 × + 532

Q ( x ) = R ₂ = 266 x ⁴ + 086 x ³ + 798 x ² + 311 x + 532

E ( x ) = A ₂ = 708 x ² + 176 x + 532

Berlekamp Welshによって生成された多項式を複製するには、Q ( x )とE ( x )をE ( x )の最も重要な係数=708で割ります。

Q ( x ) = 003 x ⁴ + 916 x ³ + 009 x ² + 007 x + 006

E ( x ) = 001 x ² + 924 x + 006

⁠Q ( x )/元）​​⁠ = P ( x ) = 003 x ² + 002 x + 001

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

c = {001, 006, 017, 034, 057, 086, 121}

症候群デコーダー

2015年頃には改良されたデコーダが開発された。^[24]デコーダはシンドロームを生成し、BCHビューと同様に、エラーロケータ多項式とシンドローム間のキー方程式は同じであるが、エラーロケータ多項式には に対応する根があり、ルックアップテーブルを使用して根をコードワードオフセットに変換する。 ${\displaystyle (1/\alpha _{i})}$

初期化:
多項式が定義されます:多項式の集合が定義されます:値の集合が生成されます:多項式の集合が生成されます: ${\displaystyle L=\Pi _{i=0}^{n-1}(x-\alpha _{i})}$
${\displaystyle n}$ ${\displaystyle L_{i}=L/(x-\alpha _{i})}$
${\displaystyle n}$ ${\displaystyle u_{i}=L_{i}(\alpha _{i})}$
${\displaystyle n}$ ${\displaystyle P_{i}=(u_{i}/(1-\alpha _{i}z))\mod (z^{n-k})}$

復号化 - エラーの可能性があるコードワード が受信されます。シンドローム多項式 が生成されます。その後エラーが検出されない場合は、そうでない場合は 拡張ユークリッドは、、から開始し、次まで続行します。エラー位置多項式は、エラー値多項式は であり、これらはの最下位項で除算されます。の正式な導関数 が生成されます。エラーのオフセットは、root = の場合の の根に対応します。のエラー値はです。 ${\displaystyle r=\{r_{0},r_{1},\dots ,r_{n-1}\}}$
${\displaystyle S=\Sigma _{i=0}^{n-1}r_{i}P_{i}}$
${\displaystyle S=0}$
${\displaystyle R_{-1}=z^{n-k}}$ ${\displaystyle R_{0}=S}$ ${\displaystyle A_{-1}=0}$ ${\displaystyle A_{0}=1}$
${\displaystyle R_{i}<(n-k)/2}$
${\displaystyle \sigma =A_{i}}$
${\displaystyle \omega =R_{i}}$
${\displaystyle \sigma }$ ${\displaystyle \omega }$ ${\displaystyle \sigma }$
${\displaystyle \sigma }$ ${\displaystyle \sigma '}$
${\displaystyle o}$ ${\displaystyle \sigma }$
${\displaystyle 1/\alpha _{i}}$ ${\displaystyle o_{i}=i}$
${\displaystyle o_{i}}$
${\displaystyle e_{i}=(-\alpha _{i}\ \omega (1/\alpha _{i}))/(u_{i}\ \sigma '(1/\alpha _{i}))}$

に対応する誤差値がオフセット で検出され、別の誤差値が計算された場合:の最も重要な係数の根に対応するの集合は、 ${\displaystyle deg(\omega )=deg(\sigma )}$ ${\displaystyle \alpha _{b}=0}$
${\displaystyle o_{b}=b}$
${\displaystyle B=\{b|\sigma (1/\alpha _{i})=0\}}$ ${\displaystyle \alpha _{i}}$ ${\displaystyle \sigma }$
${\displaystyle w=}$ ${\displaystyle \omega }$
${\displaystyle e_{b}=w\ u_{b}^{-1}\ (\Pi _{\alpha \in B}\ (-\alpha ))^{-1}}$

例

Berlekamp Welchの例と同じデータを使用する

初期化:
${\displaystyle a=\{000,001,002,003,004,005,006\}}$
${\displaystyle u=\{040,689,600,129,600,689,040\}}$

私	円周率
0	040
1	689z3 + 689z2 + 689z + 689​​
2	155z3 + 542z2 + 271z + 600​​
3	696z3 + 232z2 + 387z + 129​​
4	311z3 + 310z2 + 542z + 600​​
5	657z3 + 503z2 + 658z + 689​​
6	279z3 + 511z2 + 240z + 040​​

解読:ユークリッド:
${\displaystyle r=\{001,006,123,456,057,086,121\}}$
${\displaystyle S=785\ z^{3}+213\ z^{2}+666\ z+055}$

私	R i	A i
-1	001z4 + 000z3 + 000z2 + 000z + 000​​​	000
0	785z3 + 213z2 + 666z + 055​​	001
1	658 z 2 + 858 z + 323	200 z + 141
2	294 z + 709	905 z 2 + 020 z + 925

${\displaystyle \sigma =905\ z^{2}+020\ z+925}$
${\displaystyle \omega =294\ z+709}$
925で割る ${\displaystyle \sigma }$ ${\displaystyle \omega }$
${\displaystyle \sigma =006\ z^{2}+924\ z+1}$
${\displaystyle \omega =391\ z+55}$
${\displaystyle \sigma '=012\ z+924}$
${\displaystyle o=\{002,003\}}$
${\displaystyle e=\{000,000,106,422,000,000,000\}}$
${\displaystyle c=\{001,006,017,034,057,086,121\}=r-e}$

参照

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

注記

1. Andrewsら（2007）の著者らは、同じ符号化率（1/6）の場合、ターボ符号はリードソロモン連結符号よりも最大2 dB（ビット誤り率）優れていることを示すシミュレーション結果を提供している。^[9]

参考文献

1. Reed, Irving S. ; Solomon, Gustave (1960). 「特定の有限体上の多項式符号」(PDF) . Journal of the Society for Industrial and Applied Mathematics . 8 (2): 300– 304. doi :10.1137/0108018.
2. p ^mシンボルにおける巡回線形誤り訂正符号のクラス」. J. SIAM . 9 (2): 207– 214. doi :10.1137/0109020. JSTOR  2098821.
3. Peterson, W. Wesley (1961). Error-Correcting Codes . MIT Press. ISBN 978-0262160063. OCLC  859669631。 {{cite book}}:ISBN / 日付の非互換性（ヘルプ）
4. ピーターソン、W. ウェズリー; ウェルドン、EJ (1996) [1972]. 誤り訂正符号（第2版）. MITプレス. ISBN 978-0-585-30709-1. OCLC  45727875。
5. 杉山雄三; 笠原正之; 平沢誠; 滑川毅 (1975). 「ゴッパ符号の解読における鍵方程式の解法」.情報制御. 27 (1): 87– 99. doi : 10.1016/S0019-9958(75)90090-X .
6. Gao, Shuhong (2002年1月)、リード・ソロモン符号の復号のための新しいアルゴリズム(PDF)、クレムソン。
7. Immink, KAS (1994)、「リード・ソロモン符号とコンパクトディスク」、Wicker, Stephen B.、Bhargava, Vijay K. (編)、『リード・ソロモン符号とその応用』、IEEE Press、ISBN 978-0-7803-1025-4
8. Hagenauer, J.; Offer, E.; Papke, L. (1994). 「11. 連結システムにおけるビタビ復号器とリード・ソロモン復号器のマッチング」リード・ソロモン符号とその応用IEEE Press. p. 433. ISBN 9780470546345. OCLC  557445046。
9. Andrews, KS; Divsalar, D.; Dolinar, S.; Hamkins, J.; Jones, CR; Pollara, F. (2007). 「深宇宙アプリケーション向けターボ符号およびLDPC符号の開発」(PDF) . Proceedings of the IEEE . 95 (11): 2142–56 . doi :10.1109/JPROC.2007.905132. S2CID  9289140.
10. Lin, Shu; Costello, Daniel J. (1983). 『誤り制御符号化：基礎と応用』（Nachdr. ed.）. Englewood Cliffs, NJ: Prentice-Hall. p. 171. ISBN 978-0-13-283796-5。
11. 「bercodingとBERToolで使用される解析表現」。2019年2月1日時点のオリジナルよりアーカイブ。2019年2月1日閲覧。
12. Pfender, Florian; Ziegler, Günter M. (2004年9月)、「Kissing Numbers, Sphere Packings, and Some Unexpected Proofs」(PDF) , Notices of the American Mathematical Society , 51 (8): 873– 883, archived (PDF) from the original on 2008-05-09 , retrieved 2009-09-28コンパクト ディスクのエラー訂正コードのコンテキストで使用される Delsarte-Goethals-Seidel の定理について説明します。
13. Peterson, W. (1960年9月). 「ボーズ・チャウドゥリ符号の符号化と誤り訂正手順」. IEEE Transactions on Information Theory . 6 (4): 459– 470. doi :10.1109/TIT.1960.1057586.
14. ゴレンスタイン、ダニエル; ツィーラー、ニール (1961年6月). 「$p^m$ シンボルにおける誤り訂正符号のクラス」.応用数学協会誌. 9 (2): 207– 214. doi :10.1137/0109020.
15. Gill, John (nd). 「EE387 Notes #7, Handout #28」(PDF) . スタンフォード大学. 2014年6月30日時点のオリジナル(PDF)からアーカイブ。 2010年4月21日閲覧。
16. Lin, Shu; Costello, Daniel J. (2004). 『誤り制御符号化：基礎と応用』（第2版）. Upper Saddle River, NJ: Pearson/Prentice Hall. pp.  255– 262. ISBN 978-0130426727。
17. Guruswami, V.; Sudan, M. (1999年9月)、「リード・ソロモン符号と代数幾何学符号の改良復号法」、IEEE Transactions on Information Theory、45 (6): 1757– 1767、CiteSeerX 10.1.1.115.292、doi :10.1109/18.782097 
18. Brakensiek, Joshua; Gopi, Sivakanth; Makam, Visu (2023-06-02). 「汎用リード・ソロモン符号によるリスト復号能力の実現」.第55回ACM計算理論シンポジウム議事録. STOC 2023. ニューヨーク州ニューヨーク：Association for Computing Machinery. pp.  1488– 1501. arXiv : 2206.05256 . doi :10.1145/3564246.3585128. ISBN 978-1-4503-9913-5。
19. Guo, Zeyu; Zhang, Zihan (2023). 「ランダムパンクチャードリードソロモン符号は多項式サイズのアルファベット上でリスト復号能力を実現する」. 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS) . FOCS 2023, Santa Cruz, CA, USA, 2023. pp.  164– 176. arXiv : 2304.01403 . doi :10.1109/FOCS57990.2023.00019. ISBN 979-8-3503-1894-4。
20. Alrabiah, Omar; Guruswami, Venkatesan; Li, Ray (2023-08-18)ランダムにパンクチャーされたリード-ソロモン符号は線形サイズの体でリスト復号能力を実現する、arXiv : 2304.09445
21. Koetter, Ralf; Vardy, Alexander (2003). 「リード・ソロモン符号の代数的ソフト決定復号法」. IEEE Transactions on Information Theory . 49 (11): 2809– 2825. CiteSeerX 10.1.1.13.2021 . doi :10.1109/TIT.2003.819332. 
22. Franke, Steven J.; Taylor, Joseph H. (2016). 「JT65 (63,12) リード・ソロモン符号用オープンソース軟判定復号器」(PDF) . QEX (5/6月): 8– 17. 2017年3月9日時点のオリジナルよりアーカイブ(PDF) . 2017年6月7日閲覧。
23. 「リード・ソロモン符号の復号のための新しいアルゴリズム」（PDF）。2012年7月12日時点のオリジナル（PDF）からアーカイブ。
24. https://users.math.msu.edu/users/halljo/classes/codenotes/grs.pdf

外部リンク

情報とチュートリアル

• ウェルチ、LR（1997）、リード・ソロモン符号の本来の見方（PDF）、講義ノート
• Koetter, Ralf (2005), Reed–Solomon Codes, MIT Lecture Notes 6.451 (ビデオ), 2013年3月13日時点のオリジナルよりアーカイブ

• リード・ソロモン符号入門：原理、アーキテクチャ、実装（CMU）
• ガイゼル、ウィリアム A.（1990年8月）、リード・ソロモン誤り訂正符号化のチュートリアル、技術覚書、NASA、TM-102162
• リード、ジェフ A.（1995年4月）、CRCおよびリードソロモンECC （PDF）

実装

• Phil Karn (別名 KA9Q) による C の FEC ライブラリには、リード ソロモン コーデック (任意バージョンと最適化バージョン (223,255) の両方) が含まれています。
• オープンソースのC++リード・ソロモンソフトデコードライブラリ
• エラーと消失を含むリード・ソロモン復号法のMATLAB実装

「https://en.wikipedia.org/w/index.php?title=Reed–Solomon_error_correction&oldid=1322990324」より取得