一种差错控制方法和系统

摘要

本发明公开了一种差错控制方法和系统，适用于通信、存储等领域，在这些领域中使本发明的方法或系统，可有效地将丢失的数据恢复，提高数据的完整性。本发明的方法包括生成编码系数和冗余包、生成解码系数和恢复信源等步骤，发信端以n个信源生成m个冗余包，将信源及冗余包都发送往收信端，收信端收到的信源个数与冗余包个数之和只要大于n，就能恢复出所有n个信源。本发明利用范德蒙矩阵及扩展伽罗瓦2^q域内的运算，巧妙地实现了信息量最大化及运算量最小化。在多播及广播通信中使用本发明的差错控制方法或系统，可取得优良的效果。

主权项

1、一种差错控制方法，其特征是：该方法包括生成冗余包的方法和信源恢复的方法，其中生成冗余包的方法包括以下步骤：(1)构造编码系数矩阵A：假设有n个信源X₁、X₂、X₃......X_n，m为需要生成的冗余包的数量，选一个数域P，保证每个信源X_j都在数域P内，在数域P中任取(n+m)个不同的值K₁、K₂、K₃......K_n、L₁、L₂......L_m，取矩阵K和L如下：$K=\left[\begin{array}{cccccc}1& K_1& {K_1}^2& {K_1}^3& ......& {K_1}^{n-1}\\ 1& K_2& {K_2}^2& {K_2}^3& ......& {K_2}^{n-1}\\ 1& K_3& {K_3}^2& {K_3}^3& ......& {K_3}^{n-1}\\ ......& & & & & \\ 1& K_n& {K_n}^2& {K_n}^3& ......& {K_n}^{n-1}\end{array}\right]$$L=\left[\begin{array}{cccccc}1& L_1& {L_1}^2& {L_1}^3& ......& {L_1}^{n-1}\\ 1& L_2& {L_2}^2& {L_2}^3& ......& {L_2}^{n-1}\\ ......& & & & & \\ 1& L_m& {L_m}^2& {L_m}^3& ......& {L_m}^{n-1}\end{array}\right]$取K的逆矩阵K^-1，将矩阵L乘以矩阵K^-1，得到编码系数矩阵A如下：$A=L*K^{-1}=\left[\begin{array}{ccccc}{A}_{11}& A_{12}& A_{13}& ......& A_{1n}\\ A_{21}& A_{22}& A_{23}& ......& A_{2n}\\ ......& & & & \\ A_{m1}& A_{m2}& A_{m3}& ......& A_{\mathrm{mn}}\end{array}\right]$步骤(1)每步数学运算都采用数域P内的运算；(2)计算冗余包：取信源矩阵X如下：$X=\left[\begin{array}{c}{X}_1\\ X_2\\ X_3\\ ...\\ X_n\end{array}\right]$将编码系数矩阵A乘以信源矩阵X，得到冗余包矩阵Y如下：$Y=A*X=\left[\begin{array}{c}{Y}_1\\ Y_2\\ ...\\ Y_m\end{array}\right]$Y₁、Y₂、Y₃......Y_m即为m个冗余包；步骤(2)每步数学运算都采用与步骤(1)相同的数域P内的运算；发信端将n个信源及m个冗余包发送往收信端，当收信端收到的信源个数r小于n时，信源恢复的方法包括以下步骤：(3)构造解码系数矩阵B：假设收到X_f、X_g......X_h共r个信源，其中f＜g＜……＜h，收到t个冗余包，当t大于(n-r)时任取(n-r)个冗余包，当t小于或等于(n-r)时取所有的冗余包，这些冗余包记为Y_u、Y_v......Y_w，其中u＜v＜……＜w，取矩阵B第1行的第f列为1、其他(n-1)列为0；矩阵B第2行的第g列为1、其他(n-1)列为0......矩阵B第r行的第h列为1、其他(n-1)列为0；矩阵B第(r+1)行为步骤(1)编码系数矩阵A的第u行；矩阵B第(r+2)行为步骤(1)编码系数矩阵A的第v行......矩阵B最后1行为步骤(1)编码系数矩阵A的第w行，构成解码系数矩阵B如下：$B=\left[\begin{array}{c}\begin{array}{ccc}......& 1......0......0& 0\end{array}\\ \begin{array}{ccc}......& 0......1......0& 0\end{array}\\ \begin{array}{ccc}......& & \end{array}\\ \begin{array}{ccc}0& 0......0......1& ......\end{array}\\ \begin{array}{c}\end{array}\begin{array}{ccccc}{A}_{u1}& A_{u2}& A_{u3}& ......& A_{\mathrm{un}}\end{array}\\ \begin{array}{ccccc}{A}_{v1}& A_{v2}& A_{v3}& ......& A_{\mathrm{vn}}\end{array}\\ \begin{array}{ccccc}......& & & & \end{array}\\ \begin{array}{ccccc}{A}_{w1}& A_{w2}& A_{w3}& ......& A_{\mathrm{wn}}\end{array}\end{array}\right]$(4)恢复出信源X：当t大于(n-r)时任取(n-r)个冗余包，当t小于或等于(n-r)时取所有的冗余包，得到如下等式：$B*\left[\begin{array}{c}{X}_1\\ X_2\\ X_3\\ ...\\ X_n\end{array}\right]=\left[\begin{array}{c}{X}_f\\ X_g\\ ...\\ X_h\\ Y_u\\ Y_v\\ ...\\ Y_w\end{array}\right]$当t大于或等于(n-r)时，利用上等式解出(n-r)个未收到的信源X_j；当t小于(n-r)时，利用上等式部分解出(n-r)个未收到的信源X_j；步骤(4)每步数学运算都采用与步骤(1)相同的数域P内的运算。