CN102868411A - Crc逆序串行解码算法、扩展的并行逆序解码方法及装置 - Google Patents

Abstract

本发明公开了一种CRC逆序串行解码算法、扩展的并行逆序解码方法及装置，采用后进先出LIFO的方式，不仅能够实现零初态CRC编码的正确解码，并且能够实现非零初态的CRC编码的正确解码，能够一个时钟对多个输入比特进行快速地CRC解码。与现有技术相比，本发明充分利用了CRC编解码的特点，逆序解码，无须补零操作，能够对寄存器任意初态的CRC编码进行解码；采用并行结构，运算速度快，实现了鲁棒的、高速可变并行长度的CRC解码，便于硬件集成与实现，节省了电路系统开销，提高了系统的解码效率。

Description

CRC逆序串行解码算法、扩展的并行逆序解码方法及装置

技术领域

本发时涉及通信技术领域中编解参天技术，其涉及一种循环冗余校验(CRC，Cyclic Redundancy Check)解码算法、逆序解码方法及装置。

背景技术

CRC编码是一种常用的错误检验码，宽带码分多址/时分-同步码分多址/长期演进系统(WCDMA/TD-SCDMA/LTE)等各版本的协议中都使用了多种不同长度的CRC编码，以保证各种传输格式下信息传输的正确性。

CRC编码是一种系统循环码，编码后的数据分为信息序列和校验序列两部分，信息序列在左，校验序列在右。CRC编码作为一种循环码，其校验序列每循环一位，都可能作为某一特定消息序列的校验序列。

一般编解码原理：

发送信息序列b₀b₁…b_n-1b_n对应多项式为M(X)＝b₀Xⁿ+b₁X^n-1…+b_n-1X+b_n，生成多项式G(X)＝p_mX^m+p_m-1X^m-1…+p₁X+p₀，校验序列R(X)＝M(X)×X^m mod G(X)对应多项式为R(X)＝r_m-1X^m-1+r_m-2X^m-2…+_r1X+r₀，发送序列M_S(X)＝M(X)×X^m+R(X)；接收序列M_R(X)，如果无差错接收M_R(X)＝M_S(X)，则M_R(X)mod G(X)＝0，否则出错。

由上可知生成CRC校验位和对接收序列进行校验都通过以G(X)为模做除法的方式来实现；除法电路通常使用反馈移位寄存器来实现，图1为现有m级反馈移位寄存器来实现CRC编码器的结构示意图，寄存器初始状态一般情况下为全零(即零初态)，G1、G2为两个开关电路，当G1闭合、G2断开时，生成校验序列；当G1断开、G2闭合时，输出校验序列。图2为现有m级移位寄存器来实现解码的CRC解码器结构示意图，解码器为零初态，当G1闭合、G2断开时，进行差错校验；当G1断开、G1闭合时，输出校验结果，全零序列表示接收序列无差错。

现行CRC解码器多数都是基于该原理实现的，采用该结构的CRC解码器是一种先进先出(FIFO)的正序处理方式；该解码器可以实现零初态的解码，但无法完成非零初态CRC编码的信道差错判定工作。

现有技术也有采用并行解码的方式，如申请号为200910085524.4、名称为“快速循环冗余校验编码方法及装置”，其公开了一种并行顺序解码的方式，该种方式限定解码序列长度应为并行运算位宽的整数倍，故当输入比特流个数不是并行位宽的整数倍时，需要根据输入比特流长度在其前面添加一定数量的零比特位构成解码序列，处理方法相对复杂，影响处理速度。

发明内容

针对现有技术中存在的不足，本发明要解决的技术问题是提供一种CRC逆序串行解码算法和依据该逆序串行解码算法扩展的并行逆序解码方法，其采用后进先出(LIFO)的方式，不仅能够实现零初态CRC编码的正确解码，并且能够实现非零初态的CRC编码的正确解码，能够一个时钟对多个输入比特进行快速地CRC解码。

为达到上述目的，本发明所提供的技术方案为：一种CRC逆序串行解码算法，包括如下步骤：

A：设置(p₀，p₁…，p_m-1，p_m)(p₀＝1、p_m＝1)为生成多项式G(X)＝p_mX^m+p_m-1X^m-1…+_p1X+p₀的低次项到高次项的系数，设置t时刻寄存器i的状态序列为x_m(t)x_m-1(t)...x₂(t)x₁(t)，设置t时刻输入的处理数据为b(t)，X(t+1)为CRC编码电路由信息序列b(t)生成t+1时刻的寄存器状态，对应状态序列为x_m(t+1)x_m-1(t+1)...x₂(t+1)x₁(t+1)；

