我想为我想分类的k个不同输入生成一个n位的代码。该代码的主要要求是纠错准则：最大化了不同输入的任意两个编码之间的最小成对距离。我不需要它精确-近似会做，易于使用和速度的计算实现也是一个优先事项。
一般来说，n是几百，k是几十。
另外，k个不同的n位二进制编码之间的最小汉明距离是否有一个合理的紧界？
最佳答案
找到给定参数的最佳纠错码的问题是非常困难的，甚至近似最佳码也是困难的。除此之外，一些代码没有任何像样的解码算法，而对另一些代码来说，解码问题相当棘手。
但是，你要问的是一个特定的参数范围，其中n k，如果我理解正确，你需要一个长度为n的k维码（这样k位就被编码成n位）。在这个范围内，首先，随机码可能有很好的最小距离。唯一的问题是解码是从不切实际到棘手的任何地方，实际上计算最小距离也不是那么容易。
其次，如果你想要一个关于n≫k的显式代码，那么你可以用q=2的aBCH code做得相当好正如wikipedia页面所解释的，bch码有一个很好的解码算法。
关于最小Hamming距离的上界，在n≫k范围内，应该从Hamming bound开始，也称为体积界或球体填充界边界的概念是简单而漂亮的：如果最小距离是t，那么代码可以在距离楼层（（t-1）/2）之前纠正错误。如果你能把误差修正到某个半径，那就意味着这个半径的汉明球不会重叠。另一方面，可能的单词总数是2n，所以如果你把它除以一个hamming球中的点数（在二进制情况下是二项系数之和），你就得到了无错误代码单词数的上界。有可能突破这一界限，但对于较大的最小距离，这并不容易。在这个政权里，这是一个很好的约束。
关于algorithm - 在n位上生成大小为k的纠错码的算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/3175717/