生成 n 位大小为 k 的纠错码的算法

Question

我想为要分类的 k 个不同输入生成 n 位代码。该代码的主要要求是纠错标准:最大化不同输入的任意两个编码之间的最小成对距离。我不需要它是精确的 - 近似值就可以了，易用性和计算实现的速度也是一个优先事项。

一般情况下，n在几百，k在几十。

此外，k 个不同的 n 位二进制编码之间的最小汉明距离是否有合理的严格界限？

Answer 1

为给定参数找到准确的最佳纠错码的问题非常困难，即使是近似最佳的代码也很难。最重要的是，一些代码没有任何像样的解码算法，而对于其他代码，解码问题非常棘手。

但是，您询问的是特定范围的参数，其中 n >> k，如果我理解正确的话，您需要一个长度为 n 的 k 维代码。 (这样k位编码成n位。)在这个范围内，首先，一个随机码很可能有很好的最小距离。唯一的问题是解码从不切实际到棘手，而且实际计算最小距离也不是那么容易。

其次，如果你想要 n >> k 情况下的显式代码，那么你可以用 BCH code 做得相当好q=2。正如维基百科页面所解释的那样，有一个很好的 BCH 码解码算法。

关于最小汉明距离的上限，在 n ≫ k 范围内，您应该从 Hamming bound 开始，也称为体积边界或球堆积边界。边界的想法简单而优美:如果最小距离为 t，则代码可以纠正距离 floor((t-1)/2) 内的错误。如果您可以将误差校正到某个半径范围内，则意味着该半径的汉明球不会重叠。另一方面，可能的单词总数是 2ⁿ，因此如果将其除以一个汉明球中的点数(在二进制情况下是二项式系数的总和)，您将获得无错误代码字数的上限。有可能突破这个界限，但对于较大的最小距离来说，这并不容易。在这种情况下，这是一个很好的界限。