👩🏼‍🌾 ◀️ 🤵🏿 メッセージをエンコードする際の複数のエラーの修正 💕 👈 🕉️

情報システムでは、通信ネットワークまたはコンピューティングネットワークでのメッセージの交換には、環境または侵入者の妨害的な影響が伴い、デジタル送信中に信号の歪みが発生したり、シンボルにエラーが発生したりします。この現象との戦いは、修正コードを使用して実行されます。以前、ハミングコードについて説明し、コードワードの1つのエラーを修正する方法を示しました。当然のことながら、エラーが多い状況について疑問が生じました。今日は、コードワードに2つのエラー（複数のエラー）がある場合を検討します。理論的にはすべてが多かれ少なかれ単純で理解しやすい一方で、他方では、それはまったく明白ではありません。資料の提示は、E。Berlekampの作品に基づいています。

理論的規定

メッセージで組織化された冗長性を使用するというアイデアは、R。ハミングをここで説明する修正コードの構築に導きました。線形修正（n、k）コードは、チェック（m×n）行列Hによって特徴付けられます。行列の要件は単純です。行の数はチェックシンボルの数と一致し、その列はゼロとは異なる必要があり、すべてが異なります。さらに、列の値は、最終フィールドの要素である単語文字によってコードワードで占められている位置番号を説明します。

多くの場合、デコーダーはその単語に対して計算されたシンドローム計算を使用して、送信された単語にエラーがあるかどうかを判断します。シンドロームは、このマトリックスの列の合計にエラーベクトルの成分を掛けたものに等しくなります。Hにm行が含まれ、コードで単一のエラーを修正できる場合、ブロック（コードワード）の長さは超えません

。また、コードワードの相互の必要な距離の実現可能性も重要です。ハミングコードはこの制限に達します。ハミングコードワードの各位置には、行列Hの対応する列と一致するバイナリベクトルで番号を付けることができます。この場合、シンドロームは、エラーが発生した位置番号（エラーが1つしかない場合）または数値のバイナリ合計（複数のエラーがある場合）と直接一致します。ベクトルの番号付けは非常に有益なアイデアです。さらに、

n \leq 2^{m} - 1

$n≤2^m-1$

ワードのi番目の位置が番号付けされたI。バイナリ番号（つまり、そのような表現）は、位置ロケーターと呼ばれます。すべての二重エラーと単一エラーを修正したいとします。どうやら、これには大きなコードの冗長性が必要になります。行列Hには、より多くの行（数の2倍）が必要です。したがって、2m行の行列Hを作成します。

n \leq 2^{m} - 1

$n≤2^m-1$

列、異なる列を選択するのが妥当です。最初のm行については、ハミングコードの前のマトリックスを使用します。これらは、単語空間の基本的な単語ベクトルです。例 1m = 5およびn = 31とします。次の形式のパリティチェック行列Hを使用して、二重エラーを修正する（n、k）コードを取得することが望ましいでしょう。行列に示される関数fj（ξ）の場合、マップする関数を持つことが望ましいです。それ自体への5次元ベクトルのセット。行列の最後の5行は、関数fがビジェクション（順列）である場合にのみ、ハミングコードを定義します。最初の5行と最後の5行で別々に単一のエラーを修正できる場合は、おそらく一緒に2つのエラーを修正できます。

n \leq 2^{m} - 1

$n≤2^m-1$

必要な関数fj（ξ）を見つけるために、バイナリの5次元ベクトルを加算、減算、乗算、除算し、最大4次の多項式で表すことを学ぶ必要があります。

例2

00000←→0

00010←→1

00011←→X

...

のベクトルの和と差の和と、このような多項式の対応の差： 0±0 = 0、0±1 = 1、±0 = 1 1、1±1 = 0、±符号は有しますバイナリの場合、同じ意味です。乗算ではそうではなく、乗算の結果の指数は4を超える可能性があります。例3

11011 \leftarrow\to х^{4} + х^{3} + х + 1

$11011 ←→ ^4 +^3++1$

(х^{3} + х + 1) х^{4} + х^{3} + х + 1) = х^{7} + х^{6} + х^{5} + 3 х^{4} + 2 х^{3} + х^{2} + 2 х + 1 =

