混合Galois域机和Galois域除法器和平方根机及其方法

摘要

Galois域除法机和方法输入1和第一Galois域元素到Galois域倒数生成器以得到输出，在Galois域倒数生成器中把第一Galois域元素乘以Galois域倒数生成器的第一元素，用于m－2次预测不可约多项式的多项式乘积的平方的模数余数，其中m是Galois域的度，以得到第一Galois域元素的倒数，以及在Galois域倒数机中把第一Galois域元素的倒数乘以第二Galois域元素，用于预测不可约多项式的多项式乘积的模余数，以便在m次循环时得到两个Galois域元素的商；在更广泛的意义上，本发明包括混合Galois域机，用于对于一系列多项式输入执行一系列Galois域线性变换，以得出最后输出，其中每个输入，除了第一输入以外，是以前的Galois域线性变换的输出；Galois域平方根是通过输入Galois域元素到Galois域平方根生成器以得到输出，在Galois域平方根生成器中对该输出进行平方，用于预测m－1次不可约多项式的多项式乘积的平方的模数余数，其中m是Galois域的度，以便在(m－1)次循环中得到Galois域元素的平方根而得到的。

说明书

技术领域

本发明涉及Galois域除法机和方法，更一般地，涉及用于在一次变换运算中执行连续的Galois域变换的混合Galois域机。

相关专利申请

本专利申请主张以下申请的优先权2002年10月9日提交的、Stein等的、题目为A COMPACT GALOIS FIELD MULTIPLIER的美国临时专利申请(AD-337J)；2001年11月30日提交的、Stein等的、题目为GF2-ALU的美国临时专利中请序列号No.60/334,662(AD-239J)；2001年11月20日提交的、Stein等的、题目为PARALLEL GALOIS FIELDMULTIPLIER的美国临时专利申请序列号No.60/334,510(AD-240J)；2001年12月18日提交的、Stein等的、题目为GALOIS FIELD MULTIPLY ADD(MPA)USING GF2-ALU的美国临时专利申请序列号No.60/341,635(AD-299J)；2001年12月18日提交的、Stein等的、题目为PROGRAMMABLE GF2-ALU LINEARFEEDBACK SHIFT REGISTER-INCOMING DATA SELECTION的美国临时专利申请序列号No.60/341,737(AD-300J)。本专利申请还主张以下申请的优先权2003年3月24日提交的、Stein等的、题目为COMPACT GALOIS FIELD MULTIPLIER ENGINE的美国专利申请序列号No.10/395,620(AD-337J)；2002年1月18日提交的、Stein等的、题目为GALOIS FIELD LINEAR TRANSFORMERER的美国专利申请序列号No.10/051,533(AD-239J)；2002年1月30日提交的、Stein等的、题目为GALOIS FIELD MULTIPLIER SYSTEM的美国专利申请序列号No.10/060,699(AD-240J)；2002年8月26日提交的、授权给Stein等、题目为GALOIS FIELD MULTIPLY/MULTIPLYADD/MULTIPLY ACCUMULATE的美国专利申请序列号No.10/228,526(AD-299J)；和2002年5月1日提交的、Stein等的、题目为RECONFIG。URABLE INPUT GALOIS FIELDTRANSFORMERER SYSTEM的美国专利申请序列号No.10/136,170(AD-300J)。

背景技术

在诸如加密和错误控制编码的某些应用中，必须执行算术运算，例如在Galois域上的加法、减法、平方根、乘法和除法。在Galois域上任何两个成员之间的任何这样的运算将导致输出(和、差、平方根、乘积、商)，它是同一个Galois域上的另一个数值。在Galois域上元素的数目是2^m，其中m是域的度(degree)。例如，GF(2⁴)中具有16个不同的元素；GF(2⁸)将具有256个元素。Galois域是从特定幂次的不可约的多项式生成的。特定的度的每个Galois域将具有多个不可约的多项式，从每个多项式，通过使用相同的项但以不同的阶次可以作出不同的域。

在Galois域上的除法是通过把被除数乘以除数的倒数而完成的。这个除数倒数可以以多种方式被生成。一个方法是用存储的倒数查找表，其中除数是表的地址。这个方法的一个问题是对于每个不可约多项式的每个域，必须存储分开的表。另外，该表只能被顺序地访问：如果需要并行运算，则必须对于每个并行运算提供每个表的拷贝。另一个方法是把每个存储的Galois域元素乘以各个除数。产生一的乘积的数值就是特定的除数的倒数。再次地如果打算进行并行运算的话，所有的数值并行被存储在多个拷贝。并且，需要一个Galois域乘法器来完成检索。第三个方法使用两个线性反馈移位寄存器(LFSR)，每个被配置成生成特定的不可约多项式的选择的Galois域。第一个被初始化为除数；第二个被初始化为“1”。从除数值开始，两个寄存器的时钟被同步。当第一个LFSR的乘积等于1时，除数被乘以它的倒数。在这时第二个LFSR的乘积是Galois域元素，它是除数的倒数。这个方法的一个问题是对于每个度的每个不可约多项式的每个Galois域需要不同的LFSR对。在以上的第二查找表方法和LFSR方法中，寻找倒数需要高达2^m-1次迭代。

发明内容

所以，本发明的目的是提供改进的Galois域除法机和方法。

本发明的另一个目的是提供这样的改进的Galois域除法机，它可以以m-1次迭代完成寻找除数倒数。

本发明的另一个目的是提供这样的改进的Galois域除法机，它可以容易地重新配置成适应不同的度的不同的不可约多项式Galois域。

本发明的另一个目的是提供这样的改进的Galois域除法机，它可以用来生成除数倒数并把它乘以被除数。

本发明的另一个目的是提供这样的改进的Galois域除法机，它需要较少的功率和较小的面积。

本发明的另一个目的是提供用于在一次变换运算中执行连续Galois域变换的更一般的改进的混合的Galois域机。

