伽罗瓦域中的加法和乘法
我正在尝试在极其有限的嵌入式平台上生成二维码。除了生成纠错码字之外，规范中的所有内容似乎都相当简单。我研究了一堆现有的实现，它们都试图实现一堆直接超出我头脑的多项式数学，特别是关于伽罗瓦域。我能看到的最直接的方法，无论是数学复杂性还是内存要求，都是规范本身中列出的电路概念：
根据他们的描述，我相当有信心可以实现这一点，除了标记为 GF(256) 加法和 GF(256) 乘法的部分之外。
他们提供这样的帮助：
QR 码的多项式算法应使用按位模 2 算法和按字节计算 模 100011101 算术。这是 2^8 的伽罗瓦域 100011101 代表场的质数模数 多项式 x^8+x^4+x^3+x^2+1。
这对我来说几乎都是希腊语。
所以我的问题是：在这种伽罗瓦域算术中执行加法和乘法的最简单方法是什么？假设两个输入数字都是 8 位宽，并且我的输出也需要是 8 位宽。一些实现会预先计算，或在两个查找表中进行硬编码以帮助解决此问题，但我不确定这些是如何计算的，或者在这种情况下如何使用它们。我宁愿不为这两个表占用 512 字节内存，但这实际上取决于替代方案。我真的只需要帮助了解如何在该电路中进行单个乘法和加法运算。
I am attempting to generate QR codes on an extremely limited embedded platform. Everything in the specification seems fairly straightforward except for generating the error correction codewords. I have looked at a bunch of existing implementations, and they all try to implement a bunch of polynomial math that goes straight over my head, particularly with regards to the Galois fields. The most straightforward way I can see, both in mathematical complexity and in memory requirements is a circuit concept that is laid out in the spec itself:
With their description, I am fairly confident I could implement this with the exception of the parts labeled GF(256) addition and GF(256) Multiplication.
They offer this help:
The polynomial arithmetic for QR Code shall be calculated using bit-wise modulo 2 arithmetic and byte-wise
modulo 100011101 arithmetic. This is a Galois field of 2^8
with 100011101 representing the field's prime modulus
polynomial x^8+x^4+x^3+x^2+1.
which is all pretty much greek to me.
So my question is this: What is the easiest way to perform addition and multiplication in this kind of Galois field arithmetic? Assume both input numbers are 8 bits wide, and my output needs to be 8 bits wide also. Several implementations precalculate, or hardcode in two lookup tables to help with this, but I am not sure how those are calculated, or how I would use them in this situation. I would rather not take the 512 byte memory hit for the two tables, but it really depends on what the alternative is. I really just need help understanding how to do a single multiplication and addition operation in this circuit.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
实际上只需要一张表。这适用于 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
In practice only one table is needed. That would be for the GP(256) multiply. Note that all arithmetic is carry-less, meaning that there is no carry-propagation.
Addition and subtraction without carry is equivalent to an xor.
So in GF(256),
a + banda - bare both equivalent toa xor b.GF(256) multiplication is also carry-less, and can be done using carry-less multiplication in a similar way with carry-less addition/subtraction. This can be done efficiently with hardware support via say Intel's CLMUL instruction set.
However, the hard part, is reducing the modulo
100011101. In normal integer division, you do it using a series of compare/subtract steps. In GF(256), you do it in a nearly identical manner using a series of compare/xor steps.In fact, it's bad enough where it's still faster to just precompute all 256 x 256 multiplies and put them into a 65536-entry look-up table.
page 3 of the following pdf has a pretty good reference on GF256 arithmetic:
http://www.eecs.harvard.edu/~michaelm/CS222/eccnotes.pdf
（我正在跟踪第一个答案中指向 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 个，对数也是如此。所以这些很容易放入查找表中。这些表将在 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) 中。并且您知道如何在该字段中添加。
有帮助吗？
(I'm following up on the pointer to zxing in the first answer, since I'm the author.)
The answer about addition is exactly right; that's why working in this field is convenient on a computer.
See http://code.google.com/p/zxing/source/browse/trunk/core/src/com/google/zxing/common/reedsolomon/GenericGF.java
Yes multiplication works, and is for GF256. a * b is really the same as exp(log(a) + log(b)). And because GF256 has only 256 elements, there are only 255 unique powers of "x", and same for log. So these are easy to put in a lookup table. The tables would "wrap around" at 256, so that is why you see the "% size". "/ size" is slightly harder to explain in a sentence -- it's because really 1-255 "wrap around", not 0-255. So it's not quite just a simple modulus that's needed.
The final piece perhaps is how you reduce modulo an irreducible polynomial. The irreducibly polynomial is x^8 plus some lower-power terms, right -- call it I(x) = x^8 + R(x). And the polynomial is congruent to 0 in the field, by definition; I(x) == 0. So x^8 == -R(x). And, conveniently, addition and subtraction are the same, so x^8 == -R(x) == R(x).
The only time we need to reduce higher-power polynomials is when constructing the exponents table. You just keep multiplying by x (which is a shift left) until it gets too big -- gets an x^8 term. But x^8 is the same as R(x). So you take out the x^8 and add in R(x). R(x) merely has powers up to x^7 so it's all in a byte still, all in GF(256). And you know how to add in this field.
Helps?