版上有没有研究基础编码理论的同学？

【 在 Cop663 的大作中提到: 】 : 想找人交流一下，bch/rs，product codes之类的问题。最好是亲自做过仿真的。。。 : 谢谢 真是学术男

为什么不把具体问题说出来呢

bch译码的时候遇到一个问题，采用BM算法，当错误数目大于纠错能力（t）时，按照林纾书上的说法，得到的错误多项式的次数会大于t，这样就无需译码。但是我按照那个算法反复验证，发现在迭代2t次的时候，错误多项式的次数不会出现大于t的情况，所以也就没法判断是否超出纠错能力。如果实在搞不定，就打算换欧几里得算法来译码了。 用BM算法是可以强行译码的，如果只是单纯译码不去迭代也无所谓了（反正错了就错了）。但在实现Chase软译码的时候，需要找候选码字，这就意味着，如果超出纠错能力的话，就直接报错而不去译（错码在计算欧氏距离时是没有意义的）。 大概就是这么个问题，纠结了一个礼拜了。 这也只是一方面，也想找人再交流下对编码的一些想法。

没人搞这个啊？？？ 哎

【 在 Cop663 的大作中提到: 】 : bch译码的时候遇到一个问题，采用BM算法，当错误数目大于纠错能力（t）时，按照林纾书上的说法，得到的错误多项式的次数会大于t，这样就无需译码。但是我按照那个算法反复验证，发现在迭代2t次的时候，错误多项式的次数不会出现大于t的情况，所以也就没法判断是否超出纠错能力。如果实在搞不定，就打算换欧几里得算法来译码了。 : 用BM算法是可以强行译码的，如果只是单纯译码不去迭代也无所谓了（反正错了就错了）。但在实现Chase软译码的时候，需要找候选码字，这就意味着，如果超出纠错能力的话，就直接报错而不去译（错码在计算欧氏距离时是没有意义的）。 : 大概就是这么个问题，纠结了一个礼拜了。 : ................... 想了一个礼拜，中间跟别人讨论了一下 说一下，现在的想法，算是暂时给这个问题先花上个句号吧。 定理1： 线性码的最小距离d，若是满足d>=l+1，则可以检测l个错误 若是d>=2t+1，则可以纠t个错误 若是d>=t+l+1，则能纠正t个错误，同时检测l>=t个错误。 一个码，若是只用于检错，那它的检错能力就是d-1，检错能力比较强，比如crc。 一个码，若是同时用于检错和纠错，那么它的检错能力就要打折扣，尤其是d=2t+1时，它的检错能力和纠错能力相同，比如bch(15,5,7)码，纠错能力t=3，检错能力l=3 另外一方面，bch的各种迭代译码算法，比如PGZ，BM等，如果去研究一下它的译码原理的话，会发现，这些译码算法都是假设错误数目小于t的，很遗憾的是，非常多的讲bch的论文和书，避而不谈这一点，比如lin shu的那本书。（有些原始paper是有说明的，参看附件2，还有一本书，叫做：Error Correction Coding - Mathematical Methods and Algorithms 也提到了这一点，我把bch的部分弄了出来，放在了附件3） The art of error correct coding这本书在做仿真时时挺好的handbook，可惜在这个问题上它也装傻，sigh~根本没提BM在错误数目超出t时会怎样（我给作者发了个email说这个事情，也没理俺。。。） 但是有人遇到了类似的问题了（我自己尝试跑了一下Morelos-Zaragoza给的代码，没编译通过，一直没用c，所以太生疏了）： http://www.math.org.cn/index.php/action-viewthread-tid-985 继续回到原始问题，既然如此，那肯定还是要有对策的否则TPC也是没法实现的。 最简单的办法，根据定理1，既然该码同时用于纠错和检错的话，那么还是以bch(15,5,7)为例，可以纠两个错，检4个错，这样，当你发现错误数目有三个的时候，就不再纠错了，但是能保证正确译码（见下面的解释）。这种方法在性能上还是有些损失的吧，具体的仿真我还没跑。 对策之二就是采用扩展bch，即eBCH，在bch编码的末尾一个奇偶校验位，这样就把检错能力扩展一位，可以区分出错误为t的码和错误为t+1的码。事实上在Pyndiah的关于TPC的原始论文中，也是使用eBCH，我想也是出于类似的考虑吧。 关于定理1，还想再说两句，译码是有两种情况的： 正确译码，成功译码 而正确译码的概率p1=成功译码的概率p0-不可检错的概率p2 而用汉明球表示的话，非常的形象： 正确译码就是，接受码字在正确的码字的n维球内，不可检错译码就是接受码字在别人的n维球内，至于球与球之间的空白地带（即接受码字不属于任何一个汉明球），就是可检错误。 over 附件(1.7MB) 附件(549KB) A_Simple_Derivation_of_the_Berlekatip-Massey.pdf 附件(1.7MB) Correction_Coding_-_Mathematical_Methods_and_Algorithms_.rar

【 在 Cop663 的大作中提到: 】 : 想了一个礼拜，中间跟别人讨论了一下 : 说一下，现在的想法，算是暂时给这个问题先花上个句号吧。 : 本科时学编码，只知道最小距离d，决定检错能力，t决定纠错能力，而d=2t+1 : ................... 补充一下 如果对检错性能感兴趣的话，再推荐一本书，感觉还不错，是位fellow写的，打算最近看一下，包括linshu那本大作还是有必要从头看看的。。。其实上面的那个定理1，汉明在1950年的时候就说过了的。。。 http://www.paradise.caltech.edu/ist4/handouts/IST4_hamming1950.pdf 附件(1.3MB) Codes_for_Error_Detection.pdf

牛人，我最近也在看CRC，那个生成多项式是怎么算出来的呢？

【 在 mineral 的大作中提到: 】 : 牛人，我最近也在看CRC，那个生成多项式是怎么算出来的呢？ 呃。。。不牛。。。 这学期才接触分组码，只懂个皮毛。。。一直在看纠错码，检错码没怎么研究过。。。

那个定理一似乎本科就学过的啊。。。果然信息还是搞编码的。。