fec基础_普通独立基础

全栈程序员-用户IM • 2022年8月11日下午3:16 • 未分类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

昨天休息了一下，思考一下可以研究的点，觉得这个fec还可以，就找了一点资料研究一下。
先跑点题，闲扯一会。在找资料的过程中，能找到的资料就很少，就有点感叹。科研为什么弱呢? 可以看下90年代的论文，那水平略等于今天的一篇博客。这是积贫积弱到现在。
[1]中有段代码，求解伽罗华域的生成空间的。举的例子是GF(256)，使用的本原多项式 $P(x)=x^8+x^5+x^3+x^2+1$ 。伽罗华域上的多项式乘法，其结果需要mod P(x)，可以通过以下方式简化计算。首先，考虑 $x^8$ ， $x^8 mod P(x) = P(x) – x^8 = x^5 + x^3 +x^2 +1$ 。这个可以使用二进制数表示, 就是 $x^8$ 可以使用0b101101表示。而 $x^9=x^8*x$ ，就是对应的将 $x^8$ 二进制数据左移一位得到 $x^9$ 。但是 $x^{11}=x^{10}*x=x^8+x^6+x^5+x^3$ ，最高位的 $x^8$ 被 $x^5+ x^3 +x^2 +1$ 表示，就是代码里的alphaToMM。
剩余项 $x^6+x^5+x^3)$
可以被(alphaTo[i-1]&0xEF)<<1)=(alphaTo[i-1]^128)<<1)表示。这个操作就是消除x^{10}中的最高位，并把
$x^{5}+x^{4}+x^2$ 左移一位（进位）。
但是还需要整理，系数为偶数的项置零，这里的^符号就是异或运算，就是代码中给出的计算方法。当 $a l p h a T o [i - 1] > = 128$ 时，alphaTo[i]=alphaTo[MM]^(alphaTo[i-1]^128)<<1)。

生成元素	多项式表示	二进制表示	十进制
0	$x^0$	0b00000001	1
$x^1$	$x^1$	0b00000010	2
$x^2$	$x^2$	0b00000100	4
…	…	…
$x^7$	$x^7$	0b10000000	128
$x^8$	$x^5 + x^3 +x^2 +1$	0b00101101	45
$x^9$	$x^6+x^4+x^3+x$	0b01011010	90
$x^{10}$	$x^7+x^5+x^4+x^2$	0b10110100	180
$x^{11}$	$x^6+x^2+1$	0b01000101	69
$x^{12}$	$x^7+x^3+x$	0b10001010	138
$x^{13}$	$x^5+x^4+x^3+1$	0b00111001	57
$x^{14}$	$x^6+x^5+x^4+x$	0b01110010	114
$x^{15}$	$x^7+x^6+x^5+x^2$	0b11100100	228
$x^{16}$	$x^7+x^6+x^5+x^2+1$	0b11100101	229
$x^{17}$	$x^7+x^6+x^5+x^2+x+1$	0b11100111	231
$x^{18}$	$x^7+x^6+x^5+x+1$	0b11100011	227
$x^{19}$	$x^7+x^6+x^5+x^3+x+1$	0b11101011	235
$x^{20}$	$x^7+x^6+x^5+x^4+x^3+x+1$	0b11111011	251
$x^{21}$	$x^7+x^4+x^3+x+1$	0b10011011	155
…	…	…	…

int MM = 8;
int NN = 255;
int alphaToMM = 45;//α^8=α^5+α^3+α^2+1
int* alphaTo = new int[NN+1];
int* expOf = new int[NN+1];

alphaTo[MM] = alphaToMM;
expOf[alphaToMM] = MM;
alphaTo[NN] = 0;
expOf[0] = NN;

int i, shift;
shift = 1;
for(i=0; i<MM; i++){
    alphaTo[i] = shift;//2^i
    expOf[alphaTo[i]] = i;
    shift <<= 1;
}
shift = 128;
for(i=MM+1; i<NN; i++){
    if(alphaTo[i-1] >= shift){
        alphaTo[i] = alphaTo[MM] ^ ((alphaTo[i-1]^shift)<<1);
    }else{
        alphaTo[i] = alphaTo[i-1]<<1;
    }
    expOf[alphaTo[i]] = i;
}

在进行乘除法的时候，需要把相应的数字转换到伽罗华域的数字，再进行运算。例如，45对应的伽罗华域中的数字为 $x^8$ ,46对应的数字为 $x^9$ ， $x^8*x^9=x^{17}$ 。 $x^{17}$ 对应实数231（可以从[3]查表获取）
了解了那么久的FEC机制，也没有转化成文章。因为我在后来在对拥塞控制仿真的时候，发现能够因为网络拥塞造成的丢包率是极低的（1%左右）[7]。而且1%的丢包率，同别人在实际网络中的测试是很相符的。就算使用FEC将这1%的丢包给恢复了，又有多大的传输性能提升呢。这个想法也就放弃了。