リードソロモンコード。 簡単な例

Reed-Solomonコードのおかげで、多くの傷があるCDを読んだり、多くの干渉のある通信状態で情報を送信したりできます。 平均して、CDの場合、コードの冗長性（つまり、情報を回復するために使用できる追加の文字の数）は約25％です。 この場合、冗長の半分に相当するデータ量を復元できます。 ディスク容量が700 MBの場合、理論的には700から最大87.5 MBを復元することができます。同時に、どのシンボルがエラーで送信されたかを知る必要はありません。 また、異なるブロックのバイトが特定の順序で混合されている場合、コーディングとともにインターリーブが使用されることにも注意してください大規模な損傷は、修復可能なコードの多くのブロックで単一のエラーを引き起こします。



簡単な例を取り上げて、コーディングから受信側でのソースデータの受信まで、すべての方法を試してみましょう。 2つの数字で構成されるコードワードCを渡す必要があると仮定します-3と1は、まさにこのシーケンスで、つまり ベクトルC =（3,1）を転送する必要があります。 どこに表示されるかを正確に知らずに、最大2つのエラーを修正するとします。 これを行うには、2 * 2 = 4個の冗長文字を使用します。 私たちは言葉にゼロでそれらを書きます、すなわち Cは（3,1,0,0,0,0）に等しくなりました。 次に、数学的特徴について少し理解する必要があります。

フィールズガロア

多くの人々は、わずか20年しか住んでいない若い男のロマンチックな物語を知っていて、ある夜、彼の数学理論を書き、朝の決闘で殺されました。 これがエヴァリスト・ガロアです。 彼は大学への入学も何度か試みましたが、試験官は彼の決定を理解せず、試験に失敗しました。 彼は自分で学ばなければなりませんでした。 彼の作品を送ったガウスもポアソンも理解しませんでしたが、彼の理論は20世紀の60年代に非常に有用であり、現代の数学の新しい分野での理論計算と練習。



彼のグループ理論に基づいて、かなり単純な結論を使用します。 主なアイデア-フィールドと呼ばれる有限の（無限ではない）数があり、それを使用して既知のすべての数学演算を実行できます。 フィールドの数の数は、自然度の素数でなければなりませんが、ここで説明する単純なリードソロモンコードの場合、フィールドの次元は1次の素数です。拡張リードソロモンコードでは、次数は1以上です。

たとえば、次元7のガロア体の場合、つまり GF（7）、すべての数学演算は0、1、2、3、4、5、6の数値で発生します。

追加例：1 + 2 = 3; 4 + 5 = 9 mod 7 = 2。 ガロア体での加算はモジュロ加算です。 減算と乗算もモジュロで行われます。

除算の例：5/6 = 30/36 = 30 /（36 mod 7）= 30/1 = 30 = 30 mod 7 = 2。

次数を上げることは乗算に似ています。



べき乗中にガロア体に有用なプロパティが見つかります。 ご覧のとおり、選択したガロア体GF（7）で3または5のべき乗すると、ラインには0を除く現在のガロア体のすべての要素が含まれます。このような数値はプリミティブ要素と呼ばれます。 リードソロモンコードは通常、選択されたガロア体の最大の原始要素を使用します。 GF（7）の場合、5です。

ガロア体の数字は、同時に、通常の数字よりも互いに密接に関連している抽象化であることに注意することができます。

補間

多くの人が学年から知っているように、補間とは、与えられた点の集合で最小次数の多項式を見つけることです。 たとえば、3つのポイントとこれらのポイントにある関数の3つの値があります。 この入力を満たす関数を見つけることができます。 たとえば、これはラグランジュ変換を使用して行うのが非常に簡単です。 関数が見つかったら、さらにいくつかのポイントを作成できます。これらのポイントは、3つの開始ポイントに関連付けられます。 エンコード中に冗長文字を生成することは、補間に似た操作です。

逆離散フーリエ変換（IDFT）

