我想为要分类的 k 个不同输入生成 n 位代码。该代码的主要要求是纠错标准：不同输入的任意两个编码之间的最小成对距离最大化。我不需要它是精确的——近似就可以了，易用性和计算实现的速度也是一个优先事项。
一般来说，n 将在数百个中，k 在数十个中。
此外，k 个不同的 n 位二进制编码之间的最小汉明距离是否有合理的严格限制？
问问题
487 次
1 回答
3
为给定参数找到准确的最佳纠错码是非常困难的，即使是近似最佳的代码也很困难。最重要的是，一些代码没有任何像样的解码算法，而对于其他代码来说，解码问题非常棘手。
但是，您询问的是 n ≫ k 的特定参数范围，如果我理解正确，您需要长度为 n 的 k 维代码。（因此 k 位被编码为 n 位。）在这个范围内，首先，随机码可能具有非常好的最小距离。唯一的问题是解码从不切实际到难以处理，实际上计算最小距离也不是那么容易。
其次，如果你想要一个 n ≫ k 的显式代码，那么你可以使用 q=2的BCH 代码做得相当好。正如维基百科页面所解释的，BCH 代码有一个很好的解码算法。
关于最小汉明距离的上限，在 n ≫ k 范围内，您应该从汉明界开始，也称为体积界或球体堆积界。边界的想法简单而优美：如果最小距离为 t，那么代码可以将错误纠正到距离 floor((t-1)/2)。如果您可以将错误纠正到某个半径，则意味着该半径的汉明球不重叠。另一方面，可能的单词总数为 2 n，所以如果你将它除以一个汉明球中的点数（在二进制情况下是二项式系数的总和），你会得到无错误码字数量的上限。有可能突破这个界限，但对于较大的最小距离来说，这并不容易。在这个制度下，这是一个很好的界限。
于 2010-07-04T18:44:29.517 回答