13

我正在尝试在极其有限的嵌入式平台上生成 QR 码。除了生成纠错码字之外，规范中的所有内容似乎都相当简单。我查看了一堆现有的实现，它们都试图实现一堆让我头疼的多项式数学，特别是关于伽罗瓦域。在数学复杂性和内存要求方面，我能看到的最直接的方式是规范本身中列出的电路概念：

电路原理图

根据他们的描述，我相当有信心可以实现这一点，除了标记为 GF(256) 加法和 GF(256) 乘法的部分。

他们提供以下帮助：

QR 码的多项式算法应使用按位模 2 算法和按字节模 100011101 算法计算。这是一个 2^8 的伽罗瓦域，其中 100011101 表示该域的素数模多项式 x^8+x^4+x^3+x^2+1。

这对我来说几乎都是希腊语。

所以我的问题是：在这种伽罗瓦域算术中执行加法和乘法的最简单方法是什么？假设两个输入数字都是 8 位宽，我的输出也需要是 8 位宽。几个实现预先计算，或者在两个查找表中硬编码来帮助解决这个问题，但我不确定这些是如何计算的，或者在这种情况下我将如何使用它们。我宁愿不为这两个表占用 512 字节的内存，但这实际上取决于替代方案是什么。我真的只需要帮助了解如何在这个电路中进行单次乘法和加法运算。

4

2 回答 2

11

实际上只需要一张表。那将适用于 GP(256) 乘法。请注意，所有算术都是无进位的，这意味着没有进位传播。

不带进位的加减法等价于异或。

所以在 GF(256) 中，a + b和a - b都等价于a xor b。

GF(256) 乘法也是无进位的，并且可以使用无进位乘法以与无进位加法/减法类似的方式完成。这可以通过英特尔的 CLMUL 指令集通过硬件支持有效地完成。

但是，困难的部分是减少模数100011101。在正常的整数除法中，您使用一系列比较/减法步骤来完成。在 GF(256) 中，您使用一系列比较/异或步骤以几乎相同的方式执行此操作。

事实上，仅仅预先计算所有 256 x 256 乘法并将它们放入 65536 条目的查找表中仍然更快，这已经够糟糕的了。

以下pdf的第3页对GF256算法有很好的参考：

http://www.eecs.harvard.edu/~michaelm/CS222/eccnotes.pdf

于 2011-12-09T03:37:00.537 回答
6

（我正在跟进第一个答案中指向 zxing 的指针，因为我是作者。）

关于加法的答案是完全正确的；这就是为什么在这个领域工作在电脑上很方便。

请参阅http://code.google.com/p/zxing/source/browse/trunk/core/src/com/google/zxing/common/reedsolomon/GenericGF.java

是的，乘法有效，适用于 GF256。a * b 实际上与 exp(log(a) + log(b)) 相同。因为GF256只有256个元素，所以只有255个“x”的唯一幂，对数也是一样。所以这些很容易放在查找表中。表格将在 256 处“环绕”，这就是您看到“% size”的原因。“/ size”用一句话来解释有点困难——因为真的是1-255“环绕”，而不是0-255。因此，需要的不仅仅是一个简单的模数。

最后一部分也许是你如何减少模一个不可约多项式。不可约多项式是 x^8 加上一些低幂项，对 - 称之为 I(x) = x^8 + R(x)。根据定义，多项式在域中等于 0；I(x) == 0。所以 x^8 == -R(x)。而且，方便地，加法和减法是相同的，所以 x^8 == -R(x) == R(x)。

我们唯一需要减少高幂多项式是在构造指数表时。您只需继续乘以 x（左移），直到它变得太大——得到一个 x^8 项。但是 x^8 与 R(x) 相同。因此，您取出 x^8 并添加 R(x)。R(x) 仅具有高达 x^7 的幂，因此它仍然在一个字节中，全部在 GF(256) 中。而且您知道如何在此字段中添加。

有帮助吗？

于 2011-12-09T17:27:38.677 回答