kcptun中rs-fec原理

kcptun中的fec

kcptun使用了reed-solomon编码做前向纠错,rs码的原理解释如下:

利用了线性代数中的矩阵的计算恢复原始数据码,在kcptun中使用的是单位矩阵和范德蒙矩阵组合而成的编码矩阵,其中矩阵的计算使用有限域的加减乘除计算.

矩阵可逆证明

rs编码矩阵为什么要使用单位矩阵和范德蒙矩阵或者柯西矩阵的组合呢,很明显是因为这样的矩阵在去掉任意冗余数量的行向量后组成的n*n矩阵是可逆的.

证明如下:

  1. n*n范德蒙矩阵的行列式为: $$ \prod_{1<=j<i<=n}^{}(x_{i}-x_{j}) $$

其中 $$ x_{i} \neq x_{j} $$

所以范德蒙矩阵的行列式不为0,n*n范德蒙矩阵是满秩矩阵

  1. 假设一个(4,2)rs码矩阵为 $$ \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ x_1 & x_2 & x_3 & x_4 \\ x_{1}^{2} & x_{2}^{2} & x_3^2 & x_4^2 \\ \end{bmatrix} $$

接收端任意两个包丢失, 这里假设是第一第二个, 则恢复矩阵为:

$$ ReconstructMatrix = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ x_1 & x_2 & x_3 & x_4 \\ x_{1}^{2} & x_{2}^{2} & x_3^2 & x_4^2 \\ \end{bmatrix} $$

将收到的数据包组成列向量:

$$ data=[d_1, d_2, d_3, d_4]^T $$

则可以使用ReconstructMatrix的逆矩阵恢复原始数据包:

$$ OriginData=ReconstructMatrix^{-1} * data $$

现在要证明ReconstructMatrix必然存在逆矩阵,可以通过矩阵的行列式来证明,求行列式使用代数余子式相加:

$$ \begin{aligned} \left|ReconstructMatrix\right| &= \begin{vmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ x_1 & x_2 & x_3 & x_4 \\ x_{1}^{2} & x_{2}^{2} & x_3^2 & x_4^2 \\ \end{vmatrix} \ \ &= (-1)^{1+3} \begin{vmatrix} 0 & 0 & 1 \\ x_1 & x_2 & x_4 \\ x_{1}^{2} & x_{2}^{2} & x_4^2 \\ \end{vmatrix} \ \ &= (-1)^{1+3}(-1)^{1+3} \begin{vmatrix} x_1 & x_2 \\ x_1^2 & x_2^2 \\ \end{vmatrix} \end{aligned} $$

由于矩阵 $$ \begin{bmatrix} x_1 & x_2 \\ x_1^2 & x_2^2 \\ \end{bmatrix} $$ 是范德蒙矩阵,由第(1)步骤的范德蒙行列式可知,ReconstructMatrix的行列式的值不为0,所以必然存在逆矩阵.