本发明来自于这样的实现方案，更小的、更快速的、和更加有效的、改进的Galois域除法器可以这样得到：Galois域倒数生成器和输入选择电路初始地输入1和第一Galois域元素到Galois域倒数生成器以得到输出，以后在Galois域倒数生成器中把第一Galois域元素乘以Galois域倒数生成器的输出，用于预测m-2次不可约多项式的多项式乘积的平方的模余数，其中m是Galois域的度，以得到第一Galois域元素的倒数，以及在Galois域倒数机中把第一Galois域元素的倒数乘以第二Galois域元素，用于预测不可约多项式的多项式乘积的模余数，以便在m次循环中得到两个Galois域元素的商。

更一般地，本发明也可以这样被实现：用于对于连续多项式输入(其中每个输入，除了第一个以外，是前一个的Galois域线性变换的输出)执行连续的Galois域线性变换的改进的混合Galois域机可以通过来实现：提供第一输入输入电路以及具有可响应第一输入的小单元的矩阵的Galois域线性变换器，其被配置成在一次变换中，立即预测不可约Galois域多项式的连续Galois域线性变换的模数余数，以直接从第一输入得出Galois域线性变换的最后输出。

本发明的特征在于Galois域除法机，包括Galois域倒数生成器和输入选择电路，初始地输入1和第一Galois域元素到Galois域倒数生成器以得到输出，随后在Galois域倒数生成器中把第一Galois域元素乘以Galois域倒数生成器的输出，用于预测m-2次不可约多项式的多项式乘积的平方的模余数，其中m是Galois域的度，以得到第一Galois域元素的倒数，以及在Galois域倒数机中把第一Galois域元素的倒数乘以第二Galois域元素，用于预测不可约多项式的多项式乘积的模余数，以便在m次循环中得到两个Galois域元素的商。

在优选实施例中，倒数生成器可包括第一和第二Galois域乘法器。第一Galois域乘法器可包括第一多项式乘法器电路和第一Galois域线性变换器。第一Galois域线性变换器可包括小单元的矩阵。第一Galois域线性变换器可包括矩阵部分和单位矩阵部分。第二Galois域乘法器可包括第二多项式乘法器电路和第二Galois域线性变换器。第二Galois域线性变换器可包括小单元的矩阵。第二Galois域线性变换器单元的矩阵可包括矩阵部分和单位矩阵部分。第一Galois域乘法器的输出可被馈送到第二线性乘法器的两个相乘输入端，以提供该输出的平方。Galois域倒数生成器可包括包含第一多项式乘法器与第一Galois域变换器的Galois域乘法器，和第二Galois域变换器，用于计算Galois域乘法器输出的平方。第二Galois域变换器可以近似于第一Galois域变换器的尺寸的一半。第一和第二Galois域变换器，每个可包括小单元的矩阵，以及第二Galois域变换器可包括第一Galois域变换器的近似一半数目的小单元。Galois域倒数机可包括Galois域乘法器和程序电路，该程序电路用于编程Galois域乘法器以执行m-2次的混合的相乘-平方运算，后面跟随乘法运算，

本发明在广义上其特征在于混合Galois域机，用于对于连续的多项式输入执行连续的Galois域线性变换，以得出最后输出，其中每个输入，除了第一输入以外，是前一个Galois域线性变换的输出。有用于提供第一输入的输入电路和Galois域线性变换器，具有响应于第一输入的小单元的矩阵，以及被配置成在一次变换中，立即预测不可约Galois域多项式的连续的Galois域线性变换的模数余数，以直接从第一输入得出Galois域线性变换的最后输出。

本发明的特征还在于Galois域除法的方法，包括初始地输入1和第一Galois域元素到Galois域倒数生成器以得到输出，在Galois域倒数生成器中把第一Galois域元素乘以Galois域倒数生成器的输出，用于预测m-2次不可约多项式的多项式乘积的平方的模余数，其中m是Galois域的度，以得到第一Galois域元素的倒数，以及在Galois域倒数机中把第一Galois域元素的倒数乘以第二Galois域元素，用于预测不可约多项式的多项式乘积的模余数，以便在m次循环中得到两个Galois域元素的商。

本发明的特征还在于Galois域平方根机，包括Galois域平方根生成器和输入电路，该输入电路用于输入Galois域元素到Galois域平方根生成器，以得到在一次循环中Galois域元素的平方根。

在优选实施例中，Galois域平方根机可包括Galois域乘法器和程序电路，该程序电路用于编程Galois域乘法器，以在一次循环中执行m-1次混合平方运算。

本发明的特征还在于Galois域平方根方法，包括输入Galois域元素到Galois域平方根生成器以得到输出，以及在Galois域平方根生成器中对Galois域平方根生成器的输出进行平方，用于预测m-1次不可约多项式的多项式乘积的平方的模余数，其中m是Galois域的度，以便在(m-1)次循环中得到Galois域元素的平方根。

附图说明

通过优选实施例的以下的说明和附图，本领域技术人员将明白其它目的特性和优点，其中：

图1是按照本发明的紧凑式Galois域乘法机的功能性框图；

图2是按照本发明的传统的Galois域乘法机的更详细的功能性框图；

图3是显示本发明的减小尺寸的Galois域变换器单位矩阵特性的图1的紧凑式Galois域乘法机的更详细的功能性框图；

图4是用于图2和3的Galois域线性变换器电路的矩阵的典型的可编程X-OR电路小单元的示意图；

图5是显示了用于幂次8的特定的多项式的按照本发明的矩阵部分和单位矩阵部分单元的编程的图3和9的Galois域线性变换器电路的简化的示意图；

图6是显示了用于幂次8的另一个多项式的按照本发明的矩阵部分和单位矩阵部分单元的编程的图3和9的Galois域线性变换器电路的简化的示意图；

图7是显示了用于幂次4的再一个多项式的按照本发明的矩阵部分和单位矩阵部分单元的编程的图3和9的Galois域线性变换器电路的简化的示意图；

