CN106788878B - 一种具有单比特纠错功能的并行crc纠错方法 - Google Patents

Abstract

本发明涉及通信技术领域，具体涉及一种基于并行CRC的单比特纠错方法。本发明的目的是为了解决串行数据传输过程中传输速度受限于一条数据线造成的速度慢、基于串行传输的串行CRC算法的运算慢及基于丢包、重传的数据传输效率低下的问题。

Description

一种具有单比特纠错功能的并行CRC纠错方法

技术领域：

本发明涉及通信技术领域，具体涉及一种基于并行CRC的单比特纠错方法。

背景技术：

当今世界是一个信息化的世界，各行各业的信息交互、交流都少不了通信。CRC校验作为一种软、硬件都便于实现的数据包型校验策略已经被广泛应用于各类数据交互中，然而,CRC算法大多数被用于数据的校验。采用数据自动纠错功能取代数据重传或者丢包，可以有效的提高数据传输网络的能量消耗和数据传输效率。而在环境相对较好的情况下，单比特纠错在软、硬件的实现及纠错的可靠性方面都有着自己的天然优势。

假设传输过程使用二进制编码方式且误码率为p，一包数的数据量为n bits，则传输过程中整包数据正确的概率为(1-p)ⁿ，那么数据传输错误的概率为P_e＝1-(1-p)ⁿ。而传输过程中出现错误为单比特错误的概率为P_e1＝C_n ¹p(1-p)^n-1。从而可以得到单比特错误占总错误的比例为R＝P_e1/P_e＝np(1-p)ⁿ/(1-(1-p)ⁿ)。根据相应计算，可以得到在误码率下降的情况下，单比特错误占整包数错误的比例迅速升高，尤其当误码率低于10^-4时，单比特错误占整包数错误的比例已经高于了90％，而当误码率低于10^-6时，单比特错误占整包数错误的比例已经高于99.95％(这里的计算是根据包长度为1024bits计算得到的)。因此，可以看出当信息传输过程中的误码率较低时，单比特错误占整包错误中的比例迅速增高，计算表明，在误码率低于10^-6时，通过单比特纠错技术可以有效的降低误包率3个数量级以上。

为了提高数据的传输能力和处理能力，并行CRC算法、单比特纠错功能的引入有效的利用了有限的资源提高了数据的可靠性和安全性。

发明内容：

本发明的目的是为了解决串行数据传输过程中传输速度受限于一条数据线造成的速度慢、基于串行传输的串行CRC算法的运算慢及基于丢包、重传的数据传输效率低下的问题。

本发明为一种具有单比特纠错功能的并行CRC纠错方法，包括以下步骤：

步骤一：选择合适的CRC校验多项式、计算相应的并行算法；

根据数据传输要求和数据包长度要求，选择合适的CRC校验多项式CRC16.X25＝X¹⁶+X¹²+X⁵+1，式中Xⁱ是码元位置的标记，它表示由其系数所决定的码元取值所处的对应位置。根据相应的CRC校验多项式，经过迭代运算得到16位CRC并行运算式

R[0]＝D[12]^D[11]^D[8]^D[4]^D[0]^R[0]^R[4]^R[8]^R[11]^R[12]

R[1]＝D[13]^D[12]^D[9]^D[5]^D[1]^R[1]^R[5]^R[9]^R[12]^R[13]

R[2]＝D[14]^D[13]^D[10]^D[6]^D[2]^R[2]^R[6]^R[10]^R[13]^R[14]

R[3]＝D[15]^D[14]^D[11]^D[7]^D[3]^R[3]^R[7]^R[11]^R[14]^R[15]

R[4]＝D[15]^D[12]^D[8]^D[4]^R[4]^R[8]^R[12]^R[15]

R[5]＝D[13]^D[12]^D[11]^D[9]^D[8]^D[5]^D[4]^D[0]^R[0]^R[4]^R[5]^R[8]^R[9]^R[11]^R[12]^R[13]

R[6]＝D[14]^D[13]^D[12]^D[10]^D[9]^D[6]^D[5]^D[1]^R[1]^R[5]^R[6]^R[9]^R[10]^R[12]^R[13]^R[14]

R[7]＝D[15]^D[14]^D[13]^D[11]^D[10]^D[7]^D[6]^D[2]^R[2]^R[6]^R[7]^R[10]^R[11]^R[13]^R[14]^R[15]

R[8]＝D[15]^D[14]^D[12]^D[11]^D[8]^D[7]^D[3]^R[3]^R[7]^R[8]^R[11]^R[12]^R[14]^R[15]

R[9]＝D[15]^D[13]^D[12]^D[9]^D[8]^D[4]^R[4]^R[8]^R[9]^R[12]^R[13]^R[15]

R[10]＝D[14]^D[13]^D[10]^D[9]^D[5]^R[5]^R[9]^R[10]^R[13]^R[14]

