Reed Solomon 的构造——检测和校正

Question

如何构建可以检测和纠正错误的 RS 代码。

例如，我想构造 RS(76,64,8)，其中

8：GF(2⁸)字段，符号大小
64: 信息符号
76: 信息(64) + 校验符号(12)

我可以使用 pyfinite python 库 (https://pypi.org/project/pyfinite/) 轻松构建 6 个符号校正代码。

我也对构建一个不同的变体感兴趣，它可以使用 12 个校验符号提供 8 个符号检测或 4 个符号校正。

Answer 1

你有什么理由不能使用 python pyfinite 代码来处理你想要的情况吗？

如果有兴趣，我有一个用 C 编写的旧交互式 RS ecc 演示。用户选择 30 个可能的 GF(2^8) 字段中的 1 个，一些关于 RS 生成多项式的参数，奇偶校验字节数（定义将此限制为 20，但可以更改），数据字节数。然后用户可以输入数据、编码数据、更改数据、更改数据并标记为擦除、修复数据……。代码包括3个常用的解码器，PGZ矩阵求逆，Berleykamp Massey discrepancy，Sugiyama的扩展Euclid算法。 Euclid 解码器类似于硬件实现（模拟一对移位寄存器），因为它在 1980 年代曾用于协助硬件团队实现 RS 代码。我是用Visual Studio编译的，其他编译器应该没有太大问题。在这个答案中直接 post 它太大了，所以这里是一个 link 到一个 zip 文件，其中包括源代码和一个 readme.txt 文件：

http://rcgldr.net/misc/eccdemo8.zip

RS 码有 12 个奇偶校验位，最多可以纠正 4 个错误，同时仍检测到 8 个错误。假设出现 8 个错误的最坏情况非失败情况。代码计算出了错误的4个位置，一共产生了12个错误，4个错改的错误加上已有的8个错误。这永远不会失败，因为任何两个有效代码字之间的汉明距离是 13 个字节。对于示例失败案例，可能有 9 个错误，代码计算错了 4 个错误，导致总共有 13 个错误可能的错误更正（这将创建一个有效的代码字，但错误的代码字）。

要在计算最多 4 个错误位置后检查最多 8 个错误，应使用所有 12 个校正子验证生成的错误定位器多项式。这是在 GenPErrorsE() 中的第 871 行完成的，Sugiyama 扩展 Euclid 解码器。该检查也可以包含在其他 2 个解码器中，但由于演示程序调用所有 3 个解码器，因此不需要。请注意，如果解码器计算出 6 个错误，那么它将始终生成有效的代码字，但如果实际上有 7 个或更多错误，则可能是错误的代码字。在 eccdemo8.c 中处理此问题的最简单修复是将错误数限制为 <= 4，这只需要在第 204 行插入 4 行代码：

    GenForneyErr();             /* generate forney err values */

    /* insert this code to limit to 4 errors */        
    if(vOffsets.size > 4){      /* limit to 4 errors */
        printf("uncorrectable, > 4 errors\n");
        return;
    }

    printf("vLocators:      ");

还有另一种类型的 Reed Solomon 代码称为“原始视图”（相对于更常见的“BCH”视图）。对于 RS(n,k) 码，解码对 n 个符号进行操作，而“BCH 视图”解码器对 n-k 个符号（综合症）进行操作，使得“BCH 视图”明显快于“原始视图”。一些仅擦除代码基于“原始视图”，但最常见的情况是 Raid 6，它会生成“BCH 视图”综合症（另一种方法，综合症不是“代码字”的一部分）。 Wiki 文章解释了这一点：

https://en.wikipedia.org/wiki/Reed%E2%80%93Solomon_error_correction

Reed Solomon 的构造——检测和校正

Construction of Reed Solomon - detection and correction

detection

reed-solomon