分類したいk個の異なる入力に対してnビットのコードを生成したいと思います。このコードの主な要件は、エラー訂正基準です。つまり、異なる入力の任意の2つのエンコーディング間の最小ペアワイズ距離が最大化されることです。正確である必要はありません。概算で十分です。使いやすさと計算の実装の速度も優先事項です。
一般に、nは数百、kは数十になります。
また、k個の異なるnビットバイナリエンコーディング間の最小ハミング距離にかなり厳しい境界がありますか？
1 に答える
3
与えられたパラメータに対して正確に最良のエラー訂正コードを見つける問題は非常に困難であり、ほぼ最良のコードでさえ困難です。その上、一部のコードには適切なデコードアルゴリズムがありませんが、他のコードではデコードの問題が非常に複雑です。
ただし、n≫ kである特定の範囲のパラメーターについて質問しています。ここで、私が正しく理解していれば、長さnのk次元コードが必要です。（したがって、kビットはnビットでエンコードされます。）この範囲では、最初に、ランダムコードの最小距離が非常に良好である可能性があります。唯一の問題は、デコードが実用的でないものから扱いにくいものまであり、実際に最小距離を計算することもそれほど簡単ではないということです。
次に、ケースn≫ kの明示的なコードが必要な場合は、q=2のBCHコードでかなりうまくいくことができます。ウィキペディアのページで説明されているように、BCHコードには優れたデコードアルゴリズムがあります。
最小ハミング距離の上限については、n≫ kの範囲で、体積限界または球充填限界としても知られるハミング限界から開始する必要があります。境界の考え方は単純で美しいです。最小距離がtの場合、コードは距離floor（（t-1）/ 2）までのエラーを修正できます。ある半径までエラーを修正できる場合、それはその半径のハミングボールが重なっていないことを意味します。一方、可能な単語の総数は2nです。したがって、これを1つのハミングボールのポイント数（バイナリの場合は二項係数の合計）で割ると、エラーのないコードワードの数に上限があります。この限界を超えることは可能ですが、最小距離が大きい場合は簡単ではありません。この体制では、それは非常に良い限界です。
于 2010-07-04T18:44:29.517 に答える