$(^3++1)^4+^3++1)=^7+^6+^5+3^4+2^3+^2+2+1=$

。 4を超える次数を下げる方法が必要です。これは、次数5の還元不可能な多項式M（x）を法とする残基の構築と呼ばれます。この方法は、積の多項式から、で除算した後の残りの部分への遷移で構成されます。

= х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1

$=^7+^6+^5+^4+^2+1$

M (x) = x^{5} + x^{2} + 1

$M(x)=x^5+x^2 + 1$

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 = (х^{2} + х + 1) (х^{5} + х^{2} + 1) + х^{3} + х^{2} + х

$^7+^6+^5+^4+^2+1 =(^2+ + 1)(^5 +^2 +1) +^3 +^2 +$ または

≡記号は「に匹敵する」と読みます。一般に、A（x）≡a（x）mod M（x） A（x）= M（x）C（x）+ a（x）のような多項式C（x）が存在する場合に限ります。多項式の係数は2を法として減少します： A（x）≡a（x）mod（2、M（x））。

х^{7} + х^{6} + х^{5} + х^{4} + х^{2} + 1 \equiv (х^{3} + х^{2} + x) m o d (х^{5} + х^{2} + 1) .

$^7+^6+^5+^4+^2+1 ≡(^3+^2 + x)mod(^5 +^2 +1).$

比較の重要な特性

a（x）≡A（x）mod M（x）およびb（x）≡B（x）mod M（x）の場合、a

（x）±b（x）≡A（x）±B（x ）mod M（x）および

（x）b（x）≡（x）B（x）mod M（x）。

さらに、多項式a（x）およびA（x）の次数がM（x）の次数よりも小さい場合、式

a（x）≡A（x）mod（2、M（x））からa（x） = A（x）。

次数degM（x）には2つの異なる残基クラスがあります-つまり、m未満の次数の異なる多項式が存在するのと同じ数、つまり分割残基はいくつありますか。分割はさらに困難です。

除算アルゴリズム

数字について。

与えられたaとMに対して、a = qM + A、0≤A≤Mのように一意に定義された数qとAがあり

ます。与えられたフィールドからの係数を持つ多項式の場合。

与えられたa（x）とM（x）に対して、a（x）= q（x）M（x）+ A（x）、degA（x）となるように一意に定義された多項式q（x）とA（x）があります。）<度M（x）。

多項式を分割する可能性は、ユークリッドアルゴリズムによって提供されます。

数値については、拡張GCDの例をここで説明します。

与えられたaとbに対して、aA + bB =（a、b）となるような番号AとBがあります。ここで、（a、b）は番号aとbのGCDです。

特定のフィールドからの係数を持つ多項式の場合。

与えられたa（x）とb（x）に対して

、a（x）A（x）+ b（x）B（x）=（a（x）、b ）となるような多項式A（x）とB（x）が存在します。（バツ））、

ここで、（a（x）、b（x））は、最大次数のa（x）とb（x）の正規化された共通除数です。

a（x）とM（x）が共通の除数d（x）≠1である場合、（x）mod M（x）による除算が常に可能であるとは限りません。

a（x）による除算がA（x）による乗算と同等であることは明らかです。

（a（x）、b（x））= 1 = GCDの場合、Euclidのアルゴリズムによれば、A（x）とB（x）があり、a（x）A（x）+ b（x） B（x）= 1であるため、a（x）A（x）≡1modb（x）。バイナリ多項式がフィールドGFで還元できないことを確認する（

）は、度M（x）未満のすべての可能な除数による直接除算によって実行されます。例4。

2^{5}

$2^5$

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$ をxで除算し、（x + 1）

を線形除数で除算します。除算結果はゼロではありません。二乗除数で割る

..それらはゼロ以外のバランスを出します。次数≥3の除数は、それらの積が次数≥6を与えるため、存在しません。したがって、多項式は、モジュロを法として加算、減算、乗算、および除算できます。

х^{2}, х^{2} + х = х (х + 1), х^{2} + 1, х^{2} + 2 х + 1 = (х + 1)^{2}, х^{2} + х + 1.

$^2 , ^2 +=( +1),^2 +1, ^2 +2 +1= ( +1)^2, ^2 + + 1.$

