math - 随着错误率的增加，纠错码的开销

Question

我正在寻求帮助，以了解与纠错码（如 reed-solomon）相关的开销（需要传输的额外符号的数量），因为它旨在处理的错误率增加。例如，如果一个进程需要能够纠正每 500 个错误符号中的 1 个错误符号，那么与 100 个中的 1 个相比，该开销是多少。

我意识到在实践中经常使用复杂的方案（CD 使用重叠的编码集等），但我试图首先了解最简单的情况。开销和错误率之间的关系是近似线性的吗？二次方？指数？我意识到大 O 符号在这里不是正确的工具，所以如果这不是数学社区通常提出问题的方式，请原谅我。

对于计算与以下 reed-solomon 编码错误率相关的开销的答案，我会很兴奋：

每 10000 个 1 个符号错误 每 2000 个 1 个符号错误 每 1000 个 1 个符号错误 每 500 个 1 个符号错误 每 50 个 1 个符号错误

Answer 1

寻找汉明界。在那里您将看到具有汉明距离 d的代码，即可以检测d -1 个个位数错误并纠正t =⌊( d -1)/2⌋ 个个位数错误的代码，其大小最多为

不同的代码字。现在对于最简单的情况，假设二进制代码。因此假设q =2 作为字母大小，n =2 ^b作为b位的码字数。然后上述界限的以二为底的对数将为您提供实际可以通信的最大位数，而码率将是这两个位数之间的比率。

当您根据容错来表示码率时，您可能想要调查大码字的限制。为此，您可以将错误的绝对数量转换为错误率，以便错误数量与代码长度成正比。然后应该有可能获得有用的限制。