RTC QoS方法十三.（ReedSolomonFEC简介）

一、FlexFEC恢复的困局

在使用FlexFEC进行冗余的时候，经验值需要冗余5倍的丢包率，才能有比较高的恢复率。

Flex FEC在2D数组异或时能获得比较高的恢复率，但是如上图所示，25个包发送10个FEC包，成本为10/25=40%的冗余度。理论上加入10个冗余包，最多可以恢复10个丢包。但是该方案不能恢复任意组合的丢包，比如丢掉了1、2、6、7这4个包，将无法恢复。因为这个方案是10个一阶的FEC的组成，一阶代表只能处理一个丢包。

我们若想要达到冗余N个包，随意丢失任意组合的N个包，都能完全的恢复，矩阵需要可逆。

二、ReedSolomon原理

范德蒙矩阵具有这样良好的性质，删除任意行列得到的方阵都是可逆的。

但是我们实际应用的时候，还需要注意两个问题：

1、运算是在实数域上进行的，加减乘除可能会溢出，浮点数的计算可能损失精度。

2、我们只能计算FEC冗余数据，媒体数据不能变动，否则对整个呼叫影响很大。

第一个问题，可以引入伽罗华有限域，保证所有数据，都在定义的有限域里面。第二个问题，可以使用高斯消元法，将矩阵转换成单位阵+FEC系数阵；

1、伽罗华有限域

可以参考《密码编码学与网络安全》的有限域一章。

附上2的8次方，伽罗华域表：

uint16_t gflog_8bit[256] = 
{0,0,1,25,2,50,26,198,3,223,51,238,27,104,199,75,4,100,224,14,52,141,239,129,28,193,105,248,200,8,76,113,5,138,101,47,225,36,15,33,53,147,142,
218,240,18,130,69,29,181,194,125,106,39,249,185,201,154,9,120,77,228,114,166,6,191,139,98,102,221,48,253,226,152,37,179,16,145,34,136,54,208,148,206,143,150,
219,189,241,210,19,92,131,56,70,64,30,66,182,163,195,72,126,110,107,58,40,84,250,133,186,61,202,94,155,159,10,21,121,43,78,212,229,172,115,243,167,87,7,
112,192,247,140,128,99,13,103,74,222,237,49,197,254,24,227,165,153,119,38,184,180,124,17,68,146,217,35,32,137,46,55,63,209,91,149,188,207,205,144,135,151,178,
220,252,190,97,242,86,211,171,20,42,93,158,132,60,57,83,71,109,65,162,31,45,67,216,183,123,164,118,196,23,73,236,127,12,111,246,108,161,59,82,41,157,85,
170,251,96,134,177,187,204,62,90,203,89,95,176,156,169,160,81,11,245,22,235,122,117,44,215,79,174,213,233,230,231,173,232,116,214,244,234,168,80,88,175};uint16_t gfilog_8bit[256] = 
{1,2,4,8,16,32,64,128,29,58,116,232,205,135,19,38,76,152,45,90,180,117,234,201,143,3,6,12,24,48,96,192,157,39,78,156,37,74,148,53,106,212,181,
119,238,193,159,35,70,140,5,10,20,40,80,160,93,186,105,210,185,111,222,161,95,190,97,194,153,47,94,188,101,202,137,15,30,60,120,240,253,231,211,187,107,214,
177,127,254,225,223,163,91,182,113,226,217,175,67,134,17,34,68,136,13,26,52,104,208,189,103,206,129,31,62,124,248,237,199,147,59,118,236,197,151,51,102,204,133,
23,46,92,184,109,218,169,79,158,33,66,132,21,42,84,168,77,154,41,82,164,85,170,73,146,57,114,228,213,183,115,230,209,191,99,198,145,63,126,252,229,215,179,
123,246,241,255,227,219,171,75,150,49,98,196,149,55,110,220,165,87,174,65,130,25,50,100,200,141,7,14,28,56,112,224,221,167,83,166,81,162,89,178,121,242,249,
239,195,155,43,86,172,69,138,9,18,36,72,144,61,122,244,245,247,243,251,235,203,139,11,22,44,88,176,125,250,233,207,131,27,54,108,216,173,71,142,0};

2、高斯消元示例

6+3 RS-FEC的范德蒙矩阵经过伽罗华有限域转换后的示例：

__                             __
| 0001 0000 0000 0000 0000 0000 |
| 0001 0001 0001 0001 0001 0001 |
| 0001 0002 0004 0008 0010 0020 |
| 0001 0003 0005 000f 0011 0033 |
| 0001 0004 0010 0040 0100 0400 |
| 0001 0005 0011 0055 0101 0505 |
| 0001 0006 0014 0078 0110 0660 |
| 0001 0007 0015 006b 0111 0777 |
| 0001 0008 0040 0200 1000 8000 |
|__                           __|

经过高斯消元后，矩阵转换成单位阵+FEC系数阵的示例

__                             __
| 0001 0000 0000 0000 0000 0000 | 
| 0000 0001 0000 0000 0000 0000 | 
| 0000 0000 0001 0000 0000 0000 | 
| 0000 0000 0000 0001 0000 0000 | 
| 0000 0000 0000 0000 0001 0000 | 
| 0000 0000 0000 0000 0000 0001 | 
| 0007 0006 0005 0004 0003 0002 | 
| 0006 0007 0004 0005 0002 0003 | 
| 0387 03f8 03f8 0390 00fe 00e8 | 
|__                           __|

三、ReedSolomon编码流程

1、根据当前配置媒体包个数和冗余包个数，初始化范德蒙矩阵，并进行高斯消元和有限域转换

2、得到FEC系数阵后，编码FEC数据。

fec_data ^= gfmult(matrix_A_[media_group_num + fec_index][media_index], media_data);

3、封装RS-FEC的冗余报文头，告知该冗余报文的base_seq。tg组的媒体包个数和冗余包个数。便于解码根据该信息初始化范德蒙矩阵，并且求其对应的逆矩阵。

四、ReedSolomon解码流程

1、根据当前收报情况，按照tg顺序进行排序，丢失的媒体包在尾部用FEC包补齐。

2、根据这个顺序，将对应范德蒙矩阵的系数提取出来。如下示例是6个一组媒体包中的第5个包丢失。获取的初始状态的范德蒙矩阵，参照（2.2章节的单位阵+FEC系数阵的示例）

3、然后再对这个矩阵进行求逆，并且高斯消元，得到如下矩阵：

4、使用f004 0002 0003 f005 f007 f006这组系数，进行还原。

五、参考

《Note: Correction to the 1997 Tutorial on Reed-Solomon Coding》

技术解码 | RSFEC原理分析今天向大家介绍下RSFEC的原理https://mp.weixin.qq.com/s/4dFdz0H0mjpemDflKbTdmQ?version=4.1.31.6017&platform=win&nwr_flag=1#wechat_redirect

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