エラー検出および修正コード

ビット0とビット1は、アナログ電圧の2つの異なる範囲に対応することがわかっています。そのため、1つのシステムから別のシステムへのバイナリデータの送信中に、ノイズも追加される場合があります。このため、他のシステムで受信したデータにエラーがある可能性があります。

つまり、ビット0が1に変更されるか、ビット1が0に変更される場合があります。ノイズの干渉は避けられません。ただし、エラーが存在するかどうかを検出し、それらのエラーを修正することにより、最初に元のデータを取得できます。この目的のために、次のコードを使用できます。

エラー検出コード
エラー修正コード

エラー検出コード-受信データ（ビットストリーム）に存在するエラーを検出するために使用されます。これらのコードには、元のビットストリームに含まれる（付加される）ビットが含まれます。元のデータ（ビットストリーム）の送信中に発生した場合、これらのコードはエラーを検出します。例-パリティコード、ハミングコード。

エラー修正コード-受信データ（ビットストリーム）に存在するエラーを修正するために使用され、元のデータを取得します。エラー修正コードも、エラー検出コードと同様の戦略を使用します。例-ハミングコード。

したがって、エラーを検出して修正するために、送信時にデータビットに追加のビットが追加されます。

パリティコード

元のビットストリームのMSBの左側またはLSBの右側のいずれかに1つのパリティビットを含める（追加する）のは簡単です。パリティコードには、選択されているパリティのタイプに基づいて、偶数パリティコードと奇数パリティコードの2つのタイプがあります。

偶数パリティコード

バイナリコードに偶数の1が存在する場合、偶数パリティビットの値はゼロでなければなりません。それ以外の場合は、1つにする必要があります。そのため、偶数の1は*偶数パリティコード*に存在します。偶数パリティコードには、データビットと偶数パリティビットが含まれます。

次の表は、各3ビットバイナリコードに対応する*偶数パリティコード*を示しています。ここでは、偶数パリティビットがバイナリコードのLSBの右側に含まれています。

Binary Code	Even Parity bit	Even Parity Code
000	0	0000
001	1	0011
010	1	0101
011	0	0110
100	1	1001
101	0	1010
110	0	1100
111	1	1111

ここで、偶数パリティコードに存在するビット数は4です。したがって、これらの偶数パリティコードで可能な偶数の1は0、2、4です。

他のシステムがこれらの偶数パリティコードのいずれかを受信した場合、受信データにエラーはありません。偶数パリティビット以外のビットは、バイナリコードのビットと同じです。
他のシステムが偶数パリティコード以外を受信した場合、受信データにエラーがあります。この場合、エラーのビット位置がわからないため、元のバイナリコードを予測することはできません。

したがって、偶数パリティビットは、受信したパリティコードのエラーを検出する場合にのみ役立ちます。ただし、エラーを修正するだけでは不十分です。

奇数パリティコード

奇数の1がバイナリコードに存在する場合、奇数のパリティビットの値はゼロでなければなりません。それ以外の場合は、1つにする必要があります。そのため、奇数の1は* oddパリティコード*に存在します。奇数パリティコードには、データビットと奇数パリティビットが含まれます。

次の表に、各3ビットバイナリコードに対応する*奇数パリティコード*を示します。ここで、奇数パリティビットは、バイナリコードのLSBの右側に含まれています。

Binary Code	Odd Parity bit	Odd Parity Code
000	1	0001
001	0	0010
010	0	0100
011	1	0111
100	0	1000
101	1	1011
110	1	1101
111	0	1110

ここで、奇数パリティコードに存在するビット数は4です。したがって、これらの奇数パリティコードで可能な1の奇数は1および3です。

他のシステムがこれらの奇数パリティコードのいずれかを受信した場合、受信データにエラーはありません。奇数パリティビット以外のビットは、バイナリコードと同じです。 *他のシステムが奇数以外のパリティコードを受信した場合、受信データにエラーがあります。この場合、エラーのビット位置がわからないため、元のバイナリコードを予測することはできません。

したがって、奇数パリティビットは、受信したパリティコードのエラーを検出する場合にのみ役立ちます。ただし、エラーを修正するだけでは不十分です。

ハミングコード

ハミングコードは、受信データに存在するエラーの検出と修正の両方に役立ちます。このコードは複数のパリティビットを使用し、これらのパリティビットを2のべき乗の位置に配置する必要があります。

次の関係が正しい（有効な） 'k'* の*最小値は、必要なパリティビット数にすぎません。

2 ^ k \ geq n + k + 1

どこで、

「n」はバイナリコードのビット数（情報）

「k」はパリティビットの数です

したがって、ハミングコードのビット数はn + kに等しくなります。

ハミングコード*を$ b _ \ {n + k} b _ \ {n + k-1} ….. b _ \ {3} b _ \ {2} b _ \ {1} $およびパリティビット$ p_とする\ {k}、p _ \ {k-1}、…. p _ \ {1} $。「k」パリティビットは、2のべき乗の位置にのみ配置できます。残りのビット位置には、バイナリコードの「n」ビットを配置できます。

要件に基づいて、ハミングコードを形成しながら偶数パリティまたは奇数パリティを使用できます。ただし、受信データにエラーが存在するかどうかを確認するには、同じパリティ技術を使用する必要があります。

パリティビット*を見つけるには、この手順に従ってください。

