一种对顺序移动窗口中数据序列进行多项式运算的方法

摘要

本发明公开一种对顺序移动窗口中数据序列进行多项式运算的方法。该方法实现的结构包括运算模块1(100)、N次移位寄存器(101)、运算模块2(110)、组合逻辑模块(111)和减法器(000)，如图所示。对于一串行数据，假设有一个大小为N的窗口，开始时窗口里的数据序列是第1位到第N位数组成的N位连续数据。工作开始后，输入N位数据，得到窗口中的N位数据经过运算后得到的有效输出，窗口顺序移动一位，窗口里的数据序列是第2位到第N+1位数组成的N位连续数据，再输入一位，得到窗口中的N数据经过运算后得到的有效输出，……，这样实现了对顺序移动窗口中数据序列进行多项式运算。

说明书

技术领域

本发明属于数字信号处理技术领域中多项式运算方面的内容。

背景技术

在数字信号处理领域，经常会对信号进行多项式运算处理。本领域中的多项式运算中，乘除法运算与普通的运算没有区别，一般用线性反馈移位寄存器(LFSR)来实现的。加减法与一般的运算不同，加减运算过程中都是对两个输入的对应位进行模2加运算，实现的电路为异或运算，运算中没有进位。多项式运算装置可以由若干个线性反馈移位寄存器(LFSR)、一些寄存器和由包含一些异或门的组合电路构成。

图1和图2图示了具有不同反馈机制的两个线性反馈移位寄存器(LFSR)的电路示意图，图中电路的输入为一位，对串行数据进行运算，每输入一位数据得出一次输出。通常线性反馈移位寄存器(LFSR)进行的是多项式乘除法的运算，一般所需的结果有两种，一种是经过运算后输出端输出的结果，即通常多说的商或积，也可以是商或积中的某几位；另一种是经过运算后运算装置各个寄存器的输出状态结果，即通常所说的余数，也可以是余数中的某几位。

图1和图2中，Z^-1表示一位移位寄存器，每个线性反馈移位寄存器(LFSR)包含若干个这样的寄存器。相邻寄存器之间可以有一个异或门，即上一个寄存器的输出与反馈信号经过异或运算后，得出的数据作为下一个寄存器的输入；相邻寄存器之间也可以直接连接，即上一个寄存器的输出直接作为下一个寄存器的输入。

多项式运算装置由若干个线性反馈移位寄存器(LFSR)、一些寄存器和由异或门组成的组合电路构成的。在开始工作前一般都需要确定初始状态，即确定运算装置中各个寄存器的输出状态。在输出端，运算装置中某几个寄存器的输出和某几个异或门的输出组成的数据，作为所需要的输出结果。

通常使用的多项式运算装置对一组串行数据进行多项式运算后，要想对另一组数据进行运算，需要重新确定运算装置的初始状态。

发明内容

本发明提出的一种对顺序移动窗口中数据序列进行多项式运算的方法，适用于多项式运算的初始状态为0的条件下。

对于一组X位串行数据，假设有一个大小为N的窗口，开始时窗口里的数据序列是第1位到第N位数组成的N位连续数据，顺序移动一位，窗口里的数据序列是第2位到第N+1位数组成的N位连续数据，再顺序移动一位，窗口里的数据序列是第3位到第N+2位数组成的N位连续数据，……，顺序移动(X-N+1)位后，窗口里的数据序列是第X-N位到第X位数组成的N位连续数据，这样，一组X位串行数据包含(X-N+1)组N位连续数据。

一般情况下，对这(X-N+1)组数据进行多项式运算，需要进行(X-N+1)轮运算，而且每轮运算前需要重新设置运算装置的初始状态。由于每轮运算都需要输入N位串行数据，所以每轮运算需要进行N次运算。

本发明提出的一种对顺序移动窗口中数据序列进行多项式运算的方法，适用于运算装置的初始状态为0时的运算，使用本发明提出的方法对这(X-N+1)组数据进行多项式运算，可以减少运算的次数。

具体的工作过程如下：

工作开始时，设置运算初始状态为0，输入N位数据后，得到由第1位到第N位数据组成的N位数经过运算后得到的有效输出，再输入一位，可以得到由第2位到第N+1位数组成的N位数经过运算后得到的有效输出，再输入一位，可以得到由第3位到第N+3位数组成的N位数经过运算后得到的有效输出，……，如图3所示。

本发明提出的一种对顺序移动窗口中数据序列进行多项式运算的方法，其原理为：

通常进行多项式运算，都是运算装置初始化后，即将运算装置的各个寄存器的输出状态设置为特定的状态后，再进行运算。当需要设置的初始状态为0时，如果开始时，运算装置的各个寄存器的输出状态不为0，这样再进行运算，初始状态对运算结果造成了影响，得不到所需要的结果，可以通过下面的方法消除初始状态对运算结果造成的影响。