フーリエ変換は 、ガロア群の理論とともに、数学的思考のもう1つの頂点であり、現在多くの分野で使用されています。 フーリエ変換は、宇宙の基本的な法則の1つであると考える人もいます。 要点：有限長の非周期信号は、さまざまな周波数と位相の正弦波の合計として表すことができ、それらから元の信号を再構築できます。 ただし、これが唯一の説明ではありません。 ガロア体の数値は、前述の正弦波のさまざまな周波数に似ているため、フーリエ変換も使用できます。

離散フーリエ変換は、離散値のフーリエ変換式です。 変換には、直接と逆の2つの方向があります。 逆変換は数学的に簡単なので、検討中の単語をC =（3,1,0,0,0,0）でコーディングしましょう。 最初の2文字は情報であり、最後の4文字は冗長であり、常に0です。

コードワードCを多項式の形式で記述します：C = 3 * x ⁰ + 1 * x ¹ + 0 * x ² + ... = 3 + x。 ガロア体として、前述のGF（7）を取ります。ここで、プリミティブ要素= 5です。IDFTを実行することにより、異なる次数のプリミティブ要素zの多項式Cの値を見つけます。 IDFT式：c _j = C（z ^j ）。 つまり、関数C（z ^j ）の値を見つけます。ここで、jはガロア体GF（7）の要素です。 j = N-2 = 7-2 = 5度と数えます。 次数の表を見ると、理由を推測できます：6次まで、値は再び1です。 繰り返します。その結果、どの程度まで上昇したかを判断することはできません-6番目または0番目。

c ₀ = C（z ⁰ ）= 3 + 1 * z ⁰ = 3 + 1 * 5 ⁰ = 4

c ₁ = C（z ¹ ）= 3 + 1 * z ¹ = 8 = 1

c ₂ = C（z ² ）= 3 + 1 * z ² = 0

...

したがって、C（3,1,0,0,0,0）=> s（4,1,0,2,5,6）。



単語c（4,1,0,2,5,6）を渡します。

エラー

エラーは、送信されたものと要約される別の単語です。 たとえば、エラーf =（0,0,0,2,0,6）。 + fで完了すると、 _f （4,1,0,4,5,5）が得られます。

直接フーリエ変換（DFT）。 デコード。 シンドローム

受信機では、単語c + f = c _f （4,1,0,4,5,5）が得られました。 送信エラーがあったかどうかを確認する方法は？ GFでIDFTを使用して情報をエンコードしたことが知られています（7）。 DFT（離散フーリエ変換）はIDFTの逆です。 エラーが発生しなかった場合、初期情報と4つのゼロ（つまり、C（3,1,0,0,0,0））を取得できます。 エラーがある場合、これらの4つのゼロの代わりに他の数字があります。 _fで DFTを実行し、エラーがあるかどうかを確認しましょう。 DFT式：C _k = N ^-1 * c（z ^-kj ）。 フィールドGF（7）のプリミティブ要素z = 5はまだ使用されています。

C ₀ = c（5 ^{-0 * j} ）/ 6 =（4 * 5 ^{-0 * 0} + 1 * 5 ^{-1 * 0} + 0 * ^{5-2 * 0} + 4 * 5 ^{-3 * 0} + 5 * 5 ^{-4 * 0} + 5 * 5 ^{-5 * 0} ）/ 6 =（4 + 1 + 4 + 0 + 5 + 5）/ 6 = 19/6 = 5/6 = 30/36 = 30 = 2;

C ₁ = c（5 ^{-1 * j} ）/ 6 =（4 * 5 ^{-0 * 1} + 1 * 5 ^{-1 * 1} + 0 * ^{5-2 * 1} + 4 * 5 ^{-3 * 1} + 5 * 5 ^{-4 * 1} + 5 * 5 ^{-5 * 1} ）/ 6 =（4 + 3/15 + 24/750 + 20/2500 + 25/15625）/ 6 =（4 + 3 + 24 + 20 + 25）/ 6 = 76/6 = 456/36 = 456 = 1;