R[11]＝D[15]^D[14]^D[11]^D[10]^D[6]^R[6]^R[10]^R[11]^R[14]^R[15]

R[12]＝D[15]^D[8]^D[7]^D[4]^D[0]^R[0]^R[4]^R[7]^R[8]^R[15]

R[13]＝D[9]^D[8]^D[5]^D[1]^R[1]^R[5]^R[8]^R[9]

R[14]＝D[10]^D[9]^D[6]^D[2]^R[2]^R[6]^R[9]^R[10]

R[15]＝D[11]^D[10]^D[7]^D[3]^R[3]^R[7]^R[10]^R[11]

其中，R代表相应寄存器中的数值，D代表相应输入数据的数值，^表示异或运算。

步骤二：建立查找表；

设G(X)为CRC的校验多项式，k为传输数据的长度，n为发送数据的长度，则校验位的长度为n-k。此时，设发送数据的多项式为v(x)，传输错误数据多项式为e(x)及接收数据多项式为r(x)，他们之间存在如下关系

r(x)＝v(x)+e(x)

令CRC校验和计算表示如下CRC_G(x){v(x)}，在G(x)、v(x)、n与k一定的情况下，计算结果应该为一个0。在接收端，用相同的CRC校验多项式进行计算，可以得到以下结论

CRC_G(x){r(x)}＝CRC_G(x){v(x)+e(x)}＝CRC_G(x){e(x)}

这说明如果存在一个合适的CRC多项校验式使不同错误类型错误得到的CRC校验结果两两不相同，那么数据中发生错误的位置可以由生成的CRC校验结果得到。

根据包长度和相应的并行CRC运算式，计算该长度各位产生错误时的CRC值，并且将该值存放至相应的存储空间待用。

步骤三：数据纠错；

通过上述方式在传输数据中加入相应的CRC，在接收方利用相同的CRC对数据进行CRC的解算，如果数据在传输过程中没有发生误码，则解算出的CRC应为0；如果解算出的CRC值不为零，则将该值与之前储存好的查找表进行比较，若产生匹配，则将查找表中的对应位与数据的对应位进行异或运算，解算后可以获得正确的数据；若没有产生匹配，则说明数据发生了未知位数的数据传输错误，应该丢弃。

本发明的优点在于：

(1)本发明采用16位并行传输方式和16位并行CRC校验运算，在工作频率保持不变的情况下，可以有效的将传输速度和运算能力提升为原来的16倍。在仅仅提升部分逻辑资源的情况下有效的提高整体的数据传输、处理能力；

(2)本发明采用数据的纠错取代数据丢包、重传，可以有效的提高数据的传输效率和可靠性，这样可以有效的提高整个系统的数据吞吐能力；

(3)本发明采用单比特纠错功能，这样做可以有效的降低良好环境下的误包率，同时可以有效的减少查找表所需的储存空间，减少硬件开销。

附图说明

图1为本发明的步骤示意图。

图2为本发明的并行CRC算法示意图。

附表说明

表1为本发明的单比特错误查找示意表。

具体实施方式

下面将结合附图及附表对本发明作进一步的详细说明。

本发明是一种具有单比特纠错功能的并行CRC纠错方法，下面结合附图，对本发明技术方案进行详细描述。

图1给出了本发明中的各步骤的具体示意图，其具体分为选择合适的CRC多项式、并行CRC算法运算、建立单比特错误查找表及数据纠错几个步骤。

从国际标准组织找寻所需并行CRC位数的相应CRC校验多项式，由于国际标准组织所给的CRC多项式覆盖的错误率高于随意写出的多项式，要结合自己的具体设计来选取，这里我们选取的CRC校验多项式CRC16.X25＝X¹⁶+X¹²+X⁵+1。

如图2所示，根据相应的CRC校验多项式运用并行算法，先计算串行算法中第一个时钟周期的理论每个寄存器中的数据；再计算第二个时钟周期的理论每个寄存器中的数据；以此类推，算出第16个周期的理论每个寄存器中的数据，这个数据也是最后的并行输出数据，算法也应该是最终的并行组合逻辑算法：

R[0]＝D[12]^D[11]^D[8]^D[4]^D[3]^R[0]^R[4]^R[8]^R[11]^R[12]

R[1]＝D[13]^D[12]^D[9]^D[5]^D[1]^R[1]^R[5]^R[9]^R[12]^R[13]

R[2]＝D[14]^D[13]^D[10]^D[6]^D[2]^R[2]^R[6]^R[10]^R[13]^R[14]

R[3]＝D[15]^D[14]^D[11]^D[7]^D[3]^R[3]^R[7]^R[11]^R[14]^R[15]

R[14]＝D[15]^D[12]^D[8]^D[4]^R[4]^R[8]^R[12]^R[15]