B：定义多项式G(X)的i次项的系数p_i为m×1阶矩阵P′的第i行第1列，其中i＝1，2，...m-1，P′的第m行第1列为1，即 $P^{\′}=\left[\begin{array}{c}{p}_1\\ p_2\\ \·\·\·\\ p_{m-1}\\ 1\end{array}\right];$ 定义m阶方阵Γ的第j行第1列为P′的第j行第1列，基中j＝1，2，...m，定义Γ的第j行第j+1列为1，其中，j＝1，2，...m-1，定义Γ的其它位置为0，即 $\mathrm{\Γ}=\left[\begin{array}{ccccc}{p}_1& 1& 0& \·\·\·& 0\\ p_2& 0& 1& \·\·\·& 0\\ \·\·\·& \·\·\·& \·\·\·& \·\·\·& \·\·\·\\ p_{m-1}& 0& 0& \·\·\·& 1\\ 1& 0& 0& \·\·\·& 0\end{array}\right];$

C：将X(t+1)逆序排列为x₁(t+1)x₂(t+1)...x_m-1(t+1)x_m(t+1)并定义为X′(t+1)，根据关系式 $X^{\′}\left(t\right)=\mathrm{\Γ}\⊗X^{\′}(t+1)\⊕\left[\begin{array}{c}0\\ \·\·\·\\ 0\\ b\left(t\right)\end{array}\right]$ 计算得到t时刻寄存器状态x₁(t)x₂(t)...x_m-1(t)x_m(t)，并定义为X′(t)，式中

为模2乘法、为模2加法运算；

D：如果步骤C中所得X′(t)的逆序与编码时的状态序列X(t)一致，则解码正确，否则解码错误。

当CRC编码寄存器状态序列X(t)为全零时，判断X′(t)是否为全零，若是则CRC解码正确，否则解码错误；当CRC编码寄存器状态序列X(t)为非零时，判断X′(t)的逆序是否与X(t)相等，若是则CRC解码正确，否则解码错误。

本发明还提供一种依据上述CRC逆序串行解码算法扩展的并行逆序解码方法，包括如下步骤：

A：定义CRC编码的m级寄存器的初始状态为X_m…X₁，并行处理位宽为w，所述w满足条件1≤w≤l-m，其中，l为解码序列长度；定义接收序列M_R(X)，其逆序定义为解码序列a₁…a_l；

B：基于矩阵P′、Γ，计算出查询矩阵 $P_w=[{\mathrm{\Γ}}^{w-1}\⊗P^{\′}{\mathrm{\Γ}}^{w-2}\⊗P^{\′}\·\·\·\mathrm{\Γ}\⊗P^{\′}{P}^{\′}];$

C：进行CRC并行逆序解码处理，即R＝crc^-1(m，w，P_w，a₁…α_l)，步骤如下：

设L＝l-m；

为取整运算；

根据如下公式进行循环计算：

$R=P_w\⊗{\left[\begin{array}{ccc}{a}_{i*w+1}& \·\·\·& q_{(i+1)*w}\end{array}\right]}^T,$

$\left[\begin{array}{ccc}{a}_{(i+1)*w+1}& \·\·\·& a_{(i+1)*\left(w\right)+m}\end{array}\right]=\left[\begin{array}{ccc}{a}_{(i+1)*w+1}& \·\·\·& a_{(i+1)*\left(w\right)+m}\end{array}\right]\⊕R^T,$

L＝L-w，其中，i为变量，其值为从0到k-1的整数；

若L≠0，继续按照如下公式计算：

$R=P_L\⊗{\left[\begin{array}{ccc}{a}_{k*w+1}& \·\·\·& q_{k*w+L}\end{array}\right]}^T,$

$\left[\begin{array}{ccc}{a}_{l-m+1}& \·\·\·& a_l\end{array}\right]=\left[\begin{array}{ccc}{a}_{l-m+1}& \·\·\·& a_l\end{array}\right]\⊕R^T,$

最终，得到R＝[a_l-m+1…α_l]，表示为R＝[_sm…s₁]；

D：将状态序列R的逆序s₁…s_m与X_m…X₁比较，相等表示CRC解码正确，不等表示CRC解码错误。

进一步地，步骤C可通过分组或一次解码实现。

