python - Reed Solomon 错误检测能力不是 2T

Question

我正在设置 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 article 中的介绍。 :

By adding t check symbols to the data, a Reed–Solomon code can detect any combination of up to and including t erroneous symbols, or correct up to and including ⌊t/2⌋ symbols.

但这似乎与我的观察不符。

我有一个图书馆，主要是从 this article 构建的.

据我所知，它运行良好。我围绕我们的实现进行了详尽的测试，发现有 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 

有碰撞

Answer 1

对于两个奇偶校验符号，校正子将仅对单个符号错误是唯一的，这就是它们可用于纠正单个符号错误的原因。在两个符号错误的情况下，校正子将是非零的(其中一个可能为零，但不会同时为零)，但对于两个错误位置和两个错误值的所有组合(这就是为什么两个符号如果只有两个奇偶校验符号，则无法纠正错误。

对于两个奇偶校验符号，汉明距离为 3 个符号。每个有效(零综合症 == 生成多项式的精确倍数)代码字与其他所有有效代码字至少相差 3 个符号，因此没有 2 个符号错误的情况会显示为有效(零综合症)代码字。

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

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

---

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

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

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