Galois字段中的加法和乘法 [英] Addition and multiplication in a Galois Field
问题描述
我正在尝试在极其有限的嵌入式平台上生成QR码. 规范中的所有内容看起来都很简单，除了生成纠错码字.我研究了很多现有的实现，并且它们都尝试实现一堆直接贯穿我头顶的多项式数学，尤其是在Galois领域方面.在数学复杂度和内存需求方面，我所能看到的最直接的方法是规范本身中列出的电路概念:
有了他们的描述，我非常相信我可以实现这一点，但标有GF(256)加法和GF(256)乘法的部分除外.
他们提供此帮助:
QR码的多项式算法应使用按位模2运算和按字节计算 取模100011101的算术运算.这是2 ^ 8的Galois字段 其中100011101代表该字段的素数模 多项式x ^ 8 + x ^ 4 + x ^ 3 + x ^ 2 + 1.
这对我来说非常希腊.
所以我的问题是:在这种Galois字段算术中执行加法和乘法的最简单方法是什么?假设两个输入数字均为8位宽，我的输出也必须为8位宽.几种实现会进行预先计算，或者在两个查找表中进行硬编码以帮助解决此问题，但是我不确定如何计算它们，或者在这种情况下如何使用它们.我不希望这两个表占用512字节的内存，但这实际上取决于替代方法是什么.我真的只需要帮助您了解如何在此电路中执行单个乘法和加法运算即可.
在实践中，只需要一个表.那将用于GP(256)乘.请注意，所有算术运算都是无进位的，这意味着没有进位传播.
没有进位的加法和减法等同于异或.
因此在GF(256)中，a + b和a - b都等同于a xor b.
但是，最困难的部分是减小模数100011101.在普通整数除法中，您可以使用一系列比较/减法步骤来完成此操作.在GF(256)中，您可以使用一系列比较/异或步骤以几乎相同的方式进行操作.
实际上，这非常糟糕，仅预先计算所有256 x 256乘法并将它们放入65536条目的查找表中仍然要更快.
以下pdf的第3页对GF256算法有很好的参考:
http://www.eecs.harvard.edu/~michaelm /CS222/eccnotes.pdf
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.
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 + b and a - b are both equivalent to a 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
这篇关于Galois字段中的加法和乘法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