图8是显示了作为在这个特定的实施例中用于支持在半(4)幂次与全(8)幂次之间的多项式幂次的稀疏矩阵的第二矩阵部分的编程的、图3和9的Galois域线性变换器电路的简化的示意图；

图9是包含本发明的减小尺寸的矩阵和减小的硬件和本地化的总线特性的、图1的紧凑式Galois域乘法机的更详细的框图；

图10是采用多个Galois域线性变换器单元的、按照本发明的Galois域乘法机的框图；

图11是在图2，3，5和9上可使用的多项式乘法器的示意图；

图12是用于图11的多项式乘法器的转移函数的图；

图13是按照本发明的除法机的简化的示意性框图；

图14是图13的Galois域乘法器和平方器的更详细的图；

图15是用于图12的多项式乘法器的减小的转移函数值的图；

图16是类似于实施图15的减小的转移函数的图14的Galois域乘法器和平方器的图；

图17是图14的Galois域线性变换器的使能的小单元的模式的示意图；

图18是利用减小的转移函数的、图16的Galois域线性变换器的使能的小单元的模式的示意图；

图19是用于对于连续的多项式输入执行连续的Galois域线性变换以得到最后输出，例如按照本发明的更一般特性的除法的混合的Galois域机的、混合的Galois域线性机的使能的小单元的模式的示意图；

图20是利用图19所示的Galois域变换的混合的Galois域机的简化的示意图；

图2l是按照本发明的Galois域除法器方法的流程图；

图22是按照本发明的平方根机的示意性框图；

图23是用于如图22所示的、对于连续多项式输入执行连续Galois域线性变换以得到最后输出，例如按照本发明的更一般特性的平方根的混合的Galois域线性机的使能的小单元的模式的示意图；

图24是按照本发明的Galois域平方根方法的流程图；以及

图25是按照本发明的混合的Galois域机的简化框图。

具体实施方式

除了下面公开的优选实施例以外，本发明能够实施其它实施例，以及以各种方式被实践或被实行。因此，应当看到，本发明不限于它应用到在下面的说明中阐述的或在附图上显示的部件的结构和安排的细节。

在公开本发明混合Galois域机和除法机及其方法之前，为了更好地了解，先说明Galois域变换器和乘法器。

Galois域GF(n)是可以在其上执行两种二进制运算的一组元素。加法和乘法必须满足交换、结合、和分布律。具有有限数目的元素的域是有限的域。二进制域的例子是在模2加法和模2乘法下的集{0，1}以及被表示为GF(2)。模2加法和模2乘法运算由以下的说明中所显示的表定义。第一行和第一列表示加到Galois域加法器和乘法器的输入。例如，1+1＝0和1*1＝1。

模2加法(XOR)

  +  0  1  0  0  1  1  1  0

模2乘法(AND)

  *  0  1  0  0  0  1  0  1

通常，如果p是任何质数，则可以证明，GF(p)是具有p个元素的有限域以及GF(p^m)是具有p^m个元素的扩展域。另外，域的不同的元素可以按一个域元素β的不同的幂次--对它取成不同的幂次--被生成。例如，GF(256)具有256个元素，它可以全部通过对质元素(primitive element)赋予256个不同的幂次被生成。

另外，系数为二进制数的多项式属于GF(2)。度为m的GF(2)上的多项式被称为不可约的，如果它对于度小于m但大于零的GF(2)上的任何多项式是不能除尽的话。多项式F(X)＝X²+X+1是不可约多项式，因为它不能被X或X+1除尽。除以X^2m+1的度为m的不可约多项式被称为质多项式。对于给定的m，可以有一个以上的质多项式。对于m＝8的质多项式的例子--在大多数通信标准中经常使用的--是F(X)＝0x11d＝x⁸+x⁴+x³+x²+1。

Galois域加法是易于用软件实现的，因为它是与模加相同的。例如，如果29和16是GF(2⁸)中的两个元素，则它们的加法作为如下的XOR运算被简单地完成：29(11101)16(10000)＝13(01101)。

另一方面，Galois域乘法是稍微复杂的，如以下的例子所显示的，它通过重复进行质元素β的乘法而计算GF(2⁴)的所有的元素。为了生成GF(2)的域元素，度m＝4的质多项式G(x)被选择为G(x)＝x⁴+x+1。为了使得乘法是按模进行以使得乘法的结果仍旧是域的元素，第5比特被设置的任何元素通过使用以下的恒等式F(β)＝β⁴+β+1＝0而得到4比特结果。通过设置β⁴＝1+β+1这个恒等式被重复地使用，形成域的不同的元素。因此，域的元素可被枚举为如下：

{0，1，β，β²，β³，1+β，β+β²，β²+β³，1+β+β³，...1+β³，}

由于β是用于GF(2⁴)的质元素，它可被设置为2以生成GF(2⁴)的域元素为{0，1，2，4，8，3，6，12，11，..9}。

可以看到，Galois域多项式乘法可以以两个基本步骤被实施。第一步骤是计算多项式乘积c(x)＝a(x)*b(x)，它被代数展开，以及同幂次被合并(加法相应于在相应的项之间的XOR运算)给出c(x)。

例如c(x)＝(a₃x³+a₂x²+a₁x¹+a₀)*(b₃x³+b₂x³+b₁x¹+b₀)

c(x)＝c₆x⁶+c₅x⁵+c₄x⁴+c₃x³+c₂x²+c₁x¹+c₀

                                      其中：

图表I

c₀＝a₀*b₀

c₁＝a₁*b₀a₀*b₁

c₂＝a₂*b₀a₁*b₁a₀*b₂

c₃＝a₃*b₀a₂*b₁a₁*b₂a₀*b₃

c₄＝a₃*b₁a₂*b₂a₁*b₃

c₅＝a₃*b₂a₂*b₃

c₆＝a₃*b₃

第二步骤是计算d(x)＝c(x)模p(x)

