一种基于循环冗余码的单比特纠错查表方法及其电路

摘要

本发明涉及一种基于循环冗余码的单比特纠错查表方法及其电路，属于数字通信技术领域。将数据段进行循环冗余码校验，得到行向量，若不为零，则从中按子空间抽取p比特元素，获得行向量R_p，剩余部分构成行向量R_q；将行向量R_p作为地址信息，从查找表中获得与该地址相对应的匹配信息和单比特错误位置信息；根据匹配信息与行向量R_q的吻合情况，得到单比特纠错指示，并进行单比特纠错。本发明的电路，包括校验器、选择器、存储器比较器和单比特纠错器。本发明方法和电路，对地址信息进行最优化控制，减少了查找表所占用的地址空间，降低了存储单元的容量；查找表信息表示简单，保证了电路的简单实现；整体电路模块清晰，结构规整，执行速度快，易于集成。

主权项

1. 一种基于循环冗余码的单比特纠错查表方法，包括如下步骤：(1)对接收到的长度为n比特的数据段进行校验位位长为m的循环冗余码校验，得到长度为m比特的校验结果，设其中最高校验位对应的序号为1，最低校验位对应的序号为m，从1到m的校验位序号中提取子空间I，I＝i₁，i₂，i₃，…，i_p，其中1≤p≤m，且i₁，i₂，i₃，…，i_p∈{1，2，…，m}，提取子空间I的过程，包括以下步骤：(1-1)将数据传输过程中的所有单比特错误图样e(x)分别进行校验位位长为m的循环冗余码校验，分别得到单比特错误图样的校验结果，校验结果的长度分别为m比特，将所有校验结果按行排列，以比特作为矩阵的基本元素，最高校验位相对应的序号为1，最低校验位相对应的序号为m，以校验位的序号作为矩阵的列号，构成一个n×m的校验矩阵A，其中n为单比特错误图样e(x)的长度；(1-2)设待提取的子空间I的元素个数为p，取p的初始值为(1-3)从上述矩阵A中任意取p列，构成n×p矩阵，共有C_m^p种矩阵组合，对C_m^p种矩阵组合进行遍历搜寻，直至找到任意两行都不相同的矩阵，该矩阵中的每一列在原A矩阵中的列号即为子空间I的元素值；若未找到任意两行都不相同的矩阵，则进行步骤(4)；(1-4)对子空间I的元素个数p赋以新值，p＝p+1，重复步骤(2)和(3)，直至找到任意两行都不相同的矩阵，以得到子空间I；(2)建立地址信息与内容信息一一映射的查找表T，建立查找表T的过程，包括以下步骤：(2-1)将数据传输过程中的所有单比特错误图样e(x)分别进行校验位位长为m的循环冗余码校验，分别得到单比特错误图样的校验结果，校验结果的长度分别为m比特，将所有校验结果按行排列，以比特作为矩阵的基本元素，最高校验位相对应的序号为1，最低校验位相对应的序号为m，以校验位的序号作为矩阵的列号，构成一个n×m的校验矩阵A，其中n为单比特错误图样e(x)的长度：(2-2)从上述矩阵A中，将上述子空间I中的元素值作为该矩阵的列号，抽取p列比特，得到n×p的子矩阵B，作为查找表T中的地址信息，A矩阵的剩余部分构成n×q子矩阵C，作为查找表T的待定内容信息中的匹配信息，m＝p+q；(2-3)根据上述单比特错误图样的按行排列的校验结果顺序，构建矩阵D，作为查找表T的待定内容信息中的单比特错误位置信息，并与上述子矩阵C合并，E＝[C，D]，构成的矩阵E，作为查找表T的内容信息；(2-4)将上述矩阵B中的一行作为查找表中的地址，矩阵E中相对应的行作为与该地址相对应的内容，构成查找表T；(3)将上述接收到的长度为n比特的数据段进行校验位位长为m的循环冗余码校验，得到以比特作为基本元素的1×m行向量R，若该行向量R为零向量，则接收的数据正确，若不为零，则进行以下步骤；(4)从上述行向量R中按子空间I抽取p比特元素，获得1×p的行向量R_p，剩余部分构成1×q的行向量R_q；(5)将上述行向量R_p作为从上述查找表T中待查找的一个地址信息，根据该地址信息，获得与该地址相对应的内容信息，该内容信息包括前q比特的匹配信息和后比特的单比特错误位置信息；(6)当上述前q比特的匹配信息与上述行向量R_q相吻合时，若进行信息位以及校验位的单比特纠错，则输出单比特纠错指示，若只进行信息位的单比特纠错，则当上述的单比特错误位置信息的最高位为“1”时，输出单比特纠错指示，为“0”时，不输出单比特纠错指示；当上述前q比特的匹配信息与上述行向量R_q不吻合时，结束纠错过程；(7)根据上述单比特错误位置信息和上述单比特纠错指示，对处在错误位置的比特进行取反操作或者与“1”异或，进行单比特纠错；(8)重复步骤(3)～(7)，完成所有接收数据段的纠错。