当CRC编码寄存器状态序列X_m…X₁为全零时，判断s₁…s_m是否为全零，若是则CRC解码正确，否则解码错误；当CRC编码寄存器状态序列X_m…X₁为非零时，判断_s1…s_m是否与X_m…X₁相等，若是则CRC解码正确，否则解码错误。

本发明还提供一种CRC并行逆序解码装置，其包括：

CRC映射转移矩阵生成模块，用于将CRC生成多项式G(X)的系数(p₀，p₁…，p_m-1，p_m)中的p_m-1至p₁生成m×1列矩阵P′和m阶方阵Γ；

CRC映射查询矩阵生成模块，用于将P′矩阵和Γ矩阵根据设定关系式生成多项式映射查询矩阵P_w；

CRC逆序解码处理模块，用于利用CRC并行逆序解码算法

R＝crc^-1(m，w，P_w，α₁…α_l)获得CRC寄存器状态序列s_m…s₁；

解码序列逆序比较模块，用于将获得的状态序列s_m…s₁的逆序s₁…s_m与X_m…X₁比较，相等表示CRC解码正确，不等表示RC解码错误。

本发明所提供的技术方案，具有以下主要特点：

(1)采用后进先出(LIFO)的方式解码，即对接收序列进行逆序解码；

(2)对于零初态、非零初态CRC编码，均可进行解码；通过调整寄存器初态能够提高CRC编码信道传输的安全性，具有一定的防破解能力。

(3)采用并行运算方式，运算所需时钟约为现有串行计算所需时钟的1/w，提高了运算效率，其中w为并行运算带宽；

(4)查询矩阵通过生成多项式生成，可根据w大小任意拓展并行解码位数；

(5)无需补零操作，可以单次解码，也可分组解码；

与现有技术相比，本发明充分利用了CRC编解码的特点，逆序解码，能够对寄存器任意初态的CRC编码进行解码；采用并行结构，运算速度快，实现了鲁棒的、高速可变并行长度的CRC解码，便于硬件集成与实现，节省了电路系统开销，提高了系统的解码效率。

附图说明

图1为p_mX^m+p_m-1X^m-1|+...+p₁X¹+p₀(p₀＝1、p_m＝1)对应的串型编码电路；

图2为p_mX^m+p_m-1X^m-1+...+p₁X¹+p₀(p₀＝1、p_m＝1)对应的FIFO串型解码电路；

图3为p_mX^m+p_m-1X^m-1+...+p₁X¹+p₀(p₀＝1、p_m＝1)对应的LIFO串型解码电路；

图4为查询矩阵P定义；

图5为当w≤m时，分组CRC逆序解码算法示意图；

图6为当w＞m时，分组CRC逆序解码算法示意图；

图7为当w＝l-m时，单次CRC逆序解码算法示意图；

图8为CRC逆序并行解码流程图；

图9为CRC逆序并行解码装置图。

具体实施方式

下面结合附图对本发明作进一步详细的说明：

本发明首先提供一种CRC逆序串行解码算法，该算法适用于一位或多位串行接收信号，具体分析如下：

定义(p₀，p₁…，p_m-1，p_m)(p₀＝1、p_m＝1)为生成多项式G(X)的低次项到高次项的系数；校验序列长度为m；并行处理长度为w；现行的CRC编码一般都是寄存器零初状态，此处设x_i(t)(1≤i≤m)为t时刻寄存器i的状态；b(t)为t时刻输入的处理数据，对应需要处理信息序列b₀b₁…b_n。

对图1进行状态分析可得

$\left[\begin{array}{c}{x}_m(t+1)\\ x_{m-1}(t+1)\\ \·\·\·\\ x_2(t+1)\\ x_1(t+1)\end{array}\right]=\left[\begin{array}{ccccc}{p}_{m-1}& 1& 0& \·\·\·& 0\\ p_{m-2}& 0& 1& \·\·\·& 0\\ \·\·\·& \·\·\·& \·\·\·& \·\·\·& \·\·\·\\ p_1& 0& 0& \·\·\·& 1\\ p_0& 0& 0& \·\·\·& 0\end{array}\right]\⊗(\left[\begin{array}{c}{x}_m\left(t\right)\\ x_{m-1}\left(t\right)\\ \·\·\·\\ x_2\left(t\right)\\ x_1\left(t\right)\end{array}\right]\⊗\left[\begin{array}{c}b\left(t\right)\\ 0\\ \·\·\·\\ 0\\ 0\end{array}\right]),$