为了说明起见，乘法通过多项式以不可约多项式为模的乘法进行。例如，(如果m(x)＝x⁸+x⁴+x³+x+1)

{57}*{83}＝{c1}因为

第一步骤

(x⁶+x⁴+x²x+1)+(x⁷+x+1)＝x¹³x¹¹x⁹x⁸x⁷

                        x⁷x⁵x³x²x

                        x⁶x⁴x²xx

                      ＝x¹³x¹¹x⁹x⁸x⁶x⁵x⁴x³1

第二步骤

x¹³+x¹¹+x⁹+x⁸+x⁶+x⁵x⁴+x³+1 modulo(x⁸+x⁴+x³+x+1)

                     ＝x⁷+x⁶+1

实现了这个方法的改进的Galois域乘法器系统10，包括乘法器电路，用于把具有在Galois域上的系数的在A寄存器中的两个多项式a₀-a₇与在B寄存器中的多项式b₀-b₇相乘，以得到它们的乘积，这由如图表II定义的15项多项式c(x)给出。乘法器电路实际上包括多个乘法器小单元。

图表II

c14＝a7*b7

c13＝a7*b6a6*b7

c12＝a7*b5a6*b6a5*b7

c11＝a7*b4a6*b5a5*b6a4*b7

c10＝a7*b3a6*b4a5*b5a4*b6a3*b7

c9＝a7*b2a6*b3a5*b4a4*b5a3*b6a2*b7

c8＝a7*b1a6*b2a5*b3a4*b4a3*b5a2*b6a1*b7

c7＝a7*b0a6*b1a5*b2a4*b3a3*b4a2*b5a1*b6a0*b7

c6＝a6*b0a5*b1a4*b2a3*b3a2*b4a1*b5a0*b6

c5＝a5*b0a4*b1a3*b2a2*b3a1*b4a0*b5；

c4＝a4*b0a3*b1a2*b2a1*b3a0*b4

c3＝a3*b0a2*b1a1*b2a0*b3

c2＝a2*b0a1*b1a0*b2

c1＝a1*b0a0*b1

c0＝a0*b0

Galois域乘法器系统的操作在2002年1月30日提交的、Stein等的、题目为GALOIS FIELD MULTIPLIER SYSTEM[AD-240J]10/060,699的美国专利申请中说明，该专利申请整体地在此引用以供参考。

15个多项式c(x)项的每个项包括如由一个*代表的与(AND)功能，以及每对项与如由一个*代表的逻辑异或相组合。如在CHART II表示的这个乘积被提交到Galois域线性变换器电路，它可包括多个Galois域线性变换器单元，每个由15×8个小单元组成，它们相应于由乘法器电路产生的乘积，以便对于预定的不可约多项式预测多项式乘积的模余数。A₀，B₀的乘法在第一单元中进行，A₁，B₁的乘法在第二单元中进行，A₂，B₂的乘法在第三单元中进行，以及A_n，B_n的乘法在最后单元中进行。Galois域线性变换器电路和它的每个变换器单元的操作在2002年1月18日提交的、Stein等的、题目为GALOIS FIELDLINEAR TRANSFORMERER[AD-239J]10/051,533的美国专利申请中说明，该专利申请整体地在此引用以供参考。每个Galois域线性变换器单元通过把多项式乘积除以不可约多项式而预测模余数。该不可约多项式例如可以是图表III上所示的任一个多项式。

图表III

：GF(2¹)

0x3(x+1)

：GF(2²)

0x7(x²+x+1)

：GF(2³)

0XB(x³+x+1)

0XD(x³+x²+1)

：GF(2⁴)

0x13(x⁴+x+1)

0x19(x⁴+x³+1)

：GF(2⁵)

0x25(x⁵+x²+1)

0x29(x⁵+x³+1)

0x2F(x⁵+x³+x²+x+1)

0x37(x⁵+x⁴+x²+x+1)

0x3B(x⁵+x⁴+x³+x+1)

0x3D(x⁵+x⁴+x³+x²+1)

：GF(2⁶)

0x43(x⁶+x+1)

0x5B(x⁶+x⁴+x³+x+1)

0x61(x⁶+x⁵+1)

0x67(x⁶+x⁵+x²+x+1)

0x6D(x⁶+x⁵+x³+x²+1)

0x73(x⁶+x⁵+x⁴+x+1)

：GF(2⁷)

0x83(x⁷+x+1)

0x89(x⁷+x³+1)

0x8F(x⁷+x³+x²+x+1)

0x91(x⁷+x⁴+1)

0x9D(x⁷+x⁴+x³+x²+1)

0xA7(x⁷+x⁵+x²+x+1)

0xAB(x⁷+x⁵+x³+x+1)

0xB9(x⁷+x⁵+x⁴+x³+1)

0xBF(x⁷+x⁵+x⁴+x³+x²+x+1)

0xC1(x⁷+x⁶+1)

0xCB(x⁷+x⁶+x³+x+1)

0xD3(x⁷+x⁶+x⁴+x+1)

0xE5(x⁷+x⁶+x⁵+x²+1)

0xF1(x⁷+x⁶+x⁵+x⁴+1)

0xF7(x⁷+x⁶+x⁵+x⁴+x²+x+1)

0xFD(x⁷+x⁶+x⁵+x⁴+x³+x²+1)

：GF(2⁸)

0x11D(x⁸+x⁴+x³+x²+1)

0x12B(x⁸+x⁵+x³+x+1)

0x12D(x⁸+x⁵+x³+x²+1)

0x14D(x⁸+x⁶+x³+x²+1)

0x15F(x⁸+x⁶+x⁴+x³+x²+x+1)

0x163(x⁸+x⁶+x⁵+x+1)

0x165(x⁸+x⁶+x⁵+x²+)

0x169(x⁸+x⁶+x⁵+x³+1)

0x171(x⁸+x⁶+x⁵+x⁴+1)

0x187(x⁸+x⁷+x²+x+1)

