伽罗瓦域中的加法和乘法

Question

我试图在极其有限的嵌入式平台上生成QR码.在一切的规范,似乎除了产生错误纠正码字相当简单.我已经看了一堆现有的实现,他们都试图实现一堆直接超越我的头的多项式数学,特别是关于Galois域.在数学复杂性和内存需求方面,我能看到的最简单的方法是在规范本身中列出的电路概念:

通过他们的描述,我相信我可以实现这一点,除了标有GF(256)加法和GF(256)乘法的部分.

他们提供这个帮助:

QR码的多项式算法应使用逐位模2算术和逐字模100011101算法计算.这是2 ^ 8的伽罗瓦域,其中100011101表示场的素数模数多项式x ^ 8 + x ^ 4 + x ^ 3 + x ^ 2 + 1.

这对我来说几乎都是希腊人.

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

Answer 1

实际上只需要一个表.这将是GP(256)倍增.请注意,所有算术都是无进位的,这意味着没有进位传播.

无进位的加法和减法等效于xor.

因此,在GF(256),a + b和a - b都等于a xor b.

GF(256)乘法也是无进位的,并且可以使用无进位乘法以类似的方式使用无进位加法/减法来完成.这可以通过英特尔的CLMUL指令集在硬件支持下高效完成.

然而,困难的部分,是减少模数100011101.在正常整数除法中,您可以使用一系列比较/减法步骤来完成.在GF(256)中,您使用一系列compare/xor步骤以几乎相同的方式完成它.

实际上,只需预先计算所有256 x 256乘法并将它们放入65536条目的查找表中,它就足够糟糕了.

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

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

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个元素,所以只有255个"x"的唯一幂,对于log也是如此.所以这些很容易放在查找表中.这些表将在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)中.而且您知道如何添加此字段.

帮助？