令 $F=\left[\begin{array}{ccccc}{p}_{m-1}& 1& 0& \·\·\·& 0\\ p_{m-2}& 0& 1& \·\·\·& 0\\ \·\·\·& \·\·\·& \·\·\·& \·\·\·& \·\·\·\\ p_1& 0& 0& \·\·\·& 1\\ p_0& 0& 0& \·\·\·& 0\end{array}\right],$

上式可简写为 $X(t+1)=F\⊗(X\left(t\right)\⊕\left[\begin{array}{c}b\left(t\right)\\ \·\·\·\\ 0\\ 0\end{array}\right])---\left(1\right)$

通过计算可得行列式det(F)＝p₀＝1≠0，F存在逆矩阵F^-1，通过初等列变换得

$F^{-1}=\left[\begin{array}{ccccc}0& \·\·\·& 0& 0& 1\\ 1& \·\·\·& 0& 0& p_{m-1}\\ \·\·\·& \·\·\·& \·\·\·& \·\·\·& \·\·\·\\ 0& \·\·\·& 1& 0& p_2\\ 0& \·\·\·& 0& 1& p_1\end{array}\right],$

因此可由(1)式推导得

$X\left(t\right)=F^{-1}\⊗X(t+1)\⊕\left[\begin{array}{c}b\left(t\right)\\ \·\·\·\\ 0\\ 0\end{array}\right],$

令 $\mathrm{\Γ}=\left[\begin{array}{ccccc}{p}_1& 1& 0& \·\·\·& 0\\ p_2& 0& 1& \·\·\·& 0\\ \·\·\·& \·\·\·& \·\·\·& \·\·\·& \·\·\·\\ p_{m-1}& 0& 0& \·\·\·& 1\\ 1& 0& 0& \·\·\·& 0\end{array}\right],$

上式可变换为

$\left[\begin{array}{c}{x}_1\left(t\right)\\ x_2\left(t\right)\\ \·\·\·\\ x_{m-1}\left(t\right)\\ x_m\left(t\right)\end{array}\right]=\left[\begin{array}{ccccc}{p}_1& 1& 0& \·\·\·& 0\\ p_2& 0& 1& \·\·\·& 0\\ \·\·\·& \·\·\·& \·\·\·& \·\·\·& \·\·\·\\ p_{m-1}& 0& 0& \·\·\·& 1\\ 1& 0& 0& \·\·\·& 0\end{array}\right]\⊗\left[\begin{array}{c}{x}_1(t+1)\\ x_2(t+1)\\ \·\·\·\\ x_{m-1}(t+1)\\ x_m(t+1)\end{array}\right]\⊗\left[\begin{array}{c}0\\ 0\\ \·\·\·\\ 0\\ b\left(t\right)\end{array}\right],$

简写为

$X^{\′}\left(t\right)=\mathrm{\Γ}\⊗X^{\′}(t+1)\⊕\left[\begin{array}{c}0\\ \·\·\·\\ 0\\ b\left(t\right)\end{array}\right]---\left(2\right)$

(1)式中X(t)为CRC编码寄存器t时刻的状态，X(t+1)为CRC编码电路由一位信息序列b(t)生成的校验序列；通过(2)式，由X′(t+1)、b(t)计算得X′(t)，若X′(t)的逆序与编码时的状态X(t)一致，说明传输过程中无错误，否者有错误发生。对应的串行解码电路(解码器为零初态)如图3所示，要求输入序列与状态序列都反向，最后得到系统初态X′(t)也是反向的，据此可判断传输过程是否有错误发生。

如图8所示，根据如上分析，本发明提供的CRC串行逆序解码方法，包括如下步骤：

A：设置(p₀，p₁…，p_m-1，p_m)(p₀＝1、p_m＝1)为生成多项式G(X)＝p_mX^m+p_m-1X^m-1…+p₁X+p₀的低次项到高次项的系数，设置t时刻寄存器i的状态序列为x_m(t)x_m-1(t)…x₂(t)x₁(t)，设置t时刻输入的处理数据为b(t)，X(t+1)为CRC编码电路由信息序列b(t)生成t+1时刻的寄存器状态，对应状态序列为x_m(t+1)x_m-1(t+1)…x₂(t+1)x₁(t+1)；

