ハミングコード: エラーの検出と修正と例

エラーとは何ですか?

通信中に送信データが破損する場合があります。外来ノイズやその他の物理的な故障の影響を受ける可能性があります。このような状況では、入力データが出力データと同じであることはできません。この不一致は「エラー」として知られています。

データエラーにより、重要なデータや安全なデータが失われる可能性があります。デジタルシステムにおけるデータ転送のほとんどは「ビット転送」の形式になります。ほんのわずかな変更でも、システム全体のパフォーマンスに影響を与える可能性があります。データ列において、1が0になったり、0が1になったりすることを「ビットエラー」といいます。

エラーのタイプ

送信者から受信者へのデータ伝送で発生するビットエラーには、主に 3 つの種類があります。

シングルビットエラー
複数のビットエラー
バーストエラー

シングルビットエラー

データシーケンス全体の 1 ビットが変更されることを「シングルビットエラー」といいます。ただし、シングルビットエラーの発生はそれほど一般的ではありません。さらに、このエラーは、データが 1 行でビット単位で転送されるパラレル通信システムでのみ発生します。そのため、1 行にノイズが含まれる可能性が高くなります。

複数のビットエラー

データシーケンスにおいて、送信機から受信機までのデータシーケンスの XNUMX ビット以上に変化がある場合、これを「多重ビットエラー」といいます。

この種のエラーは、シリアル型とパラレル型の両方のデータ通信ネットワークでよく発生します。

バーストエラー

データシーケンス内のビットセットの変化は「バーストエラー」として知られています。このタイプのデータエラーは、最初のビットの変更から最後のビットの変更まで計算されます。

エラー検出とエラー修正とは何ですか?

デジタル通信システムでは、エラーはある通信システムから別の通信システムに伝達されます。これらのエラーが検出および修正されない場合、データは失われます。効果的な通信を行うには、システムデータが高精度で転送される必要があります。これは、まずエラーを特定し、それらを修正することによって行われます。

エラー検出は、データ通信システムにおいて送信機から受信機に送信されるデータに存在するエラーを検出する方法です。

ここでは、ソースから送信されるデータに冗長コードを追加することで、これらのエラーを見つけることができます。このコードを「誤り検出コード」といいます。

誤り検出コードには次の XNUMX 種類があります。

パリティチェック
巡回冗長検査（CRC）
縦方向冗長検査 (LRC)

パリティチェック

パリティチェックとも呼ばれます。
コスト効率の高いエラー検出メカニズムを備えています。
この技術では、冗長ビットはパリティビットとして知られています。データ単位ごとに付加されます。ユニット内の 1 の合計数は偶数になる必要があり、これはパリティビットとして知られています。

縦方向の冗長性チェック

このエラー検出技術では、ビットのブロックが表形式で編成されます。 LRC メソッドは、すべての列のパリティビットを計算するのに役立ちます。このパリティのセットも元のデータとともに送信されます。パリティのブロックは、冗長性をチェックするのに役立ちます。

巡回冗長検査

巡回冗長検査は、ユニットの最後に追加する必要がある一連の冗長です。そのため、結果として得られるデータ単位は、XNUMX 番目の事前に決定された XNUMX 進数で割り切れる必要があります。

送信先では、受信データを同じ数で割る必要があります。余りがない場合、データユニットは正しいとみなされ、受け入れられます。余りがない場合、データユニットは送信中に破損したことを示しており、拒否する必要があります。

ハミング符号とは何ですか?

ハミングコードは、最大 XNUMX つの直接ビットエラーのエラー検出に役立つライナーコードです。シングルビットエラーが発生する可能性があります。

ハミングコードでは、ソースはメッセージに冗長ビットを追加することでメッセージをエンコードします。これらの冗長ビットは主に、エラー検出および訂正プロセスを実行するために、メッセージ内の特定の位置に挿入および生成されます。

ハミング符号の歴史

ハミングコードは、エラーを検出するために RWHamming によって構築された手法です。
ハミングコードは、任意の長さのデータユニットに適用する必要があり、データと冗長ビットの関係を使用します。
彼は誤り訂正法の問題に取り組み、ハミング符号と呼ばれるますます強力な一連のアルゴリズムを開発しました。
1950 年に、彼はハミングコードを公開しました。このコードは、今日 ECC メモリなどのアプリケーションで広く使用されています。

ハミング符号の適用

ハミングコードを使用する一般的なアプリケーションをいくつか示します。

衛星
コンピュータメモリ
モデム
プラズマCAM
オープンコネクタ
シールド線
組み込みプロセッサ

ハミング符号の利点

ハミングコード手法は、データストリームがシングルビットエラーに対して与えられるネットワークで効果的です。
ハミングコードはビットエラーを検出するだけでなく、エラーを含むビットをインデントして修正できるようにするのにも役立ちます。
ハミングコードは使いやすいため、コンピュータのメモリや単一エラー訂正での使用に最適です。

ハミング符号のデメリット