R[5]＝D[13]^D[12]^D[11]^D[9]^D[8]^D[5]^D[4]^D[0]^R[0]^R[4]^R45]^R[8]^R[9]^R[11]^R[12]^R[13]

R[6]＝D[14]^D[13]^D[12]^D[10]^D[9]^D[6]^D[5]^D[1]^R[1]^R[5]^R[6]^R[9]^R[10]^R[12]^R[13]^R[14]

R[7]＝D[15]^D[14]^D[13]^D[11]^D[10]^D[7]^D[6]^D[2]^R[2]^R[6]^R[7]^R[10]^R[11]^R[13]^R[14]^R[15]

R[8]＝D[15]^D[14]^D[12]^D[11]^D[8]^D[7]^D[3]^R[3]^R[7]^R[8]^R[11]^R[12]^R[14]^R[15]

R[9]＝D[15]^D[13]^D[12]^D[9]^D[8]^D[4]^R[4]^R[8]^R[9]^R[12]^R[13]^R[15]

R[10]＝D[14]^D[13]^D[10]^D[9]^D[5]^R[5]^R[9]^R[10]^R[13]^R[14]

R[11]＝D[15]^D[14]^D[11]^D[10]^D[6]^R[6]^R[10]^R[11]^R[14]^R[15]

R[12]＝D[15]^D[8]^D[7]^D[4]^D[0]^R[0]^R[4]^R[7]^R[8]^R[15]

R[13]＝D[9]^D[8]^D[5]^D[1]^R[1]^R[5]^R[8]^R[9]

R[14]＝D[10]^D[9]^D[6]^D[2]^R[2]^R[6]^R[9]^R[10]

R[15]＝D[11]^D[10]^D[7]^D[3]^R[3]^R[7]^R[10]^R[11]

分别将数据的每一位错误分别罗列出来，并且进行相应的并行CRC运算，将相应的运算建立如表1的查找表，并且在硬件中开辟相应的资源将相应的数据存到开辟的储存空间，将数据按照升序或者降序进行排序并且在该数据区标明单比特错误位置。

接收数据并且进行相应的并行CRC校验运算，最后得到的CRC值不为0时则将该值与数据区的储存数据进行比较，由于采用升序或者降序排列，那么查询所需的次数为不小于log2(M)的整数次，M为数据长度。如果查询结果错误，那么进行丢包或者重传(由于单比特占包错误的百分比通过之前的计算很高，且进行多比特纠错时需要的储存空间很大)。

z<sub>1</sub>	16’hf0ba
		z<sub>2</sub>	16’hf049
z<sub>3</sub>	16’hf034
		z<sub>4</sub>	16’h781a
z<sub>5</sub>	16’h3c0d
		z<sub>6</sub>	16’h9616
z<sub>7</sub>	16’h4b0b
		z<sub>8</sub>	16’had95
......	……
		z<sub>1037</sub>	16’h8108
z<sub>1038</sub>	16’h4084
		z<sub>1039</sub>	16’h2042
z<sub>1040</sub>	16’h1021

表1

例1

首先建立一个查询表，将一包数据中的某个比特位设置为‘1’，其他比特位全部设置为‘0’，分别计算不同比特位为‘1’的情况下CRC的数值并将它们放置在相应的查询表位置用于之后的解算后的查询。这里设z_i为数据包中的第i个比特位为‘1’的情况，T[CRC_G(z_i)]为第i个比特位为‘1’的情况下计算出的CRC数值。这里使用一个简单的例子来说明查找表是如何产生的，设CRC校验多项式为G＝x³+x+1，可以表示为1011，传输的数据为4位，这里我们需要3位CRC作为数据的校验位，则z₁＝1000000，此时我们有CRC_G(z₁)＝5，同理我们可以得到CRC_G(z₂)＝7，CRC_G(z₃)＝6，CRC_G(z₄)＝3，CRC_G(z₅)＝4，CRC_G(z₆)＝2及CRC_G(z₇)＝1。如果任意两个CRC的运算结果不相同，那么我们可以认为CRC_G对于z_i具有单映射性，即得到相应的CRC结果可以得到相对应的比特位错误信息。根据上面的运算结果我们可以得到纠错表T＝{5,7,6,3,4,2,1}，在接收方，可以根据最终计算出的CRC对照纠错表中的值确定单比特发生错误的位置并进行相应错误比特位的纠错。对于长度为n的CRC校验位，最长可以具有的数据位长度为L＝2ⁿ-n-1。

以下通过一个具体的例子来证明上面的表述，假设所需要传输的数据为M＝1101，计算得出CRC，即CRC_G(1101)＝001，那么传输的数据应该为M’＝1101001，假设在传输过程中第二比特位发生错误，那么接收到的数据应该为M”＝1001001，通过CRC校验计算，可以得到CRC_G(M”)＝7，通过查表可以看出T[2]＝7，那么说明接收到的数据的第二个比特位发生了错误，经过纠正该位错误得到正确的接收数据1101001。

