建议RS码默认使用柯西矩阵

[liping17]

//reedsolomon里面支持柯西矩阵了，加个参数应该就可以
codec, err := reedsolomon.New(dataShards, parityShards, reedsolomon.WithCauchyMatrix())
if err != nil {
return nil
}
//看minio里面，还用了WithAutoGoroutines，不知道能有多大效果
e.encoder, err = reedsolomon.New(dataBlocks, parityBlocks, reedsolomon.WithAutoGoroutines(int(e.ShardSize())))
if err != nil {
logger.LogIf(ctx, err)
return e, err
}
return

[xtaci]

柯西矩阵只是启动稍微快一点点，传输速度没有差别，
WithAutoGroutine对嵌入式不友好（router)，内存难于控制。

[liping17]

柯西矩阵不是降低解码复杂度用的么？
启用了应该是丢包的时候恢复速度更快吧

[xtaci]

在这个量级，速度没有差别，范德蒙矩阵也能到1GB/s 以上

[liping17]

解码复杂度降了应该能节约点功耗吧。无源设备（靠电池供电）的都得几毫安几毫安的降功耗。

[liping17]

另外看这个实现上把速度提升到 15GB/s per core 了，没计划试试？
https://github.com/templexxx/reedsolomon

[xtaci]

几乎没有差别，对于<100MB/s的网速

[xtaci]

有空了可以加来试试

[templexxx]

柯西矩阵不是降低解码复杂度用的么？
启用了应该是丢包的时候恢复速度更快吧

柯西矩阵求逆确实有复杂度更低的算法，但 decode matrix 并不只是一个柯西矩阵。

Cauchy Reed Solomon(CRS) 所用的算法并不同于利用 SIMD 加速有限域的算法，CRS 的提出在此之前，且性能不如 SIMD，现已不用了。

目前 Cauchy matrix 的优势在于初始化简单，由 Cauchy matrix 和单位矩阵构成的 encoding matrix 任意子矩阵可逆，证明可见：

https://github.com/templexxx/reedsolomon/blob/master/invertible.jpg

[liping17]

谢谢，学习了。虽然看不太懂。
@templexxx 请问对raptorQ/LDPC编码有没有了解，据说比RS高效，但感觉更难理解。

[templexxx]

谢谢，学习了。虽然看不太懂。
@templexxx 请问对raptorQ/LDPC编码有没有了解，据说比RS高效，但感觉更难理解。

@liping17

LDPC 有打算找时间实现一个试试，原理上确实比 RS 效率更高。暂未排期，估计还得很久 :D

[xtaci]

纠删码和纠错码应该是两回事吧，能convert?

[templexxx]

纠删码和纠错码应该是两回事吧，能convert?

@xtaci 是两回事，逻辑得变，如果用 LDPC

[xygdys]

纠删码和纠错码应该是两回事吧，能convert?

@xtaci 是两回事，逻辑得变，如果用 LDPC

请问RS纠删码和RS纠错码在实现上具体有什么区别吗

[templexxx]

@xygdys 一个可以发现错误并纠正，一个你得告诉它哪里错了然后纠正（纠删码），纠删码恢复的数据更多

[xygdys]

@xygdys 一个可以发现错误并纠正，一个你得告诉它哪里错了然后纠正（纠删码），纠删码恢复的数据更多
还有几个问题需要请教：

1. 请问必须指定错误的位置才能恢复吗，看到了一篇文章里写的RS纠错码的解码为 RSDecode(n,e,t)，其中n是数据块个数，e是错误的个数，t是原数据块的个数（也就是多项式的阶），是否是只要指定这几个参数就可以纠错？
2. 这个项目里的RS码貌似在解码的时候只传递了n,t两个参数，是否只实现了纠删功能，而非纠错功能
3. 请问有没有具体的关于RS纠错码（error correcting code，ECC）和在线纠错算法的实现（online error correcting，OEC）
4. 这个项目里针对大数据（超过有限域长度）的消息是否是通过分组（多个多项式并行）来编码的？

[templexxx]

@xygdys 一个可以发现错误并纠正，一个你得告诉它哪里错了然后纠正（纠删码），纠删码恢复的数据更多
还有几个问题需要请教：

