给数据增加冗余前向纠错编码

2008-08-11 by bborn

在不可靠的链路传送数据比如udp
如果需要增加数据传输的可靠性
我们可以在传输原始数据的时候增加冗余数据
这样只要我们收到了一定数量的数据包（不需要所有的）
就可以还原出原始的数据包
比如原始数据是“10”
分成两个包，分别为“1”和“0”
通过异或计算出一个冗余包“0”
我们收到任意两个就能组装出原始的包（知道次序的情况下）
这有些类似磁盘冗余阵列的原理

这些纠错编码的理论不少
实际上可以直接拿来用的代码很少见
好不容易找到了这个 zfec
C代码 GPL 提供了Python接口
作者看起来是个水果迷
在他的Mac中测试效率不错
FEC是Forward Error Correction的简称，意为前向纠错

虽然给了代码实际要用起来还是很麻烦的
所以这里记录一下方法

1 fec_t* fec_new(unsigned k, unsigned m);
k 把原始数据包分成k块
m 编码后生成m块数据块
块的大小都是一致的，所以很显然m>k，其中编码后的m块中，前k块就是原始的数据

2 void fec_encode(const fec_t* code, const gf*restrict const*restrict const src, gf*restrict const*restrict const fecs, const unsigned*restrict const block_nums, size_t num_block_nums, size_t sz);
编码，参数比较难看，src是包含原始数据指针的一个数组(原始数据分成k块)，fecs 是返回的包含冗余数据指针的数组，block_nums为冗余数组的序号，由我们设置传入的，k<=序号

3 void fec_decode(const fec_t* code, const gf*restrict const*restrict const inpkts, gf*restrict const*restrict const outpkts, const unsigned*restrict const index, size_t sz);
基本同上，我们只需要任意k个包就可以还原。inpkts是将收到的数据包按序传入，如果丢包则拿一个冗余包补入。outpkts是返回我们缺失的数据包，index是我们传入的数据包的序号，sz是每个包的大小

4 void fec_free(fec_t* p);
不过即使这样，还是有内存泄露，自己改改吧
//
说不清楚看代码吧

fec_t* p = fec_new( 4,6);
 
char buf[1024] = {0};
for ( int i = 0; i &lt; 1024; i++)
buf[i]= i % 255;
char* src[] = {buf, buf + 256, buf + 512, buf + 768};
 
char dest[512] = {0};
char* const fecs[] = { dest, dest + 256};
 
UINT block_nums[] = {4,5};//原始数据编号是0，1，2，3
UINT num_block_nums = 2; //block_nums的大小
UINT sz = 1024 / 4;
 
fec_encode(p, (const gf*const*)src, (gf*const*const)fecs, block_nums, num_block_nums, sz);
 
// 解码，假设我们丢失了原始的数据包 0，3
 
char* inpkts[] = {fecs[0], buf + 256, buf + 512, fecs[1]};//必须按顺序，丢失的包由冗余包补齐
char output[512] = {0};
char* const outpkts[] = { output, output + 256};
UINT index[] = {4, 1, 2, 5}; //对应inpkts的顺序
 
fec_decode(p, (const gf* const*const)inpkts, (gf* const* const)outpkts, (const unsigned* const)index, sz);
 
if ( 0 == memcmp( src[0], outpkts[0], 256))
TRACE(L"ok");
 
if ( 0 == memcmp( src[3], outpkts[1], 256))
TRACE(L"ok");
 
fec_free(p);