里德-所罗门的第一个ECC总是和异或一样吗?



我现在正在和里德-所罗门一起工作。据我了解,第一个纠错码总是与数据字的异或相同,因为范德蒙德矩阵的第一行总是 1,并且在伽罗瓦字段中添加元素等效于异或。

现在我尝试使用 ReedSolomonEncoder 的 Zxing 3.3.0 实现来获取一些代码字。请参阅 Java 中的以下列表:

ReedSolomonEncoder rs = new ReedSolomonEncoder(GenericGF.QR_CODE_FIELD_256);
int[] codeword = {72,87,0,0};
rs.encode(codeword, 2);
System.out.println("Ecc for " + codeword[0] + " and " + codeword[1]);
System.out.println("XOR: " + (72^87));
System.out.println("RS #1: " + codeword[2]); // Shouldn't this be 31 too?
System.out.println("RS #2: " + codeword[3]);

这给出了以下输出:

Ecc for 72 and 87
XOR: 31
RS #1: 28
RS #2: 3

有两种可能性:

  1. 我对里德-所罗门有一个误解
  2. 我以错误的方式使用实现(因为javadoc写得不好)

或者这是一个错误,我不相信。

它是第一个综合症,它是编码消息的独占或,并且仅当生成器多项式的形式为 (x+1) (x+α) (x+α^2) ... .在这种情况下,"第一个连续根"是 1。对于其他实现,"第一个连续根"是α,生成器多项式是 (x+α) (x+α^2) (x+α^3) ... 。生成器多项式选择还有其他变体,例如 GF(256) 中的 (x+a^127)(x+a^128) 对于自倒数多项式,1x^2 + ??x + 1。

在这种情况下,GF(256) 基于 9 位多项式 x^8+x^4+x^3+x^2+1 或十六进制 11d 。 α是基元,在这种情况下α = x+0 == 十六进制 02。

生成器多项式是 (1x + 1) (1x + 2) = 1x^2 + 3x + 2。编码过程可以可视化为长除法,如下以十六进制显示。消息乘以 x^2(用两个零填充)为两个奇偶校验字节留出空间:

48 8f
------------
1  3  2 |48 57 00 00
48 d8 90
--------
8f 90 00
8f 8c 03
--------
1c 03   remainder

余数从填充消息中减去,但加法和减法都是互斥的或 GF(256),因此编码的消息变为

48 57 1c 03

这与你得到的结果相匹配(十六进制 1c = 十进制 28)。

在这种情况下,解码时,syndrome[0] 是消息中所有字节的异或。综合征也可以可视化为长除法(综合征计算不使用填充):

syndrome 0:                 syndrome 1:
48 09 03                    48 c7 8f
------------                ------------
1  1 |48 57 1c 03           1  2 |48 57 1c 03
48 48                       48 90
-----                       -----
1f 1c                       c7 1c
1f 1f                       c7 93
-----                       -----
03 03                       8f 03
03 03                       8f 03
-----                       -----
00                          00

通过将 57 更改为 56 来创建错误值 01:

48 1e 02                    48 c6 8d
------------                ------------
1  1 |48 56 1c 03           1  2 |48 56 1c 03
48 48                       48 90
-----                       -----
1e 1c                       c6 1c
1e 1e                       c6 91
-----                       -----
02 03                       8d 03
02 02                       8d 07
-----                       -----
01                          04

相关内容

  • 没有找到相关文章

最新更新