前向纠错算法介绍

前向纠错（FEC）算法被广泛使用在实时音视频领域提升音视频的弱网抗性，只要收到FEC分组内的冗余包和一定数量的数据包，就能根据FEC算法恢复出对应的冗余包。常见的FEC实现包括M+1系列的异或算法、M+N系列的RS矩阵算法，这2种实现算法各有优缺点。

异或算法实现相对简单，将M个数据包逐字节进行异或计算，计算得到的结果即为冗余包。这种算法只需要进行异常运算，复杂度低。但是抗丢包能力弱，例如 4+1算法，5个包里面最多只能丢1个包，否则就无法恢复。

在实时音视频领域主要采用M+N系列的CRS矩阵算法。

CRS矩阵运算原理

CRS矩阵算法，RS编码只是一种应对擦除的编码，也就是应对数据块丢失的场景，并且我们是知道哪一块丢失的，然后我们可以通过冗余信息把丢失的数据块找回来。CRS指的是Cauthy RS，其中用到了柯西矩阵。计算过程相对复杂，一般需要在GF(2^8)伽罗瓦域上进行运算。具体计算过程，如下所示。

假设我们有个M个数据包，想要得到N个冗余包，一次异或计算只能得到一个冗余包，无法实现。如果直接用编码矩阵(M+N)*矩阵M，就可以得到一个M+N行的编码输出矩阵，其中L为原始数据包的长度。

CRS矩阵编码过程

编码输出矩阵的M行为原始数据，因此编码矩阵的前M行必须是一个M*M的单位阵，后N行要满足在编码矩阵M+N行中随便选择M行组成的子矩阵都是可逆的，柯西矩阵以算法复杂度较低被选中。矩阵的运算都是逐字节进行的，而单个字节能够表示的范围为0～256，如果直接进行矩阵运算得到的结果肯定会超过单个字节的上限，因此要把矩阵运算放到GF(2^8)伽罗瓦域上进行计算。

• 构造生成矩阵：生成矩阵前M项是一个单位阵，后R项是一个柯西矩阵（便于求逆）。
• 生成冗余数据：将M个原始数据包与生成矩阵做伽罗华域上的矩阵运算，即可得到N个冗余包。
• 将数据包与冗余包通过网络发送，FEC恢复最多带来（M+1)个数据包间隔。

数据在网络中传输发生丢包，只要丢失的包个数小于N，就可以通过CRS恢复原始数据。例如，采用FEC 4+2，丢失2个数据包的恢复过程。

RS矩阵解码恢复过程

接收端收到数据包后，检测到编码输出数据包中前M个包中有数据包丢失，只要丢失的包不超过冗余包个数N，就可以从收到的数据包和冗余包里选出M个数据包，当然这M个数据包对应编码矩阵中的M行，只要从编码矩阵中选出来的M行组成的可逆，就可以计算出丢失的数据。

• 求解恢复矩阵：在生成矩阵里面根据收到的数据包以及冗余包，（填充丢失数据包的位置）构成生成矩阵的子矩阵，对子矩阵求逆，得到恢复矩阵。
• 数据包恢复：选取收到的数据包以及冗余数据与恢复矩阵进行伽罗华域上的矩阵运算，求解出丢失的数据包。

数据恢复的关键步骤在于矩阵求逆，通常采用LU分解算法，时间消耗达到N^3 。

FEC算法关键优化点

FEC算法在伽罗华域的计算方式，可以进一步优化。在运算上主要有以下方面。

• 根据冗余包个数，按照特定的规则生成编码矩阵。
• 将伽罗华域上的乘、除法转换成二的幂次加减，查表计算。
• 矩阵求逆采用LDU算法，将时间消耗保持在N^2。

实践经验

之前实现过一个版本的FEC算法，为了减少运算量，采用以时间换空间的算法将生成矩阵与逆矩阵提前计算好。在进行数据恢复时，根据M和N的组合方式找到对应子矩阵，再根据子矩阵找到对应的逆矩阵。缺点也很明显，只支持特定几种类型的FEC算法，抗连续丢包能力弱。