バーガーコード

電気通信において、バーガー符号は一方向の誤り検出符号であり、発明者である JM バーガーにちなんで名付けられました。バーガー符号は、すべての一方向の誤りを検出できます。一方向の誤りとは、非対称チャネルなどで、1 を 0 に反転するか、0 を 1 に反転するだけの誤りです。バーガー符号のチェック ビットは、情報ワード内のすべての 0 を数え、その数を自然 2 進数で表すことによって計算されます。情報ワードがビットで構成されている場合、バーガー符号には「チェック ビット」が必要となり、長さ k+n のバーガー符号になります (言い換えると、チェック ビットは情報ビットまでチェックするのに十分です)。バーガー符号は、同じコード ワードで 0 から 1 への誤りが発生しない限り、任意の数の 1 から 0 へのビット反転誤りを検出できます。同様に、バーガー符号は、同じコード ワードで 1 から 0 へのビット反転誤りが発生しない限り、任意の数の 0 から 1 へのビット反転誤りを検出できます。バーガー符号では、いかなる誤りも訂正できません。 ${\displaystyle n}$${\displaystyle k=\lceil \log _{2}(n+1)\rceil }$${\displaystyle k}$${\displaystyle n=2^{k}-1}$

すべての一方向エラー検出コードと同様に、バーガー コードも遅延に敏感でない回路 で使用できます。

上で述べたように、バーガー コードは任意の数の単方向エラーを検出します。特定のコード ワードに対して、発生したエラーが値 1 の一部 (またはすべて) のビットが値 0 に変更されたことだけである場合、この変換はバーガー コードの実装によって検出されます。その理由を理解するには、次の 3 つのケースがあると考えてください。

1. コードワードの情報部分の一部の 1 ビットが 0 に変更されました。
2. コードワードのチェック (または冗長) 部分の一部の 1 ビットが 0 に変更されました。
3. 情報部分とチェック部分の両方で、一部の 1 ビットが 0 に変更されました。

ケース 1 の場合、エラーの定義により、情報セクションの 0 値ビットの数が増加します。したがって、Berger チェック コードはデータの実際の 0 ビット数よりも低くなり、チェックは失敗します。

ケース 2 では、情報セクションの 0 値ビットの数は同じままですが、チェック データの値は変更されています。一部の 1 が 0 に変わったことはわかっていますが、0 が 1 に変わったことはありません (これがこのケースのエラー モデルの定義方法です)。そのため、チェック データのエンコードされたバイナリ値は下がります (たとえば、バイナリ 1011 から 1010、または 1001、または 0011)。情報データは同じままであるため、以前と同じ数の 0 があり、変更されたチェック値と一致しなくなります。

情報セクションとチェックセクションの両方でビットが変更されたケース 3 では、ケース 1 で説明したように情報セクションのゼロの数が増え、ケース 2 で説明したようにチェック部分に格納されているバイナリ値が減っていることに注意してください。したがって、2 つが変化して別の有効なコードワードになる可能性はありません。

発生するエラーが 0 値のビットの一部が 1 に変わることだけである場合、同様の分析を実行でき、完全に有効です。したがって、特定のコードワードで発生するすべてのエラーが同じ方向に発生する場合、これらのエラーは検出されます。たとえば、送信される次のコードワードでは、エラーが反対方向に発生する可能性がありますが、すべてが互いに同じ方向である限り、エラーは検出されます。

一方向エラーは、特定の状況ではよく発生します。たとえば、フラッシュ メモリでは、ビットを 1 にリセットするよりも、0 にプログラムする方が簡単です。

• JM Berger (1961年3月)。「非対称チャネルのエラー検出コードに関するメモ」。情報制御。4 (1): 68–73。doi : 10.1016/ S0019-9958 (61)80037-5。
• Subhasish Mitra および Edward J. McCluskey、「どの同時エラー検出方式を選択すべきか?」、信頼性の高いコンピューティング センター、スタンフォード大学、2000 年。
• Tom Verhoeff (1988 年 3 月)。「遅延に敏感でないコード - 概要」(PDF)。分散コンピューティング。3 ( 1): 1–8。doi :10.1007/BF01788562。S2CID 8568354  。