采用两个相同的多项式运算装置，这两个装置的初始状态相同，都不为0。对第一个运算装置输入所要进行运算的N位数据，得出一个结果，对第二个运算装置输入N位大小为0的数据，得到一个结果，把得到的两个结果相减，即进行异或运算，得到的结果与N位数据在初始状态为0的运算装置中运算的结果相同。

含有R个寄存器的多项式运算装置，它的初始状态有2^R种，对于第二个运算装置来说，每一种初始状态对应不同的输出，可以用归纳的方法得出它们之间的逻辑关系。如果运算所需要的输出为M位，这样可以用一个R位输入M位输出的组合逻辑代替第二个多项式运算装置进行0输入运算的操作过程。

本发明提出的一种对顺序移动窗口中数据序列进行多项式运算的方法，其实现的结构图如图4所示。此种方法的实现需要两个多项式运算模块，它们包含相同的多项式运算装置，都包含R个寄存器，而且它们输入的数据也相同，但是输入数据经过N-1次移位后输入到第二个多项式运算模块的运算装置中，定义这两个多项式运算模块为运算模块1和运算模块2。

N-1次移位寄存器，即Z^-(N-1)，用于使输入数据经过N-1次移位后输送给运算模块2。

运算模块1用多项式运算装置对输入数据进行运算。它输出有两种情况，一种是所需要的结果是N个数据经过N次运算得出的N个输出，或者是N个输出中的M个，这种情况下多项式运算装置的输出端最多需要连接N-1个移位寄存器，当需要的结果是N个输出的后M个时，多项式运算装置的输出端需要连接M-1个移位寄存器，将多项式运算装置的输出与移位寄存器中的M-1个数组成的M位数据A输送给减法器。另一种情况是所需要的结果是多项式运算装置的最终状态，这时不需要另外的移位寄存器，直接输出所需要的M个状态组成的M位数据A，输送给减法器。

运算模块2包含和运算模块1中相同的多项式运算装置，用于产生各组数据运算前的初始状态，输出为模块中各个寄存器的输出状态，为R位，并将此R位输出数据B输送给组合逻辑模块。

组合逻辑模块用于计算初始状态对运算模块1造成的影响，对来自运算模块2的R位数据B进行逻辑运算得出M位的输出结果C，并输送给减法器。

减法器有两个输入，分别来自运算模块的数据A与组合逻辑模块数据C，对两个输入进行多项式减法运算，即进行异或运算，得出所要的数据作为输出，同时也是整个装置最终的输出。

本发明提出的方法可以实现对顺序移动窗口中数据序列进行多项式运算，实现方法简单，运用广泛。

附图说明：

图1为具有一种反馈机制的线性反馈移位寄存器(LFSR)电路示意图；

图2为具有另一种反馈机制的线性反馈移位寄存器(LFSR)电路示意图；

图3为本发明的具体工作过程的示意图；

图4为本发明的实现结构图；

图5为实施例所用的多项式运算装置的电路图。

具体实施方式：

下面通过一个具体的实施例子，结合附图来进一步说明本发明。

本实例要得出一组串行数据中任意连续5位数据经过运算后的结果。

本实例使用的多项式运算装置如图5所示，它包含9个寄存器，输出为一个异或门的输出。在多项式运算装置初始状态为0的条件下，本实例要得出一组串行数据中任意连续5位数据经过此运算装置进行5次运算后输出的5位数据。

由本发明提出的方法，结构图如图4所示。

运算模块1包括多项式运算装置和4个移位寄存器。由运算装置的输出和4个移位寄存器的输出组成的5位数据作为运算模块1的输出数据A，并输送给减法器。

输入数据经过一个4次移位寄存器后，输送给运算模块2。

运算模块2包含此多项式运算装置，它的输出为多项式运算装置的9个寄存器的输出状态构成的9位数据B。

多项式运算装置有9个寄存器，有2⁹种状态，输入数据全为0的话，对应2⁹种输出。利用归纳法得出一个9位输入5位输出的组合逻辑电路，或者可以用查表法得出一个9位输入5位输出的组合逻辑电路，组合逻辑模块由此组合逻辑电路组成，输入为运算模块2的9位输出数据B，输出为5位输出数据C，并将数据C输送给减法器。

减法器将来自运算模块1的5位数据A和来自组合逻辑模块5位输出数据C进行多项式减法操作，即进行异或操作，得出的结果为最终的输出。

具体工作过程如下：

工作开始时，对所有存储单元初始化，设置为0。输入5位数据后，得出由第1位到第5位数据组成的5位数经过运算后得到的有效输出，再输入一位，可以得到由第2位到第6位数组成的5位数经过运算后得到的有效输出，再输入一位，可以得到由第3位到第7位数组成的5位数经过运算后得到的有效输出，……，实现了5组数据同时进行多项式运算。

本发明提出的方法可以实现对顺序移动窗口中数据序列进行多项式运算，实现方法简单，运用广泛。