基于FEC信道编码丢包恢复技术

霞客书斋 2018-02-13

展开全文

FEC 前向差错恢复编码

FEC 是一种前向差错恢复编码技术，是通过对原生信息序列进行编码生成监督码，这些监督码作为冗余信息序列与原生信息序列一起被传输，当原生信息序列发生错误或丢失，可通过冗余信息序列以一定能力恢复原生信息序列。

对于生成的冗余数据，我们希望生成数据大小范围与原生数据一致，以免使用更多冗余来表示，比如在计算机中，以一个字节单位的数据来生成的编码数据我们不希望是个两个字节或更大数据。因此，编码通常利用了有限域的数学方法，在有限域中进行四则运算，使得编码后的数据还是在一样的大小范围内。

伽罗瓦域（galois field）

域是一个可以在其上进行加法、减法、乘法和除法运算而结果不会超出域的集合。如果域F只包含有限个元素，则称其为有限域。有限域亦称伽罗瓦域（galois field），它是伽罗瓦(Galois,E.)于18世纪30年代研究代数方程根式求解问题时引出的。

伽罗瓦域的阶（元素个数）必为素数的幂，即有限域的阶可表示为pn（p是素数、n是正整数），记为GF(pn)。计算机应用一般取 p=2 来计算二进制运算。

GF(pn) 中有 pn个元素，除了 0，1 之外的元素由本原多项式 P(x)生成。本原多项式（primitive polynomial）是一个不可约多项式，不能够进行因子分解，它只能整除x2n−1+1 , 而不能整除其他xJ−1+1, 其中 J<(2n−1) 。当一个域上的本原多项式确定了，这个域上的运算也就确定了。本原多项式一般通过查表可得，同一个域往往有多个本原多项式。通过将域中的元素化为多项式形式，可以将域上的乘法运算转化为普通的多项式乘法再模本原多项式。

GF(pn) 中元素加法和乘法单位元分别是 0和1，对于域中的乘法，当p为素数时，才能保证集合中的所有的元素都有乘法逆元(0除外)。

通过本原多项式生成元素

例 GF(24), 其本原多项式 P(x)=x4+x+1, 令 GF(24)的元素为 0、1、a1、a2、……、a14 , 则ai 生成的多项式为 ximod(P(x)) , 如下表：

元素	多项式	对应数值
0	0modP(x)=0	0000 (0)
1	1modP(x)=1	0001 (1)
a1	x1modP(x)=x	0010 (2)
a2	x2modP(x)=x2	0100 (4)
a3	x3modP(x)=x3	1000 (8)
a4	x4modP(x)=x+1	0011 (3)
a5	x5modP(x)=x2+x	0110 (6)
a6	x6modP(x)=x3+x2	1100 (12)
a7	x7modP(x)=x3+x+1	1011 (11)
a8	x8modP(x)=x2+1	0101 (5)
a9	x9modP(x)=x3+x	1010 (10)
a10	x10modP(x)=x2+x+1	0111 (7)
a11	x11modP(x)=x3+x2+x	1110 (14)
a12	x12modP(x)=x3+x2+x+1	0010 (15)
a13	x13modP(x)=x3+x2+1	1101 (13)
a14	x14modP(x)=x3+1	1001 (9)

上面例子建立GF中元素与数值一一对应关系。

上述可以看出，GF 的元素其实就是二进制多项式构成的循环码，由循环码的特性，定义GF中元素的四则运算，保证了运算后的结果还是域的中元素。例如，加法 a4+a9=(0011)xor(1010)=(1001)=a14 , 即元素的加法是对应数值的异或结果对应的元素；a4∗a9=a((4+9)mod15)=a13 , 即元素相乘为其幂值相加求模对应的元素。

设数值 y,u,v,z, 元素ai,aj,a((i+j)mod(n−1)),a((i−j)mod(n−1))分别为y,u,v,z在GF(2n)中对应的元素，为则GF中四则运算为：
加减法：数值异或 k⊕l
乘法：k∗l⇒a((i+j)mod(n−1))⇒v
除法：k/l⇒a((i−j)mod(n−1))⇒z

常用本原多项式：

