アルゴリズムを発生させるためのサイズk誤り訂正コードnビット

Question

いを生成するコードnビットのための入力をしたい分類.主要このコードの誤り訂正基準る最低限のpairwise距離他のエンコーディングの異なる入力を最大限に引き出します.もいらないので正確-近似すい、使いやすさと速度の計算実施に優先します。

一般に、nの数百人、kの十数.

また、ある場合には合理的に逼迫が大きくなるにつれ形成される最低限のハミング距離k異なるnビットのバイナリエンコーディング?

Answer 1

指定されたパラメーターの正確なエラー修正コードを見つける問題は非常に困難であり、ほぼ最高のコードであっても難しいです。それに加えて、一部のコードにはまともなデコードアルゴリズムがありませんが、他のコードではデコードの問題は非常に難しいです。

ただし、n≫ kの特定の範囲のパラメーターについて尋ねています。 （そのため、KビットがNビットでエンコードされます。）この範囲では、最初に、ランダムコードは非常に良好な最小距離を持つ可能性があります。唯一の問題は、デコードが非現実的なものから操作可能なものまでであり、実際に最小距離を計算することもそれほど簡単ではないということです。

第二に、ケースn≫Kの明示的なコードが必要な場合は、 BCHコード q = 2で。 Wikipediaページが説明するように、BCHコードには優れたデコードアルゴリズムがあります。

最小ハミング距離の上限に関しては、範囲n≫kで始める必要があります。 ハミングバウンド, 、ボリュームバウンドまたは球体パッキングバウンドとも呼ばれます。バインドのアイデアはシンプルで美しいです。最小距離がTの場合、コードは距離床までエラーを修正できます（（T-1）/2）。エラーを半径まで修正できる場合、その半径のハミングボールが重複しないことを意味します。一方、可能な単語の総数は2ですⁿ, 、したがって、それを1つのハミングボール（バイナリケースでは二項係数の合計）のポイント数で割ると、エラーのないコードワードの数に上限が得られます。この境界を打ち負かすことは可能ですが、最小距離が大きい場合は簡単ではありません。この体制では、それは非常に良い境界です。