シングルビットのエラー検出および訂正コード。ただし、複数のビットでエラーが検出された場合、結果として、変更すべき正しいビットが別のビットになる可能性があります。これにより、データにさらなるエラーが発生する可能性があります。
ハミングコードアルゴリズムは単一ビットの問題のみを解決できます。

ハミングコードでメッセージをエンコードする方法

送信者がメッセージをエンコードするために使用するプロセスには、次の 3 つのステップが含まれます。

冗長ビットの総数の計算。
冗長ビットの位置を確認します。
最後に、これらの冗長ビットの値を計算します。

上記の冗長ビットがメッセージ内に埋め込まれている場合、メッセージはユーザーに送信されます。

ステップ1） 冗長ビットの総数の計算。

メッセージに次の内容が含まれていると仮定します。

n– データビット数
p – np が少なくとも (n + p + 1) 個の異なる状態を示すことができるように追加される冗長ビットの数。

ここで、(n + p) は、(n + p) 個の各ビット位置でのエラーの位置を示し、2 つの追加の状態はエラーがないことを示します。 p ビットは XNUMX を示すことができるため、^p 州、2^p 少なくとも (n + p + 1) に等しくなければなりません。

ステップ2） 冗長ビットを正しい位置に配置します。

冗長ビットは、2 のべき乗のビット位置に配置する必要があります。たとえば、1、2、4、8、16 などです。これらは p と呼ばれます。₁ (位置 1)、p₂ (位置 2)、p₃ (4 番目の位置) など

ステップ3） 冗長ビットの値の計算。

冗長ビットは、1 の数が偶数または奇数になるパリティビットである必要があります。

XNUMX 種類のパリティは次のとおりです。

メッセージ内のビットの総数が偶数になることを偶数パリティと呼びます。
メッセージ内のビットの総数を奇数にすることを奇数パリティと呼びます。

ここでは、すべての冗長ビット p1 をパリティとして計算する必要があります。これは、バイナリ表現の最初の位置に 1 を含む必要があるすべてのビット位置 (p1 の位置を除く) をカバーする必要があります。

P1 は、バイナリ表現で 1 を含まない重要度の低い位置に 1 が含まれる位置 (3、5、7、9、…) のすべてのデータビットのパリティビットです。

P2 は、バイナリ表現の右から 1 番目の位置に 2 が含まれる位置にあるすべてのデータビットのパリティビットであり、2 は含まれません (3、6、7、10、11、…)。

P3 は、バイナリ表現で右から 1 番目の位置に 3 が含まれる位置 (4 は含まない) の各ビットのパリティビットです (5-7、12-15、…)。

ハミングコードによるメッセージの復号化

受信者は、エラーを見つけて修正するために再計算を実行する必要がある受信メッセージを受け取ります。

再計算プロセスは次の手順で実行されます。

冗長ビット数をカウントします。
すべての冗長ビットが正しく配置されています。
パリティチェック

ステップ1） 冗長ビット数のカウント

エンコード、冗長ビット数にも同じ式を使用できます。

2^p ? n + p + 1

ここで、データのビット数、p は冗長ビットの数です。

ステップ2） すべての冗長ビットを正しく配置する

ここで、p は 2 のべき乗のビット位置 (たとえば、1、2、4、8 など) にある冗長ビットです。

ステップ3） パリティチェック

パリティビットは、データビットと冗長ビットに基づいて計算する必要があります。

p1 = パリティ(1、3、5、7、9、11…)

p2 = パリティ(2、3、6、7、10、11…)

p3 = パリティ(4-7、12-15、20-23…)

製品概要

通信中に送信データが破損する可能性がある
1 種類のビットエラーは、2) シングルビットエラー、3) 複数ビットエラー、XNUMX) バーストビットエラーです。
データシーケンス全体の XNUMX ビットに加えられた変更は、「シングルビットエラー」として知られています。
データシーケンスにおいて、送信機から受信機までのデータシーケンスの XNUMX ビット以上に変化がある場合、これを「多重ビットエラー」といいます。
データシーケンス内のビットセットの変化は「バーストエラー」として知られています。
エラー検出は、データ通信システムにおいて送信機から受信機に送信されるデータに存在するエラーを検出する方法です。
1 種類の誤り検出コードは、2) パリティチェック、3) 巡回冗長検査 (CRC)、XNUMX) 縦方向冗長検査 (LRC) です。
ハミングコードは、最大 XNUMX つの直接ビットエラーのエラー検出に役立つライナーコードです。シングルビットエラーが発生する可能性があります。
ハミングコードは、エラーを検出するために RWHamming によって構築された手法です。
ハミングコードを使用する一般的な用途には、衛星コンピュータのメモリ、モデム、組み込みプロセッサなどがあります。
ハミングコード方式の最大の利点は、データストリームがシングルビットエラーに対して与えられるネットワークで効果的です。
ハミングコード法の最大の欠点は、単一ビットの問題しか解決できないことです。
ハミングコードを使用して、メッセージの暗号化と復号化のプロセスを実行できます。