4

我需要对短消息(100 到 200 位之间)使用纠错技术。可用于添加冗余位的空间限制为 20-50%。

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

任何人都可以建议使用合适的错误代码(带有相关参数)吗?

4

2 回答 2

9

看看 Reed Solomon 纠错。

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

如需不同的选项,请查看此处- 参见项目 #11

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

于 2012-06-28T11:13:12.430 回答
2

Reed-Solomon 编码器以 RS(CAPACITY,PAYLOAD) 的形式描述。容量始终为 2^SYMBOL-1,其中 SYMBOL 是每个 Reed-Solomon 符号中的位数。很多时候,这个 SYMBOL 大小是 8 位(一个普通字节)。它通常可以是 3 到 16 位之间的任何值。对于 8 位符号,Reed-Solomon 编码器将命名为 RS(255,PAYLOAD)。

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

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

例如,如果平均每 8 位发生一次错误,则 8 位符号将不合适;几乎每个符号都会有错误!您可能会选择 4 位符号并使用 RS(15,11) 编解码器——一次最多可处理 11 个 4 位符号,每个块产生 4 个奇偶校验符号。符号大小越小,容量越低(例如,对于 4 位的符号大小,2^4-1 == 15 个符号容量)。

但通常,您会使用 8 位符号。如果您有更实际的错误率,例如 10% 的 8 位符号是错误的,那么您可以使用 RS(255,205)——每 255 个符号 Reed-Solomon“码字”有 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 );

发送您的数据,稍后,在您收到数据+奇偶校验后,恢复原始数据(并丢弃 50 个奇偶校验符号):

int corrected = rscodec.decode( data );

如果数据可以恢复,将返回纠正的符号数,如果 Reed-Solomon 码字包含太多错误,则返回 -1。

享受!

于 2015-02-10T01:15:08.067 回答