次のプロパティを持つデータ転送メディアからのデータのチャンクがあるとします。
この場合に最適なエラー検出およびエラー訂正アルゴリズムは何ですか? もちろん、チャンクごとの有用なデータ量と成功検証 (修正) 確率の間の妥協点は常にあります。
開始点を決定する方法には答えないので、これは完全な質問に対する部分的な答えにすぎません。そのためのmcdowellaの答えを参照してください。コメントを意図したのですが、長すぎます。
継続的に送信されるメッセージにより、エラー訂正の必要はもうありません。1つのビットフリップ（またはそれらの束）が発生した場合でも、送信される同じビットのすべてのインスタンスに影響を与える可能性はほとんどありません。特に、それが永久に繰り返される場合はそうです。したがって、この意味で、冗長係数はNであり、ブロードキャストが進むにつれてNは無限大に近づきます。
したがって、確認するサンプルが多数あるため、64ビットの再構築は非常に簡単になりました。受信者がサイクル長を知っていると仮定すると、ストリームをポーリングして、64の位置のそれぞれについて各ビットの出現回数を数えることができます。
つまり、100回の完全なサイクルの後、次のようになります。
Bit # 0s / 1s Interpret bit as
Bit 0: 100 / 0 0
Bit 1: 0 / 100 1
Bit 2: 99 / 1 0
Bit 3: 98 / 2 0
Bit 4: 1 / 99 1
...
Bit 63: 96 / 4 0
これらのサンプルに基づいて、正しいビット値が何であるかを統計的に把握できます。受信者がサイクルを受信し続ける時間が長いほど、境界は強くなります。したがって、十分なサイクルが転送されれば、任意の高いエラー率を許容できます。
もちろん、これは64ビットだけでなくすべてのサイクル長に適用されます。したがって、この方法をmcdowellaの方法と組み合わせてください（そして、データサイズはおそらくindex-foot-printのために増加します）。
サイクル周期が受信者に知られていない場合、それを理解する2つの方法があります。
長さを推測し、ポーリングを実行します。相関が非常に高い長さになるまで、さまざまな長さでこれを繰り返します。（各ビットの信頼水準が高い）
受信したデータに対してフーリエ変換を実行します。これにより、データのノイズがそれほど大きくないことを前提として、期間が即座に明らかになります。
これは、 http://en.wikipedia.org/wiki/Frame_Relayからいくつかのアイデアをつまんだ試みです。
01110 の固定ヘッダーで各 64 ビット チャンクを開始します。より多くのヘッダー情報 (シーケンス番号または代替ビット フラグ、チェックサムなど) がある場合は、ビット パターン 01110 が表示されないように調整できます。任意のデータの場合、0111 を 01111 に置き換えます。これは、有効なデータ レートが基礎となるデータに依存するようになったことを意味します。このレイヤーへのデータのプロバイダーに、たとえばhttp://en.wikipedia.org/wiki/Randomizerを適用して、データがかなりランダムであることを確認してもらいます。ここでの合計データ損失は約 6 ビットだと思います。これは、0..63 のシフトを記述するのに必要な 6 ビットに適合します。
レシーバーで 01110 を探して、チャンクの真の開始をマークします。そのようなパターンが 1 つも見られない場合は、チャンクが文字化けしていることがわかります。既存の 01110 を破壊し、偽の 01110 を生成するには、少なくとも 2 ビットのエラーが必要だと思います。
チャンクのミスアラインメントを引き起こす文字化けは、典型的なビット文字化けのようには見えないため、CRC エラー率の計算はそのままでは適用されません。各チャンクに非 CRC チェックサムを含めます。おそらく、禁止されている 5 ビット パターン 01110 を回避するために mod 31 または mod 961 で計算されたチェックですが、これに何に隣接するかによっては、より制限する必要がある場合があります。多項式 CRC とは異なり、エラーが検出されない可能性は約 31 分の 1 または 961 分の 1 であり、すべての単一エラーについて特定の保証はありません。
チャンクごとのエラー修正を賢明に行うのに十分なスペースがあるとは思いませんが、列に適用される SECDED などを使用して、M 個の通常のチャンクごとに N 個のエラー修正チャンクを含めることができます。たとえば、57 個のデータ ベアリング チャンクと 6 個のエラー訂正チャンクがあり、各ペイロード ビット位置を 57 データ ビットと 6 個のチェックサム ビットを持つものとして扱います。これは、たとえばチャンクの再整列が失敗するなど、エラーによって 1 つのチャンクがすべて破損するか、まったく破損しない場合にうまく機能します。
コメントの後 -
編集
OK、1 つのメッセージを継続的に送信すると、帯域幅は少なくなりますが、CPU は比較的多くなります。次の 2 つのことが思い浮かびます。
1) メッセージに何らかのチェックサムまたはその他の制約がある場合、たとえば、すべてのシングル ビット エラーを考慮し、受信したメッセージのビットを反転させ、チェックサムが機能するかどうかを確認することにより、限定的なエラー修正を実現できます。
2) メッセージを介して渡された 5 ビット ウィンドウのみを調べることで、メッセージが上記のビット スタッフィング スキームに準拠しているかどうかを確認できます。ラップアラウンドで適切に動作するように微調整する必要がある場合でも、これは当てはまると思います。これは、扱いやすいサイズの BDD によってメッセージをチェックできることを意味します (Knuth 4A セクション 7.1.4)。これは、ビット スタッフィング スキームに準拠する 64 ビット メッセージの数をカウントし、メッセージ番号とメッセージの間で効率的に変換できることを意味します (同じセクション)。したがって、送信されるデータに関するランダム化や最悪のケースの仮定を基にすることなく、このスキームを使用できます。これは、範囲 0..N (N は BDD を介して計算されます) の数値のエンコーディングと見なすだけで、 64 ビット メッセージ。実際、それほどエレガントではありませんが、BDD の代わりに 5 ビット状態の動的計画法を使用できると思います。