java - 将MATLAB的Reed Solomon函数移植到Java

Question

我已经在带有RS（160,80）的MATLAB中实现了一个简单的RS纠错方案。基本过程如下：


我生成的消息长度为80，每个符号8位，并且生成的RS代码长度为160。
生成RS代码后，我添加/异或另一个代码长度为160的Galois字段。（此字段仅包含00000000和00000001）。这是为了模拟在方案中添加错误。这会产生我的嘈杂代码。
现在，我采用另一个GF字段（与[00000000 00000001]相似，其类型与我用来创建噪声的那个符号不同）少于40个。我在上一步中将其添加/异或到生成的噪声代码中。
最后，我通过RS解码器运行它，该解码器检索我的原始消息。


我的MATLAB函数：

function RSKeyExchange(dev1, dev2)
    dev1_fp = zeros(1,160);
    dev2_fp = zeros(1,160);

    for i=1:160
        dev1_fp(i) = str2double(dev1.key(i));
        dev2_fp(i) = str2double(dev2.key(i));
    end

    n = 160;        % total code length
    k = 80;         % message length - actual message for syncronisation
    m = 8;          % order (2^m)

    % therefore, RS decoder can detect t = n-k = 80 errors
    % and correct t/2 = 40 errors

    msg = gf(randi([1 255],1 ,80), m);
    code = rsenc(msg, n, k);

    noise_add = gf(dev1_fp, 8);
    noise_remove = gf(dev2_fp, 8);

    noisy_code = code + noise_add;

    % noisy_code is now transmitted from dev1 to dev2 (sender to receiver)

    decommited_code = noisy_code + noise_remove;
    [rxcode, cnumerr] = rsdec(decommited_code, n, k);

    fprintf('Number of errors corrected: %d\n', cnumerr);
end

现在，我一直在寻找将其移植到Java的方法。我已经查找了库，但是不确定如何准确地移植我的特定用例。


Zxing-仅接受QR和Aztec代码作为输入
Backblaze - JavaReedSolomon-修复了代码擦除，这不是我正在产生的那种错误，并且输入是以文件的形式（对于这里发生的事情很困惑）
Simple RS error correction example-感觉更清晰一些，但仅将字符串作为输入。我觉得我可以对其进行修改以适合我的用例，但是我不确定如何增加噪音。我不确定如何通过此实现生成RS（160，80）代码，也不确定如何生成自定义GF字段以增加噪声。


任何帮助将不胜感激（尤其是如果您可以将我指向一个适合我的用例的实现，或帮助修改上面可用的资源之一）

谢谢！

Answer 1

我看了“简单RS”示例“ GF28” Java代码。解码器似乎仅处理擦除（输入之一是错误索引数组）。它使用基于十六进制11B = x ^ 8 + x ^ 4 + x ^ 3 + x + 1的GF（256），与AES加密相同。由于最低的“原始数”是3（除零以外的所有数字都可以视为3的幂），而不是“原始”数是2的字段，因此这是一种不寻常的选择。字段多项式是通过PX定义的，因此可以轻松更改。我不确定为什么它动态生成表而不是在初始化期间生成表，而是使用第二组true / false表指示是否已生成特定表值。

我有一个用于8位GF（256）字段的C RS演示程序。它是交互式的，如果生成多项式的第一个连续根为1（如果未指定，则选择第一个连续的根），则选择一个字段（其中有30个），是否使用自反多项式（通常不使用） root是“原语”），奇偶校验字节数和数据字节数。它处理擦除和错误，并且因为它是一个演示程序，所以它包含3种主要类型的解码器算法Peterson矩阵算法，Sugiyama对扩展Euclid算法的改编，Berlekamp Massey算法以及Forney算法生成错误值的代码。交互部分可以用选择所有这些参数的代码代替。根据您的情况，将MAXPAR的定义从20更改为80（最大奇偶校验数）。用户输入是通过stdin进行的，因此可以使用文本输入文件来运行演示。

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

在我的演示中，要生成代码字，用户输入值（用户选项“ E”或“ C”），然后输入“ N”进行编码。为了产生错误，用户在特定位置输入值。为了生成擦除，用户使用“ P”选项在特定位置输入擦除值。 “ F”用于固定（纠正）代码字。

Wiki文章包含3种主要类型的解码器的逻辑。它还说明了傅立叶变换，但是傅立叶变换需要使用其他解码器之一才能生成误差多项式，这是不实际的。

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



根据您的评论，我查看了Zxing库。方法的描述有点简洁，使用了错误的术语。这是描述的重做：

GenericGF(primitive, size, b)
    primitive - wrong term, this is the field polynomial

    size - The description is "size of the field", but that is
    determined by the polynomial, a n+1 bit polynomial is used
    for an n bit field. My guess is this is the size of the
    generator polynomial, perhaps the number of roots.

    b - alpha raised to the b power is the first consecutive root.
    alpha is the primitive for the particular field. Unlike the
    comment, b == 0 is about as common as b == 1.

https://en.wikipedia.org/wiki/Primitive_element_(finite_field)

encode(int[] toEncode, int ecBytes)
    toEncode - toEncode includes space for the "parity" data used
    to encode the message.

    ecByte - the number of "parity" elements at the end of to Encode.
    Why is it named ecBytes when it is an array of ints?

decode(int[] received, int twoS )
    received is an array of concatenated encoded messages?
    Since encode generates a single encoded message, then it would
    make more sense for decode to decode a single encoded message.

    twoS - the number of encoded messages?

    Based on the references, it is using the Sugiyama adaptation
    of extended Euclid algorithm. A side benefit is that the
    error evaluator polynomial is generated during the process.

包装注释也有错误。 GF（256）码字的最大大小为255个字节，因为错误位置限制在0到254范围内。这是因为位置与功率有关，而GF（256）中提高到255的任何数字都是：相同的数字。



请注意，在不触发库异常的情况下可能会进行错误更正。但是，如果使用80个奇偶校验字节，则可能会出现41个错误。错误校正将涉及生成一组40个位置和值，这些位置和值产生一个有效的码字，但与原始码字相差81个或更多字节（81个或更多错误）。但是，如果缩短的代码字为160个字节，则所有40个生成的位置都必须在0到159的范围内。假设计算位置的随机，均匀分布，则它们进行错误校正的几率将是（（160！） /（（（160-40）！））/（255 ^ 40）！= 3.86×10 ^ -11。如果使用全长（255）码字或更少的奇偶校验，则错误校正是一个问题。



我做了一个Java RS ecc GF（256）的例子。它不处理擦除（这需要修改已知擦除位置的校正子，然后将错误定位器与擦除定位器合并）。它使用Euclid算法来计算错误定位器和错误评估器多项式。已评论，但您可能需要阅读Wiki RS文章才能更好地理解它。该代码通过按需使用byte＆0xff将Java带符号的字节转换为无符号整数来处理Java。我将参数设置为80个消息字节，80个奇偶校验字节以匹配问题的示例。尽管对于GF（256），加法和减法都是异或，但代码使用单独的函数进行加法和减法，因此该代码与算法相对应，因为它将应用于GF（p），其中p是质数，例如GF（ 257）。对于GF（p），Lambda的“导数”的计算也将有所不同，这在此处进行了解释：

https://en.wikipedia.org/wiki/Forney_algorithm#Formal_derivative

链接到Java rsecc GF（256）示例：

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

由于交互式C版本具有交互性，因此它易于交互，显示一些内部计算（可以更改定义以启用/禁用显示的内容），并且用户可以尝试不同的变体。