0x18D(x⁸+x⁷+x³+x²+1)

0x1A9(x⁸+x⁷+x⁵+x³+1)

0x1C3(x⁸+x⁷+x⁶+x+1)

0x1CF(x⁸+x⁷+x⁵+x³+x²+x+1)

0x1E7(x⁸+x⁷+x⁶+x⁵+x²+x+1)

0x1F5(x⁸+x⁷+x⁵+x⁴+x²+1)

这里给出的Galois域乘法器GF(2⁸)能够对于幂次2⁸与幂次2⁴以及在如下图表III所示的进行。

GF乘法的例子为如下：

在GF()乘法之前：                   在GF9()乘法之后：

多项式0x11d                        多项式0x11d

45 23 00 01h                       45 23 00 01h

GF()                               GF()

$>>>57340001>h>>xx>>>s>$ >>>57340001>h>>>72920001>h>>>s>$$

图1上显示紧凑式Galois域乘法机10其伴随有A输入寄存器12、B输入寄存器14和C输出寄存器16。紧凑Galois域乘法机10能够进行多种不同的运算，包括乘、乘加和乘法累加(multiply-accumulate)。

传统的Galois域乘法机10a，图2，需要三个寄存器，A寄存器12a、B寄存器14a和C寄存器26a。这些寄存器的负担必须由相关的数字信号处理器(DSP)核心28承载，以及需要很大的外部总线工作。除了用于提供数据到A寄存器12a的总线30、用于提供数据到B寄存器14a的总线34和用于提供数据到C寄存器26a的总线36以外，需要用于把来自寄存器16a的输出反馈到数字信号处理器28的总线32和用于把从数字信号处理器28输出的数据反馈到B寄存器14a或C寄存器26a的总线34或总线36。总线31连接Galois域线性变换器电路20与输出寄存器16a。因此多项式乘法器电路18可以把适当的数值提供到Galois域线性变换器电路20的矩阵22的乘法输入端40，连同从C寄存器26a反馈到矩阵22的加法器输入端42的数值，以执行乘、乘加和乘法累加功能。矩阵22在这里被显示为8×15矩阵，用于支持幂次8的多项式的乘法，但它可以被做成更大或更小，包含更多或更少的单元24，取决于要被提供服务的多项式的幂次。

在机器10b中Galois域线性变换器电路20b的矩阵22b的图3的每行的单元24b的数目通过把矩阵22b配置成两个矩阵部分，即矩阵部分50和单位矩阵部分52，而可以减小一半。单位矩阵部分只需要一组单元54，其中当乘法器电路的输出是具有小于不可约多项式幂次的幂次的多项式时，这些单位矩阵部分单元代表余数的预测。因此，在图3上，其中不可约多项式具有8的幂次，小于8的任何多项式将不超过模数，以及将被通过矩阵，因此在单位矩阵部分52中的缺失的小单元是不必要的。这几乎节省矩阵22a所需要的单元的一半，导致更小的、更简单的和更快速的机器。

图4的每个单元24b可包括与电路100和异或电路102。有数据输入端104和使能输入端106。异或电路102把在线108上的输出提供到下一个异或电路的输入端以及在它的输入端110处接收来自前面的异或电路的输出，除了其输出被连接到矩阵的输出端的最后的异或电路，以及其输入端被连接到加法器电路--图3的42b或图9的42g--的第一个异或电路以外。在线106上的使能信号使得线104上的数据能够传送通过与门100以及由异或电路102对于它与线110上的输入执行异或运算。线106上使能信号的缺乏只把线110上的输入通过异或门102传送到输出线108。在线106上的使能信号使能单元24。这样，这个矩阵可能对于任何特定的不可约多项式被重新配置。

图3的机器10b的效能可以通过从图表III选择不可约多项式，如上文，以及通过使能必须的小单元来实施它而被理解。例如，为了实施代表不可约多项式x⁸+x⁴+x³+x²+1、被称为0x11d的、幂次8的第一多项式，被使能的小单元，总的用24cc表示，通过如以前在图3上显示的单元54c的线形成单位矩阵52c，图5。当从图表III选择第二不可约多项式0x12b时，不可约多项式x⁸+x⁵+x³+x+1产生在矩阵部分50d和单位矩阵部分52d中的使能的小单元，图6的24dd，的模式，其中单位矩阵部分52d再次导致使能的小单元54d的线。

需要的小单元的数目的减小不仅仅限于具有与不可约多项式相同的幂次的多项式。它也适用于任何具有不可约多项式的幂次的一半或更小的幂次的多项式。例如，8×15矩阵22b(图3所示的和在图5与6上为了说明被参考的)也可以支持幂次为1，2，3或4的多项式，但不支持幂次为5，6和7的多项式，如果不可约多项式幂次是16，支持它的矩阵也可以支持幂次直到8的多项式，但不支持9到15的多项式。如果它是32的幂次，则它可以支持32幂次直到16的多项式，但不支持17到31的多项式。例如，如图7所示，对于四次方的不可约多项式，矩阵部分50e和单位矩阵部分52e变为更小的，以及可以在矩阵22e内的任何地方被实施。这里，矩阵部分50e具有多个使能的小单元24ee，以及在单位矩阵52e中的使能单元，它们现在具有使能的小单元54e的更小的线，形成单位矩阵部分52e。

如果希望为幂次为5，6和7的中间多项式服务，单位矩阵部分可以用稀疏矩阵部分52f代替(图8)，在其中使能的小单元52ff，52fff，52ffff的附加线可被利用来分别支持幂次为7，6和5的多项式。但它多少了对于降低矩阵的尺寸和需要的单元数目的减小。