1. 请问必须指定错误的位置才能恢复吗，看到了一篇文章里写的RS纠错码的解码为 RSDecode(n,e,t)，其中n是数据块个数，e是错误的个数，t是原数据块的个数（也就是多项式的阶），是否是只要指定这几个参数就可以纠错？
2. 这个项目里的RS码貌似在解码的时候只传递了n,t两个参数，是否只实现了纠删功能，而非纠错功能
3. 请问有没有具体的关于RS纠错码（error correcting code，ECC）和在线纠错算法的实现（online error correcting，OEC）
4. 这个项目里针对大数据（超过有限域长度）的消息是否是通过分组（多个多项式并行）来编码的？

按道理你能问这些问题应该对纠删码，纠错码是有一定了解了。我这里简单说一下你应该就明白了，或者该知道去查阅什么资料了：

1. 这个项目用的是erasure code，不是 ECC
2. reedsolomon 的 ECC实现 GitHub 上有开源项目，你可以搜一下。这个编码历史有差不多 60年了，什么实现都很成熟了
3. 这个项目用的是 GF2^8（1字节），编码基于矩阵运算做的。

[xygdys]

@templexxx 太感谢了

[EEEEEric-tao]

求问有没有C++（或C）版本的 柯西矩阵的RS纠删源码 @templexxx @liping17

[templexxx]

求问有没有C++（或C）版本的 柯西矩阵的RS纠删源码 @templexxx @liping17

@EEEEEric-tao https://github.com/intel/isa-l/tree/master/erasure_code

[xtaci]

Cauchy Matrix比ReedSolomon在编解码效率上有对比么？

[EEEEEric-tao]

@xtaci 粗略看了下https://github.com/intel/isa-l/tree/master/erasure_code里面的代码，cauchy在求解逆矩阵还是使用的高斯消元法---复杂度O(n^3)， 那么效率只能体现在编码端了，编码端构造编码矩阵直接查inv表
@templexxx 有没有研究利用cauchy矩阵加速逆矩阵计算的 我看网上有一些零零散散的优化方案 求探讨下

[templexxx]

@xtaci 粗略看了下https://github.com/intel/isa-l/tree/master/erasure_code里面的代码，cauchy在求解逆矩阵还是使用的高斯消元法---复杂度O(n^3)， 那么效率只能体现在编码端了，编码端构造编码矩阵直接查inv表 @templexxx 有没有研究利用cauchy矩阵加速逆矩阵计算的 我看网上有一些零零散散的优化方案 求探讨下

上面的评论有提到，现在都用 SIMD 加速有限域运算了，编解码效率 vandermonde 还是 cauchy 没区别 @EEEEEric-tao

只不过为了保证编码后原始数据不变的性质，vandermonde matrix 由于不是任意子矩阵可逆所以要进行一个初等变换：

1. 关于可逆性的证明：https://github.com/templexxx/reedsolomon/blob/master/invertible.jpg
2. 关于 vandermonde matrix 的变换： https://github.com/klauspost/reedsolomon/blob/6a9df697dce81ba20ee4aa223ef76dacd172cb4d/reedsolomon.go#L251

[EEEEEric-tao]

@templexxx
谢谢大佬 编解码效率确实没区别 区别在于cauchy初始化生成矩阵复杂度稍微低一些 范德蒙矩阵 \alpha^N 涉及到的乘法多一些 查表也多一些
我其实想问的是单位阵抽取行与cauchy阵抽取行组成的矩阵求逆有没有一些讨巧的计算方法

[templexxx]

@templexxx 谢谢大佬 编解码效率确实没区别 区别在于cauchy初始化生成矩阵复杂度稍微低一些 范德蒙矩阵 \alpha^N 涉及到的乘法多一些 查表也多一些 我其实想问的是单位阵抽取行与cauchy阵抽取行组成的矩阵求逆有没有一些讨巧的计算方法

@EEEEEric-tao 求逆运算开销不算大，理论上特殊矩阵求逆应该可以找到一些讨巧的方法。考虑到 GFN，随着N变大，编码速度快速下降，那么求逆运算开销的上升占整体的开销也不大了。另外可以缓存逆矩阵的结果，用一个 bitmap 作 key 就可以。