一种并行LFSR架构的实现方法

技术领域

本发明属于硬件系统中的并行LFSR架构设计技术领域，涉及应用LFSR的 硬件电路设计，如并行BCH编码器构造和CRC校验编码器构造，更为具体的是， 设计应用高速并行LFSR架构处理数据的硬件系统。

背景技术

线性反馈移位寄存器(LinearFeedbackShiftRegister,LFSR)广泛应用 于BCH编码器设计和CRC校验编码器设计领域，用于计算两个多项式的余子式。 假设相关的生成多项式g(x)＝g_n-kx^n-k+...+g₁x+g₀(k为编码前信息长度， n为编码后信息长度)，则对应串行LFSR编码器结构如图1所示。图中的⊕为 异或操作，为伽罗华域的相乘操作，r_n-k-1(t),...,r₁(t),r₀(t)为存储校验位信 息的寄存器，u(t)为输入的待编码信息。这种编码器虽然结构简单，具有很高 的运行速度，但还是受到输入位宽的限制，吞吐率不高，很难应用在高速通信系 统中。

为解决现有的串行LFSR架构在吞吐率上的劣势，JeffH.Derby提出了基于 状态空间模型的并行LFSR架构，该架构可同时处理pbit(称p为并行度)的 数据，只需要个时钟周期即可完成校验位的计算。

应用状态空间模型，普通的串行LFSR结构(图1)可以被描述为以下的公 式：

R(t+1)＝A×R(t)+b×u(t)

其中R(t)为t时刻各校验位寄存器的值，u(t)为t时刻输入的待编码 信息，A和b的构造如下：

b＝(g_n-k-1,...,g₁,g₀)^T

基于该串行公式能推导出pbit数据处理后的结果，即pbit数据并行输 入时校验位的计算公式：

R(t+1)＝A^p×R(t)+B_p×U_p(t)

其中，U_p(t)和B_p的构造如下：

U_p(t)＝(u(tp),u(tp+1),...,u(tp+p-1))^T

B_p＝(A^p-1b,...,Ab,b)

该公式表示的电路结构如图2所示，由于矩阵A^p和B_p实际上表示的是 电路两个部分连接的方式，该类矩阵又被称之为连接矩阵。

状态空间变换法通过引入一个转换矩阵T，将上述的公式转换为：

R_T(t+1)＝A_pT×R_T(t)+B_pT×U_p(t)

R(t+1)＝T×R_T(t+1)

其中：

A_pT＝T^-1×A^p×T

B_pT＝T^-1×B_p

通过这种变换，各连接矩阵中非零元素的个数减少，系统的复杂度也因此降低， 达到优化的目的。变换后电路的结构如图3所示。

为了使变换后的电路的复杂度最低，状态空间转换法采用如下的方法构造转 换矩阵T：先假设一个向量b₁，再利用它构造T，结构如下：

T＝(b₁,A^pb₁,A^2pb₁,...,A^(p-1)pb₁)

只要此时的T是可逆矩阵，通过状态空间变换便可将矩阵A^p转换为一个友矩 阵A_pT，即A_pT每一行最多只有两个非零元素，则每一条反馈通路最多只包含 一个异或门，从而降低了电路的复杂度。在这种方式的基础上，只要遍历所有b₁(2^p种可能值)，便可以找到最佳的T，使得电路整体的复杂度最低。

但是，状态空间转换法存在以下两个问题。首先，状态空间转换法构造转换 矩阵的目的是为了使矩阵A^p转换为一个友矩阵A_pT，为了完成这样的变换， 可能会额外增加矩阵B_pT和T中“1”的个数，最后虽然矩阵A_pT有很少的“1”， 但需要很长的关键路径计算矩阵B_pT和T表示的连接电路。其次，状态空间 转换法以向量b₁为媒介构造矩阵T，而b₁的可能值只有2^n-k种，远远小 于T的可能值的数量(2^(n-k)×(n-k)种)。这些都暗示着可能有更好的构造转换 矩阵的方式。

发明内容

发明目的：为了构造高速的并行LFSR架构，寻找潜在的更优的状态空间转 换方式，本发明提供了一种新的构造转换矩阵的方法，能够保证转换后的电路结 构比现有的并行LFSR架构具有更低的复杂度，更少的面积和一致的速度。

技术方案：一种并行LFSR架构的实现方法，该架构可用于构造并行的BCH 码编码器或CRC校验编码器，将现有的用于构造并行LFSR架构的状态空间转 换法中转换矩阵的构造方式，修改为构造一个上三角矩阵。

所述的转换矩阵(记作T)的构造方式，先寻找一个首元素为1的n-k维 的向量(记作b₂＝(1,b₁,b₂,...,b_n-k-2,b_n-k-1),其他元素的值为0或1)作为转换矩 阵的第一行，之后的每一行通过上一行右移一位得到，记作：