B：定义多项式G(X)的i次项的系数p_t为m×1阶矩阵P′的第i行第1列，其中i＝1，2，...m-1，P′的第m行第1列为1，即 $P^{\′}=\left[\begin{array}{c}{p}_1\\ p_2\\ \·\·\·\\ p_{m-1}\\ 1\end{array}\right];$ 定义m阶方阵Γ的第j行第1列为P′的第j行第1列，其中j＝1，2，...m，定义Γ的第j行第j+1列为1，其中，j＝1，2，...m-1，定义Γ的其它位置为0，即 $\mathrm{\Γ}=\left[\begin{array}{ccccc}{p}_1& 1& 0& \·\·\·& 0\\ p_2& 0& 1& \·\·\·& 0\\ \·\·\·& \·\·\·& \·\·\·& \·\·\·& \·\·\·\\ p_{m-1}& 0& 0& \·\·\·& 1\\ 1& 0& 0& \·\·\·& 0\end{array}\right];$

C：将X(t+1)逆序排列为x1(t+1)x2(t+1)...xm-1(t+1)xm(t+1)并定义为X′(t+1)，根据关系式 $X^{\′}\left(t\right)=\mathrm{\Γ}\⊗X^{\′}(t+1)\⊕\left[\begin{array}{c}0\\ \·\·\·\\ 0\\ b\left(t\right)\end{array}\right]$ 计算得到t时刻寄存器状态X′(t)；

D：如果步骤C中所得X′(t)的逆序与编码时的状态序列X(t)一致，则解码正确，否则解码错误。

当CRC编码寄存器状态序列X(t)为全零时，判断X′(t)是否为全零，若是则CRC解码正确，否则解码错误；当CRC编码寄存器状态序列X(t)为非零时，判断X′(t)的逆序是否与X(t)相等，若是则CRC解码正确，否则解码错误。

根据上述CRC串行逆序解码算法，本发明还提出了一种扩展的CRC并行逆序解码方法，包括如下步骤：

A：定义CRC编码的m级寄存器的初始状态为X_m...X₁，并行处理位宽为w，所述w满足条件1≤w≤l-m，其中，l为解码序列长度；定义接收序列M_R(X)，其逆序定义为解码序列a₁…a_l；

B：基于矩阵P′、Γ，计算出查询矩阵 $P_w=[{\mathrm{\Γ}}^{w-1}\⊗P^{\′}{\mathrm{\Γ}}^{w-2}\⊗P^{\′}\·\·\·\mathrm{\Γ}\⊗P^{\′}{P}^{\′}];$

C：进行CRC并行逆序解码处理，即R＝crc^-1(m，w，P_w，a₁…a_l)，最终，得到R＝[a_l-m+1…a_l]，表示为R＝[s_m…s₁]；

D：将状态序列R的逆序s₁…s_m与X_m…X₁比较，相等表示CRC解码正确，不等表示CRC解码错误。

上述步骤C中，CRC并行逆序解码R＝crc^-1(m，w，P_w，a₁…a_l)处理方式具体如下流程：

设L＝l-m；

为取整运算；根据如下公式进行循环计算：

$R=P_w\⊗{\left[\begin{array}{ccc}{a}_{i*w+1}& \·\·\·& q_{(i+1)*w}\end{array}\right]}^T,$

$\left[\begin{array}{ccc}{a}_{(i+1)*w+1}& \·\·\·& a_{(i+1)*\left(w\right)+m}\end{array}\right]=\left[\begin{array}{ccc}{a}_{(i+1)*w+1}& \·\·\·& a_{(i+1)*\left(w\right)+m}\end{array}\right]\⊕R^T,$

L＝L-w，其中，i为变量，其值为从0到k-1的整数；

若L≠0，继续按照如下公式计算：

$R=P_L\⊗{\left[\begin{array}{ccc}{a}_{k*w+1}& \·\·\·& q_{k*w+L}\end{array}\right]}^T,$

$\left[\begin{array}{ccc}{a}_{l-m+1}& \·\·\·& a_l\end{array}\right]=\left[\begin{array}{ccc}{a}_{l-m+1}& \·\·\·& a_l\end{array}\right]\⊕R^T;$

最终，得到R＝[a_l-m+1…a_l]，表示为R＝[s_m…s₁]。在软件实现上，可通过下表进行：

注：由于P_L中L＜w，由图4可知P_L包含在P_w中，无须重新生成。

当w≤m时，CRC逆序解码算法通过分组实现，如图5所示；

当w＞m时，CRC逆序解码算法也通过分组实现，如图6所示；

当w＝l-m时，CRC逆序解码算法可以一次解码完成，一次解码包含一次矩阵运算和一次加法运算，如图7所示；

所以CRC逆序解码的并行位宽需满足如下条件1≤w≤l-m，w＝1时即为图3中的串行方案。

