用於在n位上生成大小爲k的糾錯碼的算法

Question

我想爲要分類的k個不同輸入生成n位代碼。此代碼的主要要求是糾錯標準：任何兩個不同輸入編碼之間的最小成對距離最大化。我不需要它是確切的 - 大概會做，易用性和計算實施的速度也是一個優先事項。

一般來說，n將會在幾百，幾十k。

此外，k個不同的n位二進制編碼之間的最小海明距離是否存在相當嚴格的界限？

Answer 1

尋找給定參數的確切最佳糾錯碼的問題非常困難，即使大約最好的碼也很難。最重要的是，一些代碼沒有任何體面的解碼算法，而對於其他代碼，解碼問題相當棘手。

然而，你問的是一個特定的參數範圍，其中n >> k，如果我理解正確，你需要一個長度爲n的k維碼。 （所以k比特用n比特編碼。）在這個範圍內，首先，一個隨機碼可能有非常好的最小距離。唯一的問題是解碼從不切實際到可解碼的任何地方，實際上計算最小距離也不是那麼容易。第二，如果你想要一個明確的代碼n的情況下，那麼你可以做一個BCH code與q = 2相當不錯。正如維基百科頁面所解釋的，BCH碼有一個很好的解碼算法。

關於最小漢明距離的上限，在n»k的範圍內，您應該從Hamming bound開始，也就是所謂的體積界限或球體打包界限。邊界的思想簡單而美觀：如果最小距離是t，那麼代碼可以糾正直到距離底部（（t-1）/ 2）的誤差。如果您可以將誤差修正到某個半徑，則意味着該半徑的漢明球不重疊。另一方面，可能的單詞總數爲2 ⁿ，所以如果用一個漢明球（在二進制情況下是二項係數的和）中的點數除以得到一個上限關於無錯碼字的數量。有可能擊敗這個界限，但是對於大的最小距離來說這並不容易。在這個制度中，這是一個非常好的約束。