输入寄存器的数目可以从3减小到2，以及所依赖的与数字信号处理器(DSP)28g，图9，的通信的外部总线的数目可被减小并本地化为机器10g本身的内部。因此，如图9所示，只有两个输入寄存器A12g和B14g，来自输出端31g的反馈不需要通过DSP28g而是在机器10g上通过内部总线60直接地本地地进到乘法器输入部分62和加法器输入选择电路64。数字信号处理器28g只需要把线66上的控制信号提供到乘法器输入部分62和把线68上的控制信号提供到加法器输入选择电路64。因此，在相乘模式下，乘法器输入选择电路62把来自B寄存器14g的输入传送到多项式乘法器电路18g，而加法器输入选择电路64把加性相同电平(additive identity level)(在本例中是地电平70)提供到Galois域线性变换器电路20g的加法器输入端42g。在乘加模式下，数字信号处理器28指令乘法器输入选择电路62把来自矩阵22g的输出通过线60反馈到多项式乘法器电路18g和指令加法器输入选择电路64把在B寄存器14g中的多项式传送到Galois域线性变换器电路20g的加法器输入端42g。在乘-累加模式，数字信号处理器28指令乘法器输入选择电路62把来自B寄存器14g的多项式传递到多项式乘法器电路18g和指令加法器输入选择电路64反馈Galois域线性变换器电路20g的、在线60上的输出。

另一个特性是藉助于选择地使能小单元24g而得到的Galois域线性变换器电路20g的可重新配置性。可重新配置的控制电路80选择地使能对于实施所选择的不可约多项式的系数所需要的一个单元24g，并且可以减小它本身尺寸，因为它需要控制的小单元的数目已经减小。

可重新配置的输入Galois域线性变换器电路的操作在2002年5月1日提交的、Stein等的、题目为RECONFIG URABLE INPUTGALOIS FIELD LINEAR TRANSFORMERER SYSTEM(AD-300J)的美国专利申请序列号No.10/136,170和所有的它的优先权申请和文件中被说明，它们整体地在此引用以供参考。

虽然至今为了简单性起见，说明仅仅是对于一个机器作出的，但多个机器可以一起被利用，如图10所示，其中每个机器具有乘法器电路10h，10i，10j，10k...10n和Galois域线性变换器20h，20i，20j，20k...20n电路。通过单个中央可重新配置的控制电路80¹控制它们全部，这些机器可以共享同样的宽度[32，64，128]比特，A和B寄存器每个工作在不同的8比特(字节)分段上，或每个可以由它的自己的可重新配置的控制单元80h，80i，80j，80k...80n提供服务，以及每个由它的自己的A和B寄存器对A₀和B₀，12h和14h；A₁和B₁，12i和14i；A₂和B₂ 12j和14j；A₃和B₃，12k和14k等等服务。

在这里所示的实施例中可使用来提供输出c0-c14的多项式乘法器电路181，(图11)，其包括多个与门120，它们与异或门122相组合可以把任何来自A寄存器12I与B寄存器14I的多项式对(例如如图12的表124所示的多项式a0-a7，多项式b0-b7)相乘。

在图13上显示按照本发明的Galois域除法机150，包括Galois域倒数生成器155，具有Galois域乘法器152和第二Galois域乘法器154，用于执行平方功能。机器150通过执行操作β_l*1/β_k执行除法β_l/β_k，其中β_l和β_k是Galois域的元素，例如当m＝8时，也就是GF(2⁸)：域的度是8。初始地，Galois域乘法器152接收1和β_k，以及把它们相乘。然后该输出在Galois域乘法器154中进行平方以及被反馈到Galois域乘法器152。这个结果被反复乘以β_k共m-2次，这样，总共发生m-1次迭代。这时，得到倒数1/β_k以及代替β_k被提供，(因为β_k已经经过m-2次迭代的每次迭代)，现在β₁被提供来执行乘法β_l*(1/β_k)。因此，在总共m次迭代中发生整个除法，m-1次用于生成倒数和1次用于把除数的倒数与被除数相乘以得到商。定时地施加“1”，β_k和β₁由输入选择电路171执行。

$>>>\beta >>>2>m>>->2>>>=>>1>\beta >>>s>的事实通过以下的说明来证明，给定：$

GF(q)的域由数字{0，1，...(q-1)}组成。如果我们把{0，1，...(q-1)}的每个成员乘以β(β是域成员并≠0)，以得到{1β，2β，...(q-1)β}，我们可以容易地看到，我们再次得到相同的组(具有改变的序号)。这意味着，1·2·...·(q-1)＝1β·2β·...(q-1)β＝1·2·...·(q-1)β^(q-1)通过从两个边消除因子1·2·...·(q-1)保证得到：

β^q-1＝1.                                             (1)

所以

β^-1＝β^q-2                                          (2)

用2^m代替q，导致表达式：

$>>>\beta >>>2>m>>->2>>>=>>1>\beta >>->->->>(>3>)>>>s>$

图13是这个表达式的直接的实现。

按照(3)，对于n＝7我们需要计算β²⁵⁴。β²⁵⁴可被计算为β¹²⁸·β⁶⁴·β³²·β¹⁶·β⁸·β⁴·β²。它们可被迭代地计算为

n＝1：(β·1)²＝β²

n＝2：(β²·1)²＝β⁴·β²

n＝3：(β⁴·β²·β)²＝β⁸·β⁴·β²＝β¹⁴

.

.

.

.

n＝7：(β⁶⁴·β³²·β¹⁶·β⁸·β⁴·β²·β·)²＝β¹²⁸·β⁶⁴·β³²·β¹⁶·β⁸·β⁴·β²＝β²⁵⁴

图13的电路从1的初始值开始以及在155时生成以下连续的数值：

 迭代数  1  2  3  4  5  6  7 在点155的数值  β³  β⁶  β¹⁴  β³⁰  β⁶²  β¹²⁶  β²⁵⁴

可以看到，β^-1的最终的数值在(n-1)次循环中得到。相同的电路对于所有的中间的幂次mGF(2^m){m＝3.7}的生成，例如，如果m＝4，则在n＝3时生成 $>>>\beta >>>2>m>>->2>>>=>14>.>>s>$