特别地，当CRC编码为零初态时，步聚D中判断R是为全零，若是则CRC校验正确，否则接收序列有错误发生。

本发明的基本思想是，利用CRC串行逆运算原理，提出一种护展的CRC逆序并行解码算法，由CRC生成多项式映射查询矩阵，通过设置并行CRC逆序解码的位宽进行分组处理，最后获得CRC编码器的寄存器初始状态，完成CRC编码的逆序校验。

本发明可以在WCDMA/TD-SCDMA/LTE等基带芯片的CRC解码单元使用，节省CRC解码所需时钟，提高芯片整体效率；也可设置CRC编码器的初始状态，提高传输序列的安全性。

为了能使本发明的技术方案及其技术优势更加清晰，下面结合实施例进一步说明本发明用于基带芯片的快速CRC解码方法。

实施例1(零初态)：

以WCDMA/TD-SCDMA/LTE中基带芯片都用到得编码长度为m＝8的CRC编码为例，并行位宽w＝4，CRC编码生成多项式为G(x)＝X⁸+X⁷+X⁴+X³+X+1，信息序列M(x)＝X¹³+X¹²+X⁹+X⁸+X⁵+X⁴+X²+X，对应序列为：M(x)＝[11001100110110]，G(x)＝[110011011]。本实施例分零初态、非零初态两种情况。

在零初态下，[X_m…X₁]＝[0...0]，采用图1所示CRC编码方法计算后得R(x)＝X⁷+X⁴+X²+X，对应R(x)＝[10010110]。

根据本发明的并行循环冗余校验逆序解码方法解码：

步骤A、[X_m…X₁]＝[0...0]；信息序列 M(x)＝[11001100110110]，校验序列R(x)＝[10010110]，

无差错接收序列M_R(X)的逆序[a₁…a_l]＝[0110100101101100110011]；w＝4；l＝22；m＝8；

步骤B、 $P^{\′}=\left[\begin{array}{c}1\\ 0\\ 1\\ 1\\ 0\\ 0\\ 1\\ 1\end{array}\right],$ $\mathrm{\Γ}=\left[\begin{array}{cccccccc}1& 1& 0& 0& 0& 0& 0& 0\\ 0& 0& 1& 0& 0& 0& 0& 0\\ 1& 0& 0& 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 1& 0& 0& 0\\ 0& 0& 0& 0& 0& 1& 0& 0\\ 0& 0& 0& 0& 0& 0& 1& 0\\ 1& 0& 0& 0& 0& 0& 0& 1\\ 1& 0& 0& 0& 0& 0& 0& 0\end{array}\right],$ $P_4=\left[\begin{array}{cccc}0& 0& 1& 1\\ 0& 0& 1& 0\\ 1& 0& 0& 1\\ 1& 1& 1& 1\\ 0& 1& 0& 0\\ 0& 0& 1& 0\\ 1& 0& 0& 1\\ 0& 1& 1& 1\end{array}\right];$

步骤C、调用R＝crc^-1(m，w，P_w，a₁…a_l)得[s_m…s₁]＝[0...0]全零序列；

步骤D、[s₁…s_m]＝[X_m…X₁]，CRC校验正确。得到结论为正确解码。

如果采用图2所示正序CRC解码方法解码：

无差错接收校验序列解码序列为M_R(x)＝(b₉…b_nr_m-1··r₀)，M_R(X)＝[1100110011011010010110]，计算得[X_m…X₁]＝[00000000]，全零序列。得到的结论也为正确解码。

实施例2(非零初态)：

其它条件同实施例1，在非零初态下设[X_m…X₁]＝[00110110]，采用图1所示CRC编码方法计算后得R(x)＝[0110001 1]。

根据本发明的并行循环冗余校验逆序解码方法解码：

步骤A中[a₁…a_l]＝[1100011001101100110011]，步骤B中P′Γ、P₄与实施例1一致，步骤C调用R＝crc^-1(m，w，P_w，a₁…a^l]计算得[s_m…s₁]＝[01101100]与[X_m…X₁]的逆序相同，CRC校验正确。得到结论为正确解码。

采用图2所示正序CRC解码方法解码：

无差错接收校验序列M_R(X)＝[1100110011011001100011]，计算得[X_m…X₁]＝[11110101]。得到结论为错误解码，由此可见，正序CRC解码方法仅适用于零初态，不适用于非零初态。