ビット位置b〜3〜、b〜5〜、b〜7〜などに存在するものの数に基づいて、* p〜1〜*の値を見つけます。同等のバイナリのこれらのビット位置（サフィックス）はすべて、2 ^ 0 ^の場所の値に「1」があります。
ビット位置b〜3〜、b〜6〜、b〜7〜などに存在するものの数に基づいて、* p〜2〜*の値を見つけます。同等のバイナリのこれらすべてのビット位置（サフィックス）は、2 ^ 1 ^の場所の値に「1」があります。
ビット位置b〜5〜、b〜6〜、b〜7〜などに存在するものの数に基づいて、* p〜3〜*の値を見つけます。同等のバイナリのこれらすべてのビット位置（サフィックス）は、2 ^ 2 ^の場所の値に「1」があります。
同様に、パリティビットの他の値を見つけます。

チェックビット*を見つけるには、この手順に従ってください。

ビット位置b〜1〜、b〜3〜、b〜5〜、b〜7〜などに存在するものの数に基づいて、c〜1〜の値を見つけます。同等のバイナリのこれらのビット位置（サフィックス）はすべて、2 ^ 0 ^の場所の値に「1」があります。
ビット位置b〜2〜、b〜3〜、b〜6〜、b〜7〜などに存在するものの数に基づいて、c〜2〜の値を見つけます。同等のバイナリのこれらすべてのビット位置（サフィックス）は、2 ^ 1 ^の場所の値に「1」があります。
ビット位置b〜4〜、b〜5〜、b〜6〜、b〜7〜などに存在するものの数に基づいて、c〜3〜の値を見つけます。同等のバイナリのこれらすべてのビット位置（サフィックス）は、2 ^ 2 ^の場所の値に「1」があります。
同様に、チェックビットの他の値を見つけます。

受信データのチェックビットに相当する10進数は、エラーが存在するビット位置の値を示します。そのビット位置に存在する値を補完するだけです。したがって、パリティビットを削除した後、元のバイナリコードを取得します。

例1

バイナリコードのハミングコード、d〜4〜d〜3〜d〜2〜d〜1〜 = 1000を見つけましょう。偶数パリティビットを考慮してください。

指定されたバイナリコードのビット数はn = 4です。

次の数学的な関係を使用して、必要なパリティビット数を見つけることができます。

2 ^ k \ geq n + k + 1

上記の数学的関係では、n = 4に置き換えます。

\右矢印2 ^ k \ geq 4 + k + 1

\右矢印2 ^ k \ geq 5 + k

上記の関係を満たすkの最小値は3です。したがって、3つのパリティビットp〜1〜、p〜2〜、およびp〜3〜が必要です。したがって、バイナリコードには4ビット、パリティビットは3ビットあるため、ハミングコードのビット数は7になります。以下に示すように、ハミングコードにパリティビットとバイナリコードのビットを配置する必要があります。

7ビットハミングコード*は$ b _ \ {7} b _ \ {6} b _ \ {5} b _ \ {4} b _ \ {3} b _ \ {2} b _ \ {1} = d _ \ {4 } d _ \ {3} d _ \ {2} p _ \ {3} d _ \ {1} p _ \ {2} bp _ \ {1} $

バイナリコードのビットを代入すると、ハミングコードは$ b _ \ {7} b _ \ {6} b _ \ {5} b _ \ {4} b _ \ {3} b _ \ {2} b _ \ {1} = 100p _ \ {3} Op _ \ {2} p _ \ {1} $。次に、パリティビットを見つけましょう。

p _ \ {1} = b _ \ {7} \ oplus b _ \ {5} \ oplus b _ \ {3} = 1 \ oplus 0 \ oplus 0 = 1

p _ \ {2} = b _ \ {7} \ oplus b _ \ {6} \ oplus b _ \ {3} = 1 \ oplus 0 \ oplus 0 = 1

p _ \ {3} = b _ \ {7} \ oplus b _ \ {6} \ oplus b _ \ {5} = 1 \ oplus 0 \ oplus 0 = 1

これらのパリティビットを代入すると、*ハミングコード*は$ b _ \ {7} b _ \ {6} b _ \ {5} b _ \ {4} b _ \ {3} b _ \ {2} b _ \ {1} =になります1001011 $。

例2

上記の例では、ハミングコードを$ b _ \ {7} b _ \ {6} b _ \ {5} b _ \ {4} b _ \ {3} b _ \ {2} b _ \ {1} = 1001011 $として取得しました。次に、受け取ったコードが$ b _ \ {7} b _ \ {6} b _ \ {5} b _ \ {4} b _ \ {3} b _ \ {2} b _ \ {1} =の場合のエラー位置を見つけましょう1001111 $。

次に、チェックビットを見つけましょう。

c _ \ {1} = b _ \ {7} \ oplus b _ \ {5} \ oplus b _ \ {3} \ oplus b _ \ {1} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1

c _ \ {2} = b _ \ {7} \ oplus b _ \ {6} \ oplus b _ \ {3} \ oplus b _ \ {2} = 1 \ oplus 0 \ oplus 1 \ oplus1 = 1

c _ \ {3} = b _ \ {7} \ oplus b _ \ {6} \ oplus b _ \ {5} \ oplus b _ \ {4} = 1 \ oplus 0 \ oplus 0 \ oplus1 = 0

チェックビットの10進値は、受信したハミングコードのエラーの位置を示します。

c _ \ {3} c _ \ {2} c _ \ {1} = \ left（011 \ right）_ \ {2} = \ left（3 \ right）_ \ {10}

したがって、ハミングコードの3番目のビット（b〜3〜）に存在するエラー。元のバイナリコードを取得するために、そのビットに存在する値を補完し、パリティビットを削除するだけです。

Digital-circuits-error-detection-correction-codes

目次

エラー検出および修正コード

パリティコード

偶数パリティコード

奇数パリティコード

ハミングコード

例1

例2