C ₂ = c（ ^{5-2 * j} ）/ 6 =（4 * 5 ^{-0 * 2} + 1 * 5 ^{-1 * 2} + 0 * ^{5-2 * 2} + 4 * 5 ^{-3 * 2} + 5 * 5 ^{-4 * 2} + 5 * 5 ^{-5 * 2} ）/ 6 =（4 + 2 + 4 + 10 + 20）/ 6 = 40/6 = 240/36 = 240 = 2;

...

_f （4,1,0,4,5,5）=> C _f （ 2,1,2,1,0,5 ）で。 エラーがなければ、強調表示された文字はゼロになります。 これで、エラーがあったことがわかります。 この場合、シンボル2,1,0,5はエラーシンドロームと呼ばれます。

エラー位置を計算するためのBerlekamp-Messiアルゴリズム

エラーを修正するには、エラーで送信された文字を知る必要があります。 この段階で、エラーのある文字の場所、エラーの数、およびそのような数のエラーを修正できるかどうかが計算されます。

Berlekamp-Messiアルゴリズムは、シンドロームの番号から準備された特別な行列（以下の例）を掛けると、ゼロベクトルを返す多項式を検索します。 アルゴリズムの証明は、この多項式の根に、結果のコードワードにエラーがある文字の位置に関する情報が含まれていることを示しています。

検討中のケースのエラーの最大数は2になる可能性があるため、2つのエラー（次数2の多項式）に対して行列形式で目的の多項式の式を記述します：= [112]。

次に、テプリッツ行列の形式でシンドローム（2,1,0,5）を記述します。 シンドロームと結果のマトリックスを見ると、そのようなマトリックスを作成する原理がすぐにわかります。 行列の次元は、上記の多項式Γによるものです。



解く方程式：



疑問符の下の要素は結果に影響しません。 G1とG2を見つける必要があります。G1とG2はエラーの位置を担当します。 作業する次元を徐々に増やしていきます。 1から開始し、マトリックスの左下の端（緑色でマーク）から最小寸法1x1で開始します。



ディメンションを増やします。 位置G1にエラーがないと仮定します。 次に、Γ1= 0。



右側に[0 0]を取得するか、計算の次元を増やすために少なくとも1つの0を取得する必要がありますが、最初のコストは1です。G1の値（現在は0）を選択して、必要な0を取得できますアルゴリズムでG1の値を選択するプロセスが最適化されます。 もう一度検討した2つの方程式を書き留め、G1を計算する3番目の方程式を導き出します。 色はそれがどこに行くかを示します。



つまり G1 =3。カウントはGFになります（7）。 G1の値が一時的なものであることも注目に値します。 G2計算中に変更される可能性があります。 右側を読み直します。



右側が0になったので、寸法を増やします。 同様に、G2 = 0と仮定します。見つかったG1 = 3を使用します。



まず、右側の3つではなく、0を取得する必要があります。アクションは前のものに対応しています。 次に、G2の値の選択。



メインの方程式に新しい値2= 2を記述し、再び右側の値を見つけようとします。



このステップでのタスクは、最初のゼロのみを取得することでしたが、偶然、マトリックスの2番目の要素もゼロであることが判明しました。 問題は解決しました。 ゼロでない場合、もう一度値の選択を行い（今回はG1とG2の両方について）、選択の次元を増やします。 このアルゴリズムに興味がある場合は、さらに2つの例を示します。

したがって、G1 = 3、G2 =2。G1とG2のゼロ以外の値は、2つのエラーがあったことを示しています。 行列Γを多項式の形式で記述します：Γ（z）= 1 + 3x + 2x ² 。 結果が0であるプリミティブ要素の次数を考慮したルート：

G（5 ³ ）= 1 + 3 * 6 + 2 * 6 ² = 91 = 13 * 7 = 0

G（5 ⁵ ）= 1 + 3 * 3 + 2 * 3 ² = 28 = 0

これは、位置3および5のエラーを意味します。

同様に、残りの値を見つけて、それらがゼロを与えないことを確認できます。

