kcp-go
kcp-go copied to clipboard
xtaci
建议RS码默认使用柯西矩阵
//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
另外看这个实现上把速度提升到 15GB/s per core 了，没计划试试？ https://github.com/templexxx/reedsolomon
柯西矩阵不是降低解码复杂度用的么？ 启用了应该是丢包的时候恢复速度更快吧
柯西矩阵求逆确实有复杂度更低的算法，但 decode matrix 并不只是一个柯西矩阵。
Cauchy Reed Solomon(CRS) 所用的算法并不同于利用 SIMD 加速有限域的算法，CRS 的提出在此之前，且性能不如 SIMD，现已不用了。
目前 Cauchy matrix 的优势在于初始化简单，由 Cauchy matrix 和单位矩阵构成的 encoding matrix 任意子矩阵可逆，证明可见：
https://github.com/templexxx/reedsolomon/blob/master/invertible.jpg
谢谢，学习了。虽然看不太懂。 @templexxx 请问对raptorQ/LDPC编码有没有了解，据说比RS高效，但感觉更难理解。
@liping17
LDPC 有打算找时间实现一个试试，原理上确实比 RS 效率更高。暂未排期，估计还得很久 :D
纠删码和纠错码应该是两回事吧，能convert?
@xtaci 是两回事，逻辑得变，如果用 LDPC
请问RS纠删码和RS纠错码在实现上具体有什么区别吗
@xygdys 一个可以发现错误并纠正，一个你得告诉它哪里错了然后纠正（纠删码），纠删码恢复的数据更多 还有几个问题需要请教：
- 请问必须指定错误的位置才能恢复吗，看到了一篇文章里写的RS纠错码的解码为 RSDecode(n,e,t)，其中n是数据块个数，e是错误的个数，t是原数据块的个数（也就是多项式的阶），是否是只要指定这几个参数就可以纠错？
- 这个项目里的RS码貌似在解码的时候只传递了n,t两个参数，是否只实现了纠删功能，而非纠错功能
- 请问有没有具体的关于RS纠错码（error correcting code，ECC）和在线纠错算法的实现（online error correcting，OEC）
- 这个项目里针对大数据（超过有限域长度）的消息是否是通过分组（多个多项式并行）来编码的？
@xygdys 一个可以发现错误并纠正，一个你得告诉它哪里错了然后纠正（纠删码），纠删码恢复的数据更多 还有几个问题需要请教：
- 请问必须指定错误的位置才能恢复吗，看到了一篇文章里写的RS纠错码的解码为 RSDecode(n,e,t)，其中n是数据块个数，e是错误的个数，t是原数据块的个数（也就是多项式的阶），是否是只要指定这几个参数就可以纠错？
- 这个项目里的RS码貌似在解码的时候只传递了n,t两个参数，是否只实现了纠删功能，而非纠错功能
- 请问有没有具体的关于RS纠错码（error correcting code，ECC）和在线纠错算法的实现（online error correcting，OEC）
- 这个项目里针对大数据（超过有限域长度）的消息是否是通过分组（多个多项式并行）来编码的？
按道理你能问这些问题应该对纠删码，纠错码是有一定了解了。我这里简单说一下你应该就明白了，或者该知道去查阅什么资料了：
- 这个项目用的是erasure code，不是 ECC
- reedsolomon 的 ECC实现 GitHub 上有开源项目，你可以搜一下。这个编码历史有差不多 60年了，什么实现都很成熟了
- 这个项目用的是 GF2^8（1字节），编码基于矩阵运算做的。