用于在n位生成大小k错误校正代码的算法

Question

我想在n位上生成一个代码，以针对我要分类的k个不同输入。该代码的主要要求是错误校正标准：最大化不同输入的任何两个编码之间的最小成对距离是最大化的。我不需要确切地说 - 大约会做到这一点，并且易于使用和计算实现的速度也是优先事项。

通常，n将在数十个数百个k中。

另外，在k不同的n位二进制编码之间的最小锤距离上是否有相当紧密的结合？

Answer 1

为给定参数找到确切的最佳错误校正代码的问题非常困难，即使大约最佳代码也很难。最重要的是，有些代码没有任何不错的解码算法，而对于其他代码来说，解码问题非常棘手。

但是，您正在询问n ≫k的特定参数范围，如果我正确理解，您想要k维的长度n。 （以便k位用n位编码。）在此范围内，首先，随机代码可能具有很好的最小距离。唯一的问题是，解码是从不切实际到难治的任何地方，实际上计算最小距离也不是那么容易。

其次，如果您需要为案例n≫k的明确代码，那么您可以通过 BCH代码 Q = 2。正如Wikipedia页面所解释的那样，BCH代码有一个很好的解码算法。

关于最小锤距的上限 锤子绑定, ，也称为体积结合或球形堆积。边界的想法简单而美丽：如果最小距离为t，则代码可以校正到距离地板（（T-1）/2）。如果您可以将错误纠正到一定半径，则意味着该半径的锤击球不会重叠。另一方面，可能的单词总数为2ⁿ, ，因此，如果将其除以一个锤球中的点数（在二进制情况下是二项式系数的总和），则您会在无错误的代码单词的数量上获得上限。可以击败这个绑定，但是对于很大的最小距离，这并不容易。在这个制度中，这是一个非常好的界限。