云盘网站如何做,网站建设前期应该做哪些准备,建材商城,英文网站模板cmsFEC算法_cloudfly_cn的博客-CSDN博客_fec算法
I 基于IP的语音和视频通话业务为了实时性#xff0c;一般都是采用UDP进行传输#xff0c;基站无线一般配置UM模式的RLC承载#xff0c;因此丢包是不可避免的#xff0c;在小区信号的边沿则丢包率会更高#xff1b;为了通话的…FEC算法_cloudfly_cn的博客-CSDN博客_fec算法
I 基于IP的语音和视频通话业务为了实时性一般都是采用UDP进行传输基站无线一般配置UM模式的RLC承载因此丢包是不可避免的在小区信号的边沿则丢包率会更高为了通话的实时性一般不会采用接收端发现丢包了然后通知发送端重传的机制因为这个在应用层的丢包检测和通知发送端重传是非常耗时的。引入前向纠错FEC机制是解决实时通话业务丢包的一个很好的机制FEC的原理就是在发送端发送数据包时插入冗余包这样即使接收端收到的数据有所丢包丢包数不大于冗余包时也是能还原出所有的数据包的。本文介绍FEC算法的原理只涉及三阶冗余因为只有前三阶的矩阵运算比较简单而且实际中也足以够用了而且阶数越高则传输冗余包占用带宽太大那就没有意义了本人曾负责的一个音视频实时通话软件就是只用到三阶冗余效果已经很好了。
本文对FEC算法进行一步一步的数学推导让不了解FEC的读者看完后可以有很好的理解从而可以使用本文的FEC算法到实际项目中或者为项目设计出更好的FEC算法同时也重温一下大学的线性代数吧。
零阶冗余没有冗余 没有加入冗余数据直接原始数据发送假设原始数据为D1、D2、D3、...、Dn则发送的数据就是D1、D2、D3、...、Dn。 (1) 编码矩阵为单位矩阵 一阶冗余 所谓一阶冗余算法就是每n个数据插入一个冗余数据也即FEC编码组长度为n1这n个数据和其对应的冗余数据构成一组数据这组数据中丢掉任何一个数据都可以通过另外n个数据恢复出来。
发送端编码 (2) 图示编码算法n4的场景
如上图示左边矩阵为编码矩阵就是在单位矩阵下面插入一行冗余算法参数右边的C1为计算出来的冗余数据。
令R1i1i1,2,...,n则上式子可以简化为
采用伽罗华有限域(Galois field :)运算则可将加减法运算化为异或运算因此C1的计算公式简化为
接收端解码
如果接收端收到的某组数据丢失了一个则可以通过如下公式推导出恢复丢失数据的公式下图我们假设丢失的数据为D2则D2的恢复矩阵运算为 (3) 图示丢包恢复过程假设n4、丢包D2 可得
因此可得到D2的恢复公式
一般地若丢失的数据为Di其中i1,2,...,nDi的恢复公式为
令R1i1且采用伽罗华有限域运算则上式子可以简化为
二阶冗余 就是每n个数据插入两个冗余数据也即FEC编码组长度为n2这n个数据和其对应的冗余数据构成一组数据这组数据中丢掉任何一或两个数据都可以恢复出来。
发送端 4二阶冗余发送编码图示(n4) 上式左边的矩阵成为编码矩阵右边的C1、C2为冗余数据其中
令R1i1、R2ii其中i1,2,...,n且采用伽罗华有限域运算则上式子可以简化为
其中gfm()函数表示伽罗华域乘法运算gfm(i,Di)表示i和Di在伽罗华域的乘法运算。
接收端
场景1、丢失一个数据包Di冗余包C1没有丢失则可以通过接收到的数据包和冗余数据C1恢复出Di其恢复算法和一阶冗余算法的一样
令R1i1i1,2,...,n且采用伽罗华有限域运算则上式子可以简化为
场景2、丢失一个数据包Di冗余包C1也丢失C2没有丢失则可以通过接收到的数据包和C2恢复出Di其恢复算法推导如下
令R2jj则上式可以简化为
若采用伽罗华域运算则上式可以简化为
其中gfm()函数表示伽罗华域乘法运算gfm(i,Di)表示在伽罗华域的乘法运算i*Digfd()函数表示伽罗华域除法运算gfd(a,b)表示在伽罗华域的除法运算a/b。
场景3、丢失两个数据包Di、Dj冗余包C1和C2没有丢失则可以通过接收到的数据和冗余数据C1、C2恢复出Di和Dj其恢复公式推导如下 (5) 传输中丢掉了两个数据包图示 整理后为 6丢弃两个数据包的恢复运算图示D3、D4丢弃
经过行操作消元整理后为
其中
因此求解D3、D4本质就是解如下方程
上式两边乘以矩阵的逆就可以求解出D3、D4
再结合根据二阶方阵的求逆公式
可以求解出
一般地如果传输中丢失Di和Dj数据包则Di和Dj的求解公式为
令R1i1、R2jji1,2,..., j1,2,...,可以简化为
采用伽罗华域运算则上面的式子变为
三阶冗余 所谓三阶冗余就是每n个数据插入三个冗余数据这n个数据和其对应的冗余数据构成一组数据这组数据中丢掉任意m个(m3)数据都可以通过收到的其它数据恢复出来。
发送端 上式左边的矩阵成为编码矩阵右边的C1,C2,C3为冗余数据其中
令R1j1、R2jj、R3jj^2其中j1,2,...,n则
采用伽罗华域(gf())运算可以将加减法变为异或操作乘除法变为加减法的查表操作C1就是一阶冗余数据C2就是二阶冗余数据C3就是三阶冗余数据。
接收端
场景1仅丢掉一个数据包Di接收到一个冗余包Ck则恢复Di的公式为
其中k 1 或 2 或 3 u ≠ i。
令R1u 1、R2u u、R3u u^2则
场景2丢掉两个数据包Di、Dj接收到两个冗余包Ck、Cm经过推导可以化简为解如下二元线性方程组
解方程可得
若令R1j1、R2jj、R3jj^2其中j1,2,...,n则上式Di和Dj的求解可简化为
场景3丢失三个数据包Di、Dj、Dk且接收到三个冗余包C1、C2、C3则经过简单的推导将丢失数据包的恢复计算抽象为解如下三元线性方程组
若令R1j1、R2jj、R3jj^2其中j1,2,...,n则上式Di和Dj的求解可简化为
根据附录的三阶矩阵求逆公式就可以直接求解出Di、Dj、Dk
采用伽罗华域(gf())运算可以将加减法变为异或操作乘除法变为加减法的查表操作。 注
【1】FEC的编码和解码都是使用伽罗华域(gf())运算。
【2】文中使用的冗余矩阵是范德蒙特行列式这样构建出来的冗余矩阵最后接收端解码求矩阵的逆时不会遇到奇异矩阵的场景否则如果出现奇迹矩阵则接收端就无法求解出丢失的数据包了。
【3】 相关的伽罗华域(gf())运算和矩阵运算请参考《FEC算法——附录》 ———————————————— 版权声明本文为CSDN博主「cloudfly_cn」的原创文章遵循CC 4.0 BY-SA版权协议转载请附上原文出处链接及本声明。 原文链接https://blog.csdn.net/u010178611/article/details/82656838