用现有串行方法获得上述CRC校验结果需要22个时钟，而本发明方法获得CRC校验结果仅需4个时钟，逆序解码且能够对非零初态CRC编码进行解码。

本发明所述并行CRC逆序解码方法可以通过硬件电路或软硬件结合的方式实现。

当为硬件实现时，芯片设计完成后，不能再进行修改。因此由于WCDMA/TD-SCDMA/LTE等系统均支持多种长度CRC编码，只须将通过本发明方法获得的对应于各CRC生成多项式的查询矩阵参数固化在系统中，硬件按照寄存器配置来选择其中一个硬件逻辑模块进行运算即可实现可变长度CRC解码。

当为硬件和软件结合实现时，芯片内部采用软件计算的方式计算CRC解码，则可以通过更新存储在存储器中的查询矩阵参数来实时修改其所对应的CRC生成多项式，以满足版本升级，模块通用等要求。

本发明还提供了一种并行循环冗余校验逆序解码装置，如图9所示，包括：

CRC映射转移矩阵生成模块，用于将CRC生成多项式G(X)的系数(p₀，p₁…，p_m-1，p_m)中的p_m-1至p₁生成m×1列矩阵P′和m阶方阵Γ；

CRC映射查询矩阵生成模块，用于将P′矩阵和Γ矩阵根据设定关系式生成多项式映射查询矩阵P_w；

CRC逆序解码处理模块，用于利用CRC并行逆序解码算法R＝crc^-1(m，w，P_w，a₁…a_l)获得CRC寄存状态序列s_m…s₁；

解码序列逆序比较模块，用于将获得的状态序列s_m…s₁的逆序s₁…s_m与X_m…X₁比较，相等表示RC解码正确，不等表示CRC解码错误。

所述CRC逆序解码算法可通过分组或一次解码实现。

特别地，当CRC编码为零初态时，判断[s_m…s₁]是否为全零，若是则CRC校验正确，否则接收序列有错误发生。

与现有技术相比，本发明充分利用了CRC编解码的特点，逆序解码，能够对寄存器任意初态的CRC编码进行解码；采用并行结构，运算速度快，实现了鲁棒的、高速可变并行长度的CRC解码，便于硬件集成与实现，节省了电路系统开销，提高了系统的解码效率。

当然，本发明还可有其它多种实施例，在不违背本发明精神及其实质的情况下，熟悉本领域的技术人员当可根据本发明做出各种相应的改变和变形，但这些相应的改变和变形都应属于本发明的保护范围。

Claims (7)

1.一种CRC逆序串行解码算法，其特征在于，包括如下步骤：

A：设置(p₀，p₁…，p_m-1，p_m)(p₀＝1、p_m＝1)为生成多项式G(X)＝p_mX^m+p_m-1X^m-1…+p₁X+p₀的低次项到高次项的系数，设置t时刻寄存器i的状态序列为x_m(t)x_m-1(t)...x₂(t)x₁(t)，设置t时刻输入的处理数据为b(t)，X(t+1)为CRC编码电路由信息序列b(t)生成t+1时刻的寄存器状态，对应状态序列为x_m(t+1)x_m-1(t+1)...x₂(t+1)x₁(t+1)；

B：定义多项式G(X)的i次项的系数p_i为m×1阶矩阵P′的第i行第1列，其中i＝1，2，...m-1，P′的第m行第1列为1，即 $P^{\′}=\left[\begin{array}{c}{p}_1\\ p_2\\ \·\·\·\\ p_{m-1}\\ 1\end{array}\right];$ 定义m阶方阵Γ的第j行第1列为P′的第j行第1列，其中j＝1，2，...m，定义Γ的第j行第j+1列为1，其中，j＝1，2，...m-1，定义Γ的其它位置为0，即 $\mathrm{\Γ}=\left[\begin{array}{ccccc}{p}_1& 1& 0& \·\·\·& 0\\ p_2& 0& 1& \·\·\·& 0\\ \·\·\·& \·\·\·& \·\·\·& \·\·\·& \·\·\·\\ p_{m-1}& 0& 0& \·\·\·& 1\\ 1& 0& 0& \·\·\·& 0\end{array}\right];$

C：将X(t+1)逆序排列为x₁(t+1)x₂(t+1)...x_m-1(t+1)x_m(t+1)并定义为X′(t+1)，根据关系式 $X^{\′}\left(t\right)=\mathrm{\Γ}\⊗X^{\′}(t+1)\⊕\left[\begin{array}{c}0\\ \·\·\·\\ 0\\ b\left(t\right)\end{array}\right]$ 计算得到t时刻寄存器状态x₁(t)x₂(t)...x_m-1(t)x_m(t)，并定义为X′(t)，式中