在以上新的构造转换矩阵的方法的基础上，应用状态空间转化法，可以得到 新的转换电路。为了找到使转换电路面积最小的转换矩阵，本发明提供两种算法 搜索最优的转换矩阵。一种遍历了向量b₂的所有可能值，另一种只遍历包含少 量非零元素的b₂的值，具有更快的搜索速度。

所述的寻找使电路面积最小的最佳转换矩阵的搜索算法，第一种算法通过穷 举法列出b₂的所有可能的值，再构造出相应的转换矩阵T，计算转换后的电路 的连接矩阵中的“1”的总数，将找到的使“1”总数最小的转换矩阵T视作最 佳转换矩阵。

所述的寻找使电路面积最小的最佳转换矩阵的搜索算法，第二种算法通过限 定向量b₂中“1”的个数，仅列举b₂的一部分仅包含少量“1”(通常小于b₂长 度的)的可能值，再构造出相应的转换矩阵T，计算转换后的电路的连接矩阵 中的“1”的总数，将找到的使“1”总数最小的转换矩阵T视作最佳转换矩阵。

附图说明

图1为常规的串行LFSR结构；

图2为常规的并行LFSR结构；

图3为经过状态空间变换的并行LFSR结构。

具体实施方式

下面结合具体实施例，进一步阐明本发明，应理解这些实施例仅用于说明本 发明而不用于限制本发明的范围，在阅读了本发明之后，本领域技术人员对本发 明的各种等价形式的修改均落于本申请所附权利要求所限定的范围。

并行LFSR架构的实现方法，该架构可用于构造并行的BCH码编码器或CRC 校验编码器，将现有的用于构造并行LFSR架构的状态空间转换法中转换矩阵的 构造方式，新的转换矩阵的构造方式如下：首先构造一个与矩阵行向量同维度的 向量b₂＝(1,b₁,b₂,...,b_n-k-1)作为矩阵的第一行，b₂的第一个元素一定为“1”， 其余元素为“0”或“1”。其他行均通过上一行右移一位得到；由b₂得到的新 的转化矩阵可以表示为：

通过新的转换矩阵，对常规并行LFSR的数学模型作状态空间变换，即：

R_T(t+1)＝A_pT×R_T(t)+B_pT×U_p(t)

R(t+1)＝T×R_T(t+1)

A_pT＝T^-1×A^p×T

B_pT＝T^-1×B_p

得到新的连接矩阵(连接电路结构)。

相应于本发明构造转换矩阵的方式，本发明搜索最优的转换矩阵的算法如下。

第一种算法首先计算出连接矩阵A和B_p，然后构造向量b₂的全部可能 值，共2^n-k-1种，接着按照转换矩阵构造的方式构造出所有可能的转换矩阵T， 根据公式计算出所有转换后的连接矩阵A_pT和B_pT，统计矩阵A_pT，B_pT和T 中“1”的总数，将总数最少的情况对应的转换矩阵作为最优的转换矩阵。

第一种算法需要遍历b₂的全部2^n-k-1种可能值，在维度较大时需要很长 的运行时间。观察到已知的最优转换矩阵均只包含少量的“1”，因此提出了第二 种搜索算法。

第二种算法首先计算出连接矩阵A和B_p，然后构造出向量b₂所有包含 i个“1”的可能值，共种，接着按照转换矩阵构造的方式构造出所有 可能的转换矩阵T，根据公式计算出所有转换后的连接矩阵A_pT和B_pT，统计 矩阵A_pT，B_pT和T中“1”的总数，将总数最少的情况对应的“1”的个数记作 S_min(i)，分别计算i从1递增时S_min(i)的值，其出现的局部最小值对应的转 换矩阵作为最优的转换矩阵。

根据以上两种搜索算法，可以为常见的几种生成多项式找到相应的最优转换 矩阵，下表列出了各生成多项式的对应的最优转换矩阵的第一行元素(b₂)。

下表列出了本发明和其他LFSR并行架构在面积和速度上的对比(XOR表示 异或门个数，DE表示延迟元件个数，CPD表示关键路径，以异或门为单位， AT＝(1.5×XOR+DE)×CPD，表示面积时间积，用于衡量电路的品质，括号里 的数值为单位化后的结果)，可以看到本发明在与其他架构一致的速度下，有更 小的面积和更低的复杂度。

[1]J.H.Derby,“High-speedCRCcomputationusingstate-spacetransformations,” inProc.IEEEGLOBECOM,Nov.2001,pp.166–170.

[2]M.AyinalaandK.K.Parhi,“High-speedparallelarchitecturesforlinear feedbackshiftregisters,”IEEETrans.SignalProcess.,vol.59,no.9,pp.4459–4469, Sep.2011.

[3]JaehwanJung,HoyoungYooandYoungjooLee,“EfficientParallelArchitecture forLinearFeedbackShiftRegisters”,IEEETransactionsonCircuitsAndSystems—Ii: ExpressBriefs,Vol.62,No.11,November2015。