纠错码

Question

我需要在短消息( 100到200比特)上使用纠错技术。可用于添加冗余比特的空间被限制在20-50%。

我将不得不用C/C++实现编码和解码。因此，它要么需要开源，要么需要足够容易编程。(我过去在解码算法方面有一些经验-它们太可怕了！)

有没有人可以建议使用合适的错误代码(以及相关的参数)？

Answer 1

看一看里德·所罗门纠错。

here提供了C++中的示例实现。

有关不同的选项，请查看here -请参阅第11项

编辑:如果你想要一个商业库- http://www.schifra.com/faq.html

Answer 2

里德-所罗门编码器以RS(容量，有效载荷)的形式描述。容量始终为2^SYMBOL-1，其中symbol是每个里德-所罗门符号中的比特数。通常，该符号大小是8比特(正常字节)。它通常可以是3到16位的任何内容。对于8位符号，里德-所罗门编码器将被命名为RS(255，有效载荷)。

有效载荷是非奇偶校验符号的数量。如果需要4个奇偶校验符号，则应指定RS(255,251)。

要有效地纠正数据块中的错误，必须首先将数据打包为符号(位组，通常仅为8位字节)。您的目标是尝试安排(如果可能)将任何错误聚集到尽可能少的符号中。

例如，如果平均每8位出现一个错误，那么8位符号将是不合适的；几乎每个符号都会有错误！您可以使用4位符号，并使用RS(15, 11 )编解码器--一次最多可使用11个4位符号，每个块产生4个奇偶校验符号。符号大小越小，容量越小(例如，对于4位的码元大小，2^4-1 == 15码元容量)。

但通常情况下，您将使用8位符号。如果你有一个更实际的错误率，比如说，你的8位符号中有10%是错误的，那么你可以使用RS( 255 , 205 ) --每255个符号50个奇偶校验符号，里德-所罗门“码字”，最大有效负载为205字节。这给了我们大约25%的奇偶性，允许我们纠正一个包含多达12.5%的错误的码字。

使用https://github.com/pjkundert/ezpwd-reed-solomon的c++/ezpwd/rs Reed-Solomon API，您可以将其指定为：

#include <ezpwd/rs>
...
ezpwd::RS<255,205> rscodec;

将数据放入std::string (它可以很好地处理原始8位二进制数据)或std::vector中，并调用API，添加50个奇偶校验符号：

std::string data;
// ... fill data with a fixed size block, up to 205 bytes
rscodec.encode( data );

发送数据，稍后，在收到data+parity后，恢复原始数据(并丢弃50个奇偶校验符号)：

int corrected = rscodec.decode( data );

如果可以恢复数据，将返回纠正的符号数，如果里德-所罗门码字包含太多错误，则返回-1。

享受吧！