n	本原多项式
4	x4+x+1
8	x8+x4+x3+x2+1
16	x16+x12+x3+x+1
32	x32+x22+x2+x+1
64	x64+x4+x3+x+1

为了乘除法计算方便，一般将数值与元素对应关系列表。计算时，将数值根据表转为对应各自的元素乘法，得到结果元素，再根据表转为对应的数值。

RS编码丢包恢复

通过使用多项式对应的GF来实现对非二进制数据运算并进行变换其实就是RS编码技术。RS(Reed-Solomon)码是一类纠错能力很强的特殊的非二进制BCH码。

对于简单普通抗丢技术，增加冗余是对原生数据一份复制，也就是增加数据的一倍冗余来恢复对应的一个数据。这种恢复性能非常低。而RS编码变换则能实现高效抗丢。

例如，有四个数据 a b c d被传输，则通过变换得到e=f(a,b,c,d)，这时若a b c d 中有一个丢失，如a丢失，那么可以通过逆变换a=fH(b,c,d,e)恢复。也就是通过增加四分之一的冗余，来抵抗一个包的丢失，但这种抵抗是任何一个数据。而如果要抗所有数据丢失，那么需要增加一倍的冗余，即四个原生数据变换到四个冗余数据。

RS编码

F∗D=C, 变换中涉及到的四则运算都在GF中进行，D是原生数据，C是监督数据（冗余数据）, F是一个线性无关矩阵（变换方程组系数），其实现有范德蒙矩阵（vandermode）和柯西矩阵。范德蒙矩阵实现比较方便，可以构建任意 n*n 的非奇异可逆矩阵,其形式如下：

⎡⎣⎢⎢⎢⎢⎢⎢⎢⎢111⋮11222⋮2n−11332⋮3n−1⋯⋯⋯⋱⋯1nn2⋮nn−1⎤⎦⎥⎥⎥⎥⎥⎥⎥⎥

例如，选取子范德蒙矩阵对 a b c d ，变换为 e f g h ：

⎡⎣⎢⎢⎢111112481416641864256⎤⎦⎥⎥⎥⎡⎣⎢⎢⎢abcd⎤⎦⎥⎥⎥=⎡⎣⎢⎢⎢efgh⎤⎦⎥⎥⎥

RS恢复

如果在n个原生数据 D 中丢失m个数据Dm，那么可以从冗余数据C中任意m个数据Cm 和原生未丢失数据Dn−m 通过F对应的子矩阵进行逆变换求解计算出丢失的Dm。

例如，a b d 丢失，我们任取冗余数据中的 e g h 和为丢失的c来恢复 :

⎡⎣⎢⎢⎢11114811664164256⎤⎦⎥⎥⎥⎡⎣⎢⎢⎢abcd⎤⎦⎥⎥⎥=⎡⎣⎢⎢⎢egh⎤⎦⎥⎥⎥

上面先将f 对应的矩阵F那一行系数去掉，接着将c 对应矩阵F那一列系数与c相乘，移位到等式右边与 e g h 分别相加：

⎡⎣⎢⎢⎢111148164256⎤⎦⎥⎥⎥⎡⎣⎢⎢⎢abd⎤⎦⎥⎥⎥=⎡⎣⎢⎢⎢e+cg+16ch+64c⎤⎦⎥⎥⎥

整理为：

⎡⎣⎢111148164256⎤⎦⎥⎡⎣⎢abd⎤⎦⎥=⎡⎣⎢e+cg+16ch+64c⎤⎦⎥

则逆变换可得 a b d:

⎡⎣⎢abd⎤⎦⎥=⎡⎣⎢111148164256⎤⎦⎥H⎡⎣⎢e+cg+16ch+64c⎤⎦⎥

RS编码通常将每n个原生数据为一组，通过n*n 的范德蒙矩阵换成一组n个冗余数据，如果丢失m个，那么任意的m个冗余便可用来逆变换恢复原生数据，最多可恢复连续n个丢失包，其中任意的冗余数据就能来用恢复这一点是普通的增加冗余的本质区别，因为冗余数据也会丢失，如果任意就能恢复那么恢复能力也就更强; RS变化中涉及的运算是在定义在GF中的，这使的不因为数据表示的大小而增加冗余开销。