。ブロック長が31、レートが21/31の二重エラー修正コードを指定するパリティチェックマトリックスHの関数の検索に移ります。31-21 = 10 = 2t-チェックシンボル= 10。このような関数は、そのルートとして、コードワード内の誤った位置の数を持っている必要があります。この関数に位置番号を代入すると、ゼロになります。

M (x) = x^{5} + x^{2} + 1

$M(x) = x^5+x^2 +1$

検索機能

β1とβ2が単語の歪んだ文字（位置）の数であると仮定します。数値β1およびβ2のバイナリ表記を使用して、これらの数値は、M（x）を法とする残差クラスとして表すことができます。対応βi→β ^（i）（x）を確立します-次数<5のバイナリ多項式。

最初の5つのテスト条件はβ1+β2を決定します。テスト方程式の2番目のセットは、f（β1）+ f（β2）を決定する必要があります。

デコーダーは、与えられたシステムに従ってβ1とβ2を決定する

必要があります。関数f（x）はどうあるべきですか？

最も単純な関数は、定数f（β）≡αβ（）modM（x）による乗算です。

しかし、その後、ξ2=αξ1、つまりシステムの方程式は依存しています。新しい5つのテスト条件では、デコーダーに新しいものは何も与えられません。

同様に、関数f（β）=β+αは、ξ2=ξ1であるため、状況を変更しません。

パワー機能を試す：最初に

f (β) = β^{2}

$f(β) = β^2$ ..。さらに、

これらの方程式も依存しています。

ξ 1^{2} = (β 1 + β 2)^{2} = β 1^{2} + 2 β 1 β 2 + β 2^{2} = β 1^{2} + β 2^{2} = ξ 2

$ξ1^2 =(β1 + β2)^2=β1^2 + 2β1β2 + β2^2 = β1^2 + β2^2 =ξ2$

したがって、2番目の方程式は最初の方程式の2乗です。

やってみる

f (β) = β^{3}

$f(β) = β^3$ ..。デコーダー方程式の形式を変更します：

場所

ξ 2 = β 1^{3} + β 2^{3} = (β 1 + β 2) (β 1^{2} - β 1 β 2 + β 2^{2}) = ξ 1 (β 1 β 2 - ξ 1^{2}) .

$ξ2 =β1^3 + β2^3=(β1 + β2)(β1^2 -β1β2+ β2^2)=ξ1(β1β2-ξ1^2).$

したがって、ξ1≠0の場合、次のようになります。

したがって、β1とβ2は式を満たします。

したがって、正確に2つのエラーが発生した場合、それらのロケーターはこの式を満たします。この方程式は

、M（x）を法とするバイナリ多項式のフィールドに正確に2つのルートがあるため、デコーダーは常に2つの必要なロケーターを見つけることができます。

エラーが1つだけ発生した場合、β1=ξ1および $β1^2 = ξ2$ ..。したがって、この場合、唯一のエラーは方程式β+ξ1= 0または1 +ξ1β ^-1 = 0を満たします。

最後に、エラーが発生しなかった場合、この場合はξ1+ξ2= 0の場合、デコーダーは常にデコードを実行します。

（実際には）ルートがエラーロケーターである多項式ではなく、ルートがロケーターと相互にある多項式で操作する方が便利です。それら。それらの乗法の逆数です。

エラーが2つ以下の場合、デコーダーがエラー番号を判別できることは明らかです。 3つ以上のシンボルが歪んでいると、デコードエラーまたはデコードエラーが発生します。

だから関数

f (x) = x^{3}

$f(x) = x^3$ コードワード長が31および10のチェックシンボルを持つバイナリコードのチェックマトリックスHの下5行を作成し、すべての二重エラーを修正するのに適しています。

最初の5つのチェックは、エラー番号の合計（S1）を指定します。次の5つのチェックは、エラー数の3乗の合計です（S3）。

デコード手順は、次の3つの主要なステップで構成されます。

受信した各コードワードがチェックされ、S1とS3が計算されます。
σ（z）でエラーロケーター多項式を見つけます。
根σ（z）の相互値が計算され、結果の単語の対応する位置の記号が変更されます。

メッセージをエンコードする際の複数のエラーの修正

理論的規定

比較の重要な特性

除算アルゴリズム

検索機能

More articles: