FEC 的介绍

作者：付秋平

在传统的无线信道传输环境下，数字信号在传输的过程中往往由于各种原因，使得在传送的数据流中产生误码，使得接收端无法完全正常恢复发送端的原始数据，所以通过信道编码，使得数据流进行一定的处理，使得系统具有一定的纠错能力和抗干扰能力，可以极大的避免误码的产生，误码的处理技术主要有纠错、交织等等。在IP网络环境下，误码已经由底层得到了保证，在使用UDP进行数据传输的时候，重点会关注在了丢包等环节，使用的技术也大致相同，如使用交织抗连续丢包、ARQ数据等待重传、FEC数据恢复等。

这里只介绍一下FEC的数据恢复技术，FEC的主要原理是通过对原始数据进行一定的算法处理，增加冗余内容，通过牺牲一定的传输带宽，来保证最后即使只接收到部分正常的数据和冗余内容，也能完整将原始数据恢复出来，被广泛的应用于数据存储和音视频传输领域等。

1： 从小学方程说起

小学的时候很常见的这样的一类题目，题目的内容如下：

小明家里养了一群鸡和猪，如果按看到的头的数目数数的话有9，如果按看到的脚的数目数的话有26，那么请问小明家里的鸡和猪的数目各是多少呢？

对于大多数从应试教育里面百炼成钢的各位同学来说，很容易列出如下方程，并快速得到答案。

假设X为猪的数目，Y为鸡的数目，那么X+Y=9，4X + 2Y = 26，那么能得到X=4, Y=5。也就是说猪有4只，鸡有5只。

可是题目换一个角度，我们可以再增加一个条件，可以表示出同样的内容，比如1/4的猪数目+1/5的鸡的数目为2，那么我们即使去掉上述两个中的一个条件，我们也仍然能够得到正确的解。

通过增加冗余方程的数量，最终去掉其中的任何一个，我们都能够求出原始的值域，这恰恰就是FEC所要达到目的，在代数里面表示为矩阵，也是FEC恢复的基础。

2：九九乘法表-伽罗华

加减乘除，从一年级就开始学，小朋友使用手指笔画，手指不够就用脚趾来凑。九九乘法表也是从那个时候就开始背诵，一一得一，二二得四，三三得九。仿佛背诵的越熟悉就越掌握了世界的某种真理，直到有一天在卖拐的小品里赵本山问了范伟这样的两个问题：

1.你有一群羊，我有一群羊，两群羊合在一起，现在有几群羊？

2.树上七只鸟，猎人开枪打死了一只，问现在还剩下几只？

这个是玩笑，它当然不能用纯数学来进行描述，尽管是玩笑，可是它也问出了一个奇怪的问题，如果有一天，数字并不按九九乘法表这个样子展现会将是一个什么有趣的结果？为什么3x3一定是9，而不能是5？

伽罗华域就是这样的一个特殊的域，伽罗华这位年轻的天才数学家的早逝也令人惋惜，伽罗华域在某种程度上可以理解为创造出属于自己的乘法表、加法表，在特殊的场合下是非常有用和有意义的。

在上述的第一个例子中，理论上我们知道了矩阵的代数形式和整数数值，按照求逆矩阵的方式，就可以恢复出原始的数据。可是在实际应用中，让计算机来实现的时候却相当的并不友好。首先整数的表述形式并不固定，两个整数的相乘将有可能会得到一个特别大的数值。另外在进行除法的时候，将极其有可能得到浮点数，而计算机在浮点数的表示上存在着一定精度的损失，是否能够正常还原原有的数值也将是个大大的疑问，另外浮点的计算速度对于实用也着实堪忧。可是有了伽罗华域，就不一样了，所有的操作都在同一个集合中，这样上述的问题都能得到很好的解决。

3 有限域

一个域应当具有如下的性质：

1、加法和乘法的封闭性，加法和乘法结果还在域内

2、加法和乘法的交换律； a + b = b + a 和 a·b = b·a

3、加法和乘法的分配律： a + ( b + c ) = ( a + b ) + c 和 a·( b · c ) = ( a·b )· c

4、加法和乘法的分配律： a·( b + c ) = ( a·b) + ( a·c )

5、存在加法和乘法的单位元素：a+0 = a 和 a·1 = 1（注：这里的0,1 不是自然数的0,1，代表着域上的加法单位元素和乘法单位元素）

6、每个域上的元素都存在其负元和逆元： a+(-a) = 0, a·(a -1) = 1

当域中的元素是有限个的时候，这个域就是有限域，而伽罗华则提出了一种有限域的构造方法，叫做伽罗华域GF(2w)。

4 本原多项式&&伽罗华域的构造方法&&生成元

由于有限域具有如上非常棒的一些特性，因此可以被广泛的应用于通信、加密、随机序列生成等各个领域，所以如何生成有限域则成了一个广泛研究的课题，而本原多项式则是能够生成整个伽罗华域的一个关键要素。

一个n次多项式如果满足如下条件：

1. f(x)为不可约多项式。
2. f(x)可以整除xm + 1， m = 2n -1。
3. f(x)除不尽xq+ 1，q < m。则称为本原多项式。

本原多项式的寻找本身还是比较复杂，对于低阶的GF(2^w)的本原多项式基本都可以列出来，也是目前FEC主要使用的部分。

伽罗华域的构造方法：

1. 加法变成了多项式的加法，且系数模以2。
2. 乘法变成了多项式的乘法，一个二进制的多项式乘法模以一个次数为n的本原多项式。

比如f(x) = x3 +x+1 是GF(23)上的本原多项式，那么GF(23 ) 域上的元素3*7 可以转化为多项式乘法：

37(in GF(23 )) → (x+1)(x2 +x+1) mod f(x) = (x3 +1) mod(x3 +x+1) = x → 3*7 = 2 (in GF(23))

加法变为

x+1 + x2 +x+1 = x2 = 4 (in GF(23))

本身有了多项式的加法和乘法，那么元素的加法和乘法都可以通过表示为多项式的加法和乘法来完成，可是这样做的话对计算机实在是不友好，好在这个域有个特别有趣的性质即生成元。

老子说：一生二，二生三，三生万物，又有太极生两仪，两仪生四象，四象生八卦。而生成元就象是这个起始之源，通过本原多项式f(x)，一旦某个根满足f(a) = 0, 那么该根a通过遍历可以生成这个域上的所有非0元素。如a1，a2，an.....这个是一个非常有用的性质。而GF(2w)伽罗华域上2就是一个生成元。

下面来手工看下一个生成元是如何生成整个集合的，以n=3的多项式为例，本原多项式f(x) = x3 +x+1, 那么假设a为本原多项式x3 +x+1=0的根，有:

a3+a+1 = 0

=> a3+ a3 + a + 1 = a3

=> a3 = a + 1

现在有了生成元，那么问题就变成简单了，元素的加法可以表示为异或（多项式加法退化为异或），而元素的乘法a b = 2x 2y = 2 (x+y) ，除法则可以表示为生成元指数的加法和减法，然后通过查对数表来完成求值，计算机这下终于高兴了。

void generate_gf_table(int w) {

#define MAX_GF_W (8)

int prim_poly[MAX_GF_W] = {0, 0, 0xB, 0x13, 0x29, 0x43, 0x83, 0x11D};



int nw = 1 << w;

int b = 1; 

for (int i = 0; i < nw-1; i++) {     

gf_logi_table[i] = b;

gf_log_table[b] = i; 

b = b << 1;        

if (b & nw) {     

b = b ^ prim_poly[w-1];   

}       

}       

}

FEC矩阵的选择

有了矩阵方程做基础，有了伽罗华域提供了有限域上的加减乘除，有了生成元简化多项式的计算，万事均备，只欠东风，只需要选择一个合适的矩阵就可以了。下面这些矩阵的特点之一是n行取出来的子集，都能找到逆矩阵。

1. 范德蒙特矩阵

可以看到范德蒙特的矩阵在只生成一个冗余单元的时候，假设数据为d1.....dn，此时编码相当于d1⊕d2...⊕dn。目前视频的编码中使用的是范特蒙德矩阵。

1. 柯西矩阵

柯西矩阵的特点是下面是加法，可以理解异或计算，上面为除法，可以理解通过查对数表变化为减法操作，柯西矩阵在编码和解码的速度上都优于范德蒙特矩阵。目前音频的编码中使用的是柯西矩阵。

逆矩阵进行FEC恢复

前面我们已经进行了FEC的编码操作，那么FEC的冗余数据已经产生，接下来就是通过接收的冗余数据等来进行原始数据的恢复，此时需要对原始的FEC编码矩阵进行求逆操作。

G * D = GD 那么反过来就可以得到原始的数据：

G-1* GD = D

逆反矩阵G-1的寻找方法如下：

如果n阶方阵A可逆，做一个n x 2n的矩阵(A|E)， 然后对此矩阵施以初等行变换，使得A化作单位矩阵的同时，单位矩阵E此时变为E-1，即(A|E)---->(E|A-1)

初等行变换包括：

1. 某一行乘以某个值
2. 将某行乘以某个值域叠加到另外一行上
3. 行与行之间进行交换

求得了逆矩阵，最后原始数据也就可以得出了。如上便是一个FEC的基本过程。（完毕）

引用：

1、基于Reed - solomon编码的容灾存储系统的分析：

http://www.doc88.com/p-2711612363670.html

2、求解本原多项式的快速算法：

http://www.doc88.com/p-19552482288.html

3、基于柯西矩阵的erasure code详解：

http://www.tuicool.com/articles/ZNNjY3

4、RS fec原理以及其实现（PPT）

http://www.docin.com/p-691839750.html

...等