在一个实施例中，Galois域倒数生成器155a，图14，可包括Galois域乘法器152a和Galois域乘法器154a。Galois域乘法器152a包括Galois域线性变换器156和多项式乘法器158。Galois域乘法器156被显示为包括具有两个部分的异或小单元的矩阵、矩阵部分160和减小的单位矩阵部分162，但这并不是对于本发明的必须的限制，因为单位矩阵部分162可以用满阵(full matrix)实施，矩阵部分160也是如此，如果尺寸不成问题的话。Galois域乘法器154a也包括多项式乘法器164和Galois域变换器166，它也可包括，但是必须地，满阵部分168和减小的单位矩阵部分170。这里再次地，单位矩阵170在花费和面积上是有利的，但不是必须地，因为在那里可以使用满阵部分。Galois域除法机150a以m次迭代执行除法。在第一次迭代时，输入选择电路171把与β_k相组合的1引入Galois域乘法器152a，这产生在线172上的输出β_k，它被传递到Galois域乘法器154a的多项式乘法器输入端174，176。因此，执行平方函数，以及把输出反馈到输入选择电路171的输入端178。这个迭代进行m-2次，其中m是Galois域的度。在m-2次迭代后，输入选择电路171把被除数引入Galois域乘法器152a，因为这时在输出端178处的数值是倒数1/β_k。通过把β_l(被除数)乘以1/β_k(除数的倒数)，结果是β_l被除以β_k，在180处得到Galois域除法的商。

在输入端174和176处的数值具有从最高有效位到最低有效位，b₇-b₀和a₇-a₀的形式。当如这里执行平方函数时，则值b₇-b₀的每个值将分别是与值a₇-a₀的每个值相同的，因为它们是相同的数。数字b₇-b₀，a₇-a₀的数取决于多项式的尺寸，在m是8的情形下它是8个数字。无论是什么尺寸，因为在输入端处数值是相同的，异或函数将是零。也就是，进到异或门的相同的输入得到零输出，这是熟知的。因此，再次参照图12，可以看到，对于每个多项式乘法输出c₀-c₁₄，在图12上奇数编号的输出包含相同数值的对。例如，c₁等于a₁*b₀a₀*b₁。因为我们正在进行平方，我们知道在输入端174和176给出的两个数值是相同的，所以a₀和b₀是相同的以及a₁和b₁是相同的。所以c₁在被异或运算时将具有零的数值。这对于其它奇数编号的Galois域乘法器输出c₃，c₅，c₇，c₉，c₁₁，c₁₃同样是正确的。结果显示于图15的182处，其中不仅可以看到，在奇数编号的c₁-c₁₃最终结果的零值，而且剩余的非零偶数编号的数值不需要异或门，而只需要进行乘法。例如，c₀是a₀*b₀。但这是最简单的与函数，导致a₀的数值。类似地，对于c₂，把数值a₁乘以b₁，给出与函数，它导致a₁的简单的输出。相同的结果在c₄，c₆，c₈，c₁₀，c₁₂，和c₁₄中是正确的。这也适用于Galois域乘法器156b。实施平方函数的Galois域乘法器154b可以在尺寸上减小一半，这是通过矩阵部分168b和单位部分170b减小一半达到的。另外，由于功能已经转到简单的输入，如图15的列184所示，不需要两个分开的输入，所以不再需要多项式乘法器164。

Galois域变换器156c和166c，图17，被同样地实施。涂黑的圆圈表示在每个变换器中的使能的异或门小单元。编程是由在列190上的代码完成的，以及对于两个变换器156c和166c是相同的。变换器156c接收输入c₀-c₁₄以及提供输出A₀-A₇。这些形成Galois域线性变换器166c的、具有为0的A₀-A₇的输入，线性变换器166c的最后的输出是B₀-B₇。这两个变换器是对于不可约多项式(0x12b)的度8的Galois域GF(2⁸)(m＝8)被实施的。当实现图15所示的减小时，Galois域乘法器156d，图18，同样地在列190d执行所有的编程的指令，但Galois域线性变换器166d使所有其它的列，即零列取消，导致图16所示的结构。

当Galois域除法机如图16所示地被减小时，现在可以达到进一步的减小。因为Galois域除法机154b在第二Galois域变换器166b中没有多项式乘法器，可以构建单个矩阵或变换器，它在一个周期中以及通过使用单个线性变换器200(图19)直接从c₀-c₁₄传递输出B₀-B₇而不用中间项A₀-A₇。变换器200被编程来使能由涂黑色的圆圈表示的异或门小单元的组合，以便在一个Galois域线性变换器中和一次操作中执行Galois域线性变换。因此，输入c₀-c₁₄被Galois域线性变换器200直接变换成最后的输出B₀-B₇。通过使用B₇，图18，的简单的图示可以看到将两个矩阵156d和166d，图18，的减小到图19的单个矩阵Galois域线性变换器200的混合，它可被看作为等效于异或A₇，A₆和A₅，如Galois域线性变换器166d所示。然后参照Galois域线性变换器156d(其中划线表示取消项目，因为它是重复的)，可以看到，

A₅等于c₁₄，c₁₃，c₁₂，c₈，c₅

A₆等于c₉，c₆，

A₇等于and c₇，

在它们之间都利用异或函数。这导致输出c₁₄，异或c₁₃，异或c₁₂，异或c₉，异或c₈，异或c₇，异或c₆，异或c₅。因此，在矩阵200中，图19，B7可被看作为包括c₁₄，c₁₃，c₁₂，c₉，c₈，c₇，c₆和c₅的异或组合。这样的混合Galois域除法机202的一个实现显示于图20，其中图19的Galois域线性变换矩阵200与多项式乘法器204和带有双输入选择单元206，208的输入选择电路171e一起出现。现在Galois域倒数生成器205通过单个混合Galois域线性变换器200被实施。输入选择单元206能够执行乘加(MPA)，乘法累加(MAC)，和乘(MAY)。输入选择单元208类似地起作用和把如前所述的加法器输入提供到Galois域线性变换器200。程序序列器210提供控制触发器212的映射，所述触发器使能和禁止包括异或门的小单元的矩阵。程序序列器可以编程GFLT矩阵200作为在用于除法的一个周期中执行(GF_MPY(α，β))²的混合乘法器，作为用于乘法的Galois域乘法器，作为用于相乘和积累的相乘和积累，和作为用于乘加功能的乘加。