Claims (1)

1.一种具有单比特纠错功能的并行CRC纠错方法，其特征在于，

步骤一：选择合适的CRC校验多项式、计算相应的并行算法；

根据数据传输要求和数据包长度要求，选择合适的CRC校验多项式CRC16.X25＝X¹⁶+X¹²+X⁵+1，式中Xⁱ是码元位置的标记，它表示由其系数所决定的码元取值所处的对应位置；根据相应的CRC校验多项式，经过迭代运算得到16位CRC并行运算式

R[0]＝D[12]^D[11]^D[8]^D[4]^D[0]^R[0]^R[4]^R[8]^R[11]^R[12]

R[1]＝D[13]^D[12]^D[9]^D[5]^D[1]^R[1]^R[5]^R[9]^R[12]^R[13]

R[2]＝D[14]^D[13]^D[10]^D[6]^D[2]^R[2]^R[6]^R[10]^R[13]^R[14]

R[3]＝D[15]^D[14]^D[11]^D[7]^D[3]^R[3]^R[7]^R[11]^R[14]^R[15]

R[4]＝D[15]^D[12]^D[8]^D[4]^R[4]^R[8]^R[12]^R[15]

R[5]＝D[13]^D[12]^D[11]^D[9]^D[8]^D[5]^D[4]^D[0]^R[0]^R[4]^R[5]^R[8]^R[9]^R[11]^R[12]^R[13]

R[6]＝D[14]^D[13]^D[12]^D[10]^D[9]^D[6]^D[5]^D[1]^R[1]^R[5]^R[6]^R[9]^R[10]^R[12]^R[13]^R[14]

R[7]＝D[15]^D[14]^D[13]^D[11]^D[10]^D[7]^D[6]^D[2]^R[2]^R[6]^R[7]^R[10]^R[11]^R[13]^R[14]^R[15]

R[8]＝D[15]^D[14]^D[12]^D[11]^D[8]^D[7]^D[3]^R[3]^R[7]^R[8]^R[11]^R[12]^R[14]^R[15]

R[9]＝D[15]^D[13]^D[12]^D[9]^D[8]^D[4]^R[4]^R[8]^R[9]^R[12]^R[13]^R[15]

R[10]＝D[14]^D[13]^D[10]^D[9]^D[5]^R[5]^R[9]^R[10]^R[13]^R[14]

R[11]＝D[15]^D[14]^D[11]^D[10]^D[6]^R[6]^R[10]^R[11]^R[14]^R[15]

R[12]＝D[15]^D[8]^D[7]^D[4]^D[0]^R[0]^R[4]^R[7]^R[8]^R[15]

R[13]＝D[9]^D[8]^D[5]^D[1]^R[1]^R[5]^R[8]^R[9]

R[14]＝D[10]^D[9]^D[6]^D[2]^R[2]^R[6]^R[9]^R[10]

R[15]＝D[11]^D[10]^D[7]^D[3]^R[3]^R[7]^R[10]^R[11]

其中，R代表相应寄存器中的数值，D代表相应输入数据的数值，^表示异或运算；

步骤二：建立查找表；

设G(X)为CRC的校验多项式，k为传输数据的长度，n为发送数据的长度，则校验位的长度为n-k；此时，设发送数据的多项式为v(x)，传输错误数据多项式为e(x)及接收数据多项式为r(x)，他们之间存在如下关系

r(x)＝v(x)+e(x)

令CRC校验和计算表示如下CRC_G(x){v(x)}，在G(x)、v(x)、n与k一定的情况下，计算结果应该为一个0；在接收端，用相同的CRC校验多项式进行计算，可以得到以下结论

CRC_G(x){r(x)}＝CRC_G(x){v(x)+e(x)}＝CRC_G(x){e(x)}

这说明如果存在一个合适的CRC多项校验式使不同错误类型错误得到的CRC校验结果两两不相同，那么数据中发生错误的位置可以由生成的CRC校验结果得到；

根据包长度和相应的并行CRC运算式，计算该长度各位产生错误时的CRC值，并且将该值存放至相应的存储空间待用；

步骤三：数据纠错；

通过上述方式在传输数据中加入相应的CRC，在接收方利用相同的CRC对数据进行CRC的解算，如果数据在传输过程中没有发生误码，则解算出的CRC应为0；如果解算出的CRC值不为零，则将该值与之前储存好的查找表进行比较，若产生匹配，则将查找表中的对应位与数据的对应位进行异或运算，解算后可以获得正确的数据；若没有产生匹配，则说明数据发生了未知位数的数据传输错误，应该丢弃。