2

我正在建立一个 Reed Solomon 库来纠正和检测进来的错误。为简单起见，让我们看一下 Reed Solomon 配置，其中

m(symbol size)    : 8 [GF(256)]
k(user payload)   : 2
2T(parity symbols): 2

Yielding a transmitted payload of 4 octets.

这可以纠正任何 1 个符号错误，并且，这篇文章的目的，它可以检测 2 个符号错误。关于 RS 错误检测的文献有限，但您可以查看Wikipedia 文章中的简介：

通过将 t 个校验符号添加到数据中，Reed-Solomon 码可以检测最多（包括）错误符号的任意组合，或者纠正最多（包括）⌊t/2⌋ 符号的任何组合。

然而，这似乎与我的观察不符。

我有一个库，主要是根据这篇文章构建的。

据我所知，效果很好。我围绕我们的实现设置了一个详尽的测试，发现有 2 个符号错误（据我理解应该是可检测的）但事实并非如此。据我了解，一个简单的检查来查看是否发生了通过正常检查的不可纠正的错误（即错误定位器是有效的，发现错误具有有效的错误计数，多项式次数是有效的）是重新计算的伴随式更正的消息。如果校正子不为零，那么我们仍然有错误。但是，当我这样做时，校正子全为 0，表明没有发现错误，并且我们在具有 1 个错误符号的错误向量和具有 2 个错误符号的错误向量之间存在冲突。

这是测试：

# Create Message
msg_in = [0x10,0x2f]
# Append RS FEC codes
msg_enc = rs_encode_msg(msg_in)

# Apply Error
errVec = [0,0x2b,0,0xea]
for i,err in enumerate(errVec):
        msg[i] ^= err;

# Decode
# Syndromes
synd = rs_calc_syndromes(msg)
# Error Locator
err_loc = rs_find_error_locator(synd)
# Error Positions
pos = rs_find_errors(err_loc)
# Correct
msg = rs_correct_errata(msg, synd, pos, err_loc)

#Calculate syndromes again
newSynd = rs_calc_syndromes(msg)

输出：

Message
0x10 0x2f 

Encoded Message
0x10 0x2f 0x1 0x3e 

Encoded Message With Errors
0x10 0x4 0x1 0xd4

Syndromes
0xc1 0x46 
Error Locator
0x8 0x1
Error Position
0x00 # The first position

Corrected Message
0xd1 0x4 0x1 0xd4

Recalculated Syndromes
0x0 0x0

如果你还在阅读，谢谢。我知道我没有提供整个库，但我确实提供了输入、输出和关键变量值。我想知道的是我上面写的理解是否错误；我们可以检测 2T 符号错误，其中 2T 是添加符号的数量。因为从这个测试用例中似乎存在冲突，我通过计算以下错误向量中的伴随式来进一步测试这一点，这些错误向量进一步支持冲突，并且 Reed Solomon 不一定能检测到 2T 以内的所有错误。让我知道我是否错了。

error vector: 0xc1 0x0 0x0 0x0
yielding syndrome: 0xc1 0x46

和

error vector: 0x0 0x2b 0x0 0xea
yielding syndrome: 0xc1 0x46

有碰撞

4

1 回答 1

2

对于两个奇偶校验符号，校验子仅对单个符号错误是唯一的，这就是它们可用于纠正单个符号错误的原因。在两个符号错误的情况下，对于两个错误位置和两个错误值的所有组合（这就是为什么两个符号如果只有两个奇偶校验符号，则无法纠正错误）。

使用两个奇偶校验符号，汉明距离为 3 个符号。每个有效（零校正子 == 生成多项式的精确倍数）代码字与每个其他有效代码字至少相差 3 个符号，因此不会出现 2 个符号错误情况是有效（零校正子）代码字。

错误位置和值的 3 种或更多错误情况组合可能产生校正子 == 0。最简单的示例是采用有效的代码字（零错误消息），并对 3 符号生成多项式中的任何位置进行异或消息，这将是另一个有效的代码字（生成多项式的精确倍数）。

此外，还有一个最大长度的码字。对于您正在使用的 BCH 类型 Reed Solomon 代码，对于 GF(2^n)，它是 (2^n)-1 个符号。如果消息包含 2^n 或更多符号（包括奇偶校验符号），则在 message[i] 和 message[i + 2^n - 1] 处具有相同错误值的两个错误情况将产生零校正子。对于原始视图类型 Reed Solomon 码，最大长度码字为 2^n（比 BCH 类型多一个符号），但它很少使用，因为解码操作的是整个消息，而 BCH 解码操作的是伴随式。

更新 - 我忘了提到，对于两个奇偶校验符号，尝试对两个错误消息执行一个错误更正可能最终导致第三个错误，这将导致一个有效的代码字（综合症将为零），但一个不同来自三个位置的原始码字。

如果码字被缩短，这种情况发生的概率就会降低，因为任何不在缩短码字范围内的计算位置都将是检测到的错误。如果有n个符号（包括奇偶符号），则基于计算的位置在范围内的单个错误纠错的概率约为n/255。

在这种情况下，代码字大小为 4 字节，我在可能的 390150 两个错误案例中找到了 3060 个，通过执行单个错误更正最终会产生第三个错误，这将创建一个有效的代码字。

于 2019-06-21T22:23:12.360 回答