在操作中，一开始GFLT被编程作为执行(GF_MPY(α，β))²的混合乘法器，把1提供在输入端214处和把β_k提供在输入端216处。此后对于m-2次迭代，输出180被反馈到输入端214，而β_k保持在输入端216。在m-2次迭代后，当系统经过总共m-1次迭代时，在214处的输入现在是β_k的倒数。这时，GFLT被编程为Galois域乘法器，在输入端216处的β_k现在用输入β_l代替，这样，下一个乘法，第m次迭代，把β_l乘以β_k的倒数，提供输出β_l除以β_k。本发明的Galois域除法方法显示于图21，其中在开始时240，提供除数β_k和被除数β_l。然后在步骤242，进行关于这次迭代是否为第m次迭代的询问，其中m是所涉及的Galois域的度。如果这是第m次迭代，则系统直接进到步骤244，在其中执行β_l与Galois域线性变换输出的倒数1/β_k的Galois域乘法。然后在246产生商。如果迭代没有达到m，则在步骤248进行关于它是否为第一次迭代的询问。如果是的话，则在步骤250实施β_k与1的乘法，以及然后在步骤252在Galois域上执行该数值的平方。如果它不是第一次迭代，作为在步骤254，执行β_k与Galois域线性变换输出的Galois域乘法，然后在步骤252在Galois域乘法器中执行平方。来自平方计算的输出然后被反馈(步骤242)，再次开始迭代。

至今为止本发明集中在Galois域除法机和方法上，以及通过首先减小一个Galois域线性变换器的尺寸和取消一个多项式乘法器而减小该机器尺寸的能力，以及然后组合两个线性变换器的功能以使得对于一系列多项式输入执行一系列Galois域线性变换以得到最后的输出(商)，如图19和20所示。但这并不是对于本发明的必须的限制，也就是本发明不仅仅限于除法。按照本发明的混合Galois域机可以对于一系列多项式输入执行任何连续的Galois域线性变换以得到最后的输出，其中每个输入，除了第一个以外，是以前的Galois域线性变换的输出。也就是，在一次变换中，它可以立即预测不可约Galois域多项式的连续的Galois域线性变换的模数余数，以便直接从第一输入得出Galois域线性变换的最后输出。

这个事实的另一个例子可以在Galois域成员β的平方根运算中看到。图22上显示按照本发明的混合Galois域机300，它执行(m-1)次连续的Galois域线性变换302，304，...306，其中第一输入β，308被提交到Galois域变换器302，然后变换的输出变为输入加到下一个Galois域线性变换器304，它的输出变为输入加到下一个Galois域线性变换器，等等，直至它达到最后的变换器306为止，正如在本例中那样，输出。按照本发明，通过混合Galois域线性变换器310，图23，图22的(m-1)个变换器可被减小为图23所示的仅仅一个GFLT的简化的实施方案，其中初始输入β可以通过混合Galois域线性变换器平方根机330在单次运行中被变换，以便在一次迭代中提供输出。

$>>>\beta >>=>>\beta >>2>>(>m>->1>)>>>>>s>的事实通过以下给出的说明被证明：$

在(1)中我们已证明β^q-1＝1.

用2^m代替q以及在两边乘以β，导致表示式：

$>>>\beta >>2>m>>>=>\beta >->->->>(>4>)>>>s>$

在两边取导致表示式：

$>>>\beta >>>(>>2>m>>)>>/>2>>>=>>\beta >>->->->>(>5>)>>>s>$

或

$>>>\beta >>2>>(>m>->1>)>>>>=>>\beta >>->->->>(>6>)>>>s>$

图22是这个表示式的直接实现。

本发明的Galois域平方根方法显示于图24，在其中在开始312时，提供域元素β。然后在步骤314，进行关于这次迭代是否为第m-1次迭代的询问，其中m是所涉及的Galois域的度。如果这是第m-1次迭代，则系统直接进到步骤316，在其中产生β的Galois域平方根。如果迭代还没有达到m-1，则在步骤318进行关于它是否为第一次迭代的询问。如果是的话，则在步骤320在Galois域上执行该β值的平方。如果它不是第一次迭代，则在步骤322在Galois域上执行Galois域线性变换输出的平方。然后，在步骤314，来自平方计算的输出被反馈，以及迭代重新开始。编程电路控制触发器212a和编程序列器210a，编程Galois域线性变换器平方机330，如图23所示。

总之，按照本发明的混合Galois域机260，图25，通常可以执行多种连续的Galois域线性变换262，264，266，268，其中第一输入A270被提交到Galois域变换器262，然后变换的输出B变为加到下一个Galois域线性变换器264的输入，它的输出C又变为加到下一个Galois域线性变换器266的输入，它的输出D又变为加到下一个Galois域线性变换器268的输入，等等。在这种情形下，最后的输出是E。按照本发明，通过如图19所示混合Galois域线性变换器，通过减小图18的两个变换器以产生如图20所示的实施方案，初始的输入A可以通过混合的Galois域线性变换器280在单次操作中被变换，在它的一次迭代中提供最后输出E。

虽然本发明的具体的特性在某些附图中被显示以及在其它附图中未示出，但这仅仅是为了方便起见，因为每个特性可以与按照本发明的任何的或所有的其它特性相组合。这里所使用的单字“包括”，“具有”，和“带有”，被广泛地和全面地解译，而不限于任何物理的互联。而且，在本申请中公开的任何实施例不被看作为唯一可能的实施例。

本领域技术人员将会看到其它实施例以及这些实施例属于以下的权利要求内。