G => g（z ^j ）=（3,5,5,0,4,0）。 お気づきかもしれませんが、IDFTはGFで再び使用されています（7）。

Forniエラー修正

前の段階では、エラーの位置が計算されましたが、現在は正しい値を見つけるために残っています。 エラー位置を記述する多項式：G（z）= 1 + 3x + 2x ² 。 正規化された形式で記述し、4を掛けてGF（7）のプロパティを使用します：（z）= x ² + 5x + 4。

Forneyの方法はラグランジュ補間に基づいており、Berlekamp-Messiアルゴリズムで操作した多項式を使用します。

この方法は、症候群に関係のない場所に立つキャラクターをさらに計算します。 これらは実際の値に対応する位置ですが、エラーシンドロームと多項式Gの畳み込みから得られる他の値がそれらに対して計算されます。これらの計算された新しい値はシンドロームと共にエラーマスクを形成します。 次に、IDFTが実行され、結果は、送信されたコードワードと以前に合計された直接エラーです。 受信した単語から減算され、元の単語が送信されます。 次に、送信されたコードワードに対してDFTを実行し、最終的に情報を取得します。 次に、この例のコンテキストでこれがどのように起こるか。



エラーベクトルFを記述します（最後の4文字は常に使用するシンドローム、2つの疑問符は情報文字の場所にあり、これがエラーマスクです）。各文字に文字を指定します。



エラーロケータ多項式の記号（z）= x2 + 5x + 4は、次のように表されます。

前のセクションの多項式Γとテプリッツ行列の乗算は、実際には巡回畳み込み演算でした。行列から取得した線形方程式を書くと、シンドロームから得られた値（テプリッツ行列の値）は方程式ごとに単純に変化することがわかります。場所によっては、特定の方向に順番に移動します。これは畳み込みと呼ばれます。 この段落の最初に、多項式FとGを意図的に重ねて配置しました。これにより、畳み込み（特定の順序で要素ごとに乗算）を行い、多項式を視覚的に移動できます。 前のセクションの行列方程式を展開し、導入したばかりの多項式FとΓの表記法を使用します。

0* F4 +1* F3 +2* F2 = 0

0* F5 +1* F4 +2* F3 = 0

以前は、コンボリューションはシンドロームに対してのみ実行されていました。Forneyメソッドでは、F0とF1のコンボリューションが必要で、それらの値を見つける必要があります。

0* F3 +1* F2 +2* F1 = 0

0* F2 +1* F1 +2* F0 = 0

F0 = -G0 * F3-G1 * F2 = 0

F1 = -G0 * F2-G1 * F1 = 6

つまり、F =（6,0,2,1,0,5）。 エラーはIDFTエンコード形式の単語f =（0,0,0,2,0,6）で要約されたため、IDFTを実行します。

結果のコードワードcfからエラーfを引きます：（4,1,0,4,5,5）-（0,0,0,2,0,6）= s（4,1,0,2,5,6 ）

この単語のDFTを作成します：c（4,1,0,2,5,6）=> C =（3,1,0,0,0,0）。 そして、ここに私たちのキャラクター3と1があります。

おわりに

通常、拡張リードソロモンコードが使用されます。つまり、ガロア体は2のべき乗（GF（2 ^m ））で、たとえば情報バイトをエンコードします。 作業アルゴリズムは、この記事で説明したものと似ています。

アルゴリズムには、アプリケーションの分野に応じて、また各特定の品種と開発会社の年齢に応じて、さまざまな種類があります。 アルゴリズムが若いほど、複雑になります。



また、多くのデバイスは事前定義されたエラーテーブルを使用します。 ガロア算術を使用する場合、有限数の可能なエラーが取得されます。 このプロパティは、計算の数を減らすために使用されます。 ここで、シンドロームがゼロ以外であることが判明した場合、エラーの可能性があるシンドロームのテーブルと単純に比較されます。



多くの場合、コーディング理論のコースは最も難しいものの1つです。 この記事が誰かがこのトピックをより速く理解するのを助けてくれたら嬉しいです。