为模2乘法、

为模2加法运算；

D：如果步骤C中所得X′(t)的逆序与编码时的状态序列X(t)一致，则解码正确，否则解码错误。

2.根据权利要求1所述的一种CRC逆序串行解码算法，其特征在于：当CRC编码寄存器状态序列X(t)为全零时，判断X′(t)是否为全零，若是则CRC解码正确，否则解码错误；当CRC编码寄存器状态序列X(t)为非零时，判断X′(t)的逆序是否与X(t)相等，若是则CRC解码正确，否则解码错误。

3.一种采用权利要求1所述CRC逆序串行解码算法扩展的并行逆序解码方法，其特征在于，包括如下步骤：

A：定义CRC编码的m级寄存器的初始状态为X_m...X₁，并行处理位宽为w，所述w满足条件1≤w≤l-m，其中，l为解码序列长度；定义接收序列M_R(X)，其逆序定义为解码序列a₁...a_l；

B：基于矩阵P′、Γ，计算出查询矩阵 $P_w=[{\mathrm{\Γ}}^{w-1}\⊗P^{\′}{\mathrm{\Γ}}^{w-2}\⊗P^{\′}\·\·\·\mathrm{\Γ}\⊗P^{\′}{P}^{\′}];$

C：进行CRC并行逆序解码处理，即R＝crc^-1(m，w，P_w，a₁...a_l)，步骤如下：

设L＝l-m；

为取整运算；

根据如下公式进行循环计算：

$R=P_w\⊗{\left[\begin{array}{ccc}{a}_{i*w+1}& \·\·\·& q_{(i+1)*w}\end{array}\right]}^T,$

$\left[\begin{array}{ccc}{a}_{(i+1)*w+1}& \·\·\·& a_{(i+1)*\left(w\right)+m}\end{array}\right]=\left[\begin{array}{ccc}{a}_{(i+1)*w+1}& \·\·\·& a_{(i+1)*\left(w\right)+m}\end{array}\right]\⊕R^T,$

L＝L-w，其中，i为变量，其值为从0到k-1的整数；

若L≠0，继续按照如下公式计算：

$R=P_L\⊗{\left[\begin{array}{ccc}{a}_{k*w+1}& \·\·\·& q_{k*w+L}\end{array}\right]}^T,$

$\left[\begin{array}{ccc}{a}_{l-m+1}& \·\·\·& a_l\end{array}\right]=\left[\begin{array}{ccc}{a}_{l-m+1}& \·\·\·& a_l\end{array}\right]\⊕R^T,$

最终，得到R＝[a_l-m+1…a_l]，表示为R＝[s_m…s₁]；

D：将状态序列R的逆序s₁…s_m与X_m…X₁比较，相等表示CRC解码正确，不等表示CRC解码错误。

4.根据权利要求3所述的CRC逆序串行解码算法扩展的并行逆序解码方法，其特征在于：步骤C可通过分组或一次解码实现。

5.根据权利要求3所述的CRC逆序串行解码算法扩展的并行逆序解码方法，其特征在于：当CRC编码寄存器状态序列X_m…X₁为全零时，判断s₁…s_m是否为全零，若是则CRC解码正确，否则解码错误；当CRC编码寄存器状态序列X_m…X₁为非零时，判断s₁…s_m是否与X_m…X₁相等，若是则CRC解码正确，否则解码错误。

6.一种采用权利要求3所述CRC并行逆序解码方法的装置，其特征在于：包括：

CRC映射转移矩阵生成模块，用于将CRC生成多项式G(X)的系数(p₀，p₁…，p_m-1，p_m)中的p_m-1至p₁生成m×1列矩阵P′和m阶方阵Γ；

CRC映射查询矩阵生成模块，用于将P′矩阵和Γ矩阵根据设定关系式生成多项式映射查询矩阵P_w；

CRC逆序解码处理模块，用于利用CRC并行逆序解码算法R＝crc^-1(m，w，P_w，a₁…a_l)获得CRC寄存器状态序列s_m…s₁；

解码序列逆序比较模块，用于将获得的状态序列s_m…s₁的逆序s₁…s_m与X_m…X₁比较，相等表示CRC解码正确，不等表示CRC解码错误。

7.根据权利要求6所述的并行逆序解码装置，其特征在于：所述CRC逆序解码处理模块可通过分组或一次实现解码。

Images