verilog - 如何将乘法的值保持在有限域范围内？我正在实现 GF(8) 乘法

Question

我正在实现 GF(8) 乘法。原始多项式是 x^3 + x + 1。我知道基础知识：如果乘法溢出，我可以用我的原始多项式对它进行异或运算，并将其带入有限域的范围内。

但是，当溢出发生多于一位时，就会出现问题。例如： 正确结果：二进制结果 12(1001) 中的 alpha^3(011) * alpha^2(100)。乘积溢出，因此与原始多项式进行 XOR 会给出正确的值，即 alpha^5(111)。 不正确的结果：二进制结果中的 alpha^5(111) * alpha^3(011) 21(10101)。这里结果溢出了两位，并且使用原始多项式进行 XOR 不会给出正确的结果。

我错过了什么？

Answer 1

GF乘法是多项式乘法，所以没有进位。所以 111*011 = 1001 和 1001 模 1011 是 010。但是，考虑 100 * 100 = 10000 的情况。在这种情况下，您需要执行两个“除法”步骤（类似于使用低级二进制数学计算 CRC，而是使用 XOR减法）。

          10
     -------
1011 | 10000
       1011
       ----
         110
         000
         ---
         110

所以 100*100 模 1011 = 110。

您可以创建一个反对数表和一个日志表。对于这个基于 x^3 + x + 1 的 GF(8) = GF(2^3) 字段，所有 7 个非零数都是 1x + 0（十六进制 2）的幂：

  0   1   2   3   4   5   6    antilog table
001 010 100 011 110 111 101 

001 010 011 100 101 110 111    log table
  0   1   3   2   6   4   5

使用这些表，a*b = alog((log(a) + log(b))%7)。100*100 = alog((log(100)+log(100))%7) = alog((2+2)&7 = alog(4) = 110. 110*111 = alog((log(110)+log (111))%7) = alog((4+5)%7) = alog(2) = 100。

您可以通过将反对数表加倍来消除对 %7 的需要，日志表将保持不变：

  0   1   2   3   4   5   6   7   8   9  10  11  12  13  antilog table
001 010 100 011 110 111 101 001 010 100 011 110 111 101 

a*b = alog(log(a) + log(b))。也用于除法：a/b = alog(7+log(a)-log(b))。