在伽罗瓦域中的加法和乘法

Question

我正在尝试在一个非常有限的嵌入式平台上生成QR码。除了生成纠错码字之外，在规范中的所有内容都似乎非常简单明了。我已经查看了大量现有的实现，它们都试图实现一堆多项式数学，这对我来说很难理解，特别是对于Galois域方面的内容。我所能想到的最直接的方法，无论是数学上的复杂性还是存储器要求，都是规范本身提出的电路概念:

通过他们的说明，我相当自信我可以实现这个电路，但除了标记为GF（256）加法和GF（256）乘法的部分以外。

他们提供了以下帮助:

QR码的多项式算术应使用位模2算术和字节模100011101算术进行计算。这是一个2 ^ 8的有限域，100011101表示该域的质模x ^ 8 + x ^ 4 + x ^ 3 + x ^ 2 + 1。

这对我来说几乎是天书。

因此，我的问题是：在这种Galois域算术中执行加法和乘法的最简单方法是什么？假设两个输入数字宽度为8位，我的输出也需要为8位。几种实现预先计算或硬编码了两个查找表来帮助解决这个问题，但我不确定如何计算这些表，或者在这种情况下如何使用它们。我真的不想为这两个表付出512字节的内存代价，但它取决于替代方案是什么。我只是需要帮助理解如何在此电路中执行单个乘法和加法操作。

- captncraig

Answer 1

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

没有进位的加减法等效于异或运算。

因此，在GF(256)中，a + b和a - b都等同于a xor b。

GF(256)乘法也是无进位的，可以通过类似于无进位加/减的方式使用无进位乘法来完成。如果有硬件支持，例如Intel的CLMUL指令集，那么可以高效地完成。

然而，难点在于模数100011101的约简。在普通整数除法中，您可以使用一系列比较/减法步骤来完成。在GF(256)中，您可以使用一系列几乎相同的比较/异或步骤来完成。

事实上，情况很糟糕，以至于仍然更快地预先计算所有256个乘积并将它们放入65536个条目的查找表中。

以下pdf的第3页有关于GF256算术的非常好的参考资料:

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

- Mysticial

---

将加法简化为异或运算非常棒。当我只有不到2k的内存可用时，使用一个65k的查找表是不可能的。如果必要，我可以牺牲时间来节省内存，但我仍然不清楚如何通过长乘法进行计算。 - captncraig

这实际上与移位加法二进制乘法算法非常相似。只是你用异或替换了所有的加法。 - Mysticial

100011101 何时发挥作用？此外，为什么它有9位，而每个字节只有8位？ - captncraig

查看zxing源代码：他们使用以下公式进行乘法计算：int logSum = logTable[a] + logTable[b]; return expTable[(logSum % size) + logSum / size]; 这样是否足够？这需要两个表格，但可能是可以接受的。 - captncraig

明天期末考试后我会看一下那个链接。虽然我的数学很弱，但这确实是一个让我着迷的话题。 - Mysticial

Answer 2

我在第一个回答中提到了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个元素，因此"x"的幂只有255个唯一值，log也是如此。因此，这些很容易放入查找表中。表格会在256处“环绕”，这就是为什么您会看到“% 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)中。而且，您知道如何在此领域中进行加法。

能帮到您吗？

- Sean Owen

---

所以如果我理解正确，仅使用带有环绕的字节并进行加法运算是不够的？Div和mod是相当昂贵的操作，因此仅使用加法的方式是最好的。如果必要，我可以实现字节加法，使其在254->255->1->2时环绕。 - captncraig

啊，专家终于出手了... +1 - Mysticial

我实际上在尝试使用zxing代码进行GF加法和乘法时，遇到了引用电路概念的实现问题。也许我会在zxing论坛上发布详细信息。 - captncraig

如果您知道字段大小为256，则“/”和“％”操作实际上只是“>> 8”和“＆0xFF”。我想您可以进一步优化此过程。但是，在QR码解码过程中，Reed-Solomon纠错过程只是一个非常小的部分。我会很惊讶如果这是您